Optimize sparse Merkle subtree hashing

[Qyriad]

Brought up at #334 (comment), we can build a fully-balanced tree four times more efficiently than we can build an SMT subtree of the same size. This is reasonable for now, but we can and should optimize this better in the future.

[Qyriad]

It seems like this may have inadvertently been done? Re-running the benchmarks using #334 (comment) as a baseline yields much improved times on my Ryzen 7950X, and subtree8-*/256 is now very in line with the balanced versions:

balanced-merkle-even    time:   [1.3058 ms 1.3059 ms 1.3060 ms]
                        change: [-0.0788% -0.0686% -0.0586%] (p = 0.00 < 0.05)
                        Change within noise threshold.

balanced-merkle-rand    time:   [1.3097 ms 1.3099 ms 1.3101 ms]
                        change: [-0.1159% -0.0902% -0.0634%] (p = 0.00 < 0.05)
                        Change within noise threshold.

subtree8-even/1         time:   [43.768 µs 43.928 µs 44.040 µs]
                        change: [-2.2021% -1.7768% -1.3905%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-even/64        time:   [1.0466 ms 1.0467 ms 1.0467 ms]
                        change: [-62.760% -62.710% -62.642%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-even/128       time:   [1.4005 ms 1.4005 ms 1.4006 ms]
                        change: [-74.349% -74.290% -74.235%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-even/192       time:   [1.3621 ms 1.3712 ms 1.3794 ms]
                        change: [-83.912% -83.857% -83.797%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-even/256       time:   [1.3790 ms 1.3817 ms 1.3839 ms]
                        change: [-87.781% -87.758% -87.733%] (p = 0.00 < 0.05)
                        Performance has improved.

subtree8-rand/1         time:   [44.237 µs 44.245 µs 44.256 µs]
                        change: [+0.0759% +0.0945% +0.1126%] (p = 0.00 < 0.05)
                        Change within noise threshold.
subtree8-rand/64        time:   [805.59 µs 810.26 µs 814.62 µs]
                        change: [-29.996% -29.738% -29.500%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-rand/128       time:   [1.0966 ms 1.0970 ms 1.0975 ms]
                        change: [-51.753% -51.514% -51.266%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-rand/192       time:   [1.1972 ms 1.2005 ms 1.2041 ms]
                        change: [-67.268% -67.156% -67.040%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-rand/256       time:   [1.2688 ms 1.2727 ms 1.2761 ms]
                        change: [-76.831% -76.769% -76.704%] (p = 0.00 < 0.05)
                        Performance has improved.

Image version for colors:

[bobbinth]

Nice! I wonder if this is due to using hashbrown instead of BTreeMap. Do you get the old numbers if smt_hashmaps feature is not turned on?

[Qyriad]

Apparently not! Here's with smt_hashmaps compared to without:

balanced-merkle-even    time:   [1.2521 ms 1.2583 ms 1.2644 ms]
                        change: [-0.9670% -0.5270% -0.0807%] (p = 0.02 < 0.05)
                        Change within noise threshold.
balanced-merkle-rand    time:   [1.2678 ms 1.2712 ms 1.2738 ms]
                        change: [-2.4419% -2.1371% -1.7848%] (p = 0.00 < 0.05)
                        Performance has improved.

subtree8-even/1         time:   [40.029 µs 40.223 µs 40.368 µs]
                        change: [-0.0259% +0.4698% +0.9690%] (p = 0.07 > 0.05)
                        No change in performance detected.
subtree8-even/64        time:   [936.67 µs 939.84 µs 942.60 µs]
                        change: [+0.1651% +0.4006% +0.6501%] (p = 0.00 < 0.05)
                        Change within noise threshold.
subtree8-even/128       time:   [1.2559 ms 1.2625 ms 1.2705 ms]
                        change: [-1.6194% -1.2176% -0.8175%] (p = 0.00 < 0.05)
                        Change within noise threshold.
subtree8-even/192       time:   [1.2530 ms 1.2583 ms 1.2654 ms]
                        change: [-2.0012% -1.5509% -1.1504%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-even/256       time:   [1.2523 ms 1.2554 ms 1.2589 ms]
                        change: [-3.9584% -3.8551% -3.7192%] (p = 0.00 < 0.05)
                        Performance has improved.

subtree8-rand/1         time:   [40.597 µs 40.601 µs 40.605 µs]
                        change: [-0.0056% +0.0055% +0.0163%] (p = 0.35 > 0.05)
                        No change in performance detected.
subtree8-rand/64        time:   [733.62 µs 735.86 µs 738.15 µs]
                        change: [-3.1492% -2.7769% -2.3856%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-rand/128       time:   [974.85 µs 976.46 µs 978.65 µs]
                        change: [-2.9229% -2.5703% -2.2158%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-rand/192       time:   [1.0935 ms 1.0940 ms 1.0945 ms]
                        change: [-4.0548% -3.9489% -3.8495%] (p = 0.00 < 0.05)
                        Performance has improved.
subtree8-rand/256       time:   [1.2033 ms 1.2036 ms 1.2040 ms]
                        change: [-0.2255% -0.1553% -0.0830%] (p = 0.00 < 0.05)
                        Change within noise threshold.

Certainly faster, but not 77% faster.

I can investigate into what actually caused the performance increase if you'd like?