http://www.talkchess.com/forum/viewtopic.php?t=36516
is to align TT buckets to a cache-line (64 bytes). With the usual 16-byte TT entry, this should have the cache-friendly effect of loading 4 adjacent entries (slots) simultaneously. The slots can then be searched for a TT hit without invoking more cache traffic.
In testing whether my recent alignment code was correct, I somehow ended up directly measuring the times taken by TT probes.
Code: Select all
nanoseconds per TT probe
16-byte-aligned 64-byte-aligned
TT MB avg hit miss avg hit miss
2048 116 68 132 109 66 124
1024 104 61 118 98 60 111
512 93 56 106 89 56 100
256 88 54 99 85 55 95
64 78 49 88 75 49 84
32 74 46 83 69 45 77
16 66 40 74 60 37 66
8 53 33 59 48 31 52
4 33 25 35 32 24 33
2 28 24 29 28 24 28
2.66 GHz Core i5 with 8 MB L3 cache; cacheline is 64 bytes.
All searches were single-threaded, nominal 15 ply from the start position. There were about 3.2E+6 TT probes in 2.8--3.0 s.
Each run was done three times, the run with the smallest average (avg) result being chosen for the table.
Individual timings:
Code: Select all
uint64_t start = mach_absolute_time(); // the best timer on a Mac
...search up to 4 TT slots for hit
uint64_t end = mach_absolute_time();
double elapsedNanoseconds = gTimerScale*(end - start - gTimerLatency);
if ( hit )
{ gTotalTTHitProbeTime += elapsedNanoseconds;
gNumTTHits++;
}
else
{ gTotalTTMissProbeTime += elapsedNanoseconds;
gNumTTMisses++;
}
Conclusion 1: 64-byte alignment indeed has a small beneficial effect, especially on TT misses (for which all 4 slots have to be read). The effect of alignment is negligible for really small TTs, presumably because they fit entirely in L3 cache. So far, so comprehensible...
Conclusion 2: the time for a TT miss is longer than for a hit. To be expected, but why, in a huge TT, is a miss so much (nearly 2x) more expensive than a hit?
Conclusion 3: probe time increases remorselessly with the size of the TT, this effect being much larger than the piddling result of alignment. Hmmm, that's unexpected. What would cause it?
Robert P.