The HAMT has buckets of size 3 for KV pairs; once there are more items under the same key-prefix, it sinks them into sub-nodes.
After disabling key-hashing, all items in a dynamic array will fall under the same key prefix. Keys are 256 bits long, and with the default 8 bit length (nibble size) that results in a maximum of 32 levels in the HAMT. Because the dynamic array puts keys next to each other, we will actually have 32 levels right after the 4th item is appended to the array.
Following 32 almost empty nodes to get to the array, and then writing back all 32 new nodes once an item is appended is wasteful. We can take insiration from the Merkle Patricia Trie which contains extension nodes to skip ahead empty levels, right to the next non-empty blocks. Optimised Sparse Merkle Trees like Jellyfish also substitute a sub-tree with a node, if that node is the only non-empty descendant. That will not be the case for us, because as the array grows, it will spill over to the next node.
Part of https://github.com/filecoin-project/ref-fvm/issues/859 Depends on https://github.com/filecoin-project/ref-fvm/issues/890
The HAMT has buckets of size 3 for KV pairs; once there are more items under the same key-prefix, it sinks them into sub-nodes.
After disabling key-hashing, all items in a dynamic array will fall under the same key prefix. Keys are 256 bits long, and with the default 8 bit length (nibble size) that results in a maximum of 32 levels in the HAMT. Because the dynamic array puts keys next to each other, we will actually have 32 levels right after the 4th item is appended to the array.
Following 32 almost empty nodes to get to the array, and then writing back all 32 new nodes once an item is appended is wasteful. We can take insiration from the Merkle Patricia Trie which contains extension nodes to skip ahead empty levels, right to the next non-empty blocks. Optimised Sparse Merkle Trees like Jellyfish also substitute a sub-tree with a node, if that node is the only non-empty descendant. That will not be the case for us, because as the array grows, it will spill over to the next node.