Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Non power of two hash table sizes

Author: Robert Hyatt

Date: 20:15:05 02/19/02

Go up one level in this thread


On February 19, 2002 at 17:45:47, J. Wesley Cleveland wrote:

>On February 19, 2002 at 10:48:25, Robert Hyatt wrote:
>
>>On February 19, 2002 at 02:36:32, Bernhard Bauer wrote:
>>
>>>On February 18, 2002 at 22:52:35, Robert Hyatt wrote:
>>>
>>>>On February 18, 2002 at 15:43:09, Alvaro Jose Povoa Cardoso wrote:
>>>>
>>>>>My program uses hash tables witch are a power of two.
>>>>>In order to compute the index to an hash table of this kind I simply do:
>>>>>  hashindex=(hashkey & hashsize)
>>>>>in witch hashsize is a mask with for example the first 12 bits set for a size of
>>>>>4096 entries.
>>>>>I would like to know how to compute the index to a hash table that can have
>>>>>sizes like 1MB, 7MB, 45MB, 49MB, 50MB, ..etc
>>>>>Could someone please explain how to do this?
>>>>>
>>>>>Thank you,
>>>>>Alvaro Cardoso
>>>>
>>>>
>>>>index = signature % hash_size
>>>
>>>If it's so easy, wouldn't it be nice to do it that way in Crafty?
>>>That way many users could use a bigger hash size.
>>>Kind regards
>>>Bernhard
>>
>>
>>It can be a killer.  For example, old SPARC machines do not _have_ an integer
>>divide instruction.  So it would kill performance.  Many newer processors do
>>the integer divide far slower than the AND I use now.
>>
>>I haven't tested the speed difference in a long time, but on the sparc where
>>Crafty started, it was huge because every divide turned into a procedure call.
>
>A division is not necessary here, e.g. (signature * hash_size) >> n where
>0 <= signature < 2**n is equivalent to signature % hash_size.


The multiply is generally no better.  Ie the hardware does a bunch of shifts
and adds which means it is just like the divide and is not a one-cycle
operation.   And the original sparcs have no integer multiply either,
unfortunately, so that also becomes a procedure call.



This page took 0.01 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.