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

Optimizations of the trie implementation #199

Open
2 tasks
abizjak opened this issue Mar 21, 2022 · 0 comments
Open
2 tasks

Optimizations of the trie implementation #199

abizjak opened this issue Mar 21, 2022 · 0 comments
Labels
[Prio] Low Should be fixed if time permits but can be postponed. [Size] Medium [Type] Task An additional feature or improvement.

Comments

@abizjak
Copy link
Contributor

abizjak commented Mar 21, 2022

Task description

There are several opportunities for optimizations of the trie implementation, both space and time wise.

At least the following ones should be considered. Any changes should be accompanied by meaningful benchmarks or arguments why memory use is reduced.

Sub-tasks

  • The Stem and MutStem types contain a "stem", a list of bytes. In the vast majority of cases, for non-malicious use, these will be very short, very rarely above 40 bytes. Thus a small-scale optimization where we would use something like tinyvec/smallvec for storing the key inline if it is small could be very beneficial to both performance, and reducing memory pressure and fragmentation.
  • When serializing (and in store_update) the node's children we now waste a full byte for the child tag. This is wasteful since we could just use the top 4 bits of the Reference, still leaving 60 bits to address, which is more than will ever be needed.
@abizjak abizjak added [Type] Task An additional feature or improvement. [Size] Medium [Prio] Low Should be fixed if time permits but can be postponed. labels Mar 21, 2022
@abizjak abizjak transferred this issue from Concordium/concordium-wasm-smart-contracts Aug 12, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
[Prio] Low Should be fixed if time permits but can be postponed. [Size] Medium [Type] Task An additional feature or improvement.
Projects
None yet
Development

No branches or pull requests

1 participant