Influence of the hashtable's size on perft's speed

[petero2]

How to best parralelize your perft, how to best implement a hash replacement strategy for perft, making special program that do perft only in a super tuned way, etc.

Interesting questions :)

This inspired me to make some more tests and it turns out that for my perft program it is better to keep the table for depth=1 small enough to fit in L3 cache. Some results:

Code: Select all

  MB  d1 KB time(s) perft(8)/time
   0      0  317.25     267926000
 512    256   29.14    2917220000
 512    512   29.02    2928580000
 512   1024   28.18    3016070000
 512   2048   27.90    3046120000
 512   4096   27.16    3129220000
 512   8192   29.98    2835000000
 512    Inf   40.99    2073700000

My CPU has 8MB L3 cache and 4 HT capable cores. 4MB for the d=1 table is best and it also works ok with more than one thread:

Code: Select all

Threads time(s) perft(8)/time
      1   27.16    3129220000
      2   14.70    5782640000
      4    8.39   10134600000
      8    8.09   10511900000

This can be compared to the old hash method with no special limit on the d=1 table:

Code: Select all

Threads time(s) perft(8)/time
      1   38.58    2202960000
      2   19.92    4267870000
      4   10.80    7873920000
      8    8.77    9687600000

[JuLieN]

Thanks for your test, Peter. That's very interesting. My own hash hits rate with my monolithic 5120GB HT is of 61.6995%. Not so bad.

[ibid]

Code: Select all

┏━━━━━┳━━━━━━━━━━━┳━━━━━━━┳━━━━━━━━━━━┓
┃  MB ┃  Entries  ┃time(s)┃    nps    ┃
┣━━━━━╋━━━━━━━━━━━╋━━━━━━━╋━━━━━━━━━━━┫
┃ 0   ┃          0┃3036.76┃ 27,990,037┃
┃ 1   ┃     65,536┃2373.03┃ 35,818,711┃
┃ 2   ┃    131,072┃2134.91┃ 39,813,925┃
┃ 4   ┃    262,144┃1908.80┃ 44,530,028┃
┃ 8   ┃    524,288┃1713.45┃ 49,606,808┃
┃ 16  ┃  1,048,576┃1413.82┃ 60,120,054┃
┃ 32  ┃  2,097,152┃1198.26┃ 70,935,378┃
┃ 64  ┃  4,194,304┃ 991.71┃ 85,709,924┃
┃ 128 ┃  8,388,608┃ 809.75┃104,970,047┃
┃ 256 ┃ 16,777,216┃ 660.71┃128,648,562┃
┃ 512 ┃ 33,554,432┃ 524.94┃161,922,486┃
┃ 1024┃ 67,108,864┃ 420.87┃201,958,189┃
┃ 2048┃134,217,728┃ 325.98┃260,751,147┃
┃ 4096┃268,435,456┃ 277.55┃306,246,938┃
┃ 5120┃335,544,320┃ 273.92┃310,309,462┃
┗━━━━━┻━━━━━━━━━━━┻━━━━━━━┻━━━━━━━━━━━┛

The test was a "perft 8" from the starting position, with my engine (one thread). MB = the hashtable's size in MB; Entries = how many entries there are in the hashtable (size / 16bytes); time : time the computation took, in seconds; nps : "nodes" per second.

My results are quite different:

Code: Select all

       MB   entries time(s) perft(8)/time
   0.0000         0  340.98     249281000
   0.0625      4096  300.88     282502000
   0.1250      8192  234.50     362463000
   0.2500     16384  151.69     560336000
   0.5000     32768  100.64     844601000
   1.0000     65536   79.70    1066490000
   2.0000    131072   69.78    1218030000
   4.0000    262144   64.57    1316410000
   8.0000    524288   61.89    1373450000
  16.0000   1048576   54.74    1552830000
  32.0000   2097152   52.37    1623050000
  64.0000   4194304   48.94    1736760000
 128.0000   8388608   42.58    1996080000
 256.0000  16777216   40.94    2076230000
 512.0000  33554432   40.89    2078880000
1024.0000  67108864   40.23    2112670000
2048.0000 134217728   39.75    2138120000
4096.0000 268435456   39.38    2158540000
5120.0000 335544320   39.82    2134790000

Even a very small hash table helps quite a bit and there is little to be gained by going above 256MB.

For what it's worth, gperft with one thread:

Code: Select all

  MB  seconds
   0  200.829
   2   43.452
   4   41.349
   8   38.067
  16   33.220
  32   27.681
  64   23.250
 128   20.743
 256   19.650
 512   19.421
1024   19.427
2048   19.527
4096   19.745
5120   19.953

[ibid]

