Author: Gian-Carlo Pascutto
Date: 13:40:14 08/08/02
Go up one level in this thread
On August 08, 2002 at 16:33:10, Dann Corbit wrote: >On August 08, 2002 at 16:17:37, Gian-Carlo Pascutto wrote: > >>On August 08, 2002 at 16:16:17, Aaron Gordon wrote: >> >> >>>Indeed. This is why I am stressing people have high memory bandwidth so they >>>can have large hash tables w/o taking much of a performance hit. >> >>Why would high memory bandwith have any relation to the performance >>of large hashtables? >> >>Regardless of the size of the hashtable, the amount of data is constant >>and very small. > >Most hashtable hits will not be in cache. That is the tragedy of hashing. In >fact, if similar (but different) positions have similar hash values, then your >hash is probably severely broken. Therefore, every hash lookup will be a probe >of main memory (and every hash store a write to main memory). The on-CPU cache >will never save you. Therefore, if you do a million-million probes in a long >search and a similar number of stores, the memory speed is going to be very, >very important. The latency will be important, yes, because you will spend the time waiting for the data to come from the main memory. But bandwidth? Each probe will be exactly the size of one cacheline or a small multiple thereof. You're not moving huge continous chunks of RAM back and forth in hashing, but randomly distributed tiny amounts of data. What will determine your speed is not the bandwith but the latency. -- GCP
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.