Author: KarinsDad
Date: 11:47:53 01/19/99
Go up one level in this thread
On January 19, 1999 at 14:16:54, Eugene Nalimov wrote:
>On January 19, 1999 at 13:06:33, Bruce Moreland wrote:
>
>>
>>On January 19, 1999 at 08:13:52, Robert Hyatt wrote:
>>
>>>On January 18, 1999 at 19:01:01, Dann Corbit wrote:
>>
>>>(2) use some form of hash 'buckets'. IE in cray blitz,
>>>I took the low order N bits of the hash signature as the probe address. I took
>>>the next 10 bits as a 'rehash offset'. (call this RO). I then checked the
>>>positions at offset, offset+RO, offset+2RO, ... offset+7RO. Either approach is
>>>ok. The latter tends to solve the 'chaining' problem because two different
>>>hash keys identical in the last N bits (probe address) still may be different in
>>>the next 10 bits, giving a different 'bucket'.
>>
>>I have never understood this logic, and would like to discuss it.
>>
>>The situation is that you get a collision at one point in the table, and the
>>question is where to rehash to.
>>
>>I would like to ask why not just set RO to some constant, for instance one.
>>You've got a collision in a table that will tend to be full, I don't understand
>>why the element at some random location in the table is more likely to be empty
>>or unimportant than the one at the next index in the table.
>>
>> for (;;) {
>> if (FOverwrote(index))
>> return;
>> index = (index + 1) % tabsize;
>> }
>>
>>As opposed to:
>>
>> ro = (key >> N) & 2047;
>> for (;;) {
>> if (FOverwrote(index))
>> return;
>> index = (index + ro) % tabsize;
>> }
>>
>>I don't see what you get for your extra instructions.
>>
>>bruce
>
>Linear rehash results in large clusters of non-empty elements.
>The element that conflicts with *any* element in the cluster
>will be added to that cluster, so big cluster will be bigger
>and bigger over the time. With non-linear rehash conflicting
>elements will be added to other clusters. You can find
>discussion, analysis, and experimental results in
>
> D. Knuth, The Art of Computer Programming, Vol.3,
> 2nd edition, pp. 526-531.
>
>(the data is there in the 1st edition, too, but page numbers
>are different).
>
>At least that will happen with classic hash table, without limit
>on the # of retries. When there is such a limit I don't know what
>will happen, but suspect that when that limit is large enough
>(e.g. 8), non-linear rehash will be better (in the terms of hash
>table collisions), too - almost all assumptions are the same as in
>the classic case.
>
>From the other side, non-linear rehash tends to greatly increase #
>of L2 cache misses. For reasonable chess program and reasonable L2
>cache size the only L2 cache misses during search will happen
>during hash table probing. Several cache misses in a row easily
>can cost hundreds of CPU ticks.
>
>Eugene
Eugene,
I believe that this is one of the most non-ambiguous and informative responses
that I have ever read concerning a topic on this message board.
Even though I was not in this thread previously, I appreciate it when people are
clear and concise (and adding a reference did not hurt either).
And Bruce, your question and code sample were very helpful in understanding the
issue as well.
Thanks :) :)
KarinsDad
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.