Author: David Blackman
Date: 02:15:06 08/17/99
Go up one level in this thread
On August 16, 1999 at 12:05:01, Robert Hyatt wrote: >it is one method of handling collisions (collision here means two different >entries want to be stored in the same table location.) 8 probe means you try >8 different table entries (this is sometimes called a 'bucket approach') and >replace the least-useful one of those. It works well on machines with lots of >memory bandwidth, but less well on a PC. It can be very effective if you have >a table that is too small, for example... > >On large-memory machines, it loses its edge and can actually slow you down, >since 8 probes into a hash table for every store/lookup call is not exactly >free... If you make your 8 probes to consecutive entries in the hash table, starting with one that is divisible by 8, and you make your hash table entry size so that 8 entries is exactly the size of one first level cache line, then the penalty will most likely be too small to measure. This is because each hash access costs exactly one main memory access (which is probably what it would cost anyway) and for most programs, that's a lot more than the cost of what you do to the data once you've got it. Of course the trade offs on a Cray were different. No cache, and most odd-stride access patterns were about as fast as sequential access?
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.