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.