6 ms·

Multiplication is bad. Knuth actually also describes a hash function using random numbers and XOR. Its 10x faster than the modulo, and I belive Mikkel Thorup pr

Multiplication is bad. Knuth actually also describes a hash function using random numbers and XOR. Its 10x faster than the modulo, and I belive Mikkel Thorup proved it optimal. The idea is roughly: Say you have a hashtable of size 1024. You then create x uint arrays of size size 256. These arrays you fill up with random numbers 0-1023. To get your hash value, you take your input and for i=0..x-1 determine byte k=input[i] you lookup the value in array[i][k]. These lookup values are then XORed giving a final random value between 0-1023 ready for inserting into the hash array. No modulos. No multiplications. You only have to redo the random tables when the size changes from say 1024 to 2048. Easy peacy. Superfast.

karmakurtisaani 3y ago
How do you fill the array though? Wouldn't filling it with random numbers give you a different hash each time you rebuild the hash function? I can see it being useful for a short-lived data structure, but you wouldn't be able to use it as a shared deterministic hash function?
- RhodesianHunter 3y ago
  Why couldn't you fill it deterministically?
  - karmakurtisaani 3y ago
    I guess that was my question indeed. In the sense of how do you do it in practice? I suppose there are pseudorandom algorithms that can be easily applied.
    - cycomanic 3y ago
      Pseudorandom bit sequences PRBS are deterministic and very easy to implement (just linear feedback shift registers). Something similar is actually done in communication systems, with scrambling, to prevent long strings of transmitted ones or zeros (which cause issues for some of the hardware components). Essentially you just add or multiply the data with the PRBS sequence. At the receiver you just do the reverse operation.
- ndr 3y ago
  For in-memory tables you rarely need determinism across instances, let alone runs.
Sesse__ 3y ago
“Superfast”, until you blow through your L1 cache, which happens pretty early on if you need 1 kB of table per byte in your key. Even in the L1 cache, it's hard to beat the mul: A multiplication (which can hash multiple bytes in the case of Fibonacci hashing) has 3 cycles latency on modern x86. A single load, even from L1, is 5, I believe.
- _a_a_a_ 3y ago
  Word. It depends on access patterns of course but yeah, L1 is a valuable resource.
- eru 3y ago
  How much of a problem 3 cycles of latency is depends on what else your processor is doing. It might not be any problem at all.
tinus_hn 3y ago
The replies to this command are top HackerNews: every commenter is a bigger expert than Donald Knuth but nobody quotes any actual benchmark results to go with their theories.
- eru 3y ago
  Why? Eg https://news.ycombinator.com/item?id=35760954 https://news.ycombinator.com/item?id=35760954 quotes some (vague) numbers.
- tjoff 3y ago
  It isn't fair to assume the same rigor on a comment. But, you don't have to be a bigger expert than Knuth to dismiss an optimization done for hardware say 40 years ago (the circumstances around this particular case I don't know). Even in that case though it might still be relevant for embedded CPUs.
  - xxs 3y ago
    Embedded CPUs would have much worse memory access latency, and a lot less memory to spare - so if anything wasting memory on tables is likely to perform worse as well.
    - tjoff 3y ago
      How do you mean? Measured in cycles embedded devices typically have less latency to SRAM.
      - xxs 3y ago
        You're right, I guess. On devices where the memory (sram) tends not to have its own clock (and there is no OOO), it can effectively be one cpu cycle. PIC and ESP-32 comes to mind. If there is 'extra' not on chip memory, it'd be way worse, of course.
  - tinus_hn 3y ago
    So it’s just some unfounded handwaving? You can just dismiss one of the greatest minds in computing science by just blathering in a comment, because then it’s ‘unfair to assume rigor’? If it is all so clear and all the armchair experts here have ample experience in the field like they pretend, why is it so hard to run a few benchmarks?
vidarh 3y ago
Multiplication was bad on decades old CPU's.
_a_a_a_ 3y ago
This sounds like zobrist hashing, or related . https://en.wikipedia.org/wiki/Zobrist_hashing https://en.wikipedia.org/wiki/Zobrist_hashing " Zobrist hashing is the first known instance of the generally useful underlying technique called tabulation hashing. " so to https://en.wikipedia.org/wiki/Tabulation_hashing https://en.wikipedia.org/wiki/Tabulation_hashing " In computer science, tabulation hashing is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. It was first studied in the form of Zobrist hashing for computer games; [...] Despite its simplicity, tabulation hashing has strong theoretical properties that distinguish it from some other hash functions. In particular, it is 3-independent: [...] Because of its high degree of independence, tabulation hashing is usable with hashing methods that require a high-quality hash function, including hopscotch hashing, cuckoo hashing, and the MinHash technique for estimating the size of set intersections. " further " Method: The basic idea is as follows: First, divide the key to be hashed into smaller "blocks" of a chosen length. Then, create a set of lookup tables, one for each block, and fill them with random values. Finally, use the tables to compute a hash value for each block, and combine all of these hashes into a final hash value using the bitwise exclusive or operation.[1] "
xxs 3y ago
How come mul is bad? It is a low cycle latency - Skylake had 3cycles per imul, mul r32 - a single cycle. Div is bad but mul is great. edit: Memory access (along with div) is pretty much the only slow operation in modern CPUs -- extra pressure on L1 just to have random number is not smart at any rate, heck Marsaglia's xor (random) is likely cheaper than accessing L1, very likely all the latency to be hidden behind the memory access.
NohatCoder 3y ago
Others have hinted at this, but to be clear: This algorithm is slow, even in the optimal case where the tables are in cache. On new X86 CPUs it is theoretically limited to less than 2 bytes per cycle. Probably somewhere around 1.5 for an implementation that loads 8 bytes of input at once and shift though them in order to limit load on the load slots. Even without getting into SIMD algorithms you could load 8 bytes at a time and pretty easily go faster than that, possibly while using the multiplication instruction for mixing. This of course ignores that we are not looking up values from a hash table in a vacuum. Other code will also be competing for the cache, and that generally means that everything runs slower because of more cache misses.
dragontamer 3y ago
Modern CPU cores can perform a multiplication and addition every clock tick. Heck, I'd expect a modern Zen4 core to be able to do like 4 parallel 64-bit multiplications per clock tick on it's integer pipelines, and maybe 32x parallel 32-bit multiplications per clock tick on it's vector pipelines. Multiplications we're bad 40 years ago, but the year 2020 called and FMAC is incredibly optimized today. You should still avoid integer division (floating point division is commonly optimized as reciprocal and then multiply). But multiplications are really really fast at least as far back as 2008 or so. ------- I'm pretty sure multiplication's latency is only 5 clocks, but with all the out of order processing that occurs on modern cores, latency of just 5 ticks is rarely is the bottleneck. (A DDR4 memory load is like 200+ cycles of latency. You shouldn't even worry about 5 cycles like multiplication, especially because those out of order cores will find some work to parallelize in that time). ----- > you lookup the value in array[i][k] You know a L1 cache lookup these days is like 4 cycles of latency right? And I'm pretty sure you have fewer load/store units than multiplication units. So a load/store, even to L1 cache, might use more resources than the multiply. Might, I'd have to benchmark to be sure.
- xxs 3y ago
  Indeed, division just doesn't have a parallel algorithm, unlikely mul and add. So it's bound to be 'slow'. About 2008 - Intel core 2 (2006) had 3 cycle mul. Edit: Pentium Pro(1995)'s imul was 4 cycles. 386's imul was slow, though.

karmakurtisaani 3y ago

How do you fill the array though? Wouldn't filling it with random numbers give you a different hash each time you rebuild the hash function? I can see it being useful for a short-lived data structure, but you wouldn't be able to use it as a shared deterministic hash function?

RhodesianHunter 3y ago
Why couldn't you fill it deterministically?
- karmakurtisaani 3y ago
  I guess that was my question indeed. In the sense of how do you do it in practice? I suppose there are pseudorandom algorithms that can be easily applied.
  - cycomanic 3y ago
    Pseudorandom bit sequences PRBS are deterministic and very easy to implement (just linear feedback shift registers). Something similar is actually done in communication systems, with scrambling, to prevent long strings of transmitted ones or zeros (which cause issues for some of the hardware components). Essentially you just add or multiply the data with the PRBS sequence. At the receiver you just do the reverse operation.
ndr 3y ago
For in-memory tables you rarely need determinism across instances, let alone runs.

Sesse__ 3y ago

“Superfast”, until you blow through your L1 cache, which happens pretty early on if you need 1 kB of table per byte in your key. Even in the L1 cache, it's hard to beat the mul: A multiplication (which can hash multiple bytes in the case of Fibonacci hashing) has 3 cycles latency on modern x86. A single load, even from L1, is 5, I believe.

_a_a_a_ 3y ago
Word. It depends on access patterns of course but yeah, L1 is a valuable resource.
eru 3y ago
How much of a problem 3 cycles of latency is depends on what else your processor is doing. It might not be any problem at all.

tinus_hn 3y ago

The replies to this command are top HackerNews: every commenter is a bigger expert than Donald Knuth but nobody quotes any actual benchmark results to go with their theories.

eru 3y ago
Why? Eg https://news.ycombinator.com/item?id=35760954 https://news.ycombinator.com/item?id=35760954 quotes some (vague) numbers.
tjoff 3y ago
It isn't fair to assume the same rigor on a comment. But, you don't have to be a bigger expert than Knuth to dismiss an optimization done for hardware say 40 years ago (the circumstances around this particular case I don't know). Even in that case though it might still be relevant for embedded CPUs.
- xxs 3y ago
  Embedded CPUs would have much worse memory access latency, and a lot less memory to spare - so if anything wasting memory on tables is likely to perform worse as well.
  - tjoff 3y ago
    How do you mean? Measured in cycles embedded devices typically have less latency to SRAM.
    - xxs 3y ago
      You're right, I guess. On devices where the memory (sram) tends not to have its own clock (and there is no OOO), it can effectively be one cpu cycle. PIC and ESP-32 comes to mind. If there is 'extra' not on chip memory, it'd be way worse, of course.
- tinus_hn 3y ago
  So it’s just some unfounded handwaving? You can just dismiss one of the greatest minds in computing science by just blathering in a comment, because then it’s ‘unfair to assume rigor’? If it is all so clear and all the armchair experts here have ample experience in the field like they pretend, why is it so hard to run a few benchmarks?

vidarh 3y ago

Multiplication was bad on decades old CPU's.

_a_a_a_ 3y ago

This sounds like zobrist hashing, or related . https://en.wikipedia.org/wiki/Zobrist_hashing https://en.wikipedia.org/wiki/Zobrist_hashing " Zobrist hashing is the first known instance of the generally useful underlying technique called tabulation hashing. " so to https://en.wikipedia.org/wiki/Tabulation_hashing https://en.wikipedia.org/wiki/Tabulation_hashing " In computer science, tabulation hashing is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. It was first studied in the form of Zobrist hashing for computer games; [...] Despite its simplicity, tabulation hashing has strong theoretical properties that distinguish it from some other hash functions. In particular, it is 3-independent: [...] Because of its high degree of independence, tabulation hashing is usable with hashing methods that require a high-quality hash function, including hopscotch hashing, cuckoo hashing, and the MinHash technique for estimating the size of set intersections. " further " Method: The basic idea is as follows: First, divide the key to be hashed into smaller "blocks" of a chosen length. Then, create a set of lookup tables, one for each block, and fill them with random values. Finally, use the tables to compute a hash value for each block, and combine all of these hashes into a final hash value using the bitwise exclusive or operation.[1] "

xxs 3y ago

How come mul is bad? It is a low cycle latency - Skylake had 3cycles per imul, mul r32 - a single cycle. Div is bad but mul is great. edit: Memory access (along with div) is pretty much the only slow operation in modern CPUs -- extra pressure on L1 just to have random number is not smart at any rate, heck Marsaglia's xor (random) is likely cheaper than accessing L1, very likely all the latency to be hidden behind the memory access.

NohatCoder 3y ago

Others have hinted at this, but to be clear: This algorithm is slow, even in the optimal case where the tables are in cache. On new X86 CPUs it is theoretically limited to less than 2 bytes per cycle. Probably somewhere around 1.5 for an implementation that loads 8 bytes of input at once and shift though them in order to limit load on the load slots. Even without getting into SIMD algorithms you could load 8 bytes at a time and pretty easily go faster than that, possibly while using the multiplication instruction for mixing. This of course ignores that we are not looking up values from a hash table in a vacuum. Other code will also be competing for the cache, and that generally means that everything runs slower because of more cache misses.

dragontamer 3y ago

Modern CPU cores can perform a multiplication and addition every clock tick. Heck, I'd expect a modern Zen4 core to be able to do like 4 parallel 64-bit multiplications per clock tick on it's integer pipelines, and maybe 32x parallel 32-bit multiplications per clock tick on it's vector pipelines. Multiplications we're bad 40 years ago, but the year 2020 called and FMAC is incredibly optimized today. You should still avoid integer division (floating point division is commonly optimized as reciprocal and then multiply). But multiplications are really really fast at least as far back as 2008 or so. ------- I'm pretty sure multiplication's latency is only 5 clocks, but with all the out of order processing that occurs on modern cores, latency of just 5 ticks is rarely is the bottleneck. (A DDR4 memory load is like 200+ cycles of latency. You shouldn't even worry about 5 cycles like multiplication, especially because those out of order cores will find some work to parallelize in that time). ----- > you lookup the value in array[i][k] You know a L1 cache lookup these days is like 4 cycles of latency right? And I'm pretty sure you have fewer load/store units than multiplication units. So a load/store, even to L1 cache, might use more resources than the multiply. Might, I'd have to benchmark to be sure.

xxs 3y ago
Indeed, division just doesn't have a parallel algorithm, unlikely mul and add. So it's bound to be 'slow'. About 2008 - Intel core 2 (2006) had 3 cycle mul. Edit: Pentium Pro(1995)'s imul was 4 cycles. 386's imul was slow, though.