Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

feat: improve type.hashTreeRoot() using batch #409

Merged
merged 10 commits into from
Mar 11, 2025
Merged

feat: improve type.hashTreeRoot() using batch #409

merged 10 commits into from
Mar 11, 2025
+684 −200

Conversation

twoeths
Copy link
Contributor

@twoeths twoeths commented Oct 15, 2024

Motivation

  • improve type.hashTreeRoot() using batch

Description

  • instead of getRoots() and compute root from there, this PR implement getChunkBytes()
    • this compute root using merkleizeInto() which use batch there
    • reuse chunkBytesBuffer memory in type, almost no Uint8Array allocations in the middle
  • new hashTreeRootInto() api. This is needed in case consumers want to reuse memory allocation there
  • use allocUnsafe() of as-sha256 where it makes sense

cherry picked from #378

@twoeths twoeths mentioned this pull request Oct 15, 2024
Closed
@github-actions GitHub Actions
Copy link

github-actions bot commented Oct 15, 2024 •
edited
Loading

Performance Report

✔️ no performance regression detected

Full benchmark results
Benchmark suite Current: 82ac050 Previous: 089daed Ratio
digestTwoHashObjects 50023 times 48.297 ms/op 48.350 ms/op 1.00
digest2Bytes32 50023 times 54.957 ms/op 55.248 ms/op 0.99
digest 50023 times 53.519 ms/op 53.804 ms/op 0.99
input length 32 1.1570 us/op 1.2030 us/op 0.96
input length 64 1.3280 us/op 1.3190 us/op 1.01
input length 128 2.2510 us/op 2.2560 us/op 1.00
input length 256 3.3350 us/op 3.4580 us/op 0.96
input length 512 5.5600 us/op 5.5370 us/op 1.00
input length 1024 10.726 us/op 10.624 us/op 1.01
digest 1000000 times 857.11 ms/op 855.80 ms/op 1.00
hashObjectToByteArray 50023 times 1.2336 ms/op 1.2288 ms/op 1.00
byteArrayToHashObject 50023 times 1.5493 ms/op 1.6959 ms/op 0.91
digest64 200092 times 214.35 ms/op 214.43 ms/op 1.00
hash 200092 times using batchHash4UintArray64s 238.04 ms/op 237.83 ms/op 1.00
digest64HashObjects 200092 times 194.97 ms/op 193.96 ms/op 1.01
hash 200092 times using batchHash4HashObjectInputs 198.02 ms/op 200.26 ms/op 0.99
getGindicesAtDepth 3.5150 us/op 3.5040 us/op 1.00
iterateAtDepth 6.5240 us/op 6.6550 us/op 0.98
getGindexBits 366.00 ns/op 390.00 ns/op 0.94
gindexIterator 866.00 ns/op 867.00 ns/op 1.00
HashComputationLevel.push then loop 30.617 ms/op 27.633 ms/op 1.11
HashComputation[] push then loop 51.482 ms/op 51.581 ms/op 1.00
hash 2 Uint8Array 500000 times - hashtree 226.73 ms/op 221.38 ms/op 1.02
hashTwoObjects 500000 times - hashtree 211.71 ms/op 214.67 ms/op 0.99
executeHashComputations - hashtree 10.559 ms/op 10.224 ms/op 1.03
hash 2 Uint8Array 500000 times - as-sha256 571.93 ms/op 564.44 ms/op 1.01
hashTwoObjects 500000 times - as-sha256 514.63 ms/op 508.10 ms/op 1.01
executeHashComputations - as-sha256 50.623 ms/op 49.681 ms/op 1.02
hash 2 Uint8Array 500000 times - noble 1.2699 s/op 1.2783 s/op 0.99
hashTwoObjects 500000 times - noble 1.7308 s/op 1.7951 s/op 0.96
executeHashComputations - noble 38.615 ms/op 36.921 ms/op 1.05
getHashComputations 2.6350 ms/op 2.4606 ms/op 1.07
executeHashComputations 10.360 ms/op 12.179 ms/op 0.85
get root 15.970 ms/op 15.551 ms/op 1.03
getNodeH() x7812.5 avg hindex 12.333 us/op 12.213 us/op 1.01
getNodeH() x7812.5 index 0 7.5490 us/op 7.6500 us/op 0.99
getNodeH() x7812.5 index 7 7.5540 us/op 7.4900 us/op 1.01
getNodeH() x7812.5 index 7 with key array 6.3500 us/op 6.4290 us/op 0.99
new LeafNode() x7812.5 311.12 us/op 307.31 us/op 1.01
getHashComputations 250000 nodes 20.989 ms/op 14.982 ms/op 1.40
batchHash 250000 nodes 92.324 ms/op 87.008 ms/op 1.06
get root 250000 nodes 116.00 ms/op 119.91 ms/op 0.97
getHashComputations 500000 nodes 29.097 ms/op 28.527 ms/op 1.02
batchHash 500000 nodes 164.48 ms/op 159.26 ms/op 1.03
get root 500000 nodes 231.71 ms/op 237.70 ms/op 0.97
getHashComputations 1000000 nodes 68.039 ms/op 79.780 ms/op 0.85
batchHash 1000000 nodes 360.47 ms/op 357.80 ms/op 1.01
get root 1000000 nodes 460.94 ms/op 465.57 ms/op 0.99
multiproof - depth 15, 1 requested leaves 8.4460 us/op 7.8250 us/op 1.08
tree offset multiproof - depth 15, 1 requested leaves 18.832 us/op 17.647 us/op 1.07
compact multiproof - depth 15, 1 requested leaves 3.2590 us/op 2.9650 us/op 1.10
multiproof - depth 15, 2 requested leaves 12.183 us/op 11.635 us/op 1.05
tree offset multiproof - depth 15, 2 requested leaves 22.719 us/op 21.027 us/op 1.08
compact multiproof - depth 15, 2 requested leaves 3.2480 us/op 3.0480 us/op 1.07
multiproof - depth 15, 3 requested leaves 16.695 us/op 16.346 us/op 1.02
tree offset multiproof - depth 15, 3 requested leaves 29.251 us/op 27.046 us/op 1.08
compact multiproof - depth 15, 3 requested leaves 4.1770 us/op 3.7380 us/op 1.12
multiproof - depth 15, 4 requested leaves 21.873 us/op 21.927 us/op 1.00
tree offset multiproof - depth 15, 4 requested leaves 36.726 us/op 34.661 us/op 1.06
compact multiproof - depth 15, 4 requested leaves 4.8270 us/op 4.5710 us/op 1.06
packedRootsBytesToLeafNodes bytes 4000 offset 0 6.1710 us/op 5.7620 us/op 1.07
packedRootsBytesToLeafNodes bytes 4000 offset 1 6.0140 us/op 5.9510 us/op 1.01
packedRootsBytesToLeafNodes bytes 4000 offset 2 5.9810 us/op 6.2470 us/op 0.96
packedRootsBytesToLeafNodes bytes 4000 offset 3 6.3150 us/op 6.5230 us/op 0.97
subtreeFillToContents depth 40 count 250000 51.037 ms/op 51.450 ms/op 0.99
setRoot - gindexBitstring 21.518 ms/op 27.926 ms/op 0.77
setRoot - gindex 22.024 ms/op 27.176 ms/op 0.81
getRoot - gindexBitstring 2.5523 ms/op 2.8500 ms/op 0.90
getRoot - gindex 3.0657 ms/op 3.3816 ms/op 0.91
getHashObject then setHashObject 21.798 ms/op 24.123 ms/op 0.90
setNodeWithFn 19.363 ms/op 21.779 ms/op 0.89
getNodeAtDepth depth 0 x100000 280.23 us/op 280.07 us/op 1.00
setNodeAtDepth depth 0 x100000 2.4797 ms/op 2.6229 ms/op 0.95
getNodesAtDepth depth 0 x100000 312.54 us/op 312.08 us/op 1.00
setNodesAtDepth depth 0 x100000 759.86 us/op 767.40 us/op 0.99
getNodeAtDepth depth 1 x100000 348.63 us/op 343.08 us/op 1.02
setNodeAtDepth depth 1 x100000 8.3837 ms/op 9.7988 ms/op 0.86
getNodesAtDepth depth 1 x100000 435.98 us/op 436.13 us/op 1.00
setNodesAtDepth depth 1 x100000 7.5756 ms/op 7.5708 ms/op 1.00
getNodeAtDepth depth 2 x100000 724.11 us/op 742.14 us/op 0.98
setNodeAtDepth depth 2 x100000 14.962 ms/op 18.950 ms/op 0.79
getNodesAtDepth depth 2 x100000 17.407 ms/op 19.552 ms/op 0.89
setNodesAtDepth depth 2 x100000 22.890 ms/op 24.999 ms/op 0.92
tree.getNodesAtDepth - gindexes 9.8226 ms/op 9.8121 ms/op 1.00
tree.getNodesAtDepth - push all nodes 2.2276 ms/op 1.9273 ms/op 1.16
tree.getNodesAtDepth - navigation 311.32 us/op 311.56 us/op 1.00
tree.setNodesAtDepth - indexes 727.80 us/op 711.07 us/op 1.02
set at depth 8 752.00 ns/op 795.00 ns/op 0.95
set at depth 16 1.1290 us/op 1.2040 us/op 0.94
set at depth 32 1.9490 us/op 2.1040 us/op 0.93
iterateNodesAtDepth 8 256 14.021 us/op 14.214 us/op 0.99
getNodesAtDepth 8 256 3.6600 us/op 3.7510 us/op 0.98
iterateNodesAtDepth 16 65536 4.5008 ms/op 4.4323 ms/op 1.02
getNodesAtDepth 16 65536 1.9812 ms/op 1.6374 ms/op 1.21
iterateNodesAtDepth 32 250000 17.831 ms/op 16.168 ms/op 1.10
getNodesAtDepth 32 250000 5.6708 ms/op 4.5882 ms/op 1.24
iterateNodesAtDepth 40 250000 19.193 ms/op 15.618 ms/op 1.23
getNodesAtDepth 40 250000 5.2292 ms/op 4.4420 ms/op 1.18
250000 validators root getter 122.00 ms/op 116.60 ms/op 1.05
250000 validators batchHash() 112.79 ms/op 90.307 ms/op 1.25
250000 validators hashComputations 15.828 ms/op 14.267 ms/op 1.11
bitlist bytes to struct (120,90) 754.00 ns/op 1.0320 us/op 0.73
bitlist bytes to tree (120,90) 2.6590 us/op 3.8140 us/op 0.70
bitlist bytes to struct (2048,2048) 1.0650 us/op 1.1700 us/op 0.91
bitlist bytes to tree (2048,2048) 4.1590 us/op 4.5660 us/op 0.91
ByteListType - deserialize 7.3144 ms/op 8.3780 ms/op 0.87
BasicListType - deserialize 14.522 ms/op 18.521 ms/op 0.78
ByteListType - serialize 7.6531 ms/op 8.2961 ms/op 0.92
BasicListType - serialize 9.8887 ms/op 11.094 ms/op 0.89
BasicListType - tree_convertToStruct 27.301 ms/op 30.512 ms/op 0.89
List[uint8, 68719476736] len 300000 ViewDU.getAll() + iterate 4.8369 ms/op 5.1116 ms/op 0.95
List[uint8, 68719476736] len 300000 ViewDU.get(i) 4.3777 ms/op 4.3844 ms/op 1.00
Array.push len 300000 empty Array - number 6.7507 ms/op 7.2562 ms/op 0.93
Array.set len 300000 from new Array - number 2.0200 ms/op 2.2219 ms/op 0.91
Array.set len 300000 - number 9.3822 ms/op 6.8323 ms/op 1.37
Uint8Array.set len 300000 504.25 us/op 512.42 us/op 0.98
Uint32Array.set len 300000 581.14 us/op 553.43 us/op 1.05
Container({a: uint8, b: uint8}) getViewDU x300000 25.087 ms/op 44.307 ms/op 0.57
ContainerNodeStruct({a: uint8, b: uint8}) getViewDU x300000 10.628 ms/op 12.499 ms/op 0.85
List(Container) len 300000 ViewDU.getAllReadonly() + iterate 229.28 ms/op 198.52 ms/op 1.15
List(Container) len 300000 ViewDU.getAllReadonlyValues() + iterate 260.65 ms/op 244.38 ms/op 1.07
List(Container) len 300000 ViewDU.get(i) 6.9348 ms/op 6.4275 ms/op 1.08
List(Container) len 300000 ViewDU.getReadonly(i) 6.8126 ms/op 6.5868 ms/op 1.03
List(ContainerNodeStruct) len 300000 ViewDU.getAllReadonly() + iterate 39.278 ms/op 37.865 ms/op 1.04
List(ContainerNodeStruct) len 300000 ViewDU.getAllReadonlyValues() + iterate 6.8682 ms/op 5.0735 ms/op 1.35
List(ContainerNodeStruct) len 300000 ViewDU.get(i) 6.8306 ms/op 6.2390 ms/op 1.09
List(ContainerNodeStruct) len 300000 ViewDU.getReadonly(i) 7.6318 ms/op 6.2559 ms/op 1.22
Array.push len 300000 empty Array - object 7.3003 ms/op 6.4447 ms/op 1.13
Array.set len 300000 from new Array - object 2.1842 ms/op 2.0458 ms/op 1.07
Array.set len 300000 - object 8.0999 ms/op 6.7783 ms/op 1.19
cachePermanentRootStruct no cache 3.4770 us/op 5.7670 us/op 0.60
cachePermanentRootStruct with cache 232.00 ns/op 211.00 ns/op 1.10
epochParticipation len 250000 rws 7813 2.3781 ms/op 2.2967 ms/op 1.04
Deneb BeaconBlock.hashTreeRoot(), numTransaction=200 5.5425 ms/op
BeaconState ViewDU hashTreeRoot() vc=200000 116.16 ms/op 111.76 ms/op 1.04
BeaconState ViewDU recursive hash - commit step vc=200000 5.2778 ms/op 4.5206 ms/op 1.17
BeaconState ViewDU validator tree creation vc=10000 40.361 ms/op 38.036 ms/op 1.06
BeaconState ViewDU batchHashTreeRoot vc=200000 112.25 ms/op 102.55 ms/op 1.09
BeaconState ViewDU hashTreeRoot - commit step vc=200000 97.863 ms/op 88.798 ms/op 1.10
BeaconState ViewDU hashTreeRoot - hash step vc=200000 17.690 ms/op 17.716 ms/op 1.00
deserialize Attestation - tree 3.7730 us/op 3.7050 us/op 1.02
deserialize Attestation - struct 2.0000 us/op 1.9470 us/op 1.03
deserialize SignedAggregateAndProof - tree 5.1830 us/op 4.9660 us/op 1.04
deserialize SignedAggregateAndProof - struct 3.1340 us/op 3.1100 us/op 1.01
deserialize SyncCommitteeMessage - tree 1.5030 us/op 1.4330 us/op 1.05
deserialize SyncCommitteeMessage - struct 1.2390 us/op 1.1130 us/op 1.11
deserialize SignedContributionAndProof - tree 3.0290 us/op 2.9250 us/op 1.04
deserialize SignedContributionAndProof - struct 2.7100 us/op 2.3670 us/op 1.14
deserialize SignedBeaconBlock - tree 297.80 us/op 273.24 us/op 1.09
deserialize SignedBeaconBlock - struct 128.06 us/op 119.44 us/op 1.07
BeaconState vc 300000 - deserialize tree 687.72 ms/op 662.96 ms/op 1.04
BeaconState vc 300000 - serialize tree 146.79 ms/op 163.96 ms/op 0.90
BeaconState.historicalRoots vc 300000 - deserialize tree 923.00 ns/op 926.00 ns/op 1.00
BeaconState.historicalRoots vc 300000 - serialize tree 715.00 ns/op 674.00 ns/op 1.06
BeaconState.validators vc 300000 - deserialize tree 684.43 ms/op 611.21 ms/op 1.12
BeaconState.validators vc 300000 - serialize tree 127.24 ms/op 109.11 ms/op 1.17
BeaconState.balances vc 300000 - deserialize tree 30.099 ms/op 27.243 ms/op 1.10
BeaconState.balances vc 300000 - serialize tree 4.4855 ms/op 3.9178 ms/op 1.14
BeaconState.previousEpochParticipation vc 300000 - deserialize tree 1.0662 ms/op 909.53 us/op 1.17
BeaconState.previousEpochParticipation vc 300000 - serialize tree 350.65 us/op 337.72 us/op 1.04
BeaconState.currentEpochParticipation vc 300000 - deserialize tree 981.03 us/op 910.20 us/op 1.08
BeaconState.currentEpochParticipation vc 300000 - serialize tree 372.07 us/op 342.43 us/op 1.09
BeaconState.inactivityScores vc 300000 - deserialize tree 30.722 ms/op 26.116 ms/op 1.18
BeaconState.inactivityScores vc 300000 - serialize tree 4.5081 ms/op 4.2558 ms/op 1.06
hashTreeRoot Attestation - struct 13.844 us/op 18.002 us/op 0.77
hashTreeRoot Attestation - tree 9.0580 us/op 9.0700 us/op 1.00
hashTreeRoot SignedAggregateAndProof - struct 17.068 us/op 27.115 us/op 0.63
hashTreeRoot SignedAggregateAndProof - tree 13.481 us/op 13.542 us/op 1.00
hashTreeRoot SyncCommitteeMessage - struct 4.0210 us/op 6.9330 us/op 0.58
hashTreeRoot SyncCommitteeMessage - tree 3.6460 us/op 3.9680 us/op 0.92
hashTreeRoot SignedContributionAndProof - struct 9.8770 us/op 16.259 us/op 0.61
hashTreeRoot SignedContributionAndProof - tree 9.2780 us/op 9.1960 us/op 1.01
hashTreeRoot SignedBeaconBlock - struct 812.51 us/op 1.4076 ms/op 0.58
hashTreeRoot SignedBeaconBlock - tree 807.39 us/op 800.00 us/op 1.01
hashTreeRoot Validator - struct 4.8370 us/op 8.0410 us/op 0.60
hashTreeRoot Validator - tree 7.3760 us/op 6.8640 us/op 1.07
BeaconState vc 300000 - hashTreeRoot tree 2.3667 s/op 2.3003 s/op 1.03
BeaconState vc 300000 - batchHashTreeRoot tree 4.8055 s/op 4.1698 s/op 1.15
BeaconState.historicalRoots vc 300000 - hashTreeRoot tree 1.1580 us/op 998.00 ns/op 1.16
BeaconState.validators vc 300000 - hashTreeRoot tree 2.6440 s/op 2.4694 s/op 1.07
BeaconState.balances vc 300000 - hashTreeRoot tree 39.892 ms/op 34.638 ms/op 1.15
BeaconState.previousEpochParticipation vc 300000 - hashTreeRoot tree 4.5046 ms/op 4.2524 ms/op 1.06
BeaconState.currentEpochParticipation vc 300000 - hashTreeRoot tree 4.2603 ms/op 4.2329 ms/op 1.01
BeaconState.inactivityScores vc 300000 - hashTreeRoot tree 35.774 ms/op 34.725 ms/op 1.03
hash64 x18 8.6110 us/op 9.6140 us/op 0.90
hashTwoObjects x18 8.3620 us/op 8.0670 us/op 1.04
hash64 x1740 794.57 us/op 798.95 us/op 0.99
hashTwoObjects x1740 766.80 us/op 748.46 us/op 1.02
hash64 x2700000 1.2716 s/op 1.2288 s/op 1.03
hashTwoObjects x2700000 1.1886 s/op 1.1581 s/op 1.03
get_exitEpoch - ContainerType 232.00 ns/op 244.00 ns/op 0.95
get_exitEpoch - ContainerNodeStructType 233.00 ns/op 275.00 ns/op 0.85
set_exitEpoch - ContainerType 258.00 ns/op 276.00 ns/op 0.93
set_exitEpoch - ContainerNodeStructType 248.00 ns/op 262.00 ns/op 0.95
get_pubkey - ContainerType 1.0050 us/op 1.0490 us/op 0.96
get_pubkey - ContainerNodeStructType 260.00 ns/op 244.00 ns/op 1.07
hashTreeRoot - ContainerType 452.00 ns/op 378.00 ns/op 1.20
hashTreeRoot - ContainerNodeStructType 427.00 ns/op 349.00 ns/op 1.22
createProof - ContainerType 4.0690 us/op 3.6640 us/op 1.11
createProof - ContainerNodeStructType 23.191 us/op 20.192 us/op 1.15
serialize - ContainerType 1.8460 us/op 1.6440 us/op 1.12
serialize - ContainerNodeStructType 1.4890 us/op 1.3800 us/op 1.08
set_exitEpoch_and_hashTreeRoot - ContainerType 3.3410 us/op 2.5930 us/op 1.29
set_exitEpoch_and_hashTreeRoot - ContainerNodeStructType 8.7400 us/op 7.3570 us/op 1.19
Array - for of 9.7290 us/op 5.6860 us/op 1.71
Array - for(;;) 9.5430 us/op 5.5880 us/op 1.71
basicListValue.readonlyValuesArray() 5.8780 ms/op 4.2120 ms/op 1.40
basicListValue.readonlyValuesArray() + loop all 5.4995 ms/op 4.3320 ms/op 1.27
compositeListValue.readonlyValuesArray() 36.273 ms/op 27.013 ms/op 1.34
compositeListValue.readonlyValuesArray() + loop all 35.495 ms/op 31.819 ms/op 1.12
Number64UintType - get balances list 4.6259 ms/op 4.3351 ms/op 1.07
Number64UintType - set balances list 10.095 ms/op 9.9302 ms/op 1.02
Number64UintType - get and increase 10 then set 47.903 ms/op 44.843 ms/op 1.07
Number64UintType - increase 10 using applyDelta 17.465 ms/op 16.475 ms/op 1.06
Number64UintType - increase 10 using applyDeltaInBatch 17.048 ms/op 16.751 ms/op 1.02
tree_newTreeFromUint64Deltas 24.525 ms/op 22.391 ms/op 1.10
unsafeUint8ArrayToTree 41.865 ms/op 38.551 ms/op 1.09
bitLength(50) 247.00 ns/op 250.00 ns/op 0.99
bitLengthStr(50) 211.00 ns/op 231.00 ns/op 0.91
bitLength(8000) 229.00 ns/op 223.00 ns/op 1.03
bitLengthStr(8000) 266.00 ns/op 258.00 ns/op 1.03
bitLength(250000) 225.00 ns/op 235.00 ns/op 0.96
bitLengthStr(250000) 294.00 ns/op 293.00 ns/op 1.00
merkleize 32 chunks 15.118 us/op
merkleizeBlocksBytes 32 chunks 3.4680 us/op
merkleizeBlockArray 32 chunks 6.6850 us/op
merkleize 128 chunks 62.343 us/op
merkleizeBlocksBytes 128 chunks 8.0240 us/op
merkleizeBlockArray 128 chunks 19.033 us/op
merkleize 512 chunks 247.90 us/op
merkleizeBlocksBytes 512 chunks 23.555 us/op
merkleizeBlockArray 512 chunks 67.513 us/op
merkleize 1024 chunks 494.14 us/op
merkleizeBlocksBytes 1024 chunks 43.492 us/op
merkleizeBlockArray 1024 chunks 125.53 us/op
floor - Math.floor (53) 1.2438 ns/op 1.2476 ns/op 1.00
floor - << 0 (53) 1.2431 ns/op 1.2435 ns/op 1.00
floor - Math.floor (512) 1.2432 ns/op 1.2442 ns/op 1.00
floor - << 0 (512) 1.2424 ns/op 1.2451 ns/op 1.00
fnIf(0) 1.5535 ns/op 1.5543 ns/op 1.00
fnSwitch(0) 2.1749 ns/op 2.1771 ns/op 1.00
fnObj(0) 1.5547 ns/op 1.5612 ns/op 1.00
fnArr(0) 1.5533 ns/op 1.5542 ns/op 1.00
fnIf(4) 2.1759 ns/op 2.1744 ns/op 1.00
fnSwitch(4) 2.1806 ns/op 2.1900 ns/op 1.00
fnObj(4) 1.5544 ns/op 1.5607 ns/op 1.00
fnArr(4) 1.5556 ns/op 1.5567 ns/op 1.00
fnIf(9) 3.1314 ns/op 3.1105 ns/op 1.01
fnSwitch(9) 2.1808 ns/op 2.1769 ns/op 1.00
fnObj(9) 1.5591 ns/op 1.5777 ns/op 0.99
fnArr(9) 1.5542 ns/op 1.5544 ns/op 1.00
Container {a,b,vec} - as struct x100000 124.92 us/op 124.57 us/op 1.00
Container {a,b,vec} - as tree x100000 559.52 us/op 559.89 us/op 1.00
Container {a,vec,b} - as struct x100000 155.53 us/op 156.41 us/op 0.99
Container {a,vec,b} - as tree x100000 592.49 us/op 560.39 us/op 1.06
get 2 props x1000000 - rawObject 311.75 us/op 311.32 us/op 1.00
get 2 props x1000000 - proxy 74.976 ms/op 74.039 ms/op 1.01
get 2 props x1000000 - customObj 325.13 us/op 311.95 us/op 1.04
Simple object binary -> struct 598.00 ns/op 947.00 ns/op 0.63
Simple object binary -> tree_backed 1.7400 us/op 2.4820 us/op 0.70
Simple object struct -> tree_backed 2.2770 us/op 2.8430 us/op 0.80
Simple object tree_backed -> struct 1.5870 us/op 2.4990 us/op 0.64
Simple object struct -> binary 925.00 ns/op 1.2110 us/op 0.76
Simple object tree_backed -> binary 1.3390 us/op 1.7360 us/op 0.77
aggregationBits binary -> struct 518.00 ns/op 678.00 ns/op 0.76
aggregationBits binary -> tree_backed 2.2260 us/op 2.7350 us/op 0.81
aggregationBits struct -> tree_backed 2.8800 us/op 3.1540 us/op 0.91
aggregationBits tree_backed -> struct 1.1040 us/op 1.2780 us/op 0.86
aggregationBits struct -> binary 683.00 ns/op 835.00 ns/op 0.82
aggregationBits tree_backed -> binary 914.00 ns/op 1.1010 us/op 0.83
List(uint8) 100000 binary -> struct 1.8514 ms/op 1.7192 ms/op 1.08
List(uint8) 100000 binary -> tree_backed 290.73 us/op 275.31 us/op 1.06
List(uint8) 100000 struct -> tree_backed 1.5620 ms/op 1.3975 ms/op 1.12
List(uint8) 100000 tree_backed -> struct 1.1867 ms/op 1.1459 ms/op 1.04
List(uint8) 100000 struct -> binary 1.0447 ms/op 1.1435 ms/op 0.91
List(uint8) 100000 tree_backed -> binary 116.47 us/op 111.57 us/op 1.04
List(uint64Number) 100000 binary -> struct 1.4746 ms/op 1.3440 ms/op 1.10
List(uint64Number) 100000 binary -> tree_backed 5.7815 ms/op 4.4901 ms/op 1.29
List(uint64Number) 100000 struct -> tree_backed 6.4745 ms/op 6.5066 ms/op 1.00
List(uint64Number) 100000 tree_backed -> struct 2.7388 ms/op 2.6367 ms/op 1.04
List(uint64Number) 100000 struct -> binary 1.5757 ms/op 1.6063 ms/op 0.98
List(uint64Number) 100000 tree_backed -> binary 1.2149 ms/op 1.2282 ms/op 0.99
List(Uint64Bigint) 100000 binary -> struct 4.3145 ms/op 4.4331 ms/op 0.97
List(Uint64Bigint) 100000 binary -> tree_backed 5.3358 ms/op 4.8654 ms/op 1.10
List(Uint64Bigint) 100000 struct -> tree_backed 8.4405 ms/op 7.9153 ms/op 1.07
List(Uint64Bigint) 100000 tree_backed -> struct 5.2459 ms/op 5.1174 ms/op 1.03
List(Uint64Bigint) 100000 struct -> binary 2.2144 ms/op 2.0749 ms/op 1.07
List(Uint64Bigint) 100000 tree_backed -> binary 1.2565 ms/op 1.4173 ms/op 0.89
Vector(Root) 100000 binary -> struct 42.575 ms/op 39.591 ms/op 1.08
Vector(Root) 100000 binary -> tree_backed 49.063 ms/op 43.458 ms/op 1.13
Vector(Root) 100000 struct -> tree_backed 59.356 ms/op 54.542 ms/op 1.09
Vector(Root) 100000 tree_backed -> struct 64.877 ms/op 52.560 ms/op 1.23
Vector(Root) 100000 struct -> binary 2.9329 ms/op 2.7957 ms/op 1.05
Vector(Root) 100000 tree_backed -> binary 6.6396 ms/op 6.2213 ms/op 1.07
List(Validator) 100000 binary -> struct 118.85 ms/op 107.68 ms/op 1.10
List(Validator) 100000 binary -> tree_backed 396.60 ms/op 376.74 ms/op 1.05
List(Validator) 100000 struct -> tree_backed 428.81 ms/op 397.50 ms/op 1.08
List(Validator) 100000 tree_backed -> struct 248.56 ms/op 225.28 ms/op 1.10
List(Validator) 100000 struct -> binary 29.879 ms/op 29.560 ms/op 1.01
List(Validator) 100000 tree_backed -> binary 132.61 ms/op 113.67 ms/op 1.17
List(Validator-NS) 100000 binary -> struct 126.61 ms/op 120.94 ms/op 1.05
List(Validator-NS) 100000 binary -> tree_backed 177.04 ms/op 181.62 ms/op 0.97
List(Validator-NS) 100000 struct -> tree_backed 231.46 ms/op 213.35 ms/op 1.08
List(Validator-NS) 100000 tree_backed -> struct 183.20 ms/op 170.59 ms/op 1.07
List(Validator-NS) 100000 struct -> binary 30.001 ms/op 28.769 ms/op 1.04
List(Validator-NS) 100000 tree_backed -> binary 36.317 ms/op 34.762 ms/op 1.04
get epochStatuses - MutableVector 117.98 us/op 115.09 us/op 1.03
get epochStatuses - ViewDU 210.69 us/op 212.71 us/op 0.99
set epochStatuses - ListTreeView 2.3300 ms/op 2.1502 ms/op 1.08
set epochStatuses - ListTreeView - set() 469.88 us/op 472.51 us/op 0.99
set epochStatuses - ListTreeView - commit() 839.26 us/op 830.74 us/op 1.01
bitstring 519.50 ns/op 514.25 ns/op 1.01
bit mask 13.596 ns/op 13.867 ns/op 0.98
struct - increase slot to 1000000 934.68 us/op 932.63 us/op 1.00
UintNumberType - increase slot to 1000000 28.381 ms/op 28.312 ms/op 1.00
UintBigintType - increase slot to 1000000 177.63 ms/op 172.44 ms/op 1.03
UintBigint8 x 100000 tree_deserialize 5.9412 ms/op 5.8397 ms/op 1.02
UintBigint8 x 100000 tree_serialize 1.2220 ms/op 1.1299 ms/op 1.08
UintBigint16 x 100000 tree_deserialize 5.2507 ms/op 5.5272 ms/op 0.95
UintBigint16 x 100000 tree_serialize 1.3474 ms/op 1.3855 ms/op 0.97
UintBigint32 x 100000 tree_deserialize 5.4021 ms/op 5.6201 ms/op 0.96
UintBigint32 x 100000 tree_serialize 1.6782 ms/op 1.8839 ms/op 0.89
UintBigint64 x 100000 tree_deserialize 5.8067 ms/op 6.0277 ms/op 0.96
UintBigint64 x 100000 tree_serialize 1.7175 ms/op 2.5647 ms/op 0.67
UintBigint8 x 100000 value_deserialize 435.54 us/op 435.37 us/op 1.00
UintBigint8 x 100000 value_serialize 729.25 us/op 789.63 us/op 0.92
UintBigint16 x 100000 value_deserialize 466.82 us/op 467.59 us/op 1.00
UintBigint16 x 100000 value_serialize 786.83 us/op 839.45 us/op 0.94
UintBigint32 x 100000 value_deserialize 499.07 us/op 497.67 us/op 1.00
UintBigint32 x 100000 value_serialize 811.18 us/op 869.33 us/op 0.93
UintBigint64 x 100000 value_deserialize 566.12 us/op 561.69 us/op 1.01
UintBigint64 x 100000 value_serialize 1.0165 ms/op 1.0797 ms/op 0.94
UintBigint8 x 100000 deserialize 3.9782 ms/op 3.6284 ms/op 1.10
UintBigint8 x 100000 serialize 1.4681 ms/op 1.8198 ms/op 0.81
UintBigint16 x 100000 deserialize 3.3167 ms/op 3.1410 ms/op 1.06
UintBigint16 x 100000 serialize 1.5858 ms/op 1.5117 ms/op 1.05
UintBigint32 x 100000 deserialize 3.7591 ms/op 3.1881 ms/op 1.18
UintBigint32 x 100000 serialize 3.0765 ms/op 2.8694 ms/op 1.07
UintBigint64 x 100000 deserialize 4.7736 ms/op 4.1369 ms/op 1.15
UintBigint64 x 100000 serialize 1.6489 ms/op 1.6342 ms/op 1.01
UintBigint128 x 100000 deserialize 6.0688 ms/op 5.3990 ms/op 1.12
UintBigint128 x 100000 serialize 15.960 ms/op 14.347 ms/op 1.11
UintBigint256 x 100000 deserialize 10.173 ms/op 8.0526 ms/op 1.26
UintBigint256 x 100000 serialize 48.670 ms/op 43.221 ms/op 1.13
Slice from Uint8Array x25000 1.5283 ms/op 1.3258 ms/op 1.15
Slice from ArrayBuffer x25000 17.499 ms/op 16.751 ms/op 1.04
Slice from ArrayBuffer x25000 + new Uint8Array 19.325 ms/op 16.154 ms/op 1.20
Copy Uint8Array 100000 iterate 2.7619 ms/op 2.6558 ms/op 1.04
Copy Uint8Array 100000 slice 171.08 us/op 108.81 us/op 1.57
Copy Uint8Array 100000 Uint8Array.prototype.slice.call 178.97 us/op 110.74 us/op 1.62
Copy Buffer 100000 Uint8Array.prototype.slice.call 170.56 us/op 107.64 us/op 1.58
Copy Uint8Array 100000 slice + set 378.56 us/op 218.60 us/op 1.73
Copy Uint8Array 100000 subarray + set 176.90 us/op 106.86 us/op 1.66
Copy Uint8Array 100000 slice arrayBuffer 178.19 us/op 106.16 us/op 1.68
Uint64 deserialize 100000 - iterate Uint8Array 2.5375 ms/op 1.9314 ms/op 1.31
Uint64 deserialize 100000 - by Uint32A 2.4288 ms/op 1.9477 ms/op 1.25
Uint64 deserialize 100000 - by DataView.getUint32 x2 2.6245 ms/op 2.0050 ms/op 1.31
Uint64 deserialize 100000 - by DataView.getBigUint64 5.9750 ms/op 5.0519 ms/op 1.18
Uint64 deserialize 100000 - by byte 41.806 ms/op 40.703 ms/op 1.03

