-
Notifications
You must be signed in to change notification settings - Fork 30
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
hexary trie get
operation optimization
#234
Comments
The old implementation of the Nimble range was assuming that slices don't produce a copy, but this was changed recently. Nevertheless, keeping the key as a fixed-sized stack variable is certainly better. If you wish, you may try the |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Something I've learned after implementing multiproof block witness.
Current implementation require the
key
converted tonibblesSeq
with the role of apath
.Every time the algorithm move deeper into trie structure, it will create a
slice
of this path.But the
slice
is actually a copy.In
SecureHexaryTrie
, the key is the keccak hash value of the original key. The hash is 32 bytes or 64 nibbles. In a dense branch, the maximum trie depth at worst is 64. It also means there is possibility to make the copy of path 63 times at the deepest end of the trie, wasting memory and time.When implementing multiproof, I avoid this kind of copy and conversion of
path
toNibblesSeq
by adding an extra parameterdepth
to the recursive proc param. In multiproof algorithm we are dealing with multiple keys at once, not only one like in hexary trie.If we encounter a branch node, the depth will increase one at the next recursion. If we encounter an extension node, we will increase the depth with the length of nibbles prefix from extension node.
This
depth
parameter will act as astarting-cursor
for the immutable path when doing nibble(s) comparison.Beside adding depth parameter, the nibbles comparison also need modification, not comparing NibblesSeq vs NibblesSeq anymore but openArray[byte] vs openArray[byte].
we could throw away NibblesSeq from
get
operation.I have not look closer into the
put
operation, whether we can throw away NibblesSeq or not.The text was updated successfully, but these errors were encountered: