feat: batch hash tree root

matthewkeil commented 1 month ago

Motivation

Created on behalf of @twoeths. Keeping in draft for now but using to store some metrics from different iterations of the changes.

Update system to allow for batch hashing of trees. SIMD instruction set allows for parallel processing of hashes when running on a single core. Add the idea of levels to the hashing process to allow deeper sections of a tree to be processed before higher levels and then computes the hashes according to depth of the tree.

Description

New hashtree hasher for batch hash
Minimal memory allocation:
- use same memory allocated in type to hash all objects of the same type
- use same memory allocated in ListValidatorViewDU to hash all validators in batch
For type.hashTreeRoot():
- Preallocate memory at type level, a type.hashTreeRoot() almost does not need to allocate any temporary Uint8Arrays
- Child fields are hashed into a preallocated memory of parent
- Implement merkleizeInto() in hasher, this also does not allocate memory, and it uses batch hash
For ViewDU:
- Model HashComputation = {left: Node; right: Node; dest: Node}
- Compute HashComputations at different level from the merkle tree
- Execute the HashComputations using batch hash, order is bottom up
For BeaconState, it contains validators as ContainerNodeStructViewDUs
- Overwrite ListValidatorViewDU
- We already track viewsChanged there, when commit() we compute validator roots in batch using preallocated Uint8Array
- Save a lot of memory by avoid tree creation for validator type
Benchmark result on Mac M1
3x faster on a BeaconBlock.hashTreeRoot() call, data comes from a typical mainnet block with 200 transactions
7x faster on a BeaconState of 200k validators, 100k are modified

TODOs

[ ] resolve TODO - batch
[ ] polish the branch
[ ] create smaller PRs for as-sha256, persistent-merkle-tree and ssz

part of #355 closes #78

CLAassistant commented 1 month ago

All committers have signed the CLA.

matthewkeil commented 1 month ago

Ran perf tests on several machines. In all instances i stopped the major services checked with top that nothing substantial was running before starting the tests

`ovh---ksm-0` (x86)

  hasher
    as-sha256
      ✓ hash 2 Uint8Array 500000 times - as-sha256                          2.356940 ops/s    424.2789 ms/op        -          3 runs   17.0 s
      ✓ hashTwoObjects 500000 times - as-sha256                             2.534535 ops/s    394.5497 ms/op        -          3 runs   15.8 s
      ✓ executeHashComputations - as-sha256                                 24.87851 ops/s    40.19533 ms/op        -         23 runs   3.32 s
    noble
      ✓ hash 2 Uint8Array 500000 times - noble                              1.146827 ops/s    871.9712 ms/op        -          3 runs   34.9 s
      ✓ hashTwoObjects 500000 times - noble                                0.7592710 ops/s    1.317053  s/op        -          3 runs   52.7 s
      ✓ executeHashComputations - noble                                     19.65518 ops/s    50.87717 ms/op        -          5 runs   1.61 s
    hashtree
      ✓ hash 2 Uint8Array 500000 times - hashtree                           2.456077 ops/s    407.1533 ms/op        -          3 runs   16.3 s
      ✓ hashTwoObjects 500000 times - hashtree                              2.523110 ops/s    396.3362 ms/op        -          3 runs   16.1 s
      ✓ executeHashComputations - hashtree                                  67.66811 ops/s    14.77801 ms/op        -         21 runs   3.62 s

`matthewkeil-ax41x` (x86)

  hasher
    as-sha256
      ✓ hash 2 Uint8Array 500000 times - as-sha256                          1.996066 ops/s    500.9855 ms/op        -          3 runs   20.0 s
      ✓ hashTwoObjects 500000 times - as-sha256                             2.187445 ops/s    457.1543 ms/op        -          3 runs   18.3 s
      ✓ executeHashComputations - as-sha256                                 19.78581 ops/s    50.54128 ms/op        -         16 runs   2.90 s
    noble
      ✓ hash 2 Uint8Array 500000 times - noble                             0.8846945 ops/s    1.130334  s/op        -          3 runs   45.2 s
      ✓ hashTwoObjects 500000 times - noble                                0.5145042 ops/s    1.943619  s/op        -          3 runs   77.8 s
      ✓ executeHashComputations - noble                                     16.45166 ops/s    60.78414 ms/op        -         20 runs   4.19 s
    hashtree
      ✓ hash 2 Uint8Array 500000 times - hashtree                           3.276744 ops/s    305.1810 ms/op        -          3 runs   12.2 s
      ✓ hashTwoObjects 500000 times - hashtree                              3.924958 ops/s    254.7798 ms/op        -          3 runs   10.2 s
      ✓ executeHashComputations - hashtree                                  92.09554 ops/s    10.85829 ms/op        -         62 runs   9.26 s

`-novc--cax11` (arm64)

  hasher
    as-sha256
      ✓ hash 2 Uint8Array 500000 times - as-sha256                          1.626183 ops/s    614.9369 ms/op        -          3 runs   24.6 s
      ✓ hashTwoObjects 500000 times - as-sha256                             1.709126 ops/s    585.0945 ms/op        -          3 runs   23.4 s
      ✓ executeHashComputations - as-sha256                                 13.50287 ops/s    74.05835 ms/op        -          9 runs   2.54 s
    noble
      ✓ hash 2 Uint8Array 500000 times - noble                             0.7180529 ops/s    1.392655  s/op        -          3 runs   55.6 s
      ✓ hashTwoObjects 500000 times - noble                                0.3339791 ops/s    2.994199  s/op        -          3 runs    120 s
      ✓ executeHashComputations - noble                                     13.06625 ops/s    76.53303 ms/op        -          9 runs   2.67 s
    hashtree
      ✓ hash 2 Uint8Array 500000 times - hashtree                           2.472214 ops/s    404.4957 ms/op        -          3 runs   16.2 s
      ✓ hashTwoObjects 500000 times - hashtree                              2.888047 ops/s    346.2547 ms/op        -          3 runs   13.9 s
      ✓ executeHashComputations - hashtree                                  32.63111 ops/s    30.64560 ms/op        -         27 runs   5.51 s

Locally on M1 mac

  hasher
    as-sha256
      ✓ hash 2 Uint8Array 500000 times - as-sha256                          2.710482 ops/s    368.9380 ms/op        -          3 runs   14.8 s
      ✓ hashTwoObjects 500000 times - as-sha256                             2.882722 ops/s    346.8944 ms/op        -          3 runs   13.9 s
      ✓ executeHashComputations - as-sha256                                 31.00534 ops/s    32.25251 ms/op        -          7 runs   1.36 s
    noble
      ✓ hash 2 Uint8Array 500000 times - noble                              1.384059 ops/s    722.5124 ms/op        -          3 runs   28.9 s
      ✓ hashTwoObjects 500000 times - noble                                0.8926629 ops/s    1.120244  s/op        -          3 runs   45.0 s
      ✓ executeHashComputations - noble                                     24.98550 ops/s    40.02322 ms/op        -         36 runs   3.75 s
    hashtree
      ✓ hash 2 Uint8Array 500000 times - hashtree                           4.368933 ops/s    228.8888 ms/op        -          4 runs   11.5 s
      ✓ hashTwoObjects 500000 times - hashtree                              4.910207 ops/s    203.6574 ms/op        -          4 runs   10.2 s
      ✓ executeHashComputations - hashtree                                  148.0720 ops/s    6.753470 ms/op        -         96 runs   6.95 s

github-actions[bot] commented 2 weeks ago

Performance Report

✔️ no performance regression detected

🚀🚀 Significant benchmark improvement detected

Benchmark suite	Current: 114ad0c603d9881e8b20aa792dd9fdf2c31b9d54	Previous: ec123ec3cfcc37ff82635da7a57ad9c74cc9accb	Ratio
List(Validator-NS) 100000 struct -> binary	7.4186 ms/op	26.835 ms/op	0.28

Full benchmark results

| Benchmark suite | Current: 114ad0c603d9881e8b20aa792dd9fdf2c31b9d54 | Previous: ec123ec3cfcc37ff82635da7a57ad9c74cc9accb | Ratio | |-|-|-|-| | digestTwoHashObjects 50023 times | 48.176 ms/op | 48.074 ms/op | 1.00 | | digest64 50023 times | 51.086 ms/op | 51.160 ms/op | 1.00 | | digest 50023 times | 55.092 ms/op | 52.531 ms/op | 1.05 | | input length 32 | 1.2220 us/op | 1.1960 us/op | 1.02 | | input length 64 | 1.3850 us/op | 1.3590 us/op | 1.02 | | input length 128 | 2.3640 us/op | 2.3300 us/op | 1.01 | | input length 256 | 3.4670 us/op | 3.3610 us/op | 1.03 | | input length 512 | 5.8980 us/op | 5.5660 us/op | 1.06 | | input length 1024 | 11.297 us/op | 10.753 us/op | 1.05 | | digest 1000000 times | 832.12 ms/op | 808.93 ms/op | 1.03 | | hashObjectToByteArray 50023 times | 1.4362 ms/op | 1.4426 ms/op | 1.00 | | byteArrayToHashObject 50023 times | 2.7000 ms/op | 2.5246 ms/op | 1.07 | | digest64 200092 times | 227.97 ms/op | 206.17 ms/op | 1.11 | | hash 200092 times using batchHash4UintArray64s | 239.75 ms/op | 221.05 ms/op | 1.08 | | digest64HashObjects 200092 times | 207.98 ms/op | | hash 200092 times using batchHash4HashObjectInputs | 215.25 ms/op | 207.92 ms/op | 1.04 | | getGindicesAtDepth | 4.5660 us/op | 4.7290 us/op | 0.97 | | iterateAtDepth | 8.1110 us/op | 7.4460 us/op | 1.09 | | getGindexBits | 487.00 ns/op | 443.00 ns/op | 1.10 | | gindexIterator | 1.1290 us/op | 995.00 ns/op | 1.13 | | hash 2 Uint8Array 500000 times - as-sha256 | 572.49 ms/op | | hashTwoObjects 500000 times - as-sha256 | 497.57 ms/op | | executeHashComputations - as-sha256 | 47.433 ms/op | | hash 2 Uint8Array 500000 times - noble | 1.1907 s/op | | hashTwoObjects 500000 times - noble | 1.6067 s/op | | executeHashComputations - noble | 44.045 ms/op | | hash 2 Uint8Array 500000 times - hashtree | 230.42 ms/op | | hashTwoObjects 500000 times - hashtree | 224.75 ms/op | | executeHashComputations - hashtree | 12.362 ms/op | | getNodeH() x7812.5 avg hindex | 12.256 us/op | 12.006 us/op | 1.02 | | getNodeH() x7812.5 index 0 | 6.3940 us/op | 6.3840 us/op | 1.00 | | getNodeH() x7812.5 index 7 | 6.2920 us/op | 6.2770 us/op | 1.00 | | getNodeH() x7812.5 index 7 with key array | 6.2460 us/op | 6.3190 us/op | 0.99 | | new LeafNode() x7812.5 | 14.694 us/op | 14.774 us/op | 0.99 | | getHashComputations 250000 nodes | 28.871 ms/op | | batchHash 250000 nodes | 108.11 ms/op | | get root 250000 nodes | 123.56 ms/op | | getHashComputations 500000 nodes | 78.164 ms/op | | batchHash 500000 nodes | 235.80 ms/op | | get root 500000 nodes | 270.46 ms/op | | getHashComputations 1000000 nodes | 125.23 ms/op | | batchHash 1000000 nodes | 374.70 ms/op | | get root 1000000 nodes | 478.79 ms/op | | multiproof - depth 15, 1 requested leaves | 9.0680 us/op | 9.0540 us/op | 1.00 | | tree offset multiproof - depth 15, 1 requested leaves | 19.673 us/op | 18.895 us/op | 1.04 | | compact multiproof - depth 15, 1 requested leaves | 3.8070 us/op | 3.6910 us/op | 1.03 | | multiproof - depth 15, 2 requested leaves | 12.539 us/op | 11.834 us/op | 1.06 | | tree offset multiproof - depth 15, 2 requested leaves | 22.880 us/op | 22.350 us/op | 1.02 | | compact multiproof - depth 15, 2 requested leaves | 3.8510 us/op | 3.5110 us/op | 1.10 | | multiproof - depth 15, 3 requested leaves | 17.960 us/op | 16.438 us/op | 1.09 | | tree offset multiproof - depth 15, 3 requested leaves | 30.298 us/op | 28.375 us/op | 1.07 | | compact multiproof - depth 15, 3 requested leaves | 4.8260 us/op | 4.3360 us/op | 1.11 | | multiproof - depth 15, 4 requested leaves | 23.123 us/op | 21.791 us/op | 1.06 | | tree offset multiproof - depth 15, 4 requested leaves | 38.024 us/op | 34.989 us/op | 1.09 | | compact multiproof - depth 15, 4 requested leaves | 5.9060 us/op | 5.0690 us/op | 1.17 | | packedRootsBytesToLeafNodes bytes 4000 offset 0 | 1.9560 us/op | 2.0050 us/op | 0.98 | | packedRootsBytesToLeafNodes bytes 4000 offset 1 | 1.9520 us/op | 2.0090 us/op | 0.97 | | packedRootsBytesToLeafNodes bytes 4000 offset 2 | 2.0150 us/op | 2.0030 us/op | 1.01 | | packedRootsBytesToLeafNodes bytes 4000 offset 3 | 1.9340 us/op | 1.7370 us/op | 1.11 | | subtreeFillToContents depth 40 count 250000 | 43.734 ms/op | 46.119 ms/op | 0.95 | | setRoot - gindexBitstring | 11.256 ms/op | 8.2033 ms/op | 1.37 | | setRoot - gindex | 11.592 ms/op | 8.7189 ms/op | 1.33 | | getRoot - gindexBitstring | 2.6291 ms/op | 2.6208 ms/op | 1.00 | | getRoot - gindex | 3.4360 ms/op | 3.3839 ms/op | 1.02 | | getHashObject then setHashObject | 10.685 ms/op | 10.470 ms/op | 1.02 | | setNodeWithFn | 8.7790 ms/op | 7.7663 ms/op | 1.13 | | getNodeAtDepth depth 0 x100000 | 1.1152 ms/op | 1.1102 ms/op | 1.00 | | setNodeAtDepth depth 0 x100000 | 3.3000 ms/op | 2.3061 ms/op | 1.43 | | getNodesAtDepth depth 0 x100000 | 1.0524 ms/op | 1.0809 ms/op | 0.97 | | setNodesAtDepth depth 0 x100000 | 1.4791 ms/op | 1.4677 ms/op | 1.01 | | getNodeAtDepth depth 1 x100000 | 1.1805 ms/op | 1.1858 ms/op | 1.00 | | setNodeAtDepth depth 1 x100000 | 5.5388 ms/op | 5.1455 ms/op | 1.08 | | getNodesAtDepth depth 1 x100000 | 1.1782 ms/op | 1.2057 ms/op | 0.98 | | setNodesAtDepth depth 1 x100000 | 4.6372 ms/op | 4.3193 ms/op | 1.07 | | getNodeAtDepth depth 2 x100000 | 1.4664 ms/op | 1.4579 ms/op | 1.01 | | setNodeAtDepth depth 2 x100000 | 9.8342 ms/op | 8.8385 ms/op | 1.11 | | getNodesAtDepth depth 2 x100000 | 19.787 ms/op | 18.625 ms/op | 1.06 | | setNodesAtDepth depth 2 x100000 | 17.671 ms/op | 12.195 ms/op | 1.45 | | tree.getNodesAtDepth - gindexes | 8.5690 ms/op | 7.5144 ms/op | 1.14 | | tree.getNodesAtDepth - push all nodes | 1.9884 ms/op | 1.9786 ms/op | 1.00 | | tree.getNodesAtDepth - navigation | 234.57 us/op | 236.55 us/op | 0.99 | | tree.setNodesAtDepth - indexes | 484.43 us/op | 353.74 us/op | 1.37 | | set at depth 8 | 582.00 ns/op | 474.00 ns/op | 1.23 | | set at depth 16 | 756.00 ns/op | 618.00 ns/op | 1.22 | | set at depth 32 | 1.0670 us/op | 966.00 ns/op | 1.10 | | iterateNodesAtDepth 8 256 | 14.908 us/op | 13.575 us/op | 1.10 | | getNodesAtDepth 8 256 | 3.7030 us/op | 3.5080 us/op | 1.06 | | iterateNodesAtDepth 16 65536 | 4.5287 ms/op | 4.3698 ms/op | 1.04 | | getNodesAtDepth 16 65536 | 1.6156 ms/op | 1.7222 ms/op | 0.94 | | iterateNodesAtDepth 32 250000 | 16.450 ms/op | 15.738 ms/op | 1.05 | | getNodesAtDepth 32 250000 | 4.5234 ms/op | 4.4142 ms/op | 1.02 | | iterateNodesAtDepth 40 250000 | 16.406 ms/op | 15.922 ms/op | 1.03 | | getNodesAtDepth 40 250000 | 4.6960 ms/op | 4.3923 ms/op | 1.07 | | 1600000 validators root getter | 750.33 ms/op | | 1600000 validators batchHash() | 539.30 ms/op | | 1600000 validators hashComputations | 222.78 ms/op | | bitlist bytes to struct (120,90) | 588.00 ns/op | 490.00 ns/op | 1.20 | | bitlist bytes to tree (120,90) | 2.4280 us/op | 2.2200 us/op | 1.09 | | bitlist bytes to struct (2048,2048) | 1.0520 us/op | 905.00 ns/op | 1.16 | | bitlist bytes to tree (2048,2048) | 3.9100 us/op | 3.3070 us/op | 1.18 | | ByteListType - deserialize | 9.6181 ms/op | 7.8274 ms/op | 1.23 | | BasicListType - deserialize | 11.653 ms/op | 12.344 ms/op | 0.94 | | ByteListType - serialize | 10.235 ms/op | 6.3972 ms/op | 1.60 | | BasicListType - serialize | 13.368 ms/op | 9.7025 ms/op | 1.38 | | BasicListType - tree_convertToStruct | 23.798 ms/op | 22.973 ms/op | 1.04 | | List[uint8, 68719476736] len 300000 ViewDU.getAll() + iterate | 4.9059 ms/op | 4.3801 ms/op | 1.12 | | List[uint8, 68719476736] len 300000 ViewDU.get(i) | 4.0067 ms/op | 2.9349 ms/op | 1.37 | | Array.push len 300000 empty Array - number | 6.9643 ms/op | 6.3491 ms/op | 1.10 | | Array.set len 300000 from new Array - number | 1.9758 ms/op | 1.7588 ms/op | 1.12 | | Array.set len 300000 - number | 6.5587 ms/op | 5.4034 ms/op | 1.21 | | Uint8Array.set len 300000 | 392.18 us/op | 371.95 us/op | 1.05 | | Uint32Array.set len 300000 | 486.80 us/op | 449.14 us/op | 1.08 | | Container({a: uint8, b: uint8}) getViewDU x300000 | 26.946 ms/op | 50.922 ms/op | 0.53 | | ContainerNodeStruct({a: uint8, b: uint8}) getViewDU x300000 | 12.277 ms/op | 10.727 ms/op | 1.14 | | List(Container) len 300000 ViewDU.getAllReadonly() + iterate | 206.52 ms/op | 208.93 ms/op | 0.99 | | List(Container) len 300000 ViewDU.getAllReadonlyValues() + iterate | 285.52 ms/op | 249.80 ms/op | 1.14 | | List(Container) len 300000 ViewDU.get(i) | 7.1492 ms/op | 6.9110 ms/op | 1.03 | | List(Container) len 300000 ViewDU.getReadonly(i) | 6.6474 ms/op | 6.3930 ms/op | 1.04 | | List(ContainerNodeStruct) len 300000 ViewDU.getAllReadonly() + iterate | 39.441 ms/op | 38.916 ms/op | 1.01 | | List(ContainerNodeStruct) len 300000 ViewDU.getAllReadonlyValues() + iterate | 5.6440 ms/op | 5.3279 ms/op | 1.06 | | List(ContainerNodeStruct) len 300000 ViewDU.get(i) | 6.1461 ms/op | 5.9629 ms/op | 1.03 | | List(ContainerNodeStruct) len 300000 ViewDU.getReadonly(i) | 6.3358 ms/op | 5.9201 ms/op | 1.07 | | Array.push len 300000 empty Array - object | 6.7307 ms/op | 5.9600 ms/op | 1.13 | | Array.set len 300000 from new Array - object | 2.0369 ms/op | 2.0556 ms/op | 0.99 | | Array.set len 300000 - object | 6.1117 ms/op | 5.8189 ms/op | 1.05 | | cachePermanentRootStruct no cache | 3.5150 us/op | 8.6950 us/op | 0.40 | | cachePermanentRootStruct with cache | 211.00 ns/op | 192.00 ns/op | 1.10 | | epochParticipation len 250000 rws 7813 | 2.2848 ms/op | 2.2112 ms/op | 1.03 | | Deneb BeaconBlock.hashTreeRoot(), numTransaction=200 | 4.2181 ms/op | | BeaconState ViewDU recursive hash vc=200000 | 226.23 ms/op | | BeaconState ViewDU recursive hash - commit step vc=200000 | 163.30 ms/op | | BeaconState ViewDU validator tree creation vc=100000 | 229.85 ms/op | | BeaconState ViewDU batchHash vc=200000 | 218.58 ms/op | | BeaconState ViewDU batchHash - commit & getHashComputation vc=200000 | 191.98 ms/op | | BeaconState ViewDU batchHash - hash step vc=200000 | 34.326 ms/op | | BeaconState ViewDU hashTreeRoot vc=200000 | 203.42 ms/op | | BeaconState ViewDU hashTreeRoot - commit step vc=200000 | 180.04 ms/op | | BeaconState ViewDU hashTreeRoot - hash step vc=200000 | 40.914 ms/op | | deserialize Attestation - tree | 4.7890 us/op | 4.0850 us/op | 1.17 | | deserialize Attestation - struct | 2.0870 us/op | 1.7520 us/op | 1.19 | | deserialize SignedAggregateAndProof - tree | 4.1690 us/op | 3.5770 us/op | 1.17 | | deserialize SignedAggregateAndProof - struct | 3.2790 us/op | 2.9340 us/op | 1.12 | | deserialize SyncCommitteeMessage - tree | 1.1630 us/op | 1.0450 us/op | 1.11 | | deserialize SyncCommitteeMessage - struct | 1.1250 us/op | 1.0620 us/op | 1.06 | | deserialize SignedContributionAndProof - tree | 2.2750 us/op | 1.9690 us/op | 1.16 | | deserialize SignedContributionAndProof - struct | 2.3690 us/op | 2.2270 us/op | 1.06 | | deserialize SignedBeaconBlock - tree | 222.38 us/op | 205.57 us/op | 1.08 | | deserialize SignedBeaconBlock - struct | 134.70 us/op | 114.17 us/op | 1.18 | | BeaconState vc 300000 - deserialize tree | 555.34 ms/op | 556.43 ms/op | 1.00 | | BeaconState vc 300000 - serialize tree | 90.251 ms/op | 124.39 ms/op | 0.73 | | BeaconState.historicalRoots vc 300000 - deserialize tree | 732.00 ns/op | 708.00 ns/op | 1.03 | | BeaconState.historicalRoots vc 300000 - serialize tree | 642.00 ns/op | 622.00 ns/op | 1.03 | | BeaconState.validators vc 300000 - deserialize tree | 566.91 ms/op | 504.37 ms/op | 1.12 | | BeaconState.validators vc 300000 - serialize tree | 39.177 ms/op | 96.312 ms/op | 0.41 | | BeaconState.balances vc 300000 - deserialize tree | 21.078 ms/op | 21.089 ms/op | 1.00 | | BeaconState.balances vc 300000 - serialize tree | 5.1510 ms/op | 3.6069 ms/op | 1.43 | | BeaconState.previousEpochParticipation vc 300000 - deserialize tree | 675.80 us/op | 439.15 us/op | 1.54 | | BeaconState.previousEpochParticipation vc 300000 - serialize tree | 290.17 us/op | 290.83 us/op | 1.00 | | BeaconState.currentEpochParticipation vc 300000 - deserialize tree | 695.50 us/op | 420.11 us/op | 1.66 | | BeaconState.currentEpochParticipation vc 300000 - serialize tree | 289.35 us/op | 285.56 us/op | 1.01 | | BeaconState.inactivityScores vc 300000 - deserialize tree | 22.457 ms/op | 21.403 ms/op | 1.05 | | BeaconState.inactivityScores vc 300000 - serialize tree | 4.6346 ms/op | 3.5989 ms/op | 1.29 | | hashTreeRoot Attestation - struct | 12.234 us/op | 32.782 us/op | 0.37 | | hashTreeRoot Attestation - tree | 9.3130 us/op | 18.693 us/op | 0.50 | | hashTreeRoot SignedAggregateAndProof - struct | 16.616 us/op | 42.011 us/op | 0.40 | | hashTreeRoot SignedAggregateAndProof - tree | 13.164 us/op | 29.218 us/op | 0.45 | | hashTreeRoot SyncCommitteeMessage - struct | 3.9410 us/op | 9.8200 us/op | 0.40 | | hashTreeRoot SyncCommitteeMessage - tree | 3.2280 us/op | 6.7850 us/op | 0.48 | | hashTreeRoot SignedContributionAndProof - struct | 10.006 us/op | 26.280 us/op | 0.38 | | hashTreeRoot SignedContributionAndProof - tree | 11.352 us/op | 20.019 us/op | 0.57 | | hashTreeRoot SignedBeaconBlock - struct | 989.15 us/op | 2.3074 ms/op | 0.43 | | hashTreeRoot SignedBeaconBlock - tree | 806.17 us/op | 1.7467 ms/op | 0.46 | | hashTreeRoot Validator - struct | 4.6750 us/op | 11.697 us/op | 0.40 | | hashTreeRoot Validator - tree | 5.4230 us/op | 10.477 us/op | 0.52 | | BeaconState vc 300000 - hashTreeRoot tree | 3.4863 s/op | 3.5544 s/op | 0.98 | | BeaconState.historicalRoots vc 300000 - hashTreeRoot tree | 1.9000 us/op | 1.3280 us/op | 1.43 | | BeaconState.validators vc 300000 - hashTreeRoot tree | 1.6478 s/op | 3.3667 s/op | 0.49 | | BeaconState.balances vc 300000 - hashTreeRoot tree | 40.799 ms/op | 83.677 ms/op | 0.49 | | BeaconState.previousEpochParticipation vc 300000 - hashTreeRoot tree | 3.5450 ms/op | 9.0275 ms/op | 0.39 | | BeaconState.currentEpochParticipation vc 300000 - hashTreeRoot tree | 3.6572 ms/op | 9.0168 ms/op | 0.41 | | BeaconState.inactivityScores vc 300000 - hashTreeRoot tree | 35.512 ms/op | 81.442 ms/op | 0.44 | | hash64 x18 | 9.2640 us/op | 18.987 us/op | 0.49 | | hashTwoObjects x18 | 8.6350 us/op | 18.050 us/op | 0.48 | | hash64 x1740 | 856.78 us/op | 1.7863 ms/op | 0.48 | | hashTwoObjects x1740 | 810.07 us/op | 1.7116 ms/op | 0.47 | | hash64 x2700000 | 1.3387 s/op | 2.7833 s/op | 0.48 | | hashTwoObjects x2700000 | 1.2666 s/op | 2.6339 s/op | 0.48 | | get_exitEpoch - ContainerType | 243.00 ns/op | 200.00 ns/op | 1.22 | | get_exitEpoch - ContainerNodeStructType | 275.00 ns/op | 191.00 ns/op | 1.44 | | set_exitEpoch - ContainerType | 284.00 ns/op | 213.00 ns/op | 1.33 | | set_exitEpoch - ContainerNodeStructType | 279.00 ns/op | 239.00 ns/op | 1.17 | | get_pubkey - ContainerType | 982.00 ns/op | 866.00 ns/op | 1.13 | | get_pubkey - ContainerNodeStructType | 260.00 ns/op | 219.00 ns/op | 1.19 | | hashTreeRoot - ContainerType | 288.00 ns/op | 331.00 ns/op | 0.87 | | hashTreeRoot - ContainerNodeStructType | 276.00 ns/op | 376.00 ns/op | 0.73 | | createProof - ContainerType | 4.5610 us/op | 3.7060 us/op | 1.23 | | createProof - ContainerNodeStructType | 23.188 us/op | 19.631 us/op | 1.18 | | serialize - ContainerType | 1.8840 us/op | 1.6640 us/op | 1.13 | | serialize - ContainerNodeStructType | 1.2470 us/op | 1.3400 us/op | 0.93 | | set_exitEpoch_and_hashTreeRoot - ContainerType | 4.6630 us/op | 4.0500 us/op | 1.15 | | set_exitEpoch_and_hashTreeRoot - ContainerNodeStructType | 6.0420 us/op | 10.836 us/op | 0.56 | | ValidatorViewDU hashTreeRoot | 10.710 us/op | | ContainerNodeStructViewDU hashTreeRoot | 20.309 us/op | | Array - for of | 5.7810 us/op | 6.6800 us/op | 0.87 | | Array - for(;;) | 5.6500 us/op | 6.4110 us/op | 0.88 | | basicListValue.readonlyValuesArray() | 6.0236 ms/op | 3.8392 ms/op | 1.57 | | basicListValue.readonlyValuesArray() + loop all | 7.1873 ms/op | 4.0383 ms/op | 1.78 | | compositeListValue.readonlyValuesArray() | 30.001 ms/op | 29.054 ms/op | 1.03 | | compositeListValue.readonlyValuesArray() + loop all | 29.567 ms/op | 26.495 ms/op | 1.12 | | Number64UintType - get balances list | 4.8468 ms/op | 4.2007 ms/op | 1.15 | | Number64UintType - set balances list | 10.637 ms/op | 10.595 ms/op | 1.00 | | Number64UintType - get and increase 10 then set | 39.974 ms/op | 40.170 ms/op | 1.00 | | Number64UintType - increase 10 using applyDelta | 16.121 ms/op | 16.103 ms/op | 1.00 | | Number64UintType - increase 10 using applyDeltaInBatch | 16.226 ms/op | 16.138 ms/op | 1.01 | | tree_newTreeFromUint64Deltas | 16.974 ms/op | 16.661 ms/op | 1.02 | | unsafeUint8ArrayToTree | 33.809 ms/op | 27.704 ms/op | 1.22 | | bitLength(50) | 258.00 ns/op | 213.00 ns/op | 1.21 | | bitLengthStr(50) | 238.00 ns/op | 204.00 ns/op | 1.17 | | bitLength(8000) | 247.00 ns/op | 205.00 ns/op | 1.20 | | bitLengthStr(8000) | 279.00 ns/op | 247.00 ns/op | 1.13 | | bitLength(250000) | 249.00 ns/op | 208.00 ns/op | 1.20 | | bitLengthStr(250000) | 311.00 ns/op | 278.00 ns/op | 1.12 | | merkleizeInto 4 chunks | 1.4500 us/op | | merkleize 4 chunks | 1.9170 us/op | | merkleizeInto 8 chunks | 1.9070 us/op | | merkleize 8 chunks | 3.9400 us/op | | merkleizeInto 16 chunks | 2.6440 us/op | | merkleize 16 chunks | 7.8690 us/op | | merkleizeInto 32 chunks | 3.6470 us/op | | merkleize 32 chunks | 15.490 us/op | | floor - Math.floor (53) | 1.2378 ns/op | 1.2369 ns/op | 1.00 | | floor - << 0 (53) | 1.2372 ns/op | 1.2425 ns/op | 1.00 | | floor - Math.floor (512) | 1.2381 ns/op | 1.2375 ns/op | 1.00 | | floor - << 0 (512) | 1.2373 ns/op | 1.2366 ns/op | 1.00 | | fnIf(0) | 1.5469 ns/op | 1.5477 ns/op | 1.00 | | fnSwitch(0) | 2.1680 ns/op | 2.1641 ns/op | 1.00 | | fnObj(0) | 1.5466 ns/op | 1.5460 ns/op | 1.00 | | fnArr(0) | 1.5461 ns/op | 1.5466 ns/op | 1.00 | | fnIf(4) | 2.1700 ns/op | 2.1644 ns/op | 1.00 | | fnSwitch(4) | 2.1665 ns/op | 2.1656 ns/op | 1.00 | | fnObj(4) | 1.5505 ns/op | 1.5556 ns/op | 1.00 | | fnArr(4) | 1.5462 ns/op | 1.5505 ns/op | 1.00 | | fnIf(9) | 3.1046 ns/op | 3.0924 ns/op | 1.00 | | fnSwitch(9) | 2.1661 ns/op | 2.1640 ns/op | 1.00 | | fnObj(9) | 1.5466 ns/op | 1.5468 ns/op | 1.00 | | fnArr(9) | 1.5456 ns/op | 1.5467 ns/op | 1.00 | | Container {a,b,vec} - as struct x100000 | 123.94 us/op | 123.78 us/op | 1.00 | | Container {a,b,vec} - as tree x100000 | 341.94 us/op | 340.37 us/op | 1.00 | | Container {a,vec,b} - as struct x100000 | 154.73 us/op | 157.03 us/op | 0.99 | | Container {a,vec,b} - as tree x100000 | 371.12 us/op | 371.24 us/op | 1.00 | | get 2 props x1000000 - rawObject | 311.66 us/op | 309.56 us/op | 1.01 | | get 2 props x1000000 - proxy | 72.761 ms/op | 72.698 ms/op | 1.00 | | get 2 props x1000000 - customObj | 310.67 us/op | 309.34 us/op | 1.00 | | Simple object binary -> struct | 608.00 ns/op | 555.00 ns/op | 1.10 | | Simple object binary -> tree_backed | 1.1510 us/op | 978.00 ns/op | 1.18 | | Simple object struct -> tree_backed | 1.7660 us/op | 1.4670 us/op | 1.20 | | Simple object tree_backed -> struct | 1.7520 us/op | 1.5230 us/op | 1.15 | | Simple object struct -> binary | 1.0110 us/op | 829.00 ns/op | 1.22 | | Simple object tree_backed -> binary | 1.4800 us/op | 1.2470 us/op | 1.19 | | aggregationBits binary -> struct | 510.00 ns/op | 445.00 ns/op | 1.15 | | aggregationBits binary -> tree_backed | 2.2620 us/op | 1.8330 us/op | 1.23 | | aggregationBits struct -> tree_backed | 2.7800 us/op | 2.2310 us/op | 1.25 | | aggregationBits tree_backed -> struct | 1.1710 us/op | 928.00 ns/op | 1.26 | | aggregationBits struct -> binary | 763.00 ns/op | 683.00 ns/op | 1.12 | | aggregationBits tree_backed -> binary | 1.0570 us/op | 822.00 ns/op | 1.29 | | List(uint8) 100000 binary -> struct | 1.4583 ms/op | 1.4181 ms/op | 1.03 | | List(uint8) 100000 binary -> tree_backed | 97.424 us/op | 87.831 us/op | 1.11 | | List(uint8) 100000 struct -> tree_backed | 1.1873 ms/op | 1.1019 ms/op | 1.08 | | List(uint8) 100000 tree_backed -> struct | 1.1075 ms/op | 990.82 us/op | 1.12 | | List(uint8) 100000 struct -> binary | 1.0421 ms/op | 987.19 us/op | 1.06 | | List(uint8) 100000 tree_backed -> binary | 92.767 us/op | 87.105 us/op | 1.07 | | List(uint64Number) 100000 binary -> struct | 1.3123 ms/op | 1.1287 ms/op | 1.16 | | List(uint64Number) 100000 binary -> tree_backed | 3.3233 ms/op | 2.4237 ms/op | 1.37 | | List(uint64Number) 100000 struct -> tree_backed | 5.4794 ms/op | 4.0909 ms/op | 1.34 | | List(uint64Number) 100000 tree_backed -> struct | 2.3848 ms/op | 2.0891 ms/op | 1.14 | | List(uint64Number) 100000 struct -> binary | 1.4459 ms/op | 1.3732 ms/op | 1.05 | | List(uint64Number) 100000 tree_backed -> binary | 1.3179 ms/op | 857.72 us/op | 1.54 | | List(Uint64Bigint) 100000 binary -> struct | 3.8144 ms/op | 3.5005 ms/op | 1.09 | | List(Uint64Bigint) 100000 binary -> tree_backed | 3.3924 ms/op | 2.9895 ms/op | 1.13 | | List(Uint64Bigint) 100000 struct -> tree_backed | 5.5271 ms/op | 5.0203 ms/op | 1.10 | | List(Uint64Bigint) 100000 tree_backed -> struct | 5.3561 ms/op | 4.2791 ms/op | 1.25 | | List(Uint64Bigint) 100000 struct -> binary | 2.0527 ms/op | 2.0684 ms/op | 0.99 | | List(Uint64Bigint) 100000 tree_backed -> binary | 994.24 us/op | 861.92 us/op | 1.15 | | Vector(Root) 100000 binary -> struct | 30.857 ms/op | 29.441 ms/op | 1.05 | | Vector(Root) 100000 binary -> tree_backed | 34.297 ms/op | 24.521 ms/op | 1.40 | | Vector(Root) 100000 struct -> tree_backed | 38.887 ms/op | 36.168 ms/op | 1.08 | | Vector(Root) 100000 tree_backed -> struct | 46.683 ms/op | 43.454 ms/op | 1.07 | | Vector(Root) 100000 struct -> binary | 3.0158 ms/op | 2.5042 ms/op | 1.20 | | Vector(Root) 100000 tree_backed -> binary | 11.522 ms/op | 8.4305 ms/op | 1.37 | | List(Validator) 100000 binary -> struct | 118.02 ms/op | 97.389 ms/op | 1.21 | | List(Validator) 100000 binary -> tree_backed | 289.88 ms/op | 256.99 ms/op | 1.13 | | List(Validator) 100000 struct -> tree_backed | 305.83 ms/op | 283.39 ms/op | 1.08 | | List(Validator) 100000 tree_backed -> struct | 206.20 ms/op | 189.31 ms/op | 1.09 | | List(Validator) 100000 struct -> binary | 30.004 ms/op | 26.811 ms/op | 1.12 | | List(Validator) 100000 tree_backed -> binary | 106.58 ms/op | 101.42 ms/op | 1.05 | | List(Validator-NS) 100000 binary -> struct | 108.89 ms/op | 95.106 ms/op | 1.14 | | List(Validator-NS) 100000 binary -> tree_backed | 150.27 ms/op | 132.13 ms/op | 1.14 | | List(Validator-NS) 100000 struct -> tree_backed | 163.53 ms/op | 159.48 ms/op | 1.03 | | List(Validator-NS) 100000 tree_backed -> struct | 135.24 ms/op | 141.56 ms/op | 0.96 | | List(Validator-NS) 100000 struct -> binary | 7.4186 ms/op | 26.835 ms/op | 0.28 | | List(Validator-NS) 100000 tree_backed -> binary | 13.825 ms/op | 30.979 ms/op | 0.45 | | get epochStatuses - MutableVector | 104.93 us/op | 89.507 us/op | 1.17 | | get epochStatuses - ViewDU | 207.47 us/op | 202.50 us/op | 1.02 | | set epochStatuses - ListTreeView | 2.5874 ms/op | 1.4412 ms/op | 1.80 | | set epochStatuses - ListTreeView - set() | 425.04 us/op | 434.78 us/op | 0.98 | | set epochStatuses - ListTreeView - commit() | 637.14 us/op | 433.71 us/op | 1.47 | | bitstring | 646.15 ns/op | 638.89 ns/op | 1.01 | | bit mask | 13.869 ns/op | 13.479 ns/op | 1.03 | | struct - increase slot to 1000000 | 928.11 us/op | 927.62 us/op | 1.00 | | UintNumberType - increase slot to 1000000 | 27.298 ms/op | 21.670 ms/op | 1.26 | | UintBigintType - increase slot to 1000000 | 167.49 ms/op | 166.68 ms/op | 1.00 | | UintBigint8 x 100000 tree_deserialize | 4.5764 ms/op | 4.4755 ms/op | 1.02 | | UintBigint8 x 100000 tree_serialize | 1.0909 ms/op | 1.0908 ms/op | 1.00 | | UintBigint16 x 100000 tree_deserialize | 4.5563 ms/op | 4.5566 ms/op | 1.00 | | UintBigint16 x 100000 tree_serialize | 1.1544 ms/op | 1.1682 ms/op | 0.99 | | UintBigint32 x 100000 tree_deserialize | 4.7292 ms/op | 4.6238 ms/op | 1.02 | | UintBigint32 x 100000 tree_serialize | 1.1635 ms/op | 1.1813 ms/op | 0.98 | | UintBigint64 x 100000 tree_deserialize | 4.9809 ms/op | 5.3241 ms/op | 0.94 | | UintBigint64 x 100000 tree_serialize | 1.5514 ms/op | 1.5455 ms/op | 1.00 | | UintBigint8 x 100000 value_deserialize | 433.25 us/op | 433.09 us/op | 1.00 | | UintBigint8 x 100000 value_serialize | 591.75 us/op | 613.98 us/op | 0.96 | | UintBigint16 x 100000 value_deserialize | 464.77 us/op | 465.11 us/op | 1.00 | | UintBigint16 x 100000 value_serialize | 656.89 us/op | 673.76 us/op | 0.97 | | UintBigint32 x 100000 value_deserialize | 432.99 us/op | 433.45 us/op | 1.00 | | UintBigint32 x 100000 value_serialize | 636.69 us/op | 642.85 us/op | 0.99 | | UintBigint64 x 100000 value_deserialize | 497.45 us/op | 536.29 us/op | 0.93 | | UintBigint64 x 100000 value_serialize | 821.85 us/op | 820.04 us/op | 1.00 | | UintBigint8 x 100000 deserialize | 3.0012 ms/op | 2.9207 ms/op | 1.03 | | UintBigint8 x 100000 serialize | 1.4569 ms/op | 1.5275 ms/op | 0.95 | | UintBigint16 x 100000 deserialize | 3.1597 ms/op | 2.9470 ms/op | 1.07 | | UintBigint16 x 100000 serialize | 1.4633 ms/op | 1.5021 ms/op | 0.97 | | UintBigint32 x 100000 deserialize | 3.1729 ms/op | 2.9789 ms/op | 1.07 | | UintBigint32 x 100000 serialize | 2.7273 ms/op | 2.8512 ms/op | 0.96 | | UintBigint64 x 100000 deserialize | 4.0073 ms/op | 3.5924 ms/op | 1.12 | | UintBigint64 x 100000 serialize | 1.4982 ms/op | 1.5112 ms/op | 0.99 | | UintBigint128 x 100000 deserialize | 5.1330 ms/op | 4.8819 ms/op | 1.05 | | UintBigint128 x 100000 serialize | 15.219 ms/op | 13.846 ms/op | 1.10 | | UintBigint256 x 100000 deserialize | 8.2064 ms/op | 7.6482 ms/op | 1.07 | | UintBigint256 x 100000 serialize | 46.093 ms/op | 41.190 ms/op | 1.12 | | Slice from Uint8Array x25000 | 1.1899 ms/op | 1.1141 ms/op | 1.07 | | Slice from ArrayBuffer x25000 | 16.205 ms/op | 15.704 ms/op | 1.03 | | Slice from ArrayBuffer x25000 + new Uint8Array | 17.640 ms/op | 15.334 ms/op | 1.15 | | Copy Uint8Array 100000 iterate | 1.6706 ms/op | 1.6662 ms/op | 1.00 | | Copy Uint8Array 100000 slice | 122.08 us/op | 113.73 us/op | 1.07 | | Copy Uint8Array 100000 Uint8Array.prototype.slice.call | 122.67 us/op | 113.42 us/op | 1.08 | | Copy Buffer 100000 Uint8Array.prototype.slice.call | 112.96 us/op | 117.75 us/op | 0.96 | | Copy Uint8Array 100000 slice + set | 190.05 us/op | 185.16 us/op | 1.03 | | Copy Uint8Array 100000 subarray + set | 108.85 us/op | 118.83 us/op | 0.92 | | Copy Uint8Array 100000 slice arrayBuffer | 109.65 us/op | 121.31 us/op | 0.90 | | Uint64 deserialize 100000 - iterate Uint8Array | 1.9151 ms/op | 1.7122 ms/op | 1.12 | | Uint64 deserialize 100000 - by Uint32A | 1.9260 ms/op | 1.7533 ms/op | 1.10 | | Uint64 deserialize 100000 - by DataView.getUint32 x2 | 1.9414 ms/op | 1.7972 ms/op | 1.08 | | Uint64 deserialize 100000 - by DataView.getBigUint64 | 5.3315 ms/op | 4.8335 ms/op | 1.10 | | Uint64 deserialize 100000 - by byte | 40.241 ms/op | 39.830 ms/op | 1.01 |

by benchmarkbot/action

ChainSafe / ssz