Computer Chess Club Archives




Subject: Re: Non power of two hash table sizes

Author: Dieter Buerssner

Date: 04:26:25 02/20/02

Go up one level in this thread

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

>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.


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.