Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: is the

Author: Robert Hyatt

Date: 08:34:15 08/04/98

Go up one level in this thread


On August 04, 1998 at 06:49:36, Don Dailey wrote:

>
>>Something I still don't understand here. Some programs let you put in increments
>>of hash tables in their menu that are not powers of 2. Rebel 9 has increments of
>>2,2.5,3,4,5,6,10,13 etc.  for example. For long analysis, if you have large
>>enough hash tables you can indeed have a program that is 40-50 points stronger
>>than one with small hash tables.
>>--
>>Komputer Korner
>
>
>Most programs have hash table sizes that are a power of 2 because it is
>convienent to create an adress key with no expensive operators.  But
>there is no reason you couldn't have a table of any given size with
>very minor modifications to a chess program.  The extra time spent
>creating an address key is probably not even noticable with modern
>processors but was back in the early days when a division might have
>consumed tens of clock cycles.  It seems like the early PC's took
>around 80 cycles, but I might be remembering something else.
>
>
>If your hash table sizes are not large enough, there your program will
>indeed benefit from bigger tables.  A general rule of thumb which has
>been talked about on this group before, is that you will get 6-7 percent
>speedup if you double the hash table size.  This is only if the program
>is starved for hash table space.  A "half doubling" which is about
>41 percent more nodes would give you half this speedup or about a 3
>percent speeup.  So there is no overwhelmingly strong motivation to
>provide fine tuning of these sizing although it could make a
>significant difference if you had almost enough memory to double
>the hash table but just barely under.    In this case you might be
>missing about 5% which you might consider significant (I know I will
>work pretty hard to get a 5% speedup in my chess program)
>
>Anyone can do this experiment.  Set your hash table size small and
>time about 10 random positions pretty deeply.  Double your hash table
>size and time them again.  Note the average speedup of each position
>separately and average them together.  At some point you will stop
>seeing a benefit (when the tables are big enough.)   When you reach
>this point, you could do another test with a much longer search and
>you will see that you could indeed benefit from even bigger tables.
>The deeper the search, the bigger the tables you will need to get
>maximum benefit.  There is always a very sharp point of diminishing
>returns once they are large enough and extra memory after this is
>wasted.
>
>To find the approximate best minimal size at 40/2, you should set up
>positions that take between 5 and 10 minutes to achieve some depth
>and try to figure out what the optimal size is to accomodate this.
>Many searches at 40/2 (especially with toot'ing) will take 10 minutes
>or more depending on your opponents time allocation style and the
>programs time control algorithms.
>
>- Don



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);

On every architecture I know of, >> is faster than an integer divide,
particularly when you want the remainder.  But I don't use this because
of my Cray background...  for those not knowing, Cray has *no* integer
divide, which means the "mod" function is horribly slow...  slow as in
taking maybe 100 clock cycles or so, because you have to do some conversions
and subtractions to get the remainder.

In any case, no matter what, when counting cpu cycles, >> beats % every
time, and by a significant amount.  And the mod (remainder) function needs
three registers, dividend, divisor and remainder, while shift only needs
2, making the optimizer's job a little easier, particularly on an intel
when we only have 8 registers to use (since no one is using MMX stuff
yet.)

Whether the saving of >> over % is important or not is a good question.  It
is probably a fraction of a percent now...



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.