Das Programm von Tobias Glasmachers

Hier eine Auflistung der Tricks, die den Algorithmus vielleicht von Anderen unterscheiden:

• Ganz wichtig: Der X-Trick, 12 Platzierungen, siehe Beschreibung im Forum
• Das nächste zu besetzende Feld wird dynamisch bestimmt. Das funktioniert so: Der Quader wird in 5 Schritten gefüllt, wobei jeder Schritt eine 3x4-Ebene füllt.
  Vor jeder Füll-Operation werden die Bitmuster der aktuellen und der davorliegenden Ebene betrachtet und daraus wird ein Hash-Wert gebildet. Der einfachste Weg dies zu tun, ist sicherlich ein 24bit-Index, der das beste Feld ergibt. Diese Lösung passt leider nicht in den Prozessor-Cache.
  Deshalb werden zunächst nur die "überhängenden" Bit betrachtet, also diejenigen, die in der vorderen, aber nicht in der aktuellen Ebene gesetzt sind. Es gibt (theoretisch) 4096 Möglichkeiten, diese werden (per Hash-Tabelle) auf 30 Möglichkeiten abgebildet, nämlich 1x keine überhängenden Bit, 12x ein überhängendes Bit, 17x zwei nebeneinander liegende überhängende Bit. Alle weiteren Möglichkeiten werden einer dieser Möglichkeiten zugeordnet.
  Somit wird die vordere Ebene durch 30 Fälle beschrieben, zusammen mit der aktuellen Ebene ergibt sich eine Tabelle mit 30*4096=122880 Einträgen. Im Voraus wird für jeden der Fälle unter der Näherung, dass alle Bauklötze eingesetzt werden dürfen, das Feld berechnet, das zu den wenigesten Verzweigungen führt. Das Resultat sind unter 750 Mio. Aufrufe.
• Jeder Eintrag dieser Tabelle enthält nicht nur die Information, welches der 12 Felder der aktuellen 3x4-Ebene zu füllen ist, sonder auch, welche Nachbarfelder (links, rechts, oben, unten, davor) schon belegt sind. Dafür gibt es 192 Möglichkeiten, die Information passt also in ein Byte. Nun habe ich für jede dieser 192 Feld-Nachbar-Kombinationen und für jede aktuelle Ebene (1. und 2. sind gleich) eine Tabelle, in der die einsetzbaren Bauklötze vermerkt sind. Auf diese Weise kommt es zu relativ wenigen Versuchen, nicht passende Bausteine einzusetzen. Leider passen die 11 Bit (12 abzüglich "X") für die noch nicht verbauten Bauklötze nicht mehr in den Hash-Index.
• Für das Füllen jeder einzelnen der fünf Ebenen gibt es eine eigene Routine. Dies spart Verwaltungsaufwand und erlaubt, ab der 4. Ebene auf 32bit-Vergleiche umzusteigen.
• Vor dem Sprung in die 5. Ebene wird geprüft, ob noch einer der beiden nicht in eine Ebene passenden "3D"-Bauklötze abzulegen ist. Falls ja wird der Fall nicht weiter untersucht.
• Die Tabellen werden durch die Bauweise des Hash-Index auf eine solche Größe beschränkt, dass der Prozessor sie (hoffentlich oder fast vollständig) im Cache unterbringen kann: 580KB. Dafü wird ein etwas größerer Suchbaum in Kauf genommen (etwa 10%).

Die größten Fortschritte habe ich während der Entwicklung mit dem X-Trick, der Art der dynamischen Feld-Wahl und der Beschränkung auf Tabellen, die in den Cache passen, gemacht. Natürlich habe ich verdammt viele kleinere Tricks versucht, aber im Wesentlichen ist am Ende nichts davon übrig geblieben.

Statistik

Ich kenne mich leider überhaupt nicht mit aktuellen Prozessoren oder Compilern aus. Zum endgültigen Kompilieren des Programms habe ich aber in gutem Glauben den C-Compiler von Intel mit den Optionen -O3 -Qip -QaxW bzw. auf dem Pentium 4 -QxW verwendet.

Der Test des Programms auf verschiedenen Systemen ergab foldende Zeiten:

Prozessor Zeit Athlon, 1400 MHz 2:21 Athlon XP 2000, 1666 MHz 1:59 Pentium 4, 2400 MHz 1:53

Schon erstaunlich, der Pentium 4 scheint trotz Intel-Compiler und Pentium4-Optimierung echte Probleme mit der Performance zu haben.