Author: Sven Reichard
Date: 02:55:59 06/21/02
Go up one level in this thread
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.
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.