Computer Chess Club Archives




Subject: Re: Can Someone Rename This Thread? (was: is the

Author: Robert Hyatt

Date: 08:27:43 08/10/98

Go up one level in this thread

On August 06, 1998 at 13:27:23, fca wrote:

>On August 04, 1998 at 15:57:37, Robert Hyatt wrote:
>>On August 04, 1998 at 12:15:45, Bruce Moreland wrote:
>>>On August 04, 1998 at 11:34:15, Robert Hyatt wrote:
>>>>The most direct way of probing a table of N words, where N is not an
>>>>exact power of to is this:
>>>>address=key % N;
>>>>where % is the "modulo" operator in C.  if N is an exact power of 2,
>>>>you can replace this by
>>>>address=key>>(log2 N);
>>>The compiler should know what to do if you use a constant value of N.  If you
>>>don't, you can subtract one and complement it someplace ( N = ~(N-1) ), and then
>>>just say
>>>address = key & N
>>>This is splitting hairs though.
>>I do the latter, because my hash size is dynamic.  But key&mask only works
>>if this is a power of two, of course, which is why the % operator is needed
>>for oddball hash sizes.
>Trying to split the split hair, would it be faster still (however minutely) to
>have different bits of probing code to cover the (0) 2^n and the (1) oddball
>case, as determining the 0/1 "typing" of the max. hash size need only be done
>when it changes?
>Or have I missed something, which is more likely?

I don't like the "test" because it implies a branch, and branches are unfriendly
to deep pipeline architectures like the pentium pro and pentium/II.  It could
certainly work, and I doubt if it would be significantly slower with an extra
text to check for oddball hash sizes and use the right "formula."

>Also, is it implicit that the drawback of slightly slower probing is outweighed
>by the advantage of excess hash over a 2^n threshhold?  Or is there a region
>(0,k) above a 2^n threshhold where it is better to leave the hash at 2^n rather
>than at k+2^n?
>Or have I missed something here too, which is more likely?

An example:  in Cray Blitz, our basic hash entry let us set a hash table that
was as big as 3/4 of physical memory (same in crafty, although the hashing
algorithm is different).  That leaves 1/4 for the operating system, program,
pawn hash (and in Cray Blitz, king safety hashing).  IE by the time you adjust
those as well, you can use 3/4 of memory, plus 1/8 for king safety, plus 1/16th
for pawn hashing, leaving 1/16th for O/S and program and data.  So there's not
much to work with if the goal is to fill everything up...

>Kind regards
>PS: apologies as my terminology is doubtless non-std.

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.