4 ms·

Author may be interested in http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ http://lemire.me/blog/2016/06/27/a-fast-alternative-to-

by jlrubin 10y ago

Author may be interested in http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-m... as a way of avoiding modulo altogether.

TorKlingberg 10y ago
This is fine if you are working with 32-bit numbers on a CPU with fast 64-but multiplication. What if you have 64-bit numbers?
- jbapple 10y ago
  x86-64 has single instruction (MUL) that produces a 128-bit unsigned result by multiplying two unsigned 64-bit operands.
- gpderetta 10y ago
  In addition to what jbapple said, if your hash map has more than 2^32 buckets, the latency of the division is the last of your problem.
  - TorKlingberg 10y ago
    Sure N (number of buckets) shouldn't be too big, but x (the input value) could be.
- 79d697i6fdif 10y ago
  realistically any hash table bigger than the 32 bit boundary will be well outside any CPU caches and possibly even ram. At these sizes the memory latency will dwarf CPU speed
79d697i6fdif 10y ago
The author seems mistaken about a couple things relating to hash tables. He doesn't seem aware that, by far, the main reason for using power-of-two hash table sizes is so you can use a simple bitshift to eliminate modulo entirely. He is also going to run into modulo bias since using the remainder to calculate a slot position is biased toward certain positions for every table size that isn't a power of two. (see https://ericlippert.com/2013/12/16/how-much-bias-is-introduced-by-the-remainder-technique/ https://ericlippert.com/2013/12/16/how-much-bias-is-introduc... for cool graphs) Prime number table sizes do nothing to fix these issue. The power-of-two size with a bitshift is not just faster, it gets rid of the modulo bias. Fastrange is much faster than modulo but if his goal is to build the fastest hashtable it's stupid to use a table size of anything except a power of two. Source: I also wrote a hashtable :)
- pacoverdi 10y ago
  > He doesn't seem aware that, by far, the main reason for using power-of-two hash table sizes is so you can use a simple bitshift to eliminate modulo entirely. [...] using a power of two to size the table so that a hash can be mapped to a slot just by looking at the lower bits. He seems to know this bit :)
  - mark-r 10y ago
    He appears to know about bit masking but not bit shifting, which seems odd.
- krajzeg 10y ago
  There is a lot of material in the article on power-of-two vs non-power-of-two sizes and it definitely includes a discussion of how POT is convenient due to modulo becoming a bitmask (not a bitshift, which would be division).
- anon1385 10y ago
  >The author seems mistaken about a couple things relating to hash tables. He doesn't seem aware that, by far, the main reason for using power-of-two hash table sizes is so you can use a simple bitshift to eliminate modulo entirely. From the article: >This is the main reason why really fast hash tables usually use powers of two for the size of the array. Then all you have to do is mask off the upper bits, which you can do in one cycle.
  - rurban 10y ago
    Exactly. It's a bitmask, not a shift. But he doesn't know about ctz (counting trailing zeros) for fast load/fillrate detection. With 50% it's trivial (just a shift), but for 70% or 90% you'd need to use _builtin_ctz.
  - hinkley 10y ago
    Yeah I'm gonna need an explanation too. Even with hashes hardened against DOS attacks, the lower bits tend to vary with the input far faster than the upper bits. For instance, several popular hash algorithms (of the form 31 * hash + value) will have the same upper bits for any two strings of the same length, up to about 12 characters in length when the seed value finally gets pushed out. Unless you're still using 32 bit hashes for some reason and then it's most strings under 6 characters long. Multiply by prime and then add or xor the next value guarantees that the bottom bits are less biased and so fits with any hashtable function that uses modular math, even if the modulus is taken by bit masking. Getting the upper bits to mix would take a different operator or larger operands. I know I've encountered at least one hash function that uses a much larger prime (16 or more bits) as its multiplier, so it's not unheard of, but it's certainly not universal.
EGreg 10y ago
Speaking of avoiding non-binary logic, what do you all think of using the same simplification for doing SYNC: http://magarshak.com/blog http://magarshak.com/blog
dgacmu 10y ago
They may, but it's worth noting that if you're going to use Lemire's trick, you must have a good hash function -- which this post avoids. The trick you referenced (i use "trick" in a good sense) relies on the high-order bits of the multiplication changing substantially, which means that items that hash to 1, 2, 3, ... end up in the same bin. This is perfectly fine if your hash function maps uniformly to [0, max_int32_t] (or max_int64_t if you use the umul_hi variant), but it's not fine if you use the horrible default identity function std::hash. (Speaking from experience: I used his trick to accelerate one of the TensorFlow hash tables a while ago -- https://github.com/tensorflow/tensorflow/commit/a47a300185026fe7829990def9113bf3a5109fed https://github.com/tensorflow/tensorflow/commit/a47a30018502... )

by jlrubin 10y ago

TorKlingberg 10y ago

This is fine if you are working with 32-bit numbers on a CPU with fast 64-but multiplication. What if you have 64-bit numbers?

jbapple 10y ago
x86-64 has single instruction (MUL) that produces a 128-bit unsigned result by multiplying two unsigned 64-bit operands.
gpderetta 10y ago
In addition to what jbapple said, if your hash map has more than 2^32 buckets, the latency of the division is the last of your problem.
- TorKlingberg 10y ago
  Sure N (number of buckets) shouldn't be too big, but x (the input value) could be.
79d697i6fdif 10y ago
realistically any hash table bigger than the 32 bit boundary will be well outside any CPU caches and possibly even ram. At these sizes the memory latency will dwarf CPU speed

79d697i6fdif 10y ago

The author seems mistaken about a couple things relating to hash tables. He doesn't seem aware that, by far, the main reason for using power-of-two hash table sizes is so you can use a simple bitshift to eliminate modulo entirely. He is also going to run into modulo bias since using the remainder to calculate a slot position is biased toward certain positions for every table size that isn't a power of two. (see https://ericlippert.com/2013/12/16/how-much-bias-is-introduced-by-the-remainder-technique/ https://ericlippert.com/2013/12/16/how-much-bias-is-introduc... for cool graphs) Prime number table sizes do nothing to fix these issue. The power-of-two size with a bitshift is not just faster, it gets rid of the modulo bias. Fastrange is much faster than modulo but if his goal is to build the fastest hashtable it's stupid to use a table size of anything except a power of two. Source: I also wrote a hashtable :)

pacoverdi 10y ago
> He doesn't seem aware that, by far, the main reason for using power-of-two hash table sizes is so you can use a simple bitshift to eliminate modulo entirely. [...] using a power of two to size the table so that a hash can be mapped to a slot just by looking at the lower bits. He seems to know this bit :)
- mark-r 10y ago
  He appears to know about bit masking but not bit shifting, which seems odd.
krajzeg 10y ago
There is a lot of material in the article on power-of-two vs non-power-of-two sizes and it definitely includes a discussion of how POT is convenient due to modulo becoming a bitmask (not a bitshift, which would be division).
anon1385 10y ago
>The author seems mistaken about a couple things relating to hash tables. He doesn't seem aware that, by far, the main reason for using power-of-two hash table sizes is so you can use a simple bitshift to eliminate modulo entirely. From the article: >This is the main reason why really fast hash tables usually use powers of two for the size of the array. Then all you have to do is mask off the upper bits, which you can do in one cycle.
- rurban 10y ago
  Exactly. It's a bitmask, not a shift. But he doesn't know about ctz (counting trailing zeros) for fast load/fillrate detection. With 50% it's trivial (just a shift), but for 70% or 90% you'd need to use _builtin_ctz.
- hinkley 10y ago
  Yeah I'm gonna need an explanation too. Even with hashes hardened against DOS attacks, the lower bits tend to vary with the input far faster than the upper bits. For instance, several popular hash algorithms (of the form 31 * hash + value) will have the same upper bits for any two strings of the same length, up to about 12 characters in length when the seed value finally gets pushed out. Unless you're still using 32 bit hashes for some reason and then it's most strings under 6 characters long. Multiply by prime and then add or xor the next value guarantees that the bottom bits are less biased and so fits with any hashtable function that uses modular math, even if the modulus is taken by bit masking. Getting the upper bits to mix would take a different operator or larger operands. I know I've encountered at least one hash function that uses a much larger prime (16 or more bits) as its multiplier, so it's not unheard of, but it's certainly not universal.

EGreg 10y ago

Speaking of avoiding non-binary logic, what do you all think of using the same simplification for doing SYNC: http://magarshak.com/blog http://magarshak.com/blog

dgacmu 10y ago

They may, but it's worth noting that if you're going to use Lemire's trick, you must have a good hash function -- which this post avoids. The trick you referenced (i use "trick" in a good sense) relies on the high-order bits of the multiplication changing substantially, which means that items that hash to 1, 2, 3, ... end up in the same bin. This is perfectly fine if your hash function maps uniformly to [0, max_int32_t] (or max_int64_t if you use the umul_hi variant), but it's not fine if you use the horrible default identity function std::hash. (Speaking from experience: I used his trick to accelerate one of the TensorFlow hash tables a while ago -- https://github.com/tensorflow/tensorflow/commit/a47a300185026fe7829990def9113bf3a5109fed https://github.com/tensorflow/tensorflow/commit/a47a30018502... )