3 ms·

At some point, hashes are fast enough. I'm not going to be switching from xxhash to shave 40 picoseconds off of hashing small keys, and for large keys it's alr

At some point, hashes are fast enough. I'm not going to be switching from xxhash to shave 40 picoseconds off of hashing small keys, and for large keys it's already a few orders of magnitude faster than my NVMe drive.

neonsunset 1y ago
If whatever you are doing is heavy on hashmap lookups (and you are ok with not rewriting into something more bespoke+complicated) - the faster hash function and the cheaper baseline cost of calling it - the better (i.e. XXH3 can have disadvantages, with its popular impl. for dispatching to the necessary routine). This looks like an interesting potential alternative to GxHash. GxHash is nice but sadly I found AES intrinsics to have somewhat high latency on AMD's Zen 2/3 cores, making it a loss on short strings (but until I measured it on our server hw, M4 Max sure had me fooled, it has way better latency despite retiring more AES operations!).
- xkcd1963 1y ago
  Question, what do you do if there is a collision? I saw the github table also mentioned collisions
  - lights0123 1y ago
    They're extremely common in hashtables. You follow standard open addressing or separate chaining procedures: https://en.m.wikipedia.org/wiki/Hash_collision https://en.m.wikipedia.org/wiki/Hash_collision
    - LoganDark 1y ago
      Non-mobile link: https://en.wikipedia.org/wiki/Hash_collision https://en.wikipedia.org/wiki/Hash_collision
      - Xorakios 1y ago
        Do people still use mobile devices? I thought that was like original star trek?
        LoganDark 1y ago
        I don't know, all I know is that in my experience some HN commenters don't remove the `.m` from their Wikipedia links. Probably because that's inconvenient to do on mobile devices.
  - saagarjha 1y ago
    Fall back on secondary hashes or do probing
  - meindnoch 1y ago
    Open any data structures textbook and look for "hash map" in the table of contents.
jandrewrogers 1y ago
Quality matters. XXH3 fails something like 15% of the tests in SMHasher3. There are faster hash functions with much better quality profiles.
- leumassuehtam 1y ago
  Since you've mentioned, which hash functions are better while being faster than XXH3?
  - shpx 1y ago
    There aren't any hashes passing all tests that are faster than XXH3 for both short (1-32 byte) inputs and overall throughput from my reading of https://gitlab.com/fwojcik/smhasher3/-/tree/main/results#passing-hashes https://gitlab.com/fwojcik/smhasher3/-/tree/main/results#pas... . MeowHash, t1ha0.aesB, falkhash2 and falkhash1 have higher throughput and fail less tests, but they're slower on short inputs. wyhash is about the same on short inputs and fails less tests, but has half the throughput.
  - jandrewrogers 1y ago
    The list of non-cryptographic hash functions that aren’t currently known to be broken for general purpose hashing is pretty short. There are three dimensions to performance: latency, throughput, and microarchitecture. Algorithm designs explicitly tradeoff older microarchitecture performance for newer microarchitecture performance, depending on if the objective of portability is compatibility or consistency. For latency-optimized hashing, rapidhash is currently the fastest algorithm I know of with consistently good hash quality. Hash quality is outside the cryptographic range, which is expected for a latency-optimized design, but close enough that you can at least make a comparison. Should be pretty portable too. It is what I recommend for general-purpose small-key hashing. For throughput-optimized hashing, rotohash[0] is currently the fastest algorithm I know of, with single-core throughput saturating CPU cache bandwidth. Hash quality is at the low-end of the cryptographic range, about the same as MD5. While it is built on portable 32-bit primitives, it clearly targets modern microarchitectures — the Zen 5 performance metrics, though not listed, are crazy. This is brand new, part of a research project to efficiently and robustly checksum I/O at current hardware line rates (100s of GB/s). Any algorithm can be faster if you completely disregard quality. In fairness, the quality bar has risen quickly as we’ve become better at designing these algorithms and finding the defects. State-of-the-art algorithms a decade ago are all considered obviously and hopelessly broken today. Designing a competitive hash function now requires an extremely high degree of skill and expertise. It was much easier to come into it as a hobbyist and produce an acceptable result ten years ago. [0] https://github.com/jandrewrogers/RotoHash https://github.com/jandrewrogers/RotoHash
