Author: Koundinya Veluri
Date: 03:40:20 06/21/02
Go up one level in this thread
On June 21, 2002 at 06:23:39, Sune Fischer wrote: >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. Interesting idea. I tried something like that but not with hash tables. In an attack function I need to do about 7 table lookups. 5 of those lookups can be merged into a struct, so I did that, hoping that the whole struct element would be read in as a single table lookup (the element fits in 5 bytes). Unfortunately there was no difference :( It would have been nice to reduce 5 lookups to 1 or even 2... Koundinya
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.