3 ms·

Fair enough. Sorry! You were pretty clear. I continue to think that the world would be less confusing if people didn't go around citing GB/s for hash-table h

by cb321 1y ago

Fair enough. Sorry! You were pretty clear. I continue to think that the world would be less confusing if people didn't go around citing GB/s for hash-table hashes, but rather (perHash+-err, perCost+-err) on CPU xyz. Cuts right to the heart of the matters and then folks like jandrewrogers don't have to be vague with "small" to then inspire questions like yours. (Of course, CPUs really vary a lot, too.) I also think when people measure these fast string hashes for strings > L1 CPU cache they're mostly measuring a melange of IO/memory system not the hash computation - maybe sometimes unwittingly. L1 CPU caches can deliver 100s of GB/s after all. 1 64B cache line per cycle is 64B/0.2ns = 320 GB/s. Intel's Skylake could do that a decade ago. The memory wall can be a real bear.

kragen 1y ago
No problem! I just wanted to clear up any possible misunderstanding. Probably if you're hashing a 32KiB string, you're still in L1 cache, but your performance is probably close to this 71GB/s number, which would be 460ns.
- cb321 1y ago
  BTW, there's some analysis of some of the hash functions you mentioned (pjw, FNV1A, or djb) over here https://github.com/nim-lang/Nim/issues/23678 https://github.com/nim-lang/Nim/issues/23678 - just in-page search for "pjw" to find a table. Really only 1 cpu & 1 C compiler (though there was some solicitation of more breadth). Those byte-at-a-time hashers really are pretty slow unless your strings are very short (like under 3..6 bytes - which, hey, they might be!). Further down there are some plots/graphs with a little more compiler/cpu variety but fewer hash functions. Kind of a long thread, but maybe informative. Anyway, pictures are worth thousands of words and all that. EDIT: and FWIW, there's even some preliminary analysis of this new rapid hash TFA is about towards the bottom, but it may be an older, slower version.

by cb321 1y ago

kragen 1y ago

No problem! I just wanted to clear up any possible misunderstanding. Probably if you're hashing a 32KiB string, you're still in L1 cache, but your performance is probably close to this 71GB/s number, which would be 460ns.

cb321 1y ago
BTW, there's some analysis of some of the hash functions you mentioned (pjw, FNV1A, or djb) over here https://github.com/nim-lang/Nim/issues/23678 https://github.com/nim-lang/Nim/issues/23678 - just in-page search for "pjw" to find a table. Really only 1 cpu & 1 C compiler (though there was some solicitation of more breadth). Those byte-at-a-time hashers really are pretty slow unless your strings are very short (like under 3..6 bytes - which, hey, they might be!). Further down there are some plots/graphs with a little more compiler/cpu variety but fewer hash functions. Kind of a long thread, but maybe informative. Anyway, pictures are worth thousands of words and all that. EDIT: and FWIW, there's even some preliminary analysis of this new rapid hash TFA is about towards the bottom, but it may be an older, slower version.