Author: Dieter Buerssner
Date: 16:42:47 02/11/02
Go up one level in this thread
On February 11, 2002 at 13:23:46, Heiner Marxen wrote: >On February 11, 2002 at 10:37:45, Robert Hyatt wrote: > >>Based on that, why doesn't everyone use _any_ size for their hash tables, >>rather than using a power of 2 so that AND can extract the address part? > >Hello Bob, > >I'm not sure. In my program "chest" I _do_ use arbitrary sizes. >The additional %= size instead of &= (size-1) is not significant (for me). >The positive side is that I can use any (odd) amount of RAM available. I made the same experience. I could not find any measurable difference between power of 2 sizes and arbitrary sizes, where the "&-method" will not work anymore. Even % is not needed, and multiplication (which is typically faster) can be enough. One can take 32 bits of the hash key. Multiply this by the number of entries, and take the upper 32 bits of the 64 bit result as the index into the hash table. On x86 architecture, this is just a "mul", and the index will be in edx. With some casting, the compilers can be convinced to produce very efficient code even from C, without going to assembler. To me it looks, that the power of 2 sizes come from a time very modulo was a very expensive operation. BTW. I tried different schemes on x86, Alpha and MIPS processors, and neither architecture showed any reason to stay with the power of 2 size. I think typically the memory accesses (that will normally not be cached due to access patterns to the HT) will need more time than the index calculation. Regards, Dieter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.