Author: Robert Hyatt
Date: 12:27:01 01/20/98
Go up one level in this thread
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...
This page took 0.01 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.