Author: Robert Hyatt
Date: 19:24:57 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 :) If you _insist_ on finding an empty position in the table, then back to Knuth's The art of programming again... Your only choice is is multiple probes. And you really don't want to probe successive addresses now since you are committed to storing if at all possible... even though we are going to violate cache guidelines, because you are going to run into huge 'chaining' problems. I recommend you use the same thing we used in Cray Blitz (from Knuth of course) and just use 'other' bits from the hash signature as a random (but constant for a given probe) offset. If you want to really get cute, you should take this random offset, and round it to the nearest 'near-prime'. In this case, 'near- prime' is a number that is 'prime' relative to the size of your hash table. You do this to be sure that you touch 'every' table entry one time before you touch any table entry twice. If you don't do this, you obviously run the risk of not trying every entry, which means you might not find a suitable position to overwrite... let me know if I wasn't clear enough...
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.