Again, but including perft 9 and 10 to stress the hash tables a bit more -- this time with 6 threads. Time savings for each hash table doubling and multipliers from one ply to the next included. I didn't have the patience to do perft 10 with no hash table. I'd like to see 11 ply also, but it'd take a while...

Code: Select all

  MB    perft 8  change     mult    perft 9  change     mult   perft 10  change
   0     33.504           x28.24    946.077
   2      8.396           x23.18    194.639           x27.61   5374.213
   4      7.708  -8.93%   x20.94    161.410 -20.59%   x24.55   3962.218 -35.64%
   8      6.969 -10.60%   x18.99    132.309 -21.99%   x23.31   3084.097 -28.47%
  16      5.962 -16.89%   x17.20    102.556 -29.01%   x23.00   2359.273 -30.72%
  32      4.938 -20.74%   x15.86     78.296 -30.98%   x21.33   1670.370 -41.24%
  64      4.138 -19.33%   x15.72     65.060 -20.34%   x19.43   1264.186 -32.13%
 128      3.680 -12.45%   x15.97     58.772 -10.70%   x18.45   1084.249 -16.60%
 256      3.489  -5.47%   x15.94     55.618  -5.67%   x18.00   1001.332  -8.28%
 512      3.443  -1.34%   x15.35     52.843  -5.25%   x17.50    924.665  -8.29%
1024      3.440  -0.09%   x14.27     49.094  -7.64%   x16.93    831.219 -11.24%
2048      3.455  +0.43%   x12.87     44.467 -10.41%   x15.96    709.733 -17.12%
4096      3.496  +1.17%   x11.91     41.621  -6.84%   x14.51    604.059 -17.49%

Some of the quirky numbers are probably due to the fact that gperft uses half the memory for 2-3 ply and half for 4+ ply -- so the speedups are a combination of two factors.

[JuLieN]

Again, but including perft 9 and 10 to stress the hash tables a bit more -- this time with 6 threads. Time savings for each hash table doubling and multipliers from one ply to the next included. I didn't have the patience to do perft 10 with no hash table. I'd like to see 11 ply also, but it'd take a while...

Code: Select all

  MB    perft 8  change     mult    perft 9  change     mult   perft 10  change
   0     33.504           x28.24    946.077
   2      8.396           x23.18    194.639           x27.61   5374.213
   4      7.708  -8.93%   x20.94    161.410 -20.59%   x24.55   3962.218 -35.64%
   8      6.969 -10.60%   x18.99    132.309 -21.99%   x23.31   3084.097 -28.47%
  16      5.962 -16.89%   x17.20    102.556 -29.01%   x23.00   2359.273 -30.72%
  32      4.938 -20.74%   x15.86     78.296 -30.98%   x21.33   1670.370 -41.24%
  64      4.138 -19.33%   x15.72     65.060 -20.34%   x19.43   1264.186 -32.13%
 128      3.680 -12.45%   x15.97     58.772 -10.70%   x18.45   1084.249 -16.60%
 256      3.489  -5.47%   x15.94     55.618  -5.67%   x18.00   1001.332  -8.28%
 512      3.443  -1.34%   x15.35     52.843  -5.25%   x17.50    924.665  -8.29%
1024      3.440  -0.09%   x14.27     49.094  -7.64%   x16.93    831.219 -11.24%
2048      3.455  +0.43%   x12.87     44.467 -10.41%   x15.96    709.733 -17.12%
4096      3.496  +1.17%   x11.91     41.621  -6.84%   x14.51    604.059 -17.49%

Some of the quirky numbers are probably due to the fact that gperft uses half the memory for 2-3 ply and half for 4+ ply -- so the speedups are a combination of two factors.

Thanks for those figures, Paul. So there seems to be a practical size for each depth (or, put differently, for "the size of the problem"). 512 MB for pert 8, probably 4GB for perft 9, and much more for perft 10. When this size is reached, any greater hash size will actually start costing some time because its access through the comparatively slower memory bus will do more than compensate its benefits. There is certainly the same effects with a normal game tree and more tests should be able to determine what the ideal size for a certain search duration should be. Although the answer to this question is a bit more complex because there are different hash strategies and implementations for game trees.

But again, it was interesting to see the search times increase in your test past a certain hash size.

[Laskos]

I'm always surprised at how far some people go in "perft competition". How to best parralelize your perft, how to best implement a hash replacement strategy for perft, making special program that do perft only in a super tuned way, etc.

perft is nothing more than a unit test for the move generator. it is absolutely useless in itself. What would be more interesting, is to study the effect of hash size on the time to depth of chess engines, and ideally on elo. Is there a good study on that ?

Houdini 3, 150 positions, full hash filling, 36% speedup in TTD from 4MB to 128MB hash size. So, 6.3% speedup (TTD) for each hash doubling (at ~30s per position).