Vergleich: verschiedene Hashtablegröße / feste Suchtiefe

By Andreas Strangmüller Date 2013-06-14 17:36

Einfluss der Größe der Hashtables auf das Erreichen einer festen Suchtiefe.

Zur Reproduzierbarkeit wurde der Test mit 1 Kern durchgeführt. Plattform Windows 64-bit.
Das bedeutet, zumindest auf jedem 64 Bit Windows-Rechner wird die Engine Stockfish 3 JA 64bit, 1 Kern, Tiefe 29 bei z.B. 256 MB Hash in 604 MN erreichen (siehe untenstehende Tabelle).

Engine: Stockfish 3 JA 64bit
Grundstellung, Suchtiefe = 29 Halbzüge, AMD FX-8350 @ 4,6 GHz

MN = Million Nodes, k/s = Knoten pro Sekunde

Hashtables | Tiefe |   Zeit     | Zeit-Faktor |  MN   |    k/s    |  %-k/s
-----------+-------+------------+-------------+-------+-----------+--------
   64 MB   | 29/44 | 10:15 Min. |    1,62     |  844  | 1.372.358 |  98,26
  128 MB   | 29/41 | 08:15 Min. |    1,31     |  678  | 1.396.696 | 100,00 
  256 MB   | 29/40 | 07:21 Min. |    1,16     |  604  | 1.369.615 |  98,06
  512 MB   | 29/44 | 11:48 Min. |    1,87     |  965  | 1.362.994 |  97,59
1.024 MB   | 29/42 | 06:19 Min. |    1,00     |  512  | 1.350.923 |  96,72
2.048 MB   | 29/41 | 08:08 Min. |    1,29     |  653  | 1.333.811 |  95,50
4.096 MB   | 29/43 | 08:10 Min. |    1,29     |  647  | 1.320.408 |  94,54
8.192 MB   | 29/45 | 09:08 Min. |    1,45     |  717  | 1.308.394 |  93,68

Die Zeiten zur Erreichung einer festen Suchtiefe bei verschieden großen Hashtables sind sehr unterschiedlich.
Bei 512 MB Hash werden 11:48 Min. benötigt um Suchtiefe 29 zu erreichen (schlechtestes Ergebnis), bei 1024 MB Hash nur 6:19 Min. (bestes Ergebnis), dies ist ein Faktor von 1,87.
Interessant ist, dass bei 128 MB Hash die Zeit zum Erreichen der Suchtiefe 29 ähnlich schnell ist wie bei 4096 MB Hash.

Eine Feststellung, die keine Wertung sein soll, kann man anhand des Tests jedoch treffen:
Je größer die Hashtables, desto geringer die Knotenleistung.
Oder anders gesagt, der Zugriff der Engine Stockfish 3 auf die Hashtables, bzw. das Füllen dieser, verringert seine Knotenleistung um maximal 6,32 %, wie der Tabelle zu entnehmen ist.
Bei 128 MB sind es 1.396.696 Knoten pro Sekunde, bei 8192 MB "nur" noch 1.308.394. Im gebräuchlichen Bereich zwischen 256 MB und 2048 MB differiert die Knotenleistung
um 2,56 %, zwischen 2048 MB und 8192 MB sind es gar nur noch 1,82 %.

Gruß,
Andreas

By Michael Scheidl Date 2013-06-15 02:22 Edited 2013-06-15 02:24

Der große Zeitunterschied zwischen 512 (längste) und 1.024 MB (kürzeste) ist überraschend und eigentlich unlogisch. Ich zögere allgemeine Schlüsse zu ziehen, denn wir sehen hier nur eine Engine und eine Stellung. Ich vermute zumindest hinsichtlich 512/1024 einen untypischen Fall. Weiters hängt es sicherlich auch mit der RT. zusammen.

Hier zwei Messungen von i5-3210M, auch Windows 64 Bit (aber aus Ungeduld

nur über 25 Halbzüge):

Engine: Stockfish 3 (1024 MB)
von Tord Romstad, Marco Costalba and Joona
1/01   0:00   +0.76   1.Sf3 (28) 14
(...)
25/36   1:55   +0.28   1.d4 Sf6 2.Sf3 e6 3.c4 d5 4.Sc3 Lb4 5.e3 c5 6.Ld2 O-O 7.a3 Lxc3 8.Lxc3 cxd4 9.Sxd4 e5 10.Sf3 e4 11.Sd2 (139.301.953) 1204
Bester Zug: d2-d4 Zeit: 1:55.703 min K/s: 1.204.003 Knoten: 139.301.953

