Author: Ron Murawski
Date: 07:50:34 11/08/02
Go up one level in this thread
On November 08, 2002 at 09:20:44, Daniel Clausen wrote: >On November 08, 2002 at 07:40:45, Tony Werten wrote: > >>On November 08, 2002 at 04:14:34, Daniel Clausen wrote: >> >>>On November 07, 2002 at 18:03:52, Ron Murawski wrote: >>> >>>>On November 07, 2002 at 16:57:04, Martin Bauer wrote: >>>> >>>>>On November 07, 2002 at 16:08:49, Tony Werten wrote: >>>>> >>>>>>Somewhere from 8Mb you will get a 99,9% hitrate after a few seconds. >>>>> >>>>>Memory usage depends on waht I am storing, can you tell me a number of Hashtable >>>>>entries? >>>>> >>>> >>>>One less than a power of two (aka Mesenne number) entries is best, a prime >>>>number of entries is supposed to be acceptable. >>> >>>Shouldn't it be the opposite? "prime number is best but 2^n-1 is acceptable"? >> >>Don't think so. With a big table, collisions are not probable so no real >>difference there. But: 2^n-1 can be calculated with a cheap AND and prime most >>be done with an expensive mod. > >I agree that "prime" or "2^n-1" is not a big difference when it comes to >computer chess hashtables. The reason is that in CC you typically don't probe >many times (maybe up to 4). In other areas it's different though, and then the >probing algorithm is good when it ensures that the probe sequence probes all >possible array position eventually. (like with 'quadratic probing' and #slots >being prime) That's not the case in computer chess HTs though. > >In summary, I think that a prime number for #slots would still be a lil better, >but the fact the it's much cheaper to calculate the slot number (with the AND >2^n "trick") outweighs that in CC. > >Sargon I'm investigating power-of-two size vs prime size using single-probes. It's not at all apparent to me whether the smaller table used for a power-of-two size might slow down the engine more than the expensive mod instruction on a larger table would. In other words, if there are 36K slots available, power-of-two would only use 32K slots, whereas the prime size would use almost all of the 36K. Ron
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.