Author: Sune Fischer
Date: 03:03:53 06/21/02
Go up one level in this thread
On June 21, 2002 at 05:55:59, Sven Reichard 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. > >Sune, > >my comment was based on two pieces of information: > >1) It was said above that the modulus calculation was a _hot spot_, so I assume >it is taking considerable time. Of course, like everybody else, I couldn't >download the picture, so I don't know for sure how hot this spot really is. > >2) Some fairly old research papers state that the effect of doubling the table >size is about 3% for small sizes, and about 1% for large sizes. This might be >outdated (I don't have the exact reference, but it is from the early 90's), but >I made a similar observation in my program. I don't rule out that this is due to >the fact that my tables aren't too clever. > >Since I don't think that 1% is a considerable amount, this leads me to the >conclusion that it might be beneficial to restrict the size to powers of two. > >My 5 agurot back to you. :) > >Sven. Sven, I know about the numbers. I can't confirm if they hold water, I think it also depends on the duration of the search, the replacement scheme and other variables. I can tell you that the modulo operation on a integer is _faster_ than if you do a manual implementation of x%n as x-n*(int)(x/n), I tested that long ago. So I do not believe the modulo operation is a real hotspot, well maybe on 64 bit numbers, but you do not have to use those once you realize that the number of entries is less than 2^32. -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.