Engine: Stockfish 3 (512 MB)
von Tord Romstad, Marco Costalba and Joona
1/01   0:00   +0.76   1.Sf3 (28) 28
(...)
25/41   1:13   +0.32   1.Sf3 Sf6 2.d4 e6 3.c4 d5 4.Sc3 Lb4 5.Lg5 O-O 6.e3 Sc6 7.Ld3 Ld7 8.O-O Lxc3 9.bxc3 h6 10.Lxf6 Dxf6 11.cxd5 exd5 12.Db3 (93.391.283) 1266
Bester Zug: Sg1-f3 Zeit: 1:13.750 min K/s: 1.266.339 Knoten: 93.391.283

Hier waren 512 MB, bezogen auf 1.024 MB um 36% schneller?!

(Es war ein sauberer Neustart des ganzen Programmes). Auffällig auch die recht große Differenz der Knotenleistung.

Bei der Knotenleistung bin ich auch vorsichtig mit Interpretationen, denn immer wieder wurde gesagt daß Engines diese durchaus unterschiedlich zählen (könnten), auch andere als Rybka. Z.B. kann ich mir vorstellen daß nicht jede Engine Hashtreffer mitzählt - wo ja die Bewertung nicht mehr durchlaufen werden muß - was sich als Erklärung aufdrängen würde warum die angezeigte Knotenzahl mit mehr Hash sinkt. Inklusive Hashtreffer würde sie das dann vermutlich nicht. Ich weiß aber nicht was wo bezüglich dessen tatsächlich der Fall ist, daher ist das nur eine etwas spekulative Überlegung.

Der Punkt ist bzw. wäre, die Gesamtleistung ist ungleich der (angezeigten) Knotenleistung. Die Tabelle zeigt es ja für dieses Beispiel auch.

Vieleicht hänge ich später noch ein paar Messungen von anderen Engines und Stellungen an.

By Michael Scheidl Date 2013-06-15 05:08

Intel i5-3210M/2,5...2,9 GHz, Windows 8 x64, je ein Thread:

Komodo CCT 64 Bit, Tiefe 25:

Hash(MB)   Zeit(Sek.)   Zeitfaktor   kN/s   %-nps
-------------------------------------------------
  128         96           1,10      1510   100,0
  512         95           1,09      1453    96,2
1.024         87           1,00      1460    96,7
2.048         97           1,11      1433    94,9
-------------------------------------------------

Deep Fritz 13 32 Bit, Tiefe 23:

Hash(MB)   Zeit(Sek.)   Zeitfaktor   kN/s   %-nps
-------------------------------------------------
  128        309           2,27      2702   100,0
  512        171           1,26      2649    98,0
1.024        228           1,68      2596    96,1
2.048        136           1,00      2566    95,0
-------------------------------------------------

Es bestätigt sich die Verringerung der gezählten bzw. ausgegebenen Knoten pro Sekunde bei Vergrößerung der Hashtables.

Ich glaube, sonst bestehen viele Abhängigkeiten die unterschiedliche optimale Hashgrößen ergeben: Stellung, Rechentiefe, Computergeschwindigkeit, Engine... Insbesondere ist mir eingefallen, daß ja unterschiedliche Knotenleistungen zu einem unterschiedlichen Füllgrad des Hash pro Zeiteinheit führen.

Somit kann diese Frage auch nicht durch große Datenmassen "statistisch erschlagen" werden, weil ein allgemeiner Durchschnitt bei einer solchen Bandbreite für den Einzelfall nichts bringt. Das einzige was ich aufgrund obiger (weniger) Resultate schlußfolgere ist, daß ein Optimum zwischen 512 und 2048 MB liegen könnte - für einen Thread...

By Ingo Bauer Date 2013-06-15 06:19

[quote="Michael Scheidl"]
Das einzige was ich aufgrund obiger (weniger) Resultate schlußfolgere ist, daß ein Optimum zwischen 512 und 2048 MB liegen könnte - für einen Thread...
[/quote]

... und für Tiefe 25. Bei Tiefe 30, 35, ... kann das anders aussehen.

Das einzige wie man vielleicht eine durchschnittliche optimale Hashgröße finden könnte wäre ein großes Turnier von Engine A gegen viele fixe Engines das man jeweils mit unterschiedlichen Hashgrößen wiederholt. Also alle Engines mit 256 MB Hash und dann Engine A mit ... 128, 256, 512, 1024, 2048 ... MB Hash. Und das ist dann noch durch die gegebene Zeitkontrolle beschränkt.

Mangels praktikablem Test und der Tatsache das es sowieso nicht viel ausmacht halte ich mich für Analysen und längere Spiele an das was praktisch jeder Programmierer sagt: Viel hilft viel!

Gruß
Ingo

By Ingo Bauer Date 2013-06-15 12:36

[quote="Ingo Bauer"]
[quote="Michael Scheidl"]
Das einzige was ich aufgrund obiger (weniger) Resultate schlußfolgere ist, daß ein Optimum zwischen 512 und 2048 MB liegen könnte - für einen Thread...
[/quote]

