6 ms·

New high-quality hash measures 71GB/s on M4

148 points by nicoshev11 1y ago

deleted 1y ago
[deleted]
wpollock 1y ago
Is rapidhash cache-friendly?
- wmf 1y ago
  Hash functions don't have any data reuse so none of them are cache-friendly.
  - benwills 1y ago
    I think they may be asking about the CPU cache.
    - Dylan16807 1y ago
      You have to go out of your way to make a hash that doesn't fit into L1, so again they're all basically the same. You'll probably end up fitting entirely inside the reorder buffer plus a sequential stream from memory, with the actual caches almost irrelevant.
      - benwills 1y ago
        Sure. Any worthwhile hash function will fit in the instruction cache. But there are ways to make more or less efficient use of the data cache.
        Dylan16807 1y ago
        > Any worthwhile hash function will fit in the instruction cache. Yes, I'm talking about the data cache. > But there are ways to make more or less efficient use of the data cache. How? You need to touch every byte of input, and nothing should be faster than going right through from start to end.
        benwills 1y ago
        I don't know you're experience with hash functions, so you may already know what I'm about to say. This is a minor example, but since you asked... https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L6432 https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L6432 That's an example of a fair number of accumulators that are stored as XXHash goes through its input buffer. Many modern hash functions store more state/accumulators than they used to. Previous generations of hash functions would often just have one or two accumulators and run through the data. Many modern hash functions might even store multiple wider SIMD variables for better mixing. And if you're storing enough state that it doesn't fit in your registers, the CPU will put it into the data cache.
        Dylan16807 1y ago
        > And if you're storing enough state that it doesn't fit in your registers, the CPU will put it into the data cache. And there's 150+ registers in the actual chip. But my argument is more that there isn't really an efficient or inefficient way to use L1. So unless you have an enormous amount of state, the question is moot. And if you have so much state you're spilling to L2, that's not when you worry about good or bad cache use, that's a weird bloat problem.
        Sesse__ 1y ago
        _Fitting_ in the instruction cache isn't hard, but you'd also ideally let there be room for some other code as well :-) For a hash map lookup, where the hashing is frequently inlined a couple of times, code size matters.
  - Retr0id 1y ago
    You can have cache-unfriendly hash functions, though. For example, a common optimisation for CRC implementation involves lookup tables. If your lookup table exceeds L1 then you're going to have a bad time. If your lookup table fits exactly in L1, your benchmarks might look great, while real-world performance suffers (because your other code wants to be making use of L1, too). I'd imagine rapidhash avoids lookup tables but the question of cache-friendliness is still pertinent.
aidenn0 1y ago
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?
rurban 1y ago
It's not the fastest on smhasher anymore. umash is better and faster, and gxhash is twice as fast. It's is however very hashmap friendly because of its small size. It's a wyhash variant
- nicoshev11 1y ago
  Hey Reini, the rapidhash version on the SMHasher repo is outdated. The latest version was published last Tuesday, I'll submit it to SMHasher shortly. This new version is much faster than the previous one, and still passes all tests. It should beat umash on your benchmarks.
  - Sesse__ 1y ago
    Am I right in that RAPIDHASH_UNROLLED is now mandatory and the function is thus much larger now?
curiouscoding 1y ago
I'd love to see some benchmarks/comparison on variable length strings. For strings with random length between 10 and 30, gxhash was significantly faster than xxhash for me. I would assume because it processes chunks of up to 32 chars at a time, avoiding branch misses. Generally my feeling is that at these speeds, designing for branch-predictability for short strings might be more important than absolute throughput.
bandrami 1y ago
I saw the first four words and then was disappointed by the direction it took...
- coolcase 1y ago
  Or first 2 words
- deleted 1y ago
  [deleted]
