2 ms·

I wasn't asking how it could be faster; I was asking how much faster it was (or otherwise better), for small keys like "__umulh", where the startup/finalize ove

by kragen 1y ago

I wasn't asking how it could be faster; I was asking how much faster it was (or otherwise better), for small keys like "__umulh", where the startup/finalize overheads are worst. Clearly GB/s is a good measure if you're hashing files or Flash FTL blocks, but jandrewrogers specifically said it's state of the art for the purpose of small-key hashing, which to me means things like dictionary words and variable or method names. Maybe that's not what they meant? Even on a fairly wimpy microcontroller the hash I linked above only has about four instructions of startup/finalize overhead, even without inlining: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:'unsigned+hash17903(char+*s)+%7B%0A+unsigned+h+%3D+5381%3B%0A+while+(*s)+h+%3D+h+*+33+%2B+*s%2B%2B%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:!((h:compiler,i:(compiler:rv32-gcc1510,filters:(b:'0',binary:'1',binaryObject:'0',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++-march%3Drv32idc',overrides:!(),selection:(endColumn:1,endLineNumber:4,positionColumn:1,positionLineNumber:4,selectionStartColumn:1,selectionStartLineNumber:4,startColumn:1,startLineNumber:4),source:1),l:'5',n:'0',o:'+RISC-V+(32-bits)+gcc+15.1.0+(Editor+%231)',t:'0')),header:(),k:50,l:'4',m:100,n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename... (I modified it slightly because GCC was puzzlingly not reducing my array indexing to pointer arithmetic...)

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.
jandrewrogers 1y ago
There is a fundamental tradeoff between throughput and latency for hash functions. The rapidhash algorithm is clearly optimized for low latency in cases where the keys are small, like string dictionaries and similar. It is not competitive with throughput-optimized algorithms of similar quality when average keys are several hundred bytes or larger. If you want even lower-overhead, you will need to specialize the hash algorithm for the properties of the key set. I’ve designed narrowly specialized hashes that basically resolve to two instructions. The specifics are somewhat hardware specific but the performance crossover point as a function of key size between latency-optimized algorithms and throughput-optimized algorithms is currently in the 400-500 byte range on modern server hardware, assuming state-of-the-art quality.

by kragen 1y ago

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.

jandrewrogers 1y ago

There is a fundamental tradeoff between throughput and latency for hash functions. The rapidhash algorithm is clearly optimized for low latency in cases where the keys are small, like string dictionaries and similar. It is not competitive with throughput-optimized algorithms of similar quality when average keys are several hundred bytes or larger. If you want even lower-overhead, you will need to specialize the hash algorithm for the properties of the key set. I’ve designed narrowly specialized hashes that basically resolve to two instructions. The specifics are somewhat hardware specific but the performance crossover point as a function of key size between latency-optimized algorithms and throughput-optimized algorithms is currently in the 400-500 byte range on modern server hardware, assuming state-of-the-art quality.