Author: Robert Hyatt
Date: 18:47:00 01/21/98
Go up one level in this thread
On January 21, 1998 at 16:00:15, Don Dailey wrote: >Stuart, > >I think the best way to resolve this is to try both ways. This >issues can sometimes get very very trickly and non-intuitive. >For instance consider: > > 1.) With linear probing, there is a definite upper bound on > the number of probes you will have to apply to find an > empty location (assuming it exists.) > > 2.) With re-hashing any number of probes less than INFINITE > is possible (but not INFINITE itself!) > >This simple reasoning tells us the two are not equivalent. Here >at MIT I have access to lot's of experts on this subject (including >Ron Rivest and Charles Leiserson) and will try to pick their >brains on this subject. > >- Don > we aren't interpreting this the same way. I am not thinking of linear addressing for finding an "empty" position. I would only look at N positions, either N consecutive, or N spaced out (strided) based on some constant that could be random. I would only consider N-way set associativity however where N is a constant. The larger N is, the better the hashing algorithm will perform, but the higher the memory bandwidth needed to fetch that large set of entries. For a PC, N can't be very big or it will choke things and the cost for fetching N will override the benefit of improved hash hits. In the case of the Cray, N can be large because of the vector loads. We generally used N=16, but also played with 32, 64 and 128 with no performance hit to speak of for loading, although beyond 16 we didn't see much improvement in hashing performance either. But I would *never* consider searching linearly for an overwritable entry. That would totally bust a PC or most any non-cray architecture... At least I wouldn't search more than N entries where N is very small on the PC.
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.