Author: martin fierz
Date: 17:45:57 09/15/02
Go up one level in this thread
On September 15, 2002 at 14:28:24, Dieter Buerssner wrote: >On September 15, 2002 at 04:32:48, martin fierz wrote: > >>On September 14, 2002 at 20:24:11, scott farrell wrote: >>>How to you calculate the index for the second probe. >> >>index++; :-) > >Perhaps, it is the same I am doing, perhaps it is different. I use 3 probes. So, >make sure, the number_of_entries is a multiple of 3. The first index then is >index = hashkey(I use one 32 bit half of it)%(number_of_entries/3). Of course >the division by three, will only be done once, when initializing or resizing the >HTs. BTW. If you unroll the n probes, on x86 platform using index, index+1 and >index+2 may yield in slightly more efficient code, than the index++. Similar if >you use pointers HASHENTRY *hp = hash_mem + hash_key%size_div_by three. >Accessing hp[0], hp[1] and hp[2] may be faster, than issuing a hp++ in between, >because (depending on the size of an entry) the x86 adressing modes may handle >the offset directly in the instruction. > >Regards, >Dieter hi dieter, why do you have to make sure that the index is a multiple of N when you do N probes? i don't do that, and i don't really see a reason to do it. you can say that you want all positions which belong in a "bucket" to really be in there. but i don't see the problem of just doing index+1, index+2,... index+N-1 instead of first doing index=index-(index%N)? aloha martin
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.