Author: KarinsDad
Date: 21:31:40 01/21/99
Go up one level in this thread
On January 21, 1999 at 23:46:27, Robert Hyatt wrote: >On January 21, 1999 at 19:04:21, KarinsDad wrote: > >>On January 21, 1999 at 12:37:32, Heiner Marxen wrote: >> >>[snip] >> >>> >>>Another method (which I happen to use) to avoid bucket overlaps >>>is ``quadratic rehashing´´. Instead of using a constant increment, >>>we linearly increase the steps: inc=1,2,3,4,5,... >>> >>>XX.X..X...X....X >>>.YY.Y..Y...Y....Y >>>..ZZ.Z..Z...Z....Z >>> >>>Also, the slots of a bucket are still somewhat nearby, which is good >>>for cache locality. >>> >>>Knuth seems to not mention this method, and I do not remember where >>>I found it, so I cannot give a reference. >>> >>>Heiner >> >>I like this. I think I'll try this out. However, I think it needs a modification >>due to the following possiblity: >> >>XX.X..X......... >>YY.Y..Y...Y..... >>ZZ.Z..Z...Z....Z >> >>Thanks Heiner :) :) >> >>KarinsDad > > >Just note this will kill a PC. Because it fetches 32 byte lines from memory in >a burst cycle. for best performance you should use all those 32 bytes since you >had to wait on them. If you do anything else, you will end up hitting one line >per probe with a big cache miss penalty for each probe. > >This only works on architectures like the Cray where memory is organized a lot >differently with no cache of any kind... just high sustained thruput.. Robert, Thanks for the input. I have been thinking about this method a little bit this evening and although I came up with some good ideas, I keep pounding into the problem of 95% of the hash is full, how can I continue to find open slots without overwriting the nodes (for my program, this would currently be more preferable)? It may not be solvable this way, or at least not in a reasonable amount of time. On the other hand, each of the solutions in this thread seem to run into that problem to some extent. KarinsDad :)
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.