by benchmarkbot/action

@twoeths
Copy link
Contributor Author

twoeths commented Oct 21, 2024

tested this on feat1, see ChainSafe/lodestar#7171 (comment)
ready to review

@twoeths twoeths marked this pull request as ready for review October 21, 2024 03:18
@twoeths twoeths requested a review from a team as a code owner October 21, 2024 03:18
@twoeths twoeths mentioned this pull request Oct 21, 2024
Draft
@twoeths twoeths marked this pull request as draft October 31, 2024 03:39
@twoeths
Copy link
Contributor Author

twoeths commented Oct 31, 2024 •
edited
Loading

sha256 works in blocks, each is 64 bytes so perhaps it's more meaningful to reflect that for chunkBytesBuffer variable

also with holesky, there are 1.7M validators. For every 8 deposits we have to reallocate the whole 1.7M * 8 bytes = 13.6MB for BeaconState.balances which is not ideal. Need to instead allocate another 64 bytes in this case. This applies for all list types.

Update:

  • the hash of BeaconState.balances and everything inside BeaconState work through ViewDU so it's not revelant
  • it's more related to the hash of BeaconBlock, for example transaction data and lists like number of transactions

@twoeths twoeths force-pushed the te/improve_type_dot_hash_tree_root branch 2 times, most recently from 9e32c5c to 7ed3ced Compare November 9, 2024 02:19
@philknows philknows modified the milestones: v1.0, v1.1 Jan 22, 2025
@nazarhussain nazarhussain force-pushed the te/improve_type_dot_hash_tree_root branch from d3821ee to cbb30a2 Compare February 12, 2025 12:18
@nazarhussain nazarhussain marked this pull request as ready for review February 12, 2025 14:05
matthewkeil
matthewkeil reviewed Feb 21, 2025
View reviewed changes
Copy link
Member

@matthewkeil matthewkeil left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I left a few comments but I think this PR really needs to be reviewed by @wemeetagain

@nazarhussain nazarhussain requested a review from matthewkeil March 4, 2025 12:21
@nazarhussain nazarhussain mentioned this pull request Mar 5, 2025
Open
wemeetagain
wemeetagain previously approved these changes Mar 7, 2025
View reviewed changes
@nazarhussain nazarhussain merged commit 66742f0 into master Mar 11, 2025
9 checks passed
@nazarhussain nazarhussain deleted the te/improve_type_dot_hash_tree_root branch March 11, 2025 15:18
@wemeetagain wemeetagain mentioned this pull request Mar 11, 2025
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@nazarhussain nazarhussain nazarhussain approved these changes

@wemeetagain wemeetagain wemeetagain approved these changes

@matthewkeil matthewkeil Awaiting requested review from matthewkeil

Assignees
No one assigned
Labels
as-sha256 ssz
Projects
None yet
Milestone
v1.1
Development

Successfully merging this pull request may close these issues.
5 participants
@twoeths @nazarhussain @wemeetagain @matthewkeil @philknows