jandrewrogers 1y ago
Without getting too deep in the technical weeds, I will assert that rapidhash is an excellent small-key hash function and approximately the state-of-the-art for that purpose. There is nothing else better that I am aware of in this scope. For bulk hashing there are better functions, but XXH3, GXHash, etc are not among them, being both slower and weaker than the state-of-the-art. Hash functions that can’t pass quality tests are not serious contenders.
- kragen 1y ago
  I feel like I'm missing an enormous amount of context here, and I can't be the only one. How much better is it than old standbys like hashpjw, FNV1A, or djb's favorite¹, and how? It's apparently 350 lines of code instead of 1–10 lines of code. That seems like an important way that it's worse. And it comes with a copyright license that requires you to add it to your documentation, so the risk of forgetting that creates a risk of copyright infringement. So, how big is the benefit? How much faster is it hashing a small key like the string "__umulh"? Is it actually slower? (For those needing an introduction to hash tables, covering why that question makes sense, Chris Wellons is always excellent: https://nullprogram.com/blog/2025/01/19/ https://nullprogram.com/blog/2025/01/19/) Why does it have an array commented "default secret parameters" in the public GitHub repo? Are we supposed to change those? Do they provide some kind of security, and if so, what kind, against what threat model? The readme and https://scholar.google.com/scholar?hl=es&as_sdt=0%2C5&q=rapidhash+carli&btnG= https://scholar.google.com/scholar?hl=es&as_sdt=0%2C5&q=rapi... are no help here. https://github.com/rurban/smhasher?tab=readme-ov-file#summary https://github.com/rurban/smhasher?tab=readme-ov-file#summar... explains some of the questions at greater length but of course not rapidhash's particular answers. ______ ¹ while (s[i]) h = h * 33 + s[i++]; about 11 machine-code instructions in its full-fledged form: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:26,endLineNumber:4,positionColumn:26,positionLineNumber:4,selectionStartColumn:26,selectionStartLineNumber:4,startColumn:26,startLineNumber:4),source:'//+Type+your+code+here,+or+load+an+example.%0Aunsigned+hash17903(char+*s)+%7B%0A+unsigned+h+%3D+5381,+i+%3D+0%3B%0A+while+(s%5Bi%5D)+h+%3D+h+*+33+%2B+s%5Bi%2B%2B%5D%3B%0A+return+h%3B%0A%7D'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:g151,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-Os',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+15.1+(Editor+%231)',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:output,i:(compilerName:'x86-64+gcc+15.1',editorid:1,fontScale:14,fontUsePx:'0',j:1,wrap:'1'),l:'5',n:'0',o:'Output+of+x86-64+gcc+15.1+(Compiler+%231)',t:'0')),header:(),k:50,l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:50,l:'3',n:'0',o:'',t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename...
realo 1y ago
At a few ns per hash, it means the hash is done before photons from your screen reach your eyes. Impressive!
- CyberDildonics 1y ago
  There is a big difference between throughput and latency. If you do 8 at once with SIMD it doesn't mean you can get a single one done in 1/8th the time.
eqvinox 1y ago
Why are the numbers in the "performance" section almost all for AArch64? Where are the AMD64 numbers?
mertleee 1y ago
What's the actual application for this?
RainyDayTmrw 1y ago
Is this safe to use in public facing web servers? (Can adversaries trigger hash-DoS[1]?) [1]: https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding
zitoune 1y ago
"The fastest hash function passing all tests in SMHasher." GxHash is twice as fast and passes all SMHasher tests...

148 points by nicoshev11 1y ago

deleted 1y ago

[deleted]

wpollock 1y ago

Is rapidhash cache-friendly?

wmf 1y ago
Hash functions don't have any data reuse so none of them are cache-friendly.
- benwills 1y ago
  I think they may be asking about the CPU cache.
  - Dylan16807 1y ago
    You have to go out of your way to make a hash that doesn't fit into L1, so again they're all basically the same. You'll probably end up fitting entirely inside the reorder buffer plus a sequential stream from memory, with the actual caches almost irrelevant.
    - benwills 1y ago
      Sure. Any worthwhile hash function will fit in the instruction cache. But there are ways to make more or less efficient use of the data cache.
      - Dylan16807 1y ago
        > Any worthwhile hash function will fit in the instruction cache. Yes, I'm talking about the data cache. > But there are ways to make more or less efficient use of the data cache. How? You need to touch every byte of input, and nothing should be faster than going right through from start to end.
        benwills 1y ago
        I don't know you're experience with hash functions, so you may already know what I'm about to say. This is a minor example, but since you asked... https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L6432 https://github.com/Cyan4973/xxHash/blob/dev/xxhash.h#L6432 That's an example of a fair number of accumulators that are stored as XXHash goes through its input buffer. Many modern hash functions store more state/accumulators than they used to. Previous generations of hash functions would often just have one or two accumulators and run through the data. Many modern hash functions might even store multiple wider SIMD variables for better mixing. And if you're storing enough state that it doesn't fit in your registers, the CPU will put it into the data cache.
        Dylan16807 1y ago
        > And if you're storing enough state that it doesn't fit in your registers, the CPU will put it into the data cache. And there's 150+ registers in the actual chip. But my argument is more that there isn't really an efficient or inefficient way to use L1. So unless you have an enormous amount of state, the question is moot. And if you have so much state you're spilling to L2, that's not when you worry about good or bad cache use, that's a weird bloat problem.
      - Sesse__ 1y ago
        _Fitting_ in the instruction cache isn't hard, but you'd also ideally let there be room for some other code as well :-) For a hash map lookup, where the hashing is frequently inlined a couple of times, code size matters.
- Retr0id 1y ago
  You can have cache-unfriendly hash functions, though. For example, a common optimisation for CRC implementation involves lookup tables. If your lookup table exceeds L1 then you're going to have a bad time. If your lookup table fits exactly in L1, your benchmarks might look great, while real-world performance suffers (because your other code wants to be making use of L1, too). I'd imagine rapidhash avoids lookup tables but the question of cache-friendliness is still pertinent.

