5 ms·

Yes, that's called rejection sampling, and it's the only way to produce truly uniform output if the range doesn't evenly divide the input range. However in a s

Yes, that's called rejection sampling, and it's the only way to produce truly uniform output if the range doesn't evenly divide the input range. However in a setting of say finding buckets in a hashtable which isn't a power-of-two size, this would amount to potentially computing multiple hashes. In certain scenarios, that may be unacceptable for computational reasons. If strict uniformity isn't required, the approach presented here may be good enough. It won't be exactly uniform if the range isn't a power of two, but it'll be equally close to uniform as modulo reduction is.

kazinator 5y ago
> hashtable which isn't a power-of-two size I think, I'd never want to do such a thing, but I will remember this multiplication trick in a legitimate situation where a non-power-of-two residue is being calculated, but the mathematical residue per se is not required.
- nullc 5y ago
  If your non-power-of-two sized hashtable is compile-time-constant, the modulus will get compiled into similarly fast code. It's only needed when the size isn't a constant. Particularly for large open hashtables having to double the size of your table to go up to the next power of 2 is a really significant memory overhead... and if the size is variable, the multiply is a lot faster. It's a good technique.
  - kazinator 5y ago
    A power of two hash table doubling in size just has to adjust a clipping mask. E.g. when the size is 16 we have mask == 0xF. When the size goes to 32, we have mask == 0x1F. Reducing the hash value to the table size is just hash & mask. There is simply no modern use case for non-power-of-two hash tables. Even in open addressing. Table sizes which are prime numbers are theoretically important because they allow techniques like quadratic probing to guarantee to visit every possible table offset, thanks to Euler's theorem. This one: https://en.wikipedia.org/wiki/Euler%27s_theorem https://en.wikipedia.org/wiki/Euler%27s_theorem (Only if n is prime is the phi(n) totient function equal to n - 1, meaning that all values of the congruence are traversed by the successive powers of a.) This will go out the window if you start doubling the table, so that n is no longer prime; you instead need a predetermined sequence of primes to serve as table sizes. Quadratic probing is silly because it's been found that linear probing, in spite of its issues, wins in terms of caching performance. The only reason to go to open addressing over chained hashing would be for better caching, due to not chasing chain pointers, and then you might as well reap the full improvement from better caching by using linear probing.
    - nullc 5y ago
      > There is simply no modern use case for non-power-of-two hash tables. Even in open addressing.There is simply no modern use case for non-power-of-two hash tables. I think I'd much rather a hash table that needs 32.1 GB actually take 32.1 GB and not 64 GB especially when I need several of them, thank you very much! With the extra memory saved and the TLB/cache footprint reduced I can get a lot of performance to offset the minuscule latency difference between a widening multiply and a logical and! In a recent data structure I've worked on, using an algebraic code requiring a couple bisection searches in a couple tiny tables to decode-- to just reduce table entries by 4 bits measurably improved performance, simply from reducing the cache/tlb footprint a few percent. As computers have become faster multiplies and adds have become increasingly free relative to memory latency/bandwidth.

kazinator 5y ago

> hashtable which isn't a power-of-two size I think, I'd never want to do such a thing, but I will remember this multiplication trick in a legitimate situation where a non-power-of-two residue is being calculated, but the mathematical residue per se is not required.

nullc 5y ago
If your non-power-of-two sized hashtable is compile-time-constant, the modulus will get compiled into similarly fast code. It's only needed when the size isn't a constant. Particularly for large open hashtables having to double the size of your table to go up to the next power of 2 is a really significant memory overhead... and if the size is variable, the multiply is a lot faster. It's a good technique.
- kazinator 5y ago
  A power of two hash table doubling in size just has to adjust a clipping mask. E.g. when the size is 16 we have mask == 0xF. When the size goes to 32, we have mask == 0x1F. Reducing the hash value to the table size is just hash & mask. There is simply no modern use case for non-power-of-two hash tables. Even in open addressing. Table sizes which are prime numbers are theoretically important because they allow techniques like quadratic probing to guarantee to visit every possible table offset, thanks to Euler's theorem. This one: https://en.wikipedia.org/wiki/Euler%27s_theorem https://en.wikipedia.org/wiki/Euler%27s_theorem (Only if n is prime is the phi(n) totient function equal to n - 1, meaning that all values of the congruence are traversed by the successive powers of a.) This will go out the window if you start doubling the table, so that n is no longer prime; you instead need a predetermined sequence of primes to serve as table sizes. Quadratic probing is silly because it's been found that linear probing, in spite of its issues, wins in terms of caching performance. The only reason to go to open addressing over chained hashing would be for better caching, due to not chasing chain pointers, and then you might as well reap the full improvement from better caching by using linear probing.
  - nullc 5y ago
    > There is simply no modern use case for non-power-of-two hash tables. Even in open addressing.There is simply no modern use case for non-power-of-two hash tables. I think I'd much rather a hash table that needs 32.1 GB actually take 32.1 GB and not 64 GB especially when I need several of them, thank you very much! With the extra memory saved and the TLB/cache footprint reduced I can get a lot of performance to offset the minuscule latency difference between a widening multiply and a logical and! In a recent data structure I've worked on, using an algebraic code requiring a couple bisection searches in a couple tiny tables to decode-- to just reduce table entries by 4 bits measurably improved performance, simply from reducing the cache/tlb footprint a few percent. As computers have become faster multiplies and adds have become increasingly free relative to memory latency/bandwidth.