Hallo Wolfgang,

man müsste tatsächlich einmal verschiedene Mittel- und Endspielstellungen mit den originalen Mephisto-Boliden von Richard Lang mit und ohne Hashtables prüfen, um fundierte Aussagen machen zu können.

Gruß
Egbert

Nein, das war die Untersuchung einer Stellung in der GUI Scid.
Also quasi, wie wenn man im UCI-Protokoll ein "go infinite" eingibt.

Man konnte sehen, wie sich der Hashspeicher langsam füllt, aber ich hatte das Gefühl, der 8GB Hashspeicher hilft nicht so viel mehr wie 1GB Hashspeicher.


Viele Grüße
Markus

Hi Markus,

Es wäre extrem ungewöhnlich, wenn man das so machen würde, weil man eine Hashtabelle nicht "durchsucht". Der Index, an dem man in der Hashtabelle springt, wird direkt aus dem Hashwert berechnet. Damit hängt der Aufwand sowohl beim Speichern als auch beim Nachschlagen einer Position nicht von der Größe der Hashtabelle ab. Lediglich, wenn man die gesamte Hashtabelle schreibt, etwa zwecks Löschen, dann dauert das proportional zur Größe.

Es wäre aber eine andere Falle denkbar. Wenn die Anzahl der Einträge eine Zweierpotenz ist, dann kann man die entsprechenden untersten Bits des Hashes als Index verwenden. Das ist eine AND-Operation, die auch auf den damaligen CPUs schon schnell war, IIRC 6 Takte beim 68k.

Ist die Anzahl der Einträge keine Zweierpotenz, dann kann man stattdessen eine Division mit Rest machen und den Rest als Index verwenden. Allerdings kostet eine Division etwa 140 Takte. Oder man bastelt eine Lösung, die stattdessen die Treffer ungleichmäßig verteilt, was dann wieder schnell ist, aber die Auslastung in Teilen der Tabelle ungleichmäßig macht und dort zu weniger Effektivität führt.

Ob die Größe der Hashtabelle selber dafür eine Zweierpotenz sein muß, hängt davon ab, ob der einzelne Eintrag die Größe einer Zweierpotenz hat, was von der Engine abhängt. Klar ist aber, wenn 2MB die Anzahl von Einträgen als Zweierpotenz hat, dann kann das für 3MB nicht der Fall sein, weil eine Zweierpotenz mal 1.5 keine Zweierpotenz ergibt.

Hallo Rasmus,
vielen Dank für die sehr gute Erklärung.

viele Grüße
Markus

Hallo Micha,

AFAIK basieren die Emulationen auf dem Motorola 68000.

Dieser hat nur intern 32bit, nutzt aber nach außen nur 24bit:

Quelle und nähere technische Details:
https://www.cs.mcgill.ca/~cs573/fall...c273/lecture9/

Vielleicht ist es mühsamer die Register mit "24bit-Happen" zu füttern als es intern wieder selbst auszurechnen.

Das erklärt jedoch nicht die Unterschiede bei den echten 32bit CPUs.

MOVE-Befehle haben ein Suffix, wie viele bit auf einmal transportiert werden:

B = 8bit
W = 16bit
L = 32bit

Die Frage, die sich mir stellt, ist, ob der Programmcode bei den 32bit-CPUs für 32bit optimiert wurde, also Verwendung von:
MOVE.L

Die internen Rechenbefehle (ADD, SUB, etc.) können auf den Registern auch beim 68000er in einem Zyklus ausgeführt werden.

Daher vermute ich, dass einfach der gleiche Assemblercode wie beim 68000er verwendet wurde und
dieser viele MOVE.B-Befehle enthält, d.h. wir schaufeln immer noch mit 16-bit Eimern die Daten hin und her.

Eine Takterhöhung sagt nur aus, dass schneller mit 16bit-Eimern geschaufelt wird.

Wie gesagt, das ist nur eine Vermutung. Daher würden mich eure Kommentare interessieren.


Viele Grüße
Markus

Ergänzung: Eine andere Quelle berichtet über einen 16bit-Bus, beschreibt aber die Operationen auf dem Speicher in Kurzform:

Quelle: https://electronics.stackexchange.co...on-32-bit-data

Außerdem müssen wir auch bedenken, dass der Registerspeicher schneller ist als der Hauptspeicher.

Hallo Markus,

ich habe jahrelang 68000-Geräte programmiert. Der 68000 ist ein 16/32-Bit-Mix-Prozessor, d.h. er arbeitet intern mit 32 Bit und nach außen schaufelt er die Daten mit 8 Bit oder 16 Bit, je nach verwendetem Befehl. Die 24 Bits beziehen sich nur auf den nach außen geführten Adressbus, d.h. sie bestimmen, wieviel Speicher adressiert werden kann. Es wird also nicht in "24-Bit Happen" sondern in "16 Bit-Happen" geschaufelt, und zweimal 16 Bit zu 32 Bit zusammenzusetzen ist einfach. 32-Bit-Befehle brauchen länger, weil durch den 16-Bit-Bus die eben in zwei "Happen" aufgeteilt werden müssen. Bei den Nachfolgern 68020, 68030, 68040 ist das nicht so, die können mit tatsächlichen 32-Bit-Happen arbeiten.

Aus meiner Sicht erklärt die Bus-Breite nicht unbedingt den großen Zeitunterschied. Denn prozentual müsste der sich auch mit einer 32-Bit-Hardware so ergeben. Wenn ich einen 1 KByte Speicher mit 16-Bit-Happen fülle, dann brauche ich eine gewisse Zeit, mit 32-Bit-Happen eben nur die Hälfte. Bei einem 2KByte-Speicher brauche ich in beiden Fällen die doppelte Zeit. D.h. ein 32-Bit-System kann den Speicher schneller füllen, jedoch sollte eine Verdopplung in beiden Fällen prozentual einen ähnlichen Zeitzuwachs ergeben.

Noch eine Bemerkung zu den Hash-Tabellen. Wenn man nach dem Neustart anfängt zu analysieren, dann muss die Tabellen ja erstmal gefüllt werden, d.h. die Analyse braucht länger. Bei den nächsten Zügen, die dann ausgeführt werden, kann man eine Menge Zeit einsparen, denn man wird dann ja auch einen Großteil der zu analysierenden Stellungen schon im Hash finden. Deshalb hat man im Endspiel tatsächlich Vorteile, die sich aber erst wirklich bemerkbar machen, wenn das Endspiel schon eine Vorgeschichte hatte.

Viele Grüße
Michael

Hallo Michael,
Das ist genau der Punkt. Grosse Hashtables nützen erst was, wenn sie gefüllt sind und das dauert bei den 16 bit Geräten sehr lang.

viele Grüße
Markus