aidenn0 1y ago

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?

rurban 1y ago

It's not the fastest on smhasher anymore. umash is better and faster, and gxhash is twice as fast. It's is however very hashmap friendly because of its small size. It's a wyhash variant

nicoshev11 1y ago
Hey Reini, the rapidhash version on the SMHasher repo is outdated. The latest version was published last Tuesday, I'll submit it to SMHasher shortly. This new version is much faster than the previous one, and still passes all tests. It should beat umash on your benchmarks.
- Sesse__ 1y ago
  Am I right in that RAPIDHASH_UNROLLED is now mandatory and the function is thus much larger now?

curiouscoding 1y ago

I'd love to see some benchmarks/comparison on variable length strings. For strings with random length between 10 and 30, gxhash was significantly faster than xxhash for me. I would assume because it processes chunks of up to 32 chars at a time, avoiding branch misses. Generally my feeling is that at these speeds, designing for branch-predictability for short strings might be more important than absolute throughput.

bandrami 1y ago

I saw the first four words and then was disappointed by the direction it took...

coolcase 1y ago
Or first 2 words
deleted 1y ago
[deleted]

jandrewrogers 1y ago

Without getting too deep in the technical weeds, I will assert that rapidhash is an excellent small-key hash function and approximately the state-of-the-art for that purpose. There is nothing else better that I am aware of in this scope. For bulk hashing there are better functions, but XXH3, GXHash, etc are not among them, being both slower and weaker than the state-of-the-art. Hash functions that can’t pass quality tests are not serious contenders.

kragen 1y ago
I feel like I'm missing an enormous amount of context here, and I can't be the only one. How much better is it than old standbys like hashpjw, FNV1A, or djb's favorite¹, and how? It's apparently 350 lines of code instead of 1–10 lines of code. That seems like an important way that it's worse. And it comes with a copyright license that requires you to add it to your documentation, so the risk of forgetting that creates a risk of copyright infringement. So, how big is the benefit? How much faster is it hashing a small key like the string "__umulh"? Is it actually slower? (For those needing an introduction to hash tables, covering why that question makes sense, Chris Wellons is always excellent: https://nullprogram.com/blog/2025/01/19/ https://nullprogram.com/blog/2025/01/19/) Why does it have an array commented "default secret parameters" in the public GitHub repo? Are we supposed to change those? Do they provide some kind of security, and if so, what kind, against what threat model? The readme and https://scholar.google.com/scholar?hl=es&as_sdt=0%2C5&q=rapidhash+carli&btnG= https://scholar.google.com/scholar?hl=es&as_sdt=0%2C5&q=rapi... are no help here. https://github.com/rurban/smhasher?tab=readme-ov-file#summary https://github.com/rurban/smhasher?tab=readme-ov-file#summar... explains some of the questions at greater length but of course not rapidhash's particular answers. ______ ¹ while (s[i]) h = h * 33 + s[i++]; about 11 machine-code instructions in its full-fledged form: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:26,endLineNumber:4,positionColumn:26,positionLineNumber:4,selectionStartColumn:26,selectionStartLineNumber:4,startColumn:26,startLineNumber:4),source:'//+Type+your+code+here,+or+load+an+example.%0Aunsigned+hash17903(char+*s)+%7B%0A+unsigned+h+%3D+5381,+i+%3D+0%3B%0A+while+(s%5Bi%5D)+h+%3D+h+*+33+%2B+s%5Bi%2B%2B%5D%3B%0A+return+h%3B%0A%7D'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:g151,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-Os',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+15.1+(Editor+%231)',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:output,i:(compilerName:'x86-64+gcc+15.1',editorid:1,fontScale:14,fontUsePx:'0',j:1,wrap:'1'),l:'5',n:'0',o:'Output+of+x86-64+gcc+15.1+(Compiler+%231)',t:'0')),header:(),k:50,l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:50,l:'3',n:'0',o:'',t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename...

realo 1y ago

At a few ns per hash, it means the hash is done before photons from your screen reach your eyes. Impressive!

CyberDildonics 1y ago
There is a big difference between throughput and latency. If you do 8 at once with SIMD it doesn't mean you can get a single one done in 1/8th the time.

eqvinox 1y ago

Why are the numbers in the "performance" section almost all for AArch64? Where are the AMD64 numbers?

mertleee 1y ago

What's the actual application for this?

RainyDayTmrw 1y ago

Is this safe to use in public facing web servers? (Can adversaries trigger hash-DoS[1]?) [1]: https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding

zitoune 1y ago

"The fastest hash function passing all tests in SMHasher." GxHash is twice as fast and passes all SMHasher tests...