Author: Gerd Isenberg
Date: 13:51:09 08/26/03
Go up one level in this thread
On August 26, 2003 at 15:53:34, Dieter Buerssner wrote: >On August 26, 2003 at 15:20:22, Peter Fendrich wrote: > >>How can we use these 40Mb with a good distribution of entries? >>(I have more hash tables to combine with but let's skip that for now) >> >>Some figures in this example: >> 1 entry: 96 bits = 12 bytes >> Available memory: 88Mb >> # entries available: 7689557 >>Key for 88Mb (Key88): 23 bits (22 bits will cover 48Mb) >> Max for Key88: 96Mb (8388608 entries) >> >>When computing the Key88 from my (64 bits) Hashcode some values will of course > >Skip this step. > >>be above the upper limit 7689557 (11101010101010101010101). >>My first thought was to use modulo: Key88 %= 7689557 > >And use 32 bits of the 64 bit hash code. > >unsigned long keyxx = hashcode & 0xffffffffUL; >index = keyxx%number_of_entries; > >It will be almost uniformly distributed, unless your number of entries comes >close 2^^32. One could use the modolu directly on the 64-bit number, but that >will be a very costly operation on many platforms. For example there is no >instruction on x86 for that operation (there is a 64 bit devide by 32 bit >instruction, that also yields the modulo, but the result of the devision must be >smaller than 2^^32, otherwise you get a divide by zero - so it is not usable >here). > >Regards, >Dieter Hi Dieter, What about to save the modulo: UINT64 keyxy = (hashcode & 0xffffffffUL) * number_of_entries; index = (unsigned long) (keyxy >> 32); Didn't you introduced these index trick here before? To do a fast 32-bit*32-bit = 64-bit multiplication. Regards, Gerd
This page took 0.01 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.