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

[JuLieN]

I was curious to see if the boost a hash table gives to the speed of perft would be of geometrical progression while one increase the hash's size, or if, as I was suspecting, there would be a diminishing return. And indeed there is a diminishing return, as my test shown:

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.

[syzygy]

I was curious to see if the boost a hash table gives to the speed of perft would be of geometrical progression while one increase the hash's size, or if, as I was suspecting, there would be a diminishing return. And indeed there is a diminishing return, as my test shown:

For a perft of fixed size there is necessarily a limit to what you can gain even from a hashtable of infinite size.

I think "nodes per second" is a misleading measure in this context.

[Sven]

I was curious to see if the boost a hash table gives to the speed of perft would be of geometrical progression while one increase the hash's size, or if, as I was suspecting, there would be a diminishing return. And indeed there is a diminishing return, as my test shown:

For a perft of fixed size there is necessarily a limit to what you can gain even from a hashtable of infinite size.

I think "nodes per second" is a misleading measure in this context.

The measurement itself is o.k. but my usual comment at this point is that I would call it "leaves per second", as opposed to "visited nodes per second".

Sven

[JuLieN]

I was curious to see if the boost a hash table gives to the speed of perft would be of geometrical progression while one increase the hash's size, or if, as I was suspecting, there would be a diminishing return. And indeed there is a diminishing return, as my test shown:

For a perft of fixed size there is necessarily a limit to what you can gain even from a hashtable of infinite size.

I think "nodes per second" is a misleading measure in this context.

The measurement itself is o.k. but my usual comment at this point is that I would call it "leaves per second", as opposed to "visited nodes per second".

Sven

Exact: it's also called a "bulk counting" (because I use perft to tune my move generator, not the make/unmake.)

[petero2]

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.

[JuLieN]

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.

That's weird! I get a x8.7 "nps" from an 1MB hash to a 5120MB one, while you get only a x2. As perft is quite deterministic I guess the test conditions are different. For instance your perft is probably multi-threaded, right ? (I'm currently working on making my engine multi-threaded, so I'll soon be able to test with 8 threads...)

[petero2]

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.

That's weird! I get a x8.7 "nps" from an 1MB hash to a 5120MB one, while you get only a x2. As perft is quite deterministic I guess the test conditions are different. For instance your perft is probably multi-threaded, right ? (I'm currently working on making my engine multi-threaded, so I'll soon be able to test with 8 threads...)

My perft program can use multiple threads but was only using 1 thread in this test. However, being a dedicated perft program, it has a specialized hash table implementation. There is a separate hash table for each depth. Each table size is a power of two, but not all tables need to have the same size. Within each table I use an "always replace" strategy.

For example, with a 128KB table I get:

Code: Select all

Depth   Entries      Inserts       Probes         Hits  Hits/probes
 1         2048   1870452696   2085441610    215004619     0.103098
 2         2048     76891438     87767456     10876361     0.123922
 3         2048      3571572      4116774       545212     0.132437
 4         1024       166244       180772        14528    0.0803664
 5         1024         8161         8902          741    0.0832397

With a 1MB table I get:

Code: Select all

Depth   Entries      Inserts       Probes         Hits  Hits/probes
 1        16384    537519380    758333671    220820378     0.291192
 2        16384     27976314     37905378      9929294     0.261949
 3        16384      1540343      2076625       536291     0.258251
 4         8192        83442       126939        43497     0.342661
 5         8192         5743         8902         3159     0.354864

With a 16MB table I get:

Code: Select all

Depth   Entries      Inserts       Probes         Hits  Hits/probes
 1       262144    310535650    477465453    166937941     0.349634
 2       262144     17482888     27508400     10025683     0.364459
 3       262144      1116348      1798981       682642      0.37946
 4       131072        72137       118584        46447      0.39168
 5       131072         5365         8902         3537     0.397326

With a 5120MB table I get:

Code: Select all

Depth   Entries      Inserts       Probes         Hits  Hits/probes
 1    134217728    102662350    256993050    154338332     0.600554
 2    134217728      9418303     20200794     10782641     0.533773
 3     33554432       822669      1797389       974731     0.542304
 4     16777216        72078       118522        46444      0.39186
 5     16777216         5362         8902         3540     0.397663

From this it can be seen that even 1MB hash is enough to get close to perfect hit rate for depth 4 and 5.

[JuLieN]

Peter, your faster results come from your move generator, which is about ten times faster than my engine's as the test without hash table shows. Then your result with hash table are less good than my engine's (from 0 to 5120MB you get a x8.5 when I get a x11). Could you try with my simpler hash mechanism, if it's not too heavy a modification ? I also have an "always replace" hash, but with only one big hash table. My keys are produced by xoring the position's key with the depth ( I have an unsigned long long depth_zobrist[256] array).

[petero2]

Peter, your faster results come from your move generator, which is about ten times faster than my engine's as the test without hash table shows. Then your result with hash table are less good than my engine's (from 0 to 5120MB you get a x8.5 when I get a x11). Could you try with my simpler hash mechanism, if it's not too heavy a modification ? I also have an "always replace" hash, but with only one big hash table. My keys are produced by xoring the position's key with the depth ( I have an unsigned long long depth_zobrist[256] array).

That performs significantly worse in my tests. I get the following:

Code: Select all

       MB   entries time(s) perft(8)/time
   0.0000         0  327.09     259868000
   0.1250      8192  297.69     285533000
   1.0000     65536  225.75     376522000
  16.0000   1048576  164.30     517353000
 128.0000   8388608  102.26     831221000
 512.0000  33554432   64.53    1317200000
4096.0000 268435456   37.84    2246510000

The reason my "no hash" case runs faster than yesterday is likely because yesterday 3 of 4 cores were busy doing other things but today only one other core is busy. Therefore turbo boost helps more today. The hash hit rate statistics look like this:
128KB:

Code: Select all

Depth   Inserts       Probes         Hits  Hits/Probes
 1   2350043287   3145689978    795680833     0.252943
 2    117061868    119060137      1998392    0.0167847
 3      4865601      4865609            8  1.64419e-06
 4       197281       197281            0            0
 5         8902         8902            0            0

1MB:

Code: Select all

Depth   Inserts       Probes         Hits  Hits/Probes
 1   1491314821   2612267181   1121015803     0.429135
 2     96792778    118269863     21477736     0.181599
 3      4831679      4865609        33930   0.00697343
 4       197281       197281            0            0
 5         8902         8902            0            0

16MB:

Code: Select all

Depth   Inserts       Probes         Hits  Hits/Probes
 1    693721594   1411259923    717583908      0.50847
 2     52093639     92709631     40617699     0.438117
 3      3770065      4797641      1027588     0.214186
 4       194343       197281         2938    0.0148925
 5         8902         8902            0            0

512MB:

Code: Select all

Depth   Inserts       Probes         Hits  Hits/Probes
 1    194212369    468454548    274259022     0.585455
 2     17305764     36279245     18974080     0.523001
 3      1472448      2729211      1256795     0.460498
 4       109961       176219        66259     0.376004
 5         7951         8902          951      0.10683

4096MB:

Code: Select all

Depth   Inserts       Probes         Hits  Hits/Probes
 1    105937835    270217934    164288994     0.607987
 2      9909348     22333759     12424733     0.556321
 3       908819      1868360       959553      0.51358
 4        74941       130603        55662     0.426192
 5         5902         8902         3000     0.337003

The main problem with this hash implementation is that because of the high branching factor for perft, you need a very large table in order to get good hit rate for the larger depths.

The reason you get a larger speedup with hashing than I do is likely because with a faster move generator you gain less by hash hits because the speed of RAM is still the same.

[lucasart]

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 ?