Computer Chess Club Archives




Subject: Re: Non power of two hash table sizes

Author: Robert Hyatt

Date: 08:25:02 02/21/02

Go up one level in this thread

On February 20, 2002 at 07:26:25, Dieter Buerssner wrote:

>On February 20, 2002 at 01:14:12, Eugene Nalimov wrote:
>>Wrong. On the CPU I am currently working with:
>>Integer division:    ~40 clock cycles.
>>L1/L2/L3 cache miss: ~150-200 clock cycles.
>How many clock cycles is an integer multiply (32*32bits -> 64 bits, mul) on
>modern x86 hardware, or on your hardware?
>How about a floating point multiplication, or fimul and integer store of a
>floating point number? (One could take 32 bits of the hash key, and multiply it
>by numbers_of_entries/2^32. The later would of course be a precomputed number,
>and would be exact (no rounding) on IEEE FP-Hardware).

This is problematic.  You can't take a random 32 bit value and stuff it into a
FP register.  You can end up with NaN values, +/- infinity, and other such
numbers (denormals, etc) that will cause the multiply to fail.

First version of Crafty used double precision values for the bitmaps and it
failed badly for that reason...

>>40 is of course less than 150, but I would not call it "negligible".
>In the context of the total performance of my chess engine, I found it neglible.
>One could even do some optimization with multiplication instead of the & method,
>in the case of non power of two sizes of one hash bucket, by factoring in the
>size into the multiplicator, and some char * to hash_entry * casting.

The reason I don't use that either is that some machines don't have an integer
multiply either.  And since (for Crafty) portability is the issue, I have tried
to stay with things that work fast on _all_ machines, not just on the PC or
the Cray, for example...

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.