Author: Robert Hyatt
Date: 15:49:49 01/20/98
Go up one level in this thread
On January 20, 1998 at 17:04:35, Bruce Moreland wrote: > >On January 20, 1998 at 16:10:46, Stuart Cracraft wrote: > >>My thought on this is that in the linear case, if you have several >>positions hashing to the same slot, then the chain will fill up and >>there will be more collisions preventing replacements and storage of >>incoming positions. The rand() will perturb the algorithm differently >>each time preventing collisions from filling up these hash slot >>sequences. So that's why I+rand() is more apt to be empty than I+K. > >I think it is exactly the same either way, the difference is the >illusion of "solidness" provided by seeing three elements at sequential >indexes, as opposed to seeing three elements scattered around the table, >but equally as likely to be hit by something else. > >If there is a paradox here that I don't understand, someone please let >me know. > >bruce The biggest problem with random rehashing is cache misses. I used the random rehash scheme in Cray Blitz because I did a bunch of testing and found that the hash keys are *not* uniformly distributed. They are fairly close. But *not* uniform. And that will excite some replacement strategies to overwrite differently. With our random rehash, just because the lower N bits matched perfectly, we didn't use the same "set" of hash entries for matching tests. Each "set" would get a different random offset, extracted from the other part of the hash signature... so that two hash probes to addresses N and N+2 would not share any entries at all. Any than two probes to addresses N and N+M where N is your constant increment. To use a constant M is probably worse than using 1, because of cache. But the random rehash can make small differences when hash keys should be uniform but aren't quite. I'll bug Harry to get his test results. He ran several hundred hours of tests years ago as we played with this. For our hashing it was more efficient, produced slightly better hash hits, and costs nothing on a Cray where a vector load can have a constant stride index loaded into a register... Bob
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.