Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Possible optimization in heap size #63

Open
QGarchery opened this issue Aug 8, 2022 · 3 comments
Open

Possible optimization in heap size #63

QGarchery opened this issue Aug 8, 2022 · 3 comments

Comments

@QGarchery
Copy link
Collaborator

Found by @MathisGD.

Currently the heap size is changing at each insert, remove, and decrease operation. When it reaches _maxSortedUsers, it is divided by 2. The informal goal is to distribute high liquidity evenly on the branches of the heap, in order to maximize the total liquidity that is in the heap.

One other idea would be distribute the incoming liquidity "randomly" on the last nodes before _maxSortedUsers. This means that the size of the heap would only change up to _maxSortedUsers and then stay the same, potentially saving one SSTORE for each operation. Another potential benefit would be that the introduced randomness would mostly prevent worst case scenarios for the incoming liquidity.
Note that there is no real need for the randomness here to be truly random, and we could use a pseudo-random function instead.

@MathisGD
Copy link
Collaborator

WIP there #76

@MerlinEgalite
Copy link
Contributor

What's the state of this issue?

@MathisGD
Copy link
Collaborator

It has to be implemented ! I started something in #76, but it was far from being ready. I might go back to it when I will have a little bit more bandwidth.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants