Feedback: Speed/Collision Benchmark - Gumbotron vs XXH3 #568
Labels
No labels
announcement
bug
build
CI
dependencies
documentation
duplicate
enhancement
experience feedback
feature request
github_actions
help wanted
install
invalid
Long-term
optimization
portability
question
target-specific
test issue
wontfix
No milestone
No assignees
1 participant
Notifications
Due date
No due date set.
Dependencies
No dependencies set
Reference
gh-Cyan4973/xxHash#568
Loading…
Reference in a new issue
No description provided.
Delete branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Enter Gumbotron (a.k.a. DoubleDeuceAES_128bits) ...
My not-so-thorough runs below show that the fastest 128bit hasher is XXH3_128bits, known to me, yet:
In my view, my Gumbotron is faster, when:
Imagine the usecase where 1 terakeys are enforced (trillion, yes). And those keys are 64 bytes or 128 bytes or 256 bytes long, and they have to be put into leaves of Bayer-Trees, the size becomes nasty unless they are "compressed", for instance 1Terakeys x 64 bytes = 64TB, but compressed only 16TB. Therefore, I wrote Gumbotron.
The need for speed and "lossy compression" (i.e. shrinking keys) led me to putting a lookupper and a shrinker under one hood, namely the 128bit hasher DoubleDeuceAES_128bits.
There is no principal distinction between a lookupper and a shrinker, they both are hashers, but the latter serves as a checksum whereas the former as a hashtable.
The benchmark package (allowing to reproduce all the stuff) is freely downloadable with all the sources and binaries:
www.sanmayce.com/Lookupperorama_r11.zip
www.sanmayce.com/Gumbotron_logo.pdf
The benchmark is of two parts:
As a quick test I chose randomly two testfiles - Cihai and Judaica.
Testfile: KAZE_(Dictionary_Specification_Language_(ABBYY_Software_House))Hanyu_Cihai_new_Sea-of-Words(Zho-Zho).dsl (42,920,232 bytes)
Testmachine: Testmachine: laptop 'Brutalitto' AMD 4800H max turbo 4.3GHz, 64GB DDR4 3200MHz, Windows 10
Hashtable: 26bit, i.e. 67,108,864 slots, greater than (42,920,232 bytes), since in case of perfect hasher - slots should be more than the keys (could be all unique) at each position
Note1: The second column houses the cumulative value for all collisions, the collisions for all orders 4..64 were summed, that is.
Note2: Folding of those 128bits should lessen the collisions.
Testfile: TERAPIG_Encyclopaedia_Judaica_(in_22_volumes)_TXT.tar (107,784,192 bytes)
Testmachine: Testmachine: laptop 'Brutalitto' AMD 4800H max turbo 4.3GHz, 64GB DDR4 3200MHz, Windows 10
Hashtable: 27bit, i.e. 134,217,728 slots, greater than (107,784,192 bytes), since in case of perfect hasher - slots should be more than the keys (could be all unique) at each position
Another twist, in order to test collisions, here comes my 1 trillion 128bytes long keys testbed, since no enough memory is available, it was run as 1 billion.
Testset: "A billion Knight-Tours variants (each KT with 256 variants, the KT itself omitted) - each 128 bytes long"
Testfile: 1000000000.KnightTours.txt (130,000,000,000 bytes)
The name of the game - hashing all lines and taking either 5 bytes or 6,7,8 bytes from the hash.
This is how the console looks like:
Note: The first column houses how many occurrences of the following hash are there.
TO-DO: Wish running it with 1,000,000,000,000 (did it already, but in other game) keys - could help evaluating how badly a 128bit hash results in collision(s)...
And finally the function itself:
https://godbolt.org/z/1o38b4W1K
// gcc 10.1 -O3 -mavx -maes
// icc 19.0.0 -O3 -mavx
Hope, someone will improve on it and share.
Let us see who is the fastest 128bit hasher (for 128 bytes long keys, in particular) ...
The package (all sources included) allowing to reproduce all the runs is freely downloadable at:
www.sanmayce.com/Gumbotron_vs_XXH128.zip
The 200M keys were chosen in order to fit into 32GB machines, something like 25GB needed.
On laptop 'Compressionette' (Kaby Lake i5-7200U 2.5GHz (3.1GHz max turbo) 36GB DDR4 2133MHz, Windows 10) Gumbotron_YMM hashes 4,487/3,160= 1.41x faster than XXH128:
On laptop 'Brutalitto' (Renoir AMD 4800H max turbo 4.3GHz, 64GB DDR4 3200MHz, Windows 10) Gumbotron_YMM hashes 3,266/2,484= 1.31x faster than XXH128:
The actual (used in the benchmark) AVX code is given below (the main loop i.e. the handler of multiples of 64bytes is 1ab-096+6=283 bytes long, in 45 instructions):
To me, above fragment is the fastest when comes to short keys (maybe up to 512 bytes) and multiples of 64 bytes, isn't it?
Okay, the AVX2 mainloop (the handler of multiples of 64 bytes) code is only 40 instructions (icc 19.0.0 -O3 -mavx2), should be the fastest:
https://godbolt.org/z/oaW3zGcv5
Didn't have time to benchmark the AVX2, currently don't see how to speed it up more...