Optimize Merkle Tree Creation

[ryleung-solana]

Problem

Jump have developed an optimized function for inserting nodes into a Merkle tree (https://github.com/firedancer-io/firedancer/blob/31d260e06a55a7c6ef40f393fb94372756a625d4/src/ballet/bmtree/fd_bmtree_tmpl.c#L396-L451), which might help speed up Merklization.

Proposed Solution

Port this function to Rust, find appropriate use cases and bench.

[ryleung-solana]

@t-nelson for further details on use cases.

[ryleung-solana]

CC @t-nelson based on discussions we've concluded we want to exploit Jump's O(1) space implementation to lower memory consumption and make it more predictable.

[t-nelson]

correct. that's the goal for the places where the only output we care about is the root

[ryleung-solana]

Update: testing on mainnet has shown no improvement in memory usage, and actually it seems to have actually worsened memory consumption (left side of the screenshot is with the change, right side is without - tested against v1.16). This is possibly due to the fact that the constant memory used for calculating the merkle root is higher than the average memory consumed from just building the merkle tree for most data sets seen in practice. It may be possible to if we wanted, to drill a little deeper, but given that mem usage is constant, the only real prospect I can see for reducing memory consumption is to reduce the constant-sized memory buffer to below the size we'd need to deal with all possible cases, then reallocate as needed. However, given that the memory buffer is already quite modest-sized (only 63 elements), that likely tells us that the merkle trees we're dealing with are simply so small that it's probably not worth the effort imho. CC @t-nelson for opinions.