steeve 1y ago
No, just because you’re hashing every ms doesn’t mean we all do.

neonsunset 1y ago

If whatever you are doing is heavy on hashmap lookups (and you are ok with not rewriting into something more bespoke+complicated) - the faster hash function and the cheaper baseline cost of calling it - the better (i.e. XXH3 can have disadvantages, with its popular impl. for dispatching to the necessary routine). This looks like an interesting potential alternative to GxHash. GxHash is nice but sadly I found AES intrinsics to have somewhat high latency on AMD's Zen 2/3 cores, making it a loss on short strings (but until I measured it on our server hw, M4 Max sure had me fooled, it has way better latency despite retiring more AES operations!).

xkcd1963 1y ago
Question, what do you do if there is a collision? I saw the github table also mentioned collisions
- lights0123 1y ago
  They're extremely common in hashtables. You follow standard open addressing or separate chaining procedures: https://en.m.wikipedia.org/wiki/Hash_collision https://en.m.wikipedia.org/wiki/Hash_collision
  - LoganDark 1y ago
    Non-mobile link: https://en.wikipedia.org/wiki/Hash_collision https://en.wikipedia.org/wiki/Hash_collision
    - Xorakios 1y ago
      Do people still use mobile devices? I thought that was like original star trek?
      - LoganDark 1y ago
        I don't know, all I know is that in my experience some HN commenters don't remove the `.m` from their Wikipedia links. Probably because that's inconvenient to do on mobile devices.
- saagarjha 1y ago
  Fall back on secondary hashes or do probing
- meindnoch 1y ago
  Open any data structures textbook and look for "hash map" in the table of contents.

jandrewrogers 1y ago

Quality matters. XXH3 fails something like 15% of the tests in SMHasher3. There are faster hash functions with much better quality profiles.

leumassuehtam 1y ago
Since you've mentioned, which hash functions are better while being faster than XXH3?
- shpx 1y ago
  There aren't any hashes passing all tests that are faster than XXH3 for both short (1-32 byte) inputs and overall throughput from my reading of https://gitlab.com/fwojcik/smhasher3/-/tree/main/results#passing-hashes https://gitlab.com/fwojcik/smhasher3/-/tree/main/results#pas... . MeowHash, t1ha0.aesB, falkhash2 and falkhash1 have higher throughput and fail less tests, but they're slower on short inputs. wyhash is about the same on short inputs and fails less tests, but has half the throughput.
- jandrewrogers 1y ago
  The list of non-cryptographic hash functions that aren’t currently known to be broken for general purpose hashing is pretty short. There are three dimensions to performance: latency, throughput, and microarchitecture. Algorithm designs explicitly tradeoff older microarchitecture performance for newer microarchitecture performance, depending on if the objective of portability is compatibility or consistency. For latency-optimized hashing, rapidhash is currently the fastest algorithm I know of with consistently good hash quality. Hash quality is outside the cryptographic range, which is expected for a latency-optimized design, but close enough that you can at least make a comparison. Should be pretty portable too. It is what I recommend for general-purpose small-key hashing. For throughput-optimized hashing, rotohash[0] is currently the fastest algorithm I know of, with single-core throughput saturating CPU cache bandwidth. Hash quality is at the low-end of the cryptographic range, about the same as MD5. While it is built on portable 32-bit primitives, it clearly targets modern microarchitectures — the Zen 5 performance metrics, though not listed, are crazy. This is brand new, part of a research project to efficiently and robustly checksum I/O at current hardware line rates (100s of GB/s). Any algorithm can be faster if you completely disregard quality. In fairness, the quality bar has risen quickly as we’ve become better at designing these algorithms and finding the defects. State-of-the-art algorithms a decade ago are all considered obviously and hopelessly broken today. Designing a competitive hash function now requires an extremely high degree of skill and expertise. It was much easier to come into it as a hobbyist and produce an acceptable result ten years ago. [0] https://github.com/jandrewrogers/RotoHash https://github.com/jandrewrogers/RotoHash

steeve 1y ago

No, just because you’re hashing every ms doesn’t mean we all do.