toga and hash tables

[Uri Blass]

I read a claim that toga unlike other engines does not earn or almost does not earn from more hash tables relative to the default hash of 16 MB

see
http://chesstempo.com/chess-forum/gener ... 42.15.html


Richard wrote there:
"toga (at least all the versions I've looked at) seems to have almost no benefit from increased hash size (beyond the 16MB default)"

I wonder if people tested toga with different hash to see if this is correct.

questions:

1)Does toga perform better in test suites with 512 mbytes hash relative to 16 mbytes
2)Does toga perform better in games with 512 mbytes hash relative to 16 mbytes

[Kurt Utzinger]

I read a claim that toga unlike other engines does not earn or almost does not earn from more hash tables relative to the default hash of 16 MB

see
http://chesstempo.com/chess-forum/gener ... 42.15.html


Richard wrote there:
"toga (at least all the versions I've looked at) seems to have almost no benefit from increased hash size (beyond the 16MB default)"

I wonder if people tested toga with different hash to see if this is correct.

questions:

1)Does toga perform better in test suites with 512 mbytes hash relative to 16 mbytes
2)Does toga perform better in games with 512 mbytes hash relative to 16 mbytes

Hi Uru
Do you know a chess programm doing better in tests with 512 MB hash than with 128 MB or 256 MB hash?
Kurt

[Uri Blass]

I read a claim that toga unlike other engines does not earn or almost does not earn from more hash tables relative to the default hash of 16 MB

see
http://chesstempo.com/chess-forum/gener ... 42.15.html


Richard wrote there:
"toga (at least all the versions I've looked at) seems to have almost no benefit from increased hash size (beyond the 16MB default)"

I wonder if people tested toga with different hash to see if this is correct.

questions:

1)Does toga perform better in test suites with 512 mbytes hash relative to 16 mbytes
2)Does toga perform better in games with 512 mbytes hash relative to 16 mbytes

Hi Uru
Do you know a chess programm doing better in tests with 512 MB hash than with 128 MB or 256 MB hash?
Kurt

I did not test chess programs to make comparison so I do not know.

Maybe Bob Hyatt can test it.
I guess that the difference between 256 MB and 512 MB may be small
when you may need longer time control than blitz to see a difference of more than 1 elo so it is hard to prove a difference based on games.

It may be easier to prove a difference between 16 mbytes and 128 mbytes but again if we talk about games and not about test suites then it may be easy only for Bob with his cluster to test it.

Uri

[bob]

I read a claim that toga unlike other engines does not earn or almost does not earn from more hash tables relative to the default hash of 16 MB

see
http://chesstempo.com/chess-forum/gener ... 42.15.html


Richard wrote there:
"toga (at least all the versions I've looked at) seems to have almost no benefit from increased hash size (beyond the 16MB default)"

I wonder if people tested toga with different hash to see if this is correct.

questions:

1)Does toga perform better in test suites with 512 mbytes hash relative to 16 mbytes
2)Does toga perform better in games with 512 mbytes hash relative to 16 mbytes

Hi Uru
Do you know a chess programm doing better in tests with 512 MB hash than with 128 MB or 256 MB hash?
Kurt

Mine, at least. Any program with a working hash table will search faster as hash grows, until hash reaches one of two points (1) it can hold the entire search tree, so that making it larger makes no difference; (2) it becomes large enough that it causes TLB thrashing which will significantly increase memory latency. 256mb is unlikely to do that, nor 512mb.

[bob]

I read a claim that toga unlike other engines does not earn or almost does not earn from more hash tables relative to the default hash of 16 MB

see
http://chesstempo.com/chess-forum/gener ... 42.15.html


Richard wrote there:
"toga (at least all the versions I've looked at) seems to have almost no benefit from increased hash size (beyond the 16MB default)"

I wonder if people tested toga with different hash to see if this is correct.

questions:

1)Does toga perform better in test suites with 512 mbytes hash relative to 16 mbytes
2)Does toga perform better in games with 512 mbytes hash relative to 16 mbytes

Hi Uru
Do you know a chess programm doing better in tests with 512 MB hash than with 128 MB or 256 MB hash?
Kurt

I did not test chess programs to make comparison so I do not know.

Maybe Bob Hyatt can test it.
I guess that the difference between 256 MB and 512 MB may be small
when you may need longer time control than blitz to see a difference of more than 1 elo so it is hard to prove a difference based on games.

It may be easier to prove a difference between 16 mbytes and 128 mbytes but again if we talk about games and not about test suites then it may be easy only for Bob with his cluster to test it.

Uri

I can certainly test this, but it might be well after Christmas before I can. We had a massive A/C failure and while we have some A/C back up to get our normal servers up and going, we have nowhere near enough to deal with the heat the clusters produce. Hopefully we may see something the week after Christmas...

[bob]