... und für Tiefe 25. Bei Tiefe 30, 35, ... kann das anders aussehen.

[/quote]

Hier mal was ich meinte mit "kann das anders aussehen":

Das ist H3 mit nur einem Kern und Hashgrößen von 64MB bis 8GB in der Grundstellung jeweils Tiefe vorne und die Zeit in Sekunden bis dahin.
Immer zw dem letzten blauen und dem ersten orangenem Feld hatte ich ein 100% Hash full.
Die Reihenfolge der besten Hashgrößen ist die grüne Linie unten, also:
8GB, 256MB, 128MB, 4GB, 512MB, 64MB, 1GB, 2GB im Schnitt über alle Tiefen. Wenn man sich eine einzelne Tiefe herrauspickt, kann aber eine ganz andere Reihenfolge herrauskommen. Z.B. bei Tiefe 24 ist es:
64MB, 1GB, 4GB, 128MB, 256MB, 8GB, 512MB, 2GB.

Auch weiß ich nicht ob der Durchschnitt so erhalten bliebe wenn die 8GB mal vollaufen, also z.B bis Tiefe 28 oder 29 gerechnet werden müßte weiß niemand ...

Ich habe es nicht aufgeschrieben, je nach Hashgröße werden auch noch eine unterschiedliche Anzahl an Nodes gezeigt zum erreichen einer Tiefe. Dazu ist das nur mit einem Kern, bei mehreren darf man jede Hashmessreihe mehrmals wiederholen ... Das ganze Thema ist unerquicklich und ist nicht automatisiert kaum zu messen.

Und für eine andere Engine sieht das auch noch ganz anders aus

Gruß
Ingo

By Roland del Rio Date 2013-06-17 09:53

Wie waren dene Testbedingungnen bzgl. der large pages?

Ich setze mal eine SMP-Archtektur bei der Hardware voraus (also kein NUMA).

Viele Grüße
Roland

By Ingo Bauer Date 2013-06-17 11:01

Keine LP und auch kein Numa. Numa is irrelevant weil sowieso nur ein Thread. Wie ich auch im Test schrieb muß man das bei mehreren Threads auch noch pro Hashgröße X mal wiederholen und Durchschnittswerte bilden ... ein Faß ohne Boden.

Gruß
Ingo

By Roland del Rio Date 2013-06-17 19:17

Wohl war. Denke auch, dass ist so schwierig sauber einzufangen, dass man pragmatisch vorgehen sollte und einfach mal gegeneinander spielen lässt.
Werde das in den nächsten Wochen mal aufsetzen, vermutlich muss man sehr lange spielen lassen, denn die 100ms/Zug Turnierchen sind hier nicht gefragt.

By Roland del Rio Date 2013-06-18 13:56

Hier meine Ergebnisse zu dem Thema.
Habe drei Tests mit unterschiedlicher Bedenkzeit gemacht 0.1/1/10 sec per move.
Wie zu erwarten, ist die Hashgröße bei 100ms irrelevant,
und bei 10 sec kann man eine ganz schöne Kurve sehen.

Test bed condition:

Time per move   (ms) = 100ms / 1000ms / 10000ms
Avg game length (sec) = 12.5 / 119.6 / 1218.9
No. of games = 2100 / 1050   / 350

Hash    avg. calc move depth calc. nodes / sec

128M    12.74 / 17,21 / 21.35    1953423 / 1893032 / 1939861
64M    12.73 / 17,01 / 21.05    1951147 / 1897862 / 1933688
32M    12.61 / 16.79 / 20.77    1935968 / 1900844 / 1956165
32M    12.87 / 17.00 / 20.90    1948920 / 1903756 / 1952545
16M    12.83 / 17.05 / 20.66    1947668 / 1927191 / 1945815
8M    12.61 / 16.54 / 20.55    1931016 / 1924236 / 1978407
4M    12.69 / 16.56 / 20.36    1920663 / 1932829 / 1987248

Es gab zwei identische Engines mit 32MB als Blindtest, die Spielresultate lasse ich aufgrund der viel zu geringen
Spielanzahl weg. Aber wer will kann grob überschlagen: Bei 10 sec Bedenkzeit ist 128MB ca. 1 Halbzug tiefer als 4MB Hash,
ein Halbzug kostet in der Tiefe mit dem ganz dicken Daumen die doppelte Bedenkzeit, würde also ca. einer Verdopplung der
Taktrate entsprechen, was wiederum xxx ELO bedeuten würde ...
Interessant wären jetzt noch längere Bedenkzeiten und größere Hashareas. Mache ich vielleicht in den kommenden Tagen nochmal.
Viele Grüße