Author: Robert Hyatt
Date: 07:51:24 02/07/06
Go up one level in this thread
On February 06, 2006 at 18:03:12, Dann Corbit wrote: >A hash table is an O(1) data structure. That means that hash table lookups are >proportional to the number 1. Which means that no matter how large the hash >table is, the lookup requires constant time. Algorithm-wise, that is true. But there are additional considerations. For example, the well-known TLB problem. To do a virtual to real translation on an intel box requires one memory access to get the actual data, plus two more memory accesses to do the virtual to real address translation if a TLB miss happens. On the AMD, make that 4 additional memory accesses (for 64 bit systems). How big is the TLB? Varies. My older 2.8ghz xeons have 60 entries. The last opteron I ran on had 1024 entries. If you make your hash table fit inside 1024 pages on the opteron, it will be significantly faster than if you go outside that limit due to TLB thrashing. Of course, if an O/S is smart enough to use large page sizes rather than 4K pages, that helps enormously. Don't know whether windows does that or not however.. > >So if I have a trillion has slots in my hash table, a lookup take about the same >time as if I have a total of one hundred hash slots. And if the lookup fails, >then it fails. It does not look at additional entries. > >There are some hash table designs that "chain" a number of entries. Generally, >for chess programs, the chains are one or two additional entities (if chaining >is even implemented). Even so, the largest chain sequence I have ever seen >allowed in a chess program is 8 entries [I would recommend against using 8 >entries]. Now, in such cases, you are far more likely to scan longer chains in >small hash tables than large ones anyway. Also hardware dependent. On the Crays, we used 8. But on a vector machine it takes no longer to access a chain of length 8 than it does to access a single entry, effectively. For example, on a 2ns T90, it took about 50 clocks to read the first entry, 1 more clock to read the next, etc. So 57 vs 50 to read 8 vs 1. On the PC this is not going to happen of course. > >Here is an explanation of hash table: >http://en.wikipedia.org/wiki/Hash_table > >Bear in mind that chess programs do not generally chain more than one or two >entries -- they simply over-write old data with new. So the explanation on that >page is not fully correct for the usage in a chess program. But the >explanations on that page do show the general principles for how they work as >far as computation of the hash, storage into the table, and retrieval of the >stored data.
This page took 0.01 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.