Author: Stuart Cracraft
Date: 13:12:36 01/20/98
Go up one level in this thread
On January 20, 1998 at 15:27:01, Robert Hyatt wrote: >On January 20, 1998 at 14:15:22, Stuart Cracraft wrote: > >>Instead of linear rehashing, how about this. >> >>Include an extra field in the transposition table >>for a linked-list index. This index points to the >>next transposition table entry in the group of 8 >>hash slots that constitute the rehash sequence. >> >>Then, when a probe or put fails, don't just linear >>rehash. Instead, in the put case, generate a random number >>between 0 and the maximum index into the transposition table. >>Store this in the index field if the put fails at the >>current index and loop if necessary. In the probe case, >>just follow the linked list through the various slots that >>are (randomly) linked together, looking for a probe match. >> > >use the Cray Blitz approach. Use a different N bits from the >hash signature to produce this index. Then it will be different >depending on the initial probe signature, but will be constant for >all probes using that same signature. > >But on a PC this is bad... because cache fills are done 32 bytes at >a time. if you probe twice to two different addresses, you replace >two lines of cache and it costs you two cache miss penalties. If you >probe to two consecutive hash entries, you will get one cache miss >penalty and run faster... > > > >>The idea is that a linear rehash algorithm will always >>block quickly if the same position(s) are hashing to the >>same address. But in a random rehash algorithm, this >>is less apt to happen since a random address will be chosen >>that may not be already occupied, permitting storage instead >>of collision. >> >>Anyone tried this one? >> >>--Stuart > > >yes. it's old news. And a data structures course would call this >the "hash collision chain problem". rehashing eliminated chains, but >produces more cache thrashing... the latter is more important on a PC >that already has poor memory bandwidth... I think I'll goahead and design the code and try it on the PC and on a non-PC Unix just to see. At the worst, I can leave in an #ifdef around the random rehash so it can be used for non-PC's and linear used for PC's. Thanks for the idea of using different masks from the hash key instead of calls to random. That's going to be faster. --Stuart
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.