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: implement HashComputationLevel using LinkedList #389

Merged
merged 5 commits into from
Aug 6, 2024
Merged

feat: implement HashComputationLevel using LinkedList #389

merged 5 commits into from
Aug 6, 2024

Conversation

twoeths
Copy link
Contributor

@twoeths twoeths commented Jul 23, 2024 •
edited
Loading

Motivation

Description

  • Move HashComputation type and its utils to a separate class
  • Implement HashComputationLevel to be a linked-list like to save memory allocation:
    • when push() may reuse the existing item of LinkedList instead of allocate one
    • when it grows it only need to add one more list items, instead of allocating a whole new array to reuse and save memory
    • loop speed is same to a regular array
    • we don't need random access
  • others:
    • hashtree: allocate destNodes variable once, set it as default
    • subtreeFillToContents + setNodesAtDepth: destructure params in order not to allocate temporary objects at the consumer side

test result was persisted here

part of #378

cc @wemeetagain @g11tech

@github-actions GitHub Actions
Copy link

github-actions bot commented Jul 23, 2024 •
edited
Loading

Performance Report

✔️ no performance regression detected

Full benchmark results
Benchmark suite Current: e0d2094 Previous: 1578883 Ratio
digestTwoHashObjects 50023 times 47.872 ms/op 48.098 ms/op 1.00
digest64 50023 times 51.911 ms/op 51.043 ms/op 1.02
digest 50023 times 51.214 ms/op 58.931 ms/op 0.87
input length 32 1.1610 us/op 1.4760 us/op 0.79
input length 64 1.3190 us/op 1.6290 us/op 0.81
input length 128 2.2460 us/op 2.6700 us/op 0.84
input length 256 3.3400 us/op 3.8610 us/op 0.87
input length 512 5.5790 us/op 6.2890 us/op 0.89
input length 1024 10.789 us/op 11.592 us/op 0.93
digest 1000000 times 794.76 ms/op 894.07 ms/op 0.89
hashObjectToByteArray 50023 times 1.4281 ms/op 1.4538 ms/op 0.98
byteArrayToHashObject 50023 times 2.5412 ms/op 2.8036 ms/op 0.91
digest64 200092 times 205.14 ms/op 237.79 ms/op 0.86
hash 200092 times using batchHash4UintArray64s 216.86 ms/op 242.40 ms/op 0.89
digest64HashObjects 200092 times 193.86 ms/op 208.10 ms/op 0.93
hash 200092 times using batchHash4HashObjectInputs 199.69 ms/op 223.96 ms/op 0.89
getGindicesAtDepth 4.1830 us/op 4.6070 us/op 0.91
iterateAtDepth 7.5360 us/op 8.5470 us/op 0.88
getGindexBits 463.00 ns/op 543.00 ns/op 0.85
gindexIterator 1.0650 us/op 1.1530 us/op 0.92
HashComputationLevel.push then loop 26.825 ms/op
HashComputation[] push then loop 48.122 ms/op
hash 2 Uint8Array 500000 times - as-sha256 516.10 ms/op 589.77 ms/op 0.88
hashTwoObjects 500000 times - as-sha256 512.88 ms/op 502.44 ms/op 1.02
executeHashComputations - as-sha256 47.480 ms/op 46.575 ms/op 1.02
hash 2 Uint8Array 500000 times - noble 1.0668 s/op 1.1988 s/op 0.89
hashTwoObjects 500000 times - noble 1.5205 s/op 1.7515 s/op 0.87
executeHashComputations - noble 39.959 ms/op 38.344 ms/op 1.04
hash 2 Uint8Array 500000 times - hashtree 230.15 ms/op 234.30 ms/op 0.98
hashTwoObjects 500000 times - hashtree 217.40 ms/op 219.16 ms/op 0.99
executeHashComputations - hashtree 11.339 ms/op 16.988 ms/op 0.67
getNodeH() x7812.5 avg hindex 12.041 us/op 13.049 us/op 0.92
getNodeH() x7812.5 index 0 6.2870 us/op 6.2460 us/op 1.01
getNodeH() x7812.5 index 7 6.3300 us/op 6.2530 us/op 1.01
getNodeH() x7812.5 index 7 with key array 6.2690 us/op 6.2390 us/op 1.00
new LeafNode() x7812.5 14.744 us/op 14.671 us/op 1.00
getHashComputations 250000 nodes 18.612 ms/op 18.731 ms/op 0.99
batchHash 250000 nodes 327.17 ms/op 351.19 ms/op 0.93
get root 250000 nodes 801.03 ms/op 969.79 ms/op 0.83
getHashComputations 500000 nodes 26.633 ms/op 36.103 ms/op 0.74
batchHash 500000 nodes 580.05 ms/op 621.06 ms/op 0.93
get root 500000 nodes 1.5997 s/op 1.9052 s/op 0.84
getHashComputations 1000000 nodes 61.640 ms/op 85.949 ms/op 0.72
batchHash 1000000 nodes 1.1689 s/op 1.2345 s/op 0.95
get root 1000000 nodes 3.1226 s/op 3.8316 s/op 0.81
multiproof - depth 15, 1 requested leaves 8.1080 us/op 9.6840 us/op 0.84
tree offset multiproof - depth 15, 1 requested leaves 17.702 us/op 20.935 us/op 0.85
compact multiproof - depth 15, 1 requested leaves 3.5650 us/op 4.4030 us/op 0.81
multiproof - depth 15, 2 requested leaves 11.647 us/op 14.202 us/op 0.82
tree offset multiproof - depth 15, 2 requested leaves 21.320 us/op 24.979 us/op 0.85
compact multiproof - depth 15, 2 requested leaves 3.5180 us/op 4.4450 us/op 0.79
multiproof - depth 15, 3 requested leaves 16.182 us/op 19.463 us/op 0.83
tree offset multiproof - depth 15, 3 requested leaves 27.498 us/op 32.084 us/op 0.86
compact multiproof - depth 15, 3 requested leaves 4.1050 us/op 5.9560 us/op 0.69
multiproof - depth 15, 4 requested leaves 21.054 us/op 25.203 us/op 0.84
tree offset multiproof - depth 15, 4 requested leaves 34.220 us/op 39.971 us/op 0.86
compact multiproof - depth 15, 4 requested leaves 4.9010 us/op 7.0430 us/op 0.70
packedRootsBytesToLeafNodes bytes 4000 offset 0 1.7110 us/op 3.4100 us/op 0.50
packedRootsBytesToLeafNodes bytes 4000 offset 1 1.6930 us/op 2.8950 us/op 0.58
packedRootsBytesToLeafNodes bytes 4000 offset 2 1.7070 us/op 2.6660 us/op 0.64
packedRootsBytesToLeafNodes bytes 4000 offset 3 1.6900 us/op 2.4340 us/op 0.69
subtreeFillToContents depth 40 count 250000 38.948 ms/op 45.302 ms/op 0.86
setRoot - gindexBitstring 8.5951 ms/op 11.446 ms/op 0.75
setRoot - gindex 8.9798 ms/op 12.246 ms/op 0.73
getRoot - gindexBitstring 2.5853 ms/op 2.7112 ms/op 0.95
getRoot - gindex 3.2529 ms/op 3.6256 ms/op 0.90
getHashObject then setHashObject 9.6927 ms/op 12.206 ms/op 0.79
setNodeWithFn 7.2759 ms/op 9.6518 ms/op 0.75
getNodeAtDepth depth 0 x100000 1.1140 ms/op 1.1147 ms/op 1.00
setNodeAtDepth depth 0 x100000 2.3552 ms/op 2.9412 ms/op 0.80
getNodesAtDepth depth 0 x100000 1.0534 ms/op 1.0527 ms/op 1.00
setNodesAtDepth depth 0 x100000 1.5177 ms/op 1.4598 ms/op 1.04
getNodeAtDepth depth 1 x100000 1.1796 ms/op 1.1820 ms/op 1.00
setNodeAtDepth depth 1 x100000 5.0235 ms/op 6.3041 ms/op 0.80
getNodesAtDepth depth 1 x100000 1.1788 ms/op 1.1771 ms/op 1.00
setNodesAtDepth depth 1 x100000 4.3086 ms/op 5.2765 ms/op 0.82
getNodeAtDepth depth 2 x100000 1.4539 ms/op 1.4545 ms/op 1.00
setNodeAtDepth depth 2 x100000 8.7223 ms/op 11.988 ms/op 0.73
getNodesAtDepth depth 2 x100000 17.851 ms/op 20.101 ms/op 0.89
setNodesAtDepth depth 2 x100000 12.954 ms/op 14.807 ms/op 0.87
tree.getNodesAtDepth - gindexes 7.6174 ms/op 9.9621 ms/op 0.76
tree.getNodesAtDepth - push all nodes 1.8005 ms/op 2.1940 ms/op 0.82
tree.getNodesAtDepth - navigation 233.79 us/op 232.52 us/op 1.01
tree.setNodesAtDepth - indexes 393.97 us/op 487.95 us/op 0.81
set at depth 8 439.00 ns/op 588.00 ns/op 0.75
set at depth 16 582.00 ns/op 807.00 ns/op 0.72
set at depth 32 903.00 ns/op 1.2130 us/op 0.74
iterateNodesAtDepth 8 256 13.072 us/op 14.946 us/op 0.87
getNodesAtDepth 8 256 3.3340 us/op 3.7070 us/op 0.90
iterateNodesAtDepth 16 65536 4.1574 ms/op 4.5803 ms/op 0.91
getNodesAtDepth 16 65536 1.4957 ms/op 1.7377 ms/op 0.86
iterateNodesAtDepth 32 250000 15.292 ms/op 16.474 ms/op 0.93
getNodesAtDepth 32 250000 4.1828 ms/op 5.0082 ms/op 0.84
iterateNodesAtDepth 40 250000 15.288 ms/op 16.404 ms/op 0.93
getNodesAtDepth 40 250000 4.2135 ms/op 5.1320 ms/op 0.82
250000 validators root getter 825.63 ms/op
250000 validators batchHash() 285.02 ms/op
250000 validators hashComputations 13.638 ms/op
bitlist bytes to struct (120,90) 677.00 ns/op 586.00 ns/op 1.16
bitlist bytes to tree (120,90) 2.8350 us/op 2.7340 us/op 1.04
bitlist bytes to struct (2048,2048) 1.0890 us/op 1.2650 us/op 0.86
bitlist bytes to tree (2048,2048) 4.1050 us/op 4.3770 us/op 0.94
ByteListType - deserialize 7.3538 ms/op 10.544 ms/op 0.70
BasicListType - deserialize 17.178 ms/op 14.148 ms/op 1.21
ByteListType - serialize 7.8762 ms/op 10.549 ms/op 0.75
BasicListType - serialize 10.499 ms/op 14.591 ms/op 0.72
BasicListType - tree_convertToStruct 28.906 ms/op 27.925 ms/op 1.04
List[uint8, 68719476736] len 300000 ViewDU.getAll() + iterate 4.5685 ms/op 6.6210 ms/op 0.69
List[uint8, 68719476736] len 300000 ViewDU.get(i) 4.1131 ms/op 3.9754 ms/op 1.03
Array.push len 300000 empty Array - number 6.1546 ms/op 7.9548 ms/op 0.77
Array.set len 300000 from new Array - number 2.0844 ms/op 2.8766 ms/op 0.72
Array.set len 300000 - number 5.9215 ms/op 7.3264 ms/op 0.81
Uint8Array.set len 300000 371.61 us/op 393.20 us/op 0.95
Uint32Array.set len 300000 437.38 us/op 479.10 us/op 0.91
Container({a: uint8, b: uint8}) getViewDU x300000 51.582 ms/op 57.757 ms/op 0.89
ContainerNodeStruct({a: uint8, b: uint8}) getViewDU x300000 10.693 ms/op 11.975 ms/op 0.89
List(Container) len 300000 ViewDU.getAllReadonly() + iterate 204.08 ms/op 222.54 ms/op 0.92
List(Container) len 300000 ViewDU.getAllReadonlyValues() + iterate 256.61 ms/op 281.44 ms/op 0.91
List(Container) len 300000 ViewDU.get(i) 6.9339 ms/op 10.823 ms/op 0.64
List(Container) len 300000 ViewDU.getReadonly(i) 6.6385 ms/op 9.5995 ms/op 0.69
List(ContainerNodeStruct) len 300000 ViewDU.getAllReadonly() + iterate 40.042 ms/op 40.461 ms/op 0.99
List(ContainerNodeStruct) len 300000 ViewDU.getAllReadonlyValues() + iterate 5.3637 ms/op 6.7733 ms/op 0.79
List(ContainerNodeStruct) len 300000 ViewDU.get(i) 6.3186 ms/op 10.390 ms/op 0.61
List(ContainerNodeStruct) len 300000 ViewDU.getReadonly(i) 6.1638 ms/op 9.7459 ms/op 0.63
Array.push len 300000 empty Array - object 6.6013 ms/op 7.2653 ms/op 0.91
Array.set len 300000 from new Array - object 2.0869 ms/op 3.4506 ms/op 0.60
Array.set len 300000 - object 6.4993 ms/op 7.1740 ms/op 0.91
cachePermanentRootStruct no cache 5.6260 us/op 9.9890 us/op 0.56
cachePermanentRootStruct with cache 245.00 ns/op 283.00 ns/op 0.87
epochParticipation len 250000 rws 7813 2.3133 ms/op 2.4283 ms/op 0.95
deserialize Attestation - tree 4.4880 us/op 4.7050 us/op 0.95
deserialize Attestation - struct 1.9290 us/op 2.2840 us/op 0.84
deserialize SignedAggregateAndProof - tree 3.8400 us/op 4.8490 us/op 0.79
deserialize SignedAggregateAndProof - struct 3.0720 us/op 4.0770 us/op 0.75
deserialize SyncCommitteeMessage - tree 1.1100 us/op 1.2650 us/op 0.88
deserialize SyncCommitteeMessage - struct 996.00 ns/op 1.1920 us/op 0.84
deserialize SignedContributionAndProof - tree 2.1500 us/op 2.4780 us/op 0.87
deserialize SignedContributionAndProof - struct 2.1480 us/op 2.5910 us/op 0.83
deserialize SignedBeaconBlock - tree 218.98 us/op 245.64 us/op 0.89
deserialize SignedBeaconBlock - struct 117.62 us/op 130.47 us/op 0.90
BeaconState vc 300000 - deserialize tree 560.39 ms/op 606.77 ms/op 0.92
BeaconState vc 300000 - serialize tree 101.83 ms/op 140.97 ms/op 0.72
BeaconState.historicalRoots vc 300000 - deserialize tree 773.00 ns/op 870.00 ns/op 0.89
BeaconState.historicalRoots vc 300000 - serialize tree 618.00 ns/op 744.00 ns/op 0.83
BeaconState.validators vc 300000 - deserialize tree 513.95 ms/op 561.01 ms/op 0.92
BeaconState.validators vc 300000 - serialize tree 101.71 ms/op 99.779 ms/op 1.02
BeaconState.balances vc 300000 - deserialize tree 20.292 ms/op 21.893 ms/op 0.93
BeaconState.balances vc 300000 - serialize tree 3.6813 ms/op 7.1918 ms/op 0.51
BeaconState.previousEpochParticipation vc 300000 - deserialize tree 457.51 us/op 792.47 us/op 0.58
BeaconState.previousEpochParticipation vc 300000 - serialize tree 286.90 us/op 300.54 us/op 0.95
BeaconState.currentEpochParticipation vc 300000 - deserialize tree 473.05 us/op 827.63 us/op 0.57
BeaconState.currentEpochParticipation vc 300000 - serialize tree 286.09 us/op 304.86 us/op 0.94
BeaconState.inactivityScores vc 300000 - deserialize tree 20.993 ms/op 22.522 ms/op 0.93
BeaconState.inactivityScores vc 300000 - serialize tree 3.5949 ms/op 7.3602 ms/op 0.49
hashTreeRoot Attestation - struct 23.307 us/op 62.645 us/op 0.37
hashTreeRoot Attestation - tree 9.5750 us/op 23.452 us/op 0.41
hashTreeRoot SignedAggregateAndProof - struct 26.364 us/op 70.788 us/op 0.37
hashTreeRoot SignedAggregateAndProof - tree 13.034 us/op 30.654 us/op 0.43
hashTreeRoot SyncCommitteeMessage - struct 6.8090 us/op 18.128 us/op 0.38
hashTreeRoot SyncCommitteeMessage - tree 3.1710 us/op 7.2220 us/op 0.44
hashTreeRoot SignedContributionAndProof - struct 15.593 us/op 38.246 us/op 0.41
hashTreeRoot SignedContributionAndProof - tree 8.8750 us/op 20.813 us/op 0.43
hashTreeRoot SignedBeaconBlock - struct 1.3702 ms/op 2.9015 ms/op 0.47
hashTreeRoot SignedBeaconBlock - tree 780.25 us/op 1.8997 ms/op 0.41
hashTreeRoot Validator - struct 7.7540 us/op 15.298 us/op 0.51
hashTreeRoot Validator - tree 6.6830 us/op 13.129 us/op 0.51
BeaconState vc 300000 - hashTreeRoot tree 2.0898 s/op 4.0034 s/op 0.52
BeaconState.historicalRoots vc 300000 - hashTreeRoot tree 965.00 ns/op 1.6540 us/op 0.58
BeaconState.validators vc 300000 - hashTreeRoot tree 2.0036 s/op 3.8062 s/op 0.53
BeaconState.balances vc 300000 - hashTreeRoot tree 33.916 ms/op 83.211 ms/op 0.41
BeaconState.previousEpochParticipation vc 300000 - hashTreeRoot tree 4.1259 ms/op 10.045 ms/op 0.41
BeaconState.currentEpochParticipation vc 300000 - hashTreeRoot tree 4.1382 ms/op 10.030 ms/op 0.41
BeaconState.inactivityScores vc 300000 - hashTreeRoot tree 33.509 ms/op 81.030 ms/op 0.41
hash64 x18 9.0310 us/op 19.871 us/op 0.45
hashTwoObjects x18 8.7420 us/op 20.332 us/op 0.43
hash64 x1740 841.54 us/op 1.8450 ms/op 0.46
hashTwoObjects x1740 809.99 us/op 1.8995 ms/op 0.43
hash64 x2700000 1.2774 s/op 2.8693 s/op 0.45
hashTwoObjects x2700000 1.2611 s/op 2.9436 s/op 0.43
get_exitEpoch - ContainerType 211.00 ns/op 459.00 ns/op 0.46
get_exitEpoch - ContainerNodeStructType 198.00 ns/op 425.00 ns/op 0.47
set_exitEpoch - ContainerType 228.00 ns/op 461.00 ns/op 0.49
set_exitEpoch - ContainerNodeStructType 198.00 ns/op 446.00 ns/op 0.44
get_pubkey - ContainerType 836.00 ns/op 884.00 ns/op 0.95
get_pubkey - ContainerNodeStructType 207.00 ns/op 439.00 ns/op 0.47
hashTreeRoot - ContainerType 348.00 ns/op 720.00 ns/op 0.48
hashTreeRoot - ContainerNodeStructType 406.00 ns/op 759.00 ns/op 0.53
createProof - ContainerType 3.8330 us/op 5.6070 us/op 0.68
createProof - ContainerNodeStructType 19.715 us/op 27.166 us/op 0.73
serialize - ContainerType 1.6170 us/op 2.1220 us/op 0.76
serialize - ContainerNodeStructType 1.3190 us/op 1.7310 us/op 0.76
set_exitEpoch_and_hashTreeRoot - ContainerType 2.5720 us/op 5.5210 us/op 0.47
set_exitEpoch_and_hashTreeRoot - ContainerNodeStructType 6.8260 us/op 13.800 us/op 0.49
Array - for of 6.0510 us/op 5.8690 us/op 1.03
Array - for(;;) 5.7470 us/op 5.8750 us/op 0.98
basicListValue.readonlyValuesArray() 3.9731 ms/op 4.9419 ms/op 0.80
basicListValue.readonlyValuesArray() + loop all 4.0967 ms/op 5.1149 ms/op 0.80
compositeListValue.readonlyValuesArray() 29.596 ms/op 29.257 ms/op 1.01
compositeListValue.readonlyValuesArray() + loop all 26.732 ms/op 28.781 ms/op 0.93
Number64UintType - get balances list 4.1648 ms/op 4.6154 ms/op 0.90
Number64UintType - set balances list 8.7610 ms/op 9.7880 ms/op 0.90
Number64UintType - get and increase 10 then set 38.289 ms/op 38.538 ms/op 0.99
Number64UintType - increase 10 using applyDelta 14.422 ms/op 16.731 ms/op 0.86
Number64UintType - increase 10 using applyDeltaInBatch 14.229 ms/op 16.269 ms/op 0.87
tree_newTreeFromUint64Deltas 16.407 ms/op 17.213 ms/op 0.95
unsafeUint8ArrayToTree 30.116 ms/op 31.231 ms/op 0.96
bitLength(50) 226.00 ns/op 233.00 ns/op 0.97
bitLengthStr(50) 216.00 ns/op 217.00 ns/op 1.00
bitLength(8000) 219.00 ns/op 227.00 ns/op 0.96
bitLengthStr(8000) 257.00 ns/op 267.00 ns/op 0.96
bitLength(250000) 218.00 ns/op 228.00 ns/op 0.96
bitLengthStr(250000) 294.00 ns/op 301.00 ns/op 0.98
floor - Math.floor (53) 1.2375 ns/op 1.2385 ns/op 1.00
floor - << 0 (53) 1.2378 ns/op 1.2380 ns/op 1.00
floor - Math.floor (512) 1.2374 ns/op 1.2478 ns/op 0.99
floor - << 0 (512) 1.2443 ns/op 1.2374 ns/op 1.01
fnIf(0) 1.5535 ns/op 1.5457 ns/op 1.01
fnSwitch(0) 2.1643 ns/op 2.1699 ns/op 1.00
fnObj(0) 1.5497 ns/op 1.5492 ns/op 1.00
fnArr(0) 1.5453 ns/op 1.5463 ns/op 1.00
fnIf(4) 2.1650 ns/op 2.1650 ns/op 1.00
fnSwitch(4) 2.1637 ns/op 2.1637 ns/op 1.00
fnObj(4) 1.5509 ns/op 1.5530 ns/op 1.00
fnArr(4) 1.5453 ns/op 1.5476 ns/op 1.00
fnIf(9) 3.0911 ns/op 3.0923 ns/op 1.00
fnSwitch(9) 2.1654 ns/op 2.1645 ns/op 1.00
fnObj(9) 1.5468 ns/op 1.5496 ns/op 1.00
fnArr(9) 1.5461 ns/op 1.5521 ns/op 1.00
Container {a,b,vec} - as struct x100000 123.80 us/op 124.01 us/op 1.00
Container {a,b,vec} - as tree x100000 340.31 us/op 340.82 us/op 1.00
Container {a,vec,b} - as struct x100000 155.36 us/op 155.04 us/op 1.00
Container {a,vec,b} - as tree x100000 371.20 us/op 371.57 us/op 1.00
get 2 props x1000000 - rawObject 309.62 us/op 310.24 us/op 1.00
get 2 props x1000000 - proxy 72.709 ms/op 72.781 ms/op 1.00
get 2 props x1000000 - customObj 309.52 us/op 309.17 us/op 1.00
Simple object binary -> struct 549.00 ns/op 565.00 ns/op 0.97
Simple object binary -> tree_backed 970.00 ns/op 1.0470 us/op 0.93
Simple object struct -> tree_backed 1.4740 us/op 1.6310 us/op 0.90
Simple object tree_backed -> struct 1.4480 us/op 1.5940 us/op 0.91
Simple object struct -> binary 776.00 ns/op 850.00 ns/op 0.91
Simple object tree_backed -> binary 1.2390 us/op 1.3320 us/op 0.93
aggregationBits binary -> struct 430.00 ns/op 470.00 ns/op 0.91
aggregationBits binary -> tree_backed 1.9530 us/op 2.0660 us/op 0.95
aggregationBits struct -> tree_backed 2.3320 us/op 2.4270 us/op 0.96
aggregationBits tree_backed -> struct 950.00 ns/op 1.0350 us/op 0.92
aggregationBits struct -> binary 639.00 ns/op 747.00 ns/op 0.86
aggregationBits tree_backed -> binary 849.00 ns/op 952.00 ns/op 0.89
List(uint8) 100000 binary -> struct 1.3144 ms/op 1.1825 ms/op 1.11
List(uint8) 100000 binary -> tree_backed 85.162 us/op 86.720 us/op 0.98
List(uint8) 100000 struct -> tree_backed 1.1089 ms/op 1.1340 ms/op 0.98
List(uint8) 100000 tree_backed -> struct 974.90 us/op 1.0001 ms/op 0.97
List(uint8) 100000 struct -> binary 1.0031 ms/op 987.80 us/op 1.02
List(uint8) 100000 tree_backed -> binary 87.050 us/op 90.795 us/op 0.96
List(uint64Number) 100000 binary -> struct 1.1361 ms/op 1.2471 ms/op 0.91
List(uint64Number) 100000 binary -> tree_backed 2.9756 ms/op 3.3607 ms/op 0.89
List(uint64Number) 100000 struct -> tree_backed 4.4332 ms/op 4.7563 ms/op 0.93
List(uint64Number) 100000 tree_backed -> struct 2.1138 ms/op 2.2367 ms/op 0.95
List(uint64Number) 100000 struct -> binary 1.3393 ms/op 1.5556 ms/op 0.86
List(uint64Number) 100000 tree_backed -> binary 856.95 us/op 869.93 us/op 0.99
List(Uint64Bigint) 100000 binary -> struct 3.5642 ms/op 3.5944 ms/op 0.99
List(Uint64Bigint) 100000 binary -> tree_backed 2.8520 ms/op 3.3181 ms/op 0.86
List(Uint64Bigint) 100000 struct -> tree_backed 5.2606 ms/op 5.4001 ms/op 0.97
List(Uint64Bigint) 100000 tree_backed -> struct 4.3945 ms/op 4.8992 ms/op 0.90
List(Uint64Bigint) 100000 struct -> binary 2.0361 ms/op 2.0607 ms/op 0.99
List(Uint64Bigint) 100000 tree_backed -> binary 895.91 us/op 1.3819 ms/op 0.65
Vector(Root) 100000 binary -> struct 27.668 ms/op 30.789 ms/op 0.90
Vector(Root) 100000 binary -> tree_backed 32.244 ms/op 32.594 ms/op 0.99
Vector(Root) 100000 struct -> tree_backed 36.297 ms/op 35.251 ms/op 1.03
Vector(Root) 100000 tree_backed -> struct 42.847 ms/op 43.491 ms/op 0.99
Vector(Root) 100000 struct -> binary 2.5251 ms/op 2.6369 ms/op 0.96
Vector(Root) 100000 tree_backed -> binary 8.6505 ms/op 10.085 ms/op 0.86
List(Validator) 100000 binary -> struct 102.03 ms/op 94.057 ms/op 1.08
List(Validator) 100000 binary -> tree_backed 276.94 ms/op 291.23 ms/op 0.95
List(Validator) 100000 struct -> tree_backed 294.91 ms/op 302.31 ms/op 0.98
List(Validator) 100000 tree_backed -> struct 189.27 ms/op 197.29 ms/op 0.96
List(Validator) 100000 struct -> binary 27.131 ms/op 26.666 ms/op 1.02
List(Validator) 100000 tree_backed -> binary 100.05 ms/op 102.67 ms/op 0.97
List(Validator-NS) 100000 binary -> struct 98.779 ms/op 105.55 ms/op 0.94
List(Validator-NS) 100000 binary -> tree_backed 132.30 ms/op 144.09 ms/op 0.92
List(Validator-NS) 100000 struct -> tree_backed 167.95 ms/op 172.04 ms/op 0.98
List(Validator-NS) 100000 tree_backed -> struct 145.94 ms/op 149.45 ms/op 0.98
List(Validator-NS) 100000 struct -> binary 26.774 ms/op 26.850 ms/op 1.00
List(Validator-NS) 100000 tree_backed -> binary 31.925 ms/op 31.772 ms/op 1.00
get epochStatuses - MutableVector 111.50 us/op 91.125 us/op 1.22
get epochStatuses - ViewDU 201.90 us/op 203.25 us/op 0.99
set epochStatuses - ListTreeView 1.5835 ms/op 1.4927 ms/op 1.06
set epochStatuses - ListTreeView - set() 442.11 us/op 432.51 us/op 1.02
set epochStatuses - ListTreeView - commit() 583.97 us/op 520.98 us/op 1.12
bitstring 644.80 ns/op 636.31 ns/op 1.01
bit mask 13.821 ns/op 13.900 ns/op 0.99
struct - increase slot to 1000000 928.08 us/op 928.09 us/op 1.00
UintNumberType - increase slot to 1000000 23.279 ms/op 23.525 ms/op 0.99
UintBigintType - increase slot to 1000000 174.09 ms/op 155.34 ms/op 1.12
UintBigint8 x 100000 tree_deserialize 4.3568 ms/op 4.7437 ms/op 0.92
UintBigint8 x 100000 tree_serialize 1.1053 ms/op 1.1149 ms/op 0.99
UintBigint16 x 100000 tree_deserialize 4.4685 ms/op 4.8136 ms/op 0.93
UintBigint16 x 100000 tree_serialize 1.1151 ms/op 1.1636 ms/op 0.96
UintBigint32 x 100000 tree_deserialize 4.4303 ms/op 5.0074 ms/op 0.88
UintBigint32 x 100000 tree_serialize 1.1245 ms/op 1.1815 ms/op 0.95
UintBigint64 x 100000 tree_deserialize 5.1008 ms/op 5.2460 ms/op 0.97
UintBigint64 x 100000 tree_serialize 1.4905 ms/op 1.5897 ms/op 0.94
UintBigint8 x 100000 value_deserialize 433.32 us/op 433.00 us/op 1.00
UintBigint8 x 100000 value_serialize 564.62 us/op 595.68 us/op 0.95
UintBigint16 x 100000 value_deserialize 464.01 us/op 468.20 us/op 0.99
UintBigint16 x 100000 value_serialize 628.58 us/op 661.48 us/op 0.95
UintBigint32 x 100000 value_deserialize 433.23 us/op 433.32 us/op 1.00
UintBigint32 x 100000 value_serialize 599.03 us/op 630.69 us/op 0.95
UintBigint64 x 100000 value_deserialize 496.21 us/op 498.13 us/op 1.00
UintBigint64 x 100000 value_serialize 773.83 us/op 833.07 us/op 0.93
UintBigint8 x 100000 deserialize 2.8692 ms/op 3.0272 ms/op 0.95
UintBigint8 x 100000 serialize 1.4726 ms/op 1.4133 ms/op 1.04
UintBigint16 x 100000 deserialize 2.8684 ms/op 3.1150 ms/op 0.92
UintBigint16 x 100000 serialize 1.5199 ms/op 1.4402 ms/op 1.06
UintBigint32 x 100000 deserialize 2.9502 ms/op 3.2150 ms/op 0.92
UintBigint32 x 100000 serialize 2.7463 ms/op 2.7030 ms/op 1.02
UintBigint64 x 100000 deserialize 3.6258 ms/op 3.6790 ms/op 0.99
UintBigint64 x 100000 serialize 1.5020 ms/op 1.5052 ms/op 1.00
UintBigint128 x 100000 deserialize 5.2305 ms/op 5.2996 ms/op 0.99
UintBigint128 x 100000 serialize 14.968 ms/op 15.174 ms/op 0.99
UintBigint256 x 100000 deserialize 7.7997 ms/op 8.0697 ms/op 0.97
UintBigint256 x 100000 serialize 44.378 ms/op 45.420 ms/op 0.98
Slice from Uint8Array x25000 1.1250 ms/op 1.1276 ms/op 1.00
Slice from ArrayBuffer x25000 15.358 ms/op 16.514 ms/op 0.93
Slice from ArrayBuffer x25000 + new Uint8Array 15.567 ms/op 17.645 ms/op 0.88
Copy Uint8Array 100000 iterate 1.6589 ms/op 1.8561 ms/op 0.89
Copy Uint8Array 100000 slice 118.60 us/op 177.74 us/op 0.67
Copy Uint8Array 100000 Uint8Array.prototype.slice.call 114.85 us/op 164.50 us/op 0.70
Copy Buffer 100000 Uint8Array.prototype.slice.call 114.81 us/op 173.89 us/op 0.66
Copy Uint8Array 100000 slice + set 177.27 us/op 315.78 us/op 0.56
Copy Uint8Array 100000 subarray + set 118.31 us/op 168.51 us/op 0.70
Copy Uint8Array 100000 slice arrayBuffer 118.76 us/op 175.35 us/op 0.68
Uint64 deserialize 100000 - iterate Uint8Array 1.7610 ms/op 1.8257 ms/op 0.96
Uint64 deserialize 100000 - by Uint32A 1.7580 ms/op 1.7573 ms/op 1.00
Uint64 deserialize 100000 - by DataView.getUint32 x2 1.7249 ms/op 1.7824 ms/op 0.97
Uint64 deserialize 100000 - by DataView.getBigUint64 4.7682 ms/op 4.9919 ms/op 0.96
Uint64 deserialize 100000 - by byte 40.175 ms/op 39.996 ms/op 1.00

by benchmarkbot/action

@twoeths twoeths marked this pull request as ready for review July 23, 2024 08:55
@twoeths twoeths requested a review from a team as a code owner July 23, 2024 08:55
@g11tech
Copy link
Contributor

g11tech commented Jul 24, 2024

when it grows it only need to add one more list items, instead of allocating a whole new array to reuse and save memory

this is where it optimizes memory?

@wemeetagain wemeetagain merged commit e2c8329 into master Aug 6, 2024
8 checks passed
@wemeetagain wemeetagain deleted the te/hash_computation_level branch August 6, 2024 20:32
@wemeetagain wemeetagain mentioned this pull request Aug 6, 2024
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@wemeetagain wemeetagain wemeetagain approved these changes

@g11tech g11tech Awaiting requested review from g11tech

Assignees
No one assigned
Labels
persistent-merkle-tree
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@twoeths @g11tech @wemeetagain