Contiguous memory data type for dense Merkle tree storage

[bvrooman]

Currently, the in-memory Binary Merkle tree uses the StorageMap data struct for its storage backing.

The StorageMap uses a hash map to store key-value data. When keys are evenly spread over the key space, as is the case with the hashed keys in an SMT, a hash-map has an optimized memory footprint and O(1) runtime complexity for its CRUD operations.

When keys are monotonic integers, as is the case with the integer keys in a BMT, a hash map is not ideal. The underlying hash map will hash the integer keys into pseudorandom bytes and spread them evenly across the underlying key-space.

A better approach to storage when using monotonic integer keys is to use contiguous memory, such as an array (or vector). This provides the following performance advantages:

• Data is stored contiguously, and multiple data points can be pulled into cache memory in one data fetch from RAM. We can iterate over the data with low and predictable levels of cache misses.
• We eliminate the need to hash the keys, while maintaining random KV access to the data since keys are now integer indices

Questions:

• Is it better to use a fixed size array and preallocate a reasonably estimated maximum memory? Or is it better to use a dynamically growing container, i.e. vector?
• Using an array or vector requires memory to be initialized. Therefore, a binary Merkle tree node must have a default initializer in order to use it in an array or vector. What is the default for this node?

[bvrooman]

After spending some time investigating this, I do not believe there is enough ROI. The implementation will be more complex than I anticipated. This requires a container that supports inserting and deleting in O(1) time, i.e. a vector + freelist managed indices. An efficient implementation would require unsafe Rust, which is out of scope. Less efficient implementations may require heap allocations and will not provide the performance benefit we are looking for. I will close this, at least until a need for further optimization in this area comes up.