Author: Don Dailey
Date: 22:33:50 01/21/98
Go up one level in this thread
Hi Bob, I know there is no one trying to find a free space. But whatever the goal the two are equivalent in some sense. The question is what are the odds of getting an appropriate (whether empty or a better location to overwrite) entry quickly. If you use set associativity it's pretty much moot (which I agree is the way to go) but this discussion is quite interesting. I just figured out that there is indeed a higher likelyhood of not getting an appropriate entry on the second try with linear probing and open addressing. Wherever a used entry exists in the table, there is greater likehood of an immediate neighbor in the direction of your probe. But the interesting feature of this is that your likelihood of getting a writable location (or free spot if you're looking at it this way) increases with each probe if you are using linear addressing and STAYS EXACTLY the same with rehashing! I suspect the 2 effects cancel each other to give same average behavior but I could be completely wrong about this, it's just a guess. - Don On January 21, 1998 at 21:47:00, Robert Hyatt wrote: >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.