I read a claim that toga unlike other engines does not earn or almost does not earn from more hash tables relative to the default hash of 16 MB

see
http://chesstempo.com/chess-forum/gener ... 42.15.html


Richard wrote there:
"toga (at least all the versions I've looked at) seems to have almost no benefit from increased hash size (beyond the 16MB default)"

I wonder if people tested toga with different hash to see if this is correct.

questions:

1)Does toga perform better in test suites with 512 mbytes hash relative to 16 mbytes
2)Does toga perform better in games with 512 mbytes hash relative to 16 mbytes

Hi Uru
Do you know a chess programm doing better in tests with 512 MB hash than with 128 MB or 256 MB hash?
Kurt

Mine, at least. Any program with a working hash table will search faster as hash grows, until hash reaches one of two points (1) it can hold the entire search tree, so that making it larger makes no difference; (2) it becomes large enough that it causes TLB thrashing which will significantly increase memory latency. 256mb is unlikely to do that, nor 512mb.

Here is some sample data. I took a middlegame positoin (not a test suite position) and searched it to a fixed depth. I varied the hash size from 1mb to 256mb. This machine searches about 1.2M nodes per second on a single CPU. Multiply this by 20 for an 8-core box. Which means that this data would look more like starting at 16M and going up rather than starting at 1M and going up, due to the larger tree size.

Here's the results:

Code: Select all

log.001:              time=1:45  mat=1  n=124039743  fh=88%  nps=1.2M
log.002:              time=1:13  mat=1  n=87771998  fh=88%  nps=1.2M
log.003:              time=1:01  mat=1  n=74462806  fh=89%  nps=1.2M
log.004:              time=49.12  mat=1  n=60032781  fh=89%  nps=1.2M
log.005:              time=40.42  mat=1  n=50652577  fh=90%  nps=1.3M
log.006:              time=36.07  mat=1  n=46067378  fh=92%  nps=1.3M
log.007:              time=33.80  mat=1  n=44191172  fh=92%  nps=1.3M
log.008:              time=33.44  mat=1  n=43562882  fh=93%  nps=1.3M
log.009:              time=33.04  mat=1  n=43526928  fh=93%  nps=1.3M
log.010:              time=33.67  mat=1  n=43521889  fh=93%  nps=1.3M

You can tell where the table size becomes large enough that overwrites cease to happen. The gain from 32mb to 64 mb is only 10%, and from that point forward there is no gain at all. In a tournament game, this represents a search space of 1.3M * 33 seconds which would be similar to maybe 1.5 seconds at 24M nodes per second. That would push the sweet spot right on up. In a longish game of 3 mins per move at 20M+ nodes per second, we would be talking 4B nodes roughly, which is about 1000x larger than the above tree. Which means that the sweet spot would moves from 64mb, where the last increase was seen, to beyond 1024M, well beyond, before this speedup stops.

It is significant.

[Kurt Utzinger]

Hi Uru
Do you know a chess programm doing better in tests with 512 MB hash than with 128 MB or 256 MB hash?
Kurt

Mine, at least. Any program with a working hash table will search faster as hash grows, until hash reaches one of two points (1) it can hold the entire search tree, so that making it larger makes no difference; (2) it becomes large enough that it causes TLB thrashing which will significantly increase memory latency. 256mb is unlikely to do that, nor 512mb.

Here is some sample data. I took a middlegame positoin (not a test suite position) and searched it to a fixed depth. I varied the hash size from 1mb to 256mb. This machine searches about 1.2M nodes per second on a single CPU. Multiply this by 20 for an 8-core box. Which means that this data would look more like starting at 16M and going up rather than starting at 1M and going up, due to the larger tree size.

Here's the results:

Code: Select all

log.001:              time=1:45  mat=1  n=124039743  fh=88%  nps=1.2M
log.002:              time=1:13  mat=1  n=87771998  fh=88%  nps=1.2M
log.003:              time=1:01  mat=1  n=74462806  fh=89%  nps=1.2M
log.004:              time=49.12  mat=1  n=60032781  fh=89%  nps=1.2M
log.005:              time=40.42  mat=1  n=50652577  fh=90%  nps=1.3M
log.006:              time=36.07  mat=1  n=46067378  fh=92%  nps=1.3M
log.007:              time=33.80  mat=1  n=44191172  fh=92%  nps=1.3M
log.008:              time=33.44  mat=1  n=43562882  fh=93%  nps=1.3M
log.009:              time=33.04  mat=1  n=43526928  fh=93%  nps=1.3M
log.010:              time=33.67  mat=1  n=43521889  fh=93%  nps=1.3M

You can tell where the table size becomes large enough that overwrites cease to happen. The gain from 32mb to 64 mb is only 10%, and from that point forward there is no gain at all. In a tournament game, this represents a search space of 1.3M * 33 seconds which would be similar to maybe 1.5 seconds at 24M nodes per second. That would push the sweet spot right on up. In a longish game of 3 mins per move at 20M+ nodes per second, we would be talking 4B nodes roughly, which is about 1000x larger than the above tree. Which means that the sweet spot would moves from 64mb, where the last increase was seen, to beyond 1024M, well beyond, before this speedup stops.

It is significant.

Most interesting but could it be that you get other results if using test positions? I feel we can't compare reaching search depths and given test positions. I remember having made such tests some time ago and in most cases, the results were worse the higher the hash table size has been set.
Kurt

[ernest]

Bob,
Usually I can follow what you say.
But here, you completely lost me...

"Multiply this by 20 for an 8-core box. "
Must have been a hell of a slow machine...

"Your results table": what is what (where is table size, what is the signification the columns time n fh...)???

I am all the more sorry, since I am very interested in that subject.

In the case of testsuites with Rybka 3, there seems to be no general law showing which of 64 MB, 128, 256, 512 or 1024 hash gives better results.

[bob]

Hi Uru
Do you know a chess programm doing better in tests with 512 MB hash than with 128 MB or 256 MB hash?
Kurt

Mine, at least. Any program with a working hash table will search faster as hash grows, until hash reaches one of two points (1) it can hold the entire search tree, so that making it larger makes no difference; (2) it becomes large enough that it causes TLB thrashing which will significantly increase memory latency. 256mb is unlikely to do that, nor 512mb.

Here is some sample data. I took a middlegame positoin (not a test suite position) and searched it to a fixed depth. I varied the hash size from 1mb to 256mb. This machine searches about 1.2M nodes per second on a single CPU. Multiply this by 20 for an 8-core box. Which means that this data would look more like starting at 16M and going up rather than starting at 1M and going up, due to the larger tree size.

Here's the results:

Code: Select all

log.001:              time=1:45  mat=1  n=124039743  fh=88%  nps=1.2M
log.002:              time=1:13  mat=1  n=87771998  fh=88%  nps=1.2M
log.003:              time=1:01  mat=1  n=74462806  fh=89%  nps=1.2M
log.004:              time=49.12  mat=1  n=60032781  fh=89%  nps=1.2M
log.005:              time=40.42  mat=1  n=50652577  fh=90%  nps=1.3M
log.006:              time=36.07  mat=1  n=46067378  fh=92%  nps=1.3M
log.007:              time=33.80  mat=1  n=44191172  fh=92%  nps=1.3M
log.008:              time=33.44  mat=1  n=43562882  fh=93%  nps=1.3M
log.009:              time=33.04  mat=1  n=43526928  fh=93%  nps=1.3M
log.010:              time=33.67  mat=1  n=43521889  fh=93%  nps=1.3M

You can tell where the table size becomes large enough that overwrites cease to happen. The gain from 32mb to 64 mb is only 10%, and from that point forward there is no gain at all. In a tournament game, this represents a search space of 1.3M * 33 seconds which would be similar to maybe 1.5 seconds at 24M nodes per second. That would push the sweet spot right on up. In a longish game of 3 mins per move at 20M+ nodes per second, we would be talking 4B nodes roughly, which is about 1000x larger than the above tree. Which means that the sweet spot would moves from 64mb, where the last increase was seen, to beyond 1024M, well beyond, before this speedup stops.

It is significant.

Most interesting but could it be that you get other results if using test positions? I feel we can't compare reaching search depths and given test positions. I remember having made such tests some time ago and in most cases, the results were worse the higher the hash table size has been set.
Kurt

Test positions are mostly tactical in nature, where normal game moves are not. Once a program finds a test position solution, additional hash will not help it for future iterations nearly as much as it will help for normal positions where lots of things transpose to equal scores...

I'll run a series of matches when we get our cluster back up and vary hash size from very small to very large to see the actual ELo effect...

[bob]

Bob,
Usually I can follow what you say.
But here, you completely lost me...

"Multiply this by 20 for an 8-core box. "
Must have been a hell of a slow machine...

My laptop, in fact. I get about 1.2M nodes per second on one cpu on this particular box, where I get about 24M on the 8-core box I typically use on ICC.

"Your results table": what is what (where is table size, what is the signification the columns time n fh...)???

For each successive run the table size was doubled. It started at whatever value I gave and doubled for each successive run. The rest of the output is just normal crafty search statistics, total nodes searched, time taken to complete that search, nps, etc...

I am all the more sorry, since I am very interested in that subject.

In the case of testsuites with Rybka 3, there seems to be no general law showing which of 64 MB, 128, 256, 512 or 1024 hash gives better results.

The general rule is "big enough to store the entire tree is optimal, bigger may not help and may hurt when considering TLB issues, smaller is always worse, but perhaps not significantly worse until you pass some lower threshold.

I simply test at the projected time per move, and vary the hash size and compare the times needed to complete the last iteration that all sizes completed (larger hash sizes will likely gain a ply or more).