Author: Sune Fischer
Date: 03:23:39 06/21/02
Go up one level in this thread
On June 21, 2002 at 06:13:05, Koundinya Veluri wrote: >On June 21, 2002 at 05:52:25, Sune Fischer wrote: > >>On June 21, 2002 at 05:47:47, Koundinya Veluri wrote: >> >>>On June 21, 2002 at 05:12:28, Sune Fischer wrote: >>> >>>>On June 21, 2002 at 04:01:41, Sven Reichard wrote: >>>> >>>>>Maybe I'm missing something here, but if you furthermore agree to use a hash >>>>>table of size 2^i, i <= 32, you can replace all mods, divs and muls by a 32 bit >>>>>'and'. The performance hit of the slightly smaller table (less than factor 2) >>>>>should be outweighed by the faster access. >>>>> >>>>>just my 2 bits >>>> >>>>How do you know that? >>>>If you use power 2 size then you get pretty big jumps; 64,128,256,512. >>>>So you really have only 4 sizes of the hash. I think it is better to use 200 MB >>>>with modulo than 128 MB with AND (there are not divs or muls), the save is not >>>>_that_ much compared to what you save when getting those extra hashhits. >>>>Of course I don't _know_, I'm just guessing :) >>>> >>>>Some claim the distribution of the keys are better if the number of entries is >>>>prime, though I'm not convinced of that I can't rule it out. >>>> >>>>just my two øre. >>>>-S. >>>> >>>>>Sven. >>> >>>If you use two hash tables that use power 2 size, then there will be many more >>>total hash sizes to choose from. If you have 200 MB available, you can divide >>>that into 128 MB for one and 64 MB for the other, that's 192 MB total. >>> >>>Koundinya >> >>Then you would also need to do two memory lookups, so there goes your saving :) >> >>-S. > >I thought so too, but my program doesn't slow down much, maybe because it gets >low nps rates in the first place so that memory access is not much of a >bottleneck. But being able to use more memory isn't the only advantage of using >two tables. One table can have a higher-depth replace scheme and the other can >have an always replace scheme (as described on Bruce Moreland's chess pages) so >the second table gets many hits near the leaves. You could also do only one >lookup at a time by probing only the always-replace table near the leaves and >only the higher-depth table for the rest of the tree, or something like that to >save some lookups. > >Koundinya Funny you should mention it, I implemented that just yesterday :) I do the same except I keep them intermixed in the same table, so one entry is really two seperate hashelements. The first element is store-if-deeper and the the second store always. I always save in one or the other. The advantage is I only have to do 1 memory lookup to get access to both entries (I assume the hashelement is read in a single cacheline/whatever technoterm). Downside is the two tables must always be of equal size, I don't know if that is a major drawback, but I believe it gets outweighed by the memory save. -S.
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.