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.
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
Unexpected low speeds with the generic C?! #102
Comments
Hi @Sanmayce, sorry to reply late. Thanks for adding HighwayHash!
Yes, this is plausible. All 'reasonable' hashes can mix sufficiently to avoid collisions for non-adversarial input.
The large difference in performance between C and C++ is because the C version does not use SIMD instructions.
Ah, that would be very interesting to see studied in more detail. Bob Jenkins had a very thorough test program which filled memory with a hash table. |
It took ~240hours (on 8 cores CPU) to complete Bob Jenkins' Froggy with Gumbotron_YMM, no collisions reported.
In my view keys 1..63 long are problematic, someone can do better, yet, for now Gumbotron_YMM serves well. |
Hi Jan and Jyrki,
just included HighwayHash128 into my C program benchmarking several hashers, the problem I encountered is the very slow speed, the collisions are okay, though. Is this to be expected, considering you wrote far more stronger hasher than the non-crypto ones?!
My yesterday hashers showdown Cyan4973/xxHash#568 lacked HighwayHash, so I tried to enrich the experience.
Excuse my amateurism, but I couldn't see how to integrate your optimized CC functions, I use only C.
Roughly, HighwayHash128 (generic) works 6,336,146/153,854= 41x faster than SHA3-224, in a real scenario, with small keys.
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
The part I use is from https://github.com/google/highwayhash/tree/master/c
Similarly to the other hashers, I just use the preprocessor to include only the targeted hash, in this case these are the additions (one of four) I made:
The slowness appears with Intel v15.0 64bit and GCC 10.1 64bit compilers, options used are:
The whole package (with compiles/binaries and sources) is here:
www.sanmayce.com/Lookupperorama_r12.7z
Also, please share some thoughts on how you see collision benchmarking done right, my best shot is to run 1 trillion Knight-Tours derivatives and count the collisions within the generated 8,9 up to 16 bytes of the 128bits, however several hundred terabytes are needed, grmbl.
The text was updated successfully, but these errors were encountered: