Author: Robert Hyatt
Date: 05:52:52 01/22/99
Go up one level in this thread
On January 22, 1999 at 00:31:40, KarinsDad wrote: >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 :) You can't go very far here. Because you probe at _every_ node in the tree. If you make your probe 10x slower by looping, you will _really_ feel the slow-down, and it isn't clear that getting too cute is important, when you can buy a gig of memory for about $1,000 now...
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.