hexary trie get operation optimization

[jangko]

Something I've learned after implementing multiproof block witness.

Current implementation require the key converted to nibblesSeq with the role of a path.
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 to NibblesSeq by adding an extra parameter depth 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 a starting-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.

[zah]

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 BitArray type in nim-stew to keep the keys smaller, but it's probably not necessary.