Prime number Hash table

[jackk03]

Hi,
while studying hash tables I read that if the number of entries of the table is a prime number, that can contribute to have a more uniform distribution and therefore reduce the number of collisions.
Now, this effect is obviously more obvious if the table in quesiton isn't costantly filled to near 100%, but I still think it could bring some small gain in performance.

Does any engine already have the hash table entries set to be a prime number? or has anyone already tried and tested this?

I expect the difference to be, if any, small, and I don't have the possiiblity of doing an accurate test with my engine by running thousands of games, so that's why I'm asking for help

[AlvaroBegue]

I remember reading an implementation that used prime numbers for hash table size many years ago (maybe gnuchess?). I don't think it makes much sense to do that. Using a power-of-2 size is fine unless your hash function is broken. If your hash function is mediocre and you want to improve the distribution, pass your 64-bit hash through an avalanche function to mix in all the bits:

Code: Select all

uint64_t avalanche(uint64_t x) {
  x *= 0x61664b66ad5f0385ull;
  x ^= x >> 32;
  x *= 0xf959d19084fd5339ull;
  x ^= x >> 32;
  return x;
}

Probably even just the first two lines would be enough for this purpose, and it should be faster to evaluate than a modulo operation.

[hgm]

If your Zobrist base keys are good, the distribution of probes over the table should already be as uniform as it could ever be. Size of the table has no effect on this at all. Sizes that are not powers of two just slow down the calculation of the index from the key, especially if you use modulo or division fin it. (Bob Hyatt once reported a slowdown of Crafty of about 20% just by using the modulo for calculating the index.)

[Volker Annuss]

For hash table sizes that are not a power of 2 look here.

[jackk03]

Thanks Voler, yours seems a good idea, I will defenitely try it.
I actually tried to have a hash table with prime number of entries, and it didn't make any difference at all. I will try your idea to get rid of the modulo operation

[BeyondCritics]

Hi,
while studying hash tables I read that if the number of entries of the table is a prime number, that can contribute to have a more uniform distribution and therefore reduce the number of collisions.
...

I remember having also stumbled over this, a long time ago. Interesting that this is still around, the net never forgets.
Back in the first days of programming you had to fight very hard for performance and every program had to be a big blob of everything, including your own hash table. And at that time multiplication was as slow as division, therefore modulo hashing was not uncommon. Seemingly some assumed that modulo hashing was the only sensible way of doing it, so much that they didn't bother to mention it. And if you are only using modulo hashing, it makes sense to make the hash table always prime sized, so that you are calculating in a field, otherwise there might be issues with zero divisors.

Obligatory fun fact:
Some cicade species breed only once in n years [1] , where n is a prime number. A suggested explanation is, that this minimizes the number of resonant frequencies.

[1] https://en.wikipedia.org/wiki/Cicada