onflow / atree

Atree provides scalable arrays and scalable ordered maps.
https://onflow.org
Apache License 2.0
39 stars 16 forks source link

Update to latest version of CircleHash64 for faster speed #243

Closed fxamacker closed 2 years ago

fxamacker commented 2 years ago

Issue To Be Solved

I optimized fxamacker/circlehash over the weekend. Optimizations are fully backward compatible and speedup short input sizes, especially on Go 1.17 or newer.

Suggested Solution

Update to optimized CircleHash64.

Add the following table to README with explanation of hash algorithm choices.

Atree uses CircleHash64 with deferred+segmented BLAKE3 for collisions

Atree uses CircleHash64 because hash inputs are currently very small (usually < 64 bytes).

CircleHash64 🏅
(seeded)
SipHash
(seeded)
BLAKE3 🏅
(crypto)
SHA3-256
(crypto)
4 bytes 1.34 GB/s 0.361 GB/s 0.027 GB/s 0.00491 GB/s
8 bytes 2.70 GB/s 0.642 GB/s 0.106 GB/s 0.00984 GB/s
16 bytes 5.48 GB/s 1.03 GB/s 0.217 GB/s 0.0197 GB/s
32 bytes 8.01 GB/s 1.46 GB/s 0.462 GB/s 0.0399 GB/s
64 bytes 10.3 GB/s 1.83 GB/s 0.911 GB/s 0.0812 GB/s
128 bytes 12.8 GB/s 2.09 GB/s 1.03 GB/s 0.172 GB/s
192 bytes 14.2 GB/s 2.17 GB/s 1.04 GB/s 0.158 GB/s
256 bytes 15.0 GB/s 2.22 GB/s 1.06 GB/s 0.219 GB/s
fxamacker commented 2 years ago

Also maybe add minor tweak to Atree icon (make trees green instead of black, calmer waves) since README is being updated.

atree_icon_v20220228