Umfassende Suchoptimierung: So verarbeiten Sie ein Diagramm mit 10 Milliarden Status

Vor ein paar Monaten musste ich endlich zugeben, dass ich nicht klug genug war, um einige Level des Snakebird- Puzzles durchzugehen . Die einzige Möglichkeit, etwas von dem Selbstwertgefühl wiederzugewinnen, bestand darin, einen Löser zu schreiben. Ich könnte also so tun, als wäre das Erstellen eines Programms zum Lösen des Puzzles fast dasselbe wie das Lösen selbst. Der Code für das resultierende C ++ - Programm ist auf Github verfügbar. Der Hauptteil des im Artikel berücksichtigten Codes ist in search.h und compress.h implementiert. In diesem Beitrag werde ich hauptsächlich über die Optimierung einer Breitensuche sprechen, die 50 bis 100 GB Speicher benötigt, um in 4 GB zu passen.

Später werde ich einen weiteren Beitrag schreiben, der die Besonderheiten des Spiels beschreibt. In diesem Beitrag müssen Sie wissen, dass ich keine guten Alternativen zu Brute Force finden konnte, da keiner der üblichen Tricks funktioniert hat. Das Spiel hat viele Zustände, da es viele sich bewegende oder geschobene Objekte gibt und die Form einiger von ihnen wichtig ist, was sich im Laufe der Zeit ändern kann. Es gab keine geeignete konservative Heuristik für Algorithmen wie A *, um den Suchraum einzugrenzen. Der Suchgraph war orientiert und implizit spezifiziert, daher war eine gleichzeitige Suche in Vorwärts- und Rückwärtsrichtung unmöglich. Der einzige Schritt könnte den Zustand in vielerlei Hinsicht verändern, sodass nichts so nützlich sein könnte wie das Hashing von Zobrist .

Grobe Schätzungen haben gezeigt, dass es im größten Puzzle nach Eliminierung aller symmetrischen Positionen etwa 10 Milliarden Staaten geben wird. Selbst nach dem Packen von Zustandsbeschreibungen mit maximaler Dichte betrug die Zustandsgröße 8-10 Bytes. Mit 100 GB Arbeitsspeicher wäre die Aufgabe trivial, aber nicht für meinen Heimcomputer mit 16 GB Arbeitsspeicher. Und da Chrome 12 GB davon benötigt, liegt mein realer Speicherbedarf näher bei 4 GB. Alles, was dieses Volumen überschreitet, muss auf der Festplatte gespeichert werden (alte und rostige Festplatte).

Wie passt man 100 GB Daten in 4 GB RAM? Entweder a) die Zustände müssen auf 1/20 ihrer ursprünglichen, bereits optimierten Größe komprimiert werden, oder b) der Algorithmus sollte in der Lage sein, Zustände effektiv auf der Festplatte zu speichern und umgekehrt, oder c) eine Kombination der beiden oben genannten Methoden, oder d) ich muss mehr kaufen RAM oder mieten Sie eine leistungsstarke virtuelle Maschine für mehrere Tage. Option D habe ich nicht in Betracht gezogen, weil es zu langweilig ist. Die Optionen A und B wurden nach dem Proof of Concept mit gzip ausgeschlossen: Ein Fragment einer Zustandsbeschreibung von 50 MB wurde auf nur 35 MB komprimiert. Dies sind ungefähr 7 Bytes pro Zustand, und mein Speicher ist ungefähr 0,4 Bytes pro Zustand. Das heißt, Option B blieb bestehen, obwohl die Breitensuche für die Speicherung auf sekundären Laufwerken eher unpraktisch schien.

Inhalt

Dies ist ein ziemlich langer Beitrag, daher hier ein kurzer Überblick über die folgenden Abschnitte:

• Breitensuche Breitensuche - Wie lautet der übliche Wortlaut der Breitensuche (BFS) und warum eignet er sich nicht zum Speichern von Teilen eines Status auf der Festplatte?
• BFS mit Sortieren und Zusammenführen - eine Änderung des Algorithmus zur effizienten Stapelentsorgung redundanter Daten.
• Komprimierung - Reduziert den Speicherbedarf aufgrund der Kombination aus Standard- und nativer Komprimierung um das Hundertfache.
• Oh-oh, ich habe geschummelt! - In den ersten Abschnitten habe ich über etwas geschwiegen: Es reicht nicht aus, nur zu wissen, wo die Lösung liegt, aber wir müssen genau verstehen, wie wir sie erreichen können. In diesem Abschnitt aktualisieren wir den Basisalgorithmus so, dass genügend Daten übertragen werden, um die Lösung aus dem letzten Status neu zu erstellen.
• Sortieren + Zusammenführen mit mehreren Ausgaben - Durch das Speichern weiterer Status werden die Vorteile der Komprimierung vollständig zunichte gemacht. Der Sortier- und Zusammenführungsalgorithmus muss geändert werden, damit zwei Sätze von Ausgabedaten gespeichert werden: Einer, gut komprimiert, wird während der Suche verwendet, und der andere wird nur verwendet, um die Lösung nach dem Finden des ersten neu zu erstellen.
• Swap - Swap unter Linux ist viel schlimmer als ich dachte.
• Komprimierung neuer Zustände vor dem Zusammenführen - Bisher funktionierten Speicheroptimierungen nur mit vielen besuchten Zuständen. Es stellte sich jedoch heraus, dass die Liste der neu generierten Zustände viel größer ist, als Sie vielleicht denken. Dieser Abschnitt zeigt ein Diagramm zur effizienteren Beschreibung neuer Zustände.
• Platz sparen in übergeordneten Zuständen - Untersuchen Sie die Kompromisse zwischen der Verwendung von CPU / Speicher, um die Lösung am Ende neu zu erstellen.
• Was nicht funktionierte oder vielleicht nicht funktionierte - einige Ideen schienen vielversprechend, aber als Ergebnis mussten sie zurückgesetzt werden, während andere, die Forscher sein sollten, in diesem Fall intuitiv unangemessen erscheinen.

Breite Suche "nach Lehrbuch"

Wie sieht die Breitensuche aus und warum sollten Sie keine Festplatte darin verwenden? Vor diesem kleinen Projekt habe ich nur Optionen für die Formulierung „aus Lehrbüchern“ in Betracht gezogen, zum Beispiel:

def bfs(graph, start, end): visited = {start} todo = [start] while todo: node = todo.pop_first() if node == end: return True for kid in adjacent(node): if kid not in visited: visited.add(kid) todo.push_back(kid) return False 

Beim Erstellen neuer Kandidatenknoten durch das Programm wird jeder Knoten mit einer Hash-Tabelle bereits besuchter Knoten überprüft. Befindet es sich bereits in der Hash-Tabelle, wird der Knoten ignoriert. Andernfalls wird es der Warteschlange und der Hash-Tabelle hinzugefügt. Manchmal werden in Implementierungen die "besuchten" Informationen in die Knoten und nicht in eine fremde Tabelle eingegeben. Dies ist jedoch eine riskante Optimierung und es ist völlig unmöglich, wenn der Graph implizit angegeben wird.

Warum ist die Verwendung einer Hash-Tabelle problematisch? Weil Hash-Tabellen dazu neigen, ein völlig zufälliges Speicherzugriffsmuster zu erstellen. Wenn dies nicht der Fall ist, ist dies eine schlechte Hash-Funktion, und die Hash-Tabelle weist aufgrund von Kollisionen höchstwahrscheinlich eine schlechte Leistung auf. Dieses Direktzugriffsmuster kann zu Leistungsproblemen führen, selbst wenn die Daten in den Speicher passen: Der Zugriff auf eine große Hash-Tabelle führt wahrscheinlich zu Cache-Fehlern und TLBs (Assoziative Translation Buffer). Was aber, wenn sich ein erheblicher Teil der Daten auf der Festplatte und nicht im Speicher befindet? Die Folgen werden katastrophal sein: etwas in der Größenordnung von 10 ms pro Suchvorgang.

Bei 10 Milliarden eindeutigen Status benötigen wir nur vier Monate, um auf die Datenträger-E / A zu warten, wenn wir nur auf die Hash-Tabelle zugreifen. Das passt nicht zu uns; Die Aufgabe muss unbedingt konvertiert werden, damit das Programm große Datenpakete in einem einzigen Durchgang verarbeiten kann.

BFS mit Sortieren und Zusammenführen

Wenn wir Datenzugriffsvorgänge so weit wie möglich in Pakete integrieren möchten, was wäre dann die maximal erreichbare Annäherung? Da das Programm nicht weiß, welche Knoten in einer Schicht der Tiefe N + 1 verarbeitet werden sollen, bis die Schicht N vollständig verarbeitet ist, scheint es offensichtlich, dass es notwendig ist, Zustände mindestens einmal pro Tiefe zu deduplizieren.

Wenn wir gleichzeitig mit der gesamten Ebene arbeiten, können wir Hash-Tabellen aufgeben und die Menge der besuchten und neuen Zustände als sortierte Streams beschreiben (z. B. als Dateistreams, Arrays, Listen). Wir können die neue besuchte Menge trivial finden, indem wir die Mengen von Flüssen kombinieren, und es ist ebenso trivial, die Menge zu finden, die anhand der Differenz der Mengen zu tun ist.

Zwei Operationen mit Sätzen können kombiniert werden, sodass sie mit beiden Threads in einem Durchgang funktionieren. Tatsächlich untersuchen wir beide Streams, verarbeiten das kleinere Element und bewegen uns dann entlang des Streams, aus dem das Element entnommen wurde (oder entlang beider Flows, wenn die Elemente am Anfang gleich sind). In beiden Fällen fügen wir den Artikel dem neu besuchten Satz hinzu. Dann bewegen wir uns entlang des Stroms neuer Zustände vorwärts und fügen der neuen Aufgabenmenge ein Element hinzu:

 def bfs(graph, start, end): visited = Stream() todo = Stream() visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return True for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited) return False # Merges sorted streams new and visited. Return a sorted stream of # elements that were just present in new, and another sorted # stream containing the elements that were present in either or # both of new and visited. def merge_sorted_streams(new, visited): out_todo, out_visited = Stream(), Stream() while visited or new: if visited and new: if visited.peek() == new.peek(): out_visited.add(visited.pop()) new.pop() elif visited.peek() < new.peek(): out_visited.add(visited.pop()) elif visited.peek() > new.peek(): out_todo.add(new.peek()) out_visited.add(new.pop()) elif visited: out_visited.add(visited.pop()) elif new: out_todo.add(new.peek()) out_visited.add(new.pop()) return out_todo, out_visited 

Das Datenzugriffsmuster ist jetzt vollständig linear und vorhersehbar, es gibt keine willkürlichen Zugriffe während der Fusion. Daher wird die Verzögerung des Festplattenbetriebs für uns nicht wichtig, und das einzige, was wichtig bleibt, ist die Bandbreite.

Wie wird die theoretische Leistung bei einer vereinfachten Verteilung von Daten über 100 Tiefenebenen aussehen, von denen jede 100 Millionen Zustände hat? Der gemittelte Zustand wird 50 Mal gelesen und geschrieben. Dies ergibt 10 Bytes / Zustand * 5 Milliarden Zustände * 50 = 2,5 TB. Meine Festplatte kann angeblich mit einer durchschnittlichen Geschwindigkeit von 100 MB / s lesen und schreiben, dh durchschnittlich dauert die E / A (2 * 2,5 TB) / (100 MB / s) = ~ 50 k / s = ~ 13 Stunden . Dies sind ein paar Bestellungen weniger als das vorherige Ergebnis (vier Monate)!

Es ist auch erwähnenswert, dass dieses vereinfachte Modell die Größe der neu erzeugten Zustände nicht berücksichtigt. Vor dem Zusammenführungsschritt müssen sie zum Sortieren + Deduplizieren im Speicher gespeichert werden. Wir werden dies in den folgenden Abschnitten behandeln.

Komprimierung

In der Einleitung sagte ich, dass in den ersten Experimenten die Zustandskomprimierung nicht vielversprechend aussah und das Komprimierungsverhältnis nur 30% betrug. Nachdem jedoch Änderungen am Algorithmus vorgenommen wurden, wurden die Zustände optimiert. Sie sollten viel einfacher zu komprimieren sein.

Um diese Theorie zu testen, habe ich zstd mit einem Puzzle von 14,6 Millionen Zuständen verwendet, von denen jeder 8 Bytes groß war. Nach dem Sortieren wurden sie durchschnittlich auf 1,4 Bytes pro Status komprimiert. Es scheint ein ernsthafter Schritt nach vorne zu sein. Es reicht nicht aus, das gesamte Programm im Speicher auszuführen, aber es kann die E / A-Zeit der Festplatte auf nur einige Stunden reduzieren.

Ist es möglich, das Ergebnis des modernen Allzweckkomprimierungsalgorithmus irgendwie zu verbessern, wenn wir etwas über die Datenstruktur wissen? Sie können sich fast sicher sein. Ein gutes Beispiel hierfür ist das PNG-Format. Theoretisch ist die Komprimierung nur ein Standard-Deflate-Durchgang. Anstatt Rohdaten zu komprimieren, wird das Bild zunächst mit PNG-Filtern konvertiert. Das PNG-Filter ist im Wesentlichen eine Formel zum Vorhersagen des Werts eines Bytes von Rohdaten basierend auf dem Wert des gleichen Bytes in der vorherigen Zeile und / oder des gleichen Bytes des vorherigen Pixels. Beispielsweise konvertiert der Filter "up" jedes Byte, indem er beim Komprimieren die Werte der vorherigen Zeile davon subtrahiert und beim Entpacken die entgegengesetzte Operation ausführt. Angesichts der Bildtypen, für die PNG verwendet wird, besteht das Ergebnis fast immer aus Nullen oder Zahlen nahe Null. Deflate kann solche Daten viel besser komprimieren als Rohdaten.

Kann dieses Prinzip auf BFS-Statusdatensätze angewendet werden? Es scheint, dass dies möglich sein sollte. Wie bei PNG haben wir eine konstante Liniengröße und können erwarten, dass die benachbarten Linien sehr ähnlich sind. Die ersten Proben mit dem Subtraktions- / Additionsfilter, gefolgt von zstd, führten zu einer Verbesserung des Kompressionsverhältnisses um weitere 40%: 0,87 Bytes pro Zustand. Filtervorgänge sind trivial, daher sind sie aus Sicht des CPU-Verbrauchs praktisch „kostenlos“.

Mir war nicht klar, ob weitere Verbesserungen vorgenommen werden konnten oder ob dies eine praktische Grenze war. In den Bilddaten können Sie logischerweise erwarten, dass die benachbarten Bytes derselben Zeile ähnlich sind. Aber in diesen Staaten gibt es so etwas nicht. Tatsächlich können etwas ausgefeiltere Filter die Ergebnisse noch verbessern. Am Ende bin ich zu diesem System gekommen:

Angenommen, wir haben benachbarte Zeilen R1 = [1, 2, 3, 4] und R2 = [1, 2, 6, 4]. Bei der Ausgabe von R2 vergleichen wir jedes Byte mit dem gleichen Byte der vorherigen Zeile, und 0 zeigt eine Übereinstimmung an, und 1 zeigt eine Nichtübereinstimmung an: diff = [0, 0, 1, 0]. Dann übergeben wir diese Bitmap, die als VarInt codiert ist, gefolgt von nur Bytes, die nicht mit der vorherigen Zeile übereinstimmen. In diesem Beispiel erhalten wir zwei Bytes 0b00000100 6. Dieser Filter komprimiert die Referenzdaten für sich genommen auf 2,2 Bytes / Status. Durch die Kombination des Filters + zstd haben wir die Datengröße auf 0,42 Byte / Status reduziert. Anders ausgedrückt, dies sind 3,36 Bit pro Status, was nur ein bisschen mehr ist als unsere ungefähren berechneten Indikatoren, die erforderlich sind, um sicherzustellen, dass alle Daten in den RAM passen.

In der Praxis verbessern sich die Kompressionsverhältnisse, weil sortierte Sätze dichter werden. Wenn die Suche den Punkt erreicht, an dem der Speicher Probleme verursacht, können die Komprimierungsraten viel besser werden. Das größte Problem ist, dass wir am Ende 4,6 Milliarden besuchte Staaten bekommen. Nach dem Sortieren belegen diese Zustände 405 MB und werden gemäß dem oben dargestellten Schema komprimiert. Dies ergibt 0,7 Bits pro Zustand . Am Ende nehmen Komprimierung und Dekomprimierung etwa 25% der CPU-Zeit des Programms in Anspruch. Dies ist jedoch ein hervorragender Kompromiss, um den Speicherverbrauch um das Hundertfache zu reduzieren.

Der obige Filter scheint aufgrund des VarInt-Headers in jeder Zeile etwas kostspielig zu sein. Es scheint einfach zu sein, ein Upgrade auf Kosten niedriger CPU-Kosten oder einer leichten Erhöhung der Komplexität durchzuführen. Ich habe verschiedene Optionen ausprobiert, Daten nach Spalten sortiert oder Bitmasken in größeren Blöcken usw. geschrieben. Diese Optionen allein ergaben viel höhere Komprimierungsverhältnisse, zeigten jedoch keine gute Leistung, wenn die Filterausgabe durch zstd komprimiert wurde. Und es war kein zstd-Fehler, die Ergebnisse mit gzip und bzip2 waren ähnlich. Ich habe keine besonders genialen Theorien darüber, warum sich herausgestellt hat, dass diese bestimmte Art der Codierung bei der Komprimierung viel besser ist als andere Optionen.

Ein weiteres Rätsel: Die Komprimierungsrate erwies sich als viel besser, wenn die Daten eher nach Little-Endian als nach Big-Endian sortiert wurden. Anfangs dachte ich, dass es passiert ist, weil es bei der Little-Endian-Sortierung mehr führende Nullen mit der von VarInt codierten Bitmaske gibt. Dieser Unterschied bleibt jedoch auch bei Filtern bestehen, die keine solchen Abhängigkeiten aufweisen.

(Es gibt viele Untersuchungen zum Komprimieren sortierter Sätze von Ganzzahlen, da diese die Grundbausteine ​​von Suchmaschinen sind. Ich fand jedoch nicht viele Informationen zum Komprimieren sortierter Datensätze konstanter Länge und wollte nicht raten, die Daten als Ganzzahlwerte mit willkürlicher Genauigkeit darzustellen.)

Oh-oh, ich habe geschummelt!

Möglicherweise haben Sie bemerkt, dass die obigen BFS-Implementierungen im Pseudocode nur Boolesche Werte zurückgeben - die Lösung wurde gefunden / nicht gefunden. Dies ist nicht besonders nützlich. In den meisten Fällen müssen wir eine Liste der genauen Schritte der Lösung erstellen und nicht nur die Verfügbarkeit der Lösung melden.

Auf den ersten Blick scheint dieses Problem leicht zu lösen zu sein. Anstatt Sätze von Zuständen zu erfassen, müssen Sie Statusbeziehungen zu übergeordneten Zuständen erfassen. Nachdem Sie die Lösung gefunden haben, können Sie einfach von Ende zu Anfang von der Liste der elterlichen Lösungen zurückkehren. Für eine auf Hash-Tabellen basierende Lösung würde dies ungefähr so ​​aussehen:

 def bfs(graph, start, end): visited = {start: None} todo = [start] while todo: node = todo.pop_first() if node == end: return trace_solution(node, visited) for kid in adjacent(node): if kid not in visited: visited[kid] = node todo.push_back(kid) return None def trace_solution(state, visited): if state is None: return [] return trace_solution(start, visited[state]) + [state] 

Leider werden dadurch alle im vorherigen Abschnitt erzielten Komprimierungsvorteile zerstört. Sie basieren auf der Annahme, dass benachbarte Linien sehr ähnlich sind. Wenn wir nur die Staaten selbst betrachten, ist dies wahr. Es gibt jedoch keinen Grund zu der Annahme, dass dies für Elternstaaten gilt. Tatsächlich handelt es sich um zufällige Daten. Zweitens sollte eine Sort + Merge-Lösung alle Zustände lesen und schreiben, die bei jeder Iteration angezeigt werden. Um die Verknüpfung des Status / übergeordneten Status zu speichern, müssen wir bei jeder Iteration all diese schlecht komprimierten Daten lesen und auf die Festplatte schreiben.

Sortieren + Zusammenführen mit mehreren Ausgaben

Ganz am Ende, wenn Sie zur Lösung zurückkehren, benötigt das Programm nur Bündel von Zuständen / übergeordneten Zuständen. Daher können wir zwei Datenstrukturen parallel speichern. Besucht werden weiterhin die besuchten Staaten, wie sie zuvor während der Zusammenführung neu berechnet wurden. Eltern ist mindestens eine sortierte Liste von Status / Eltern-Statuspaaren, die nicht überschrieben werden. Nach jedem Zusammenführungsvorgang wird das Paar "Status + übergeordneter Status" zu den übergeordneten Elementen hinzugefügt.

 def bfs(graph, start, end): parents = Stream() visited = Stream() todo = Stream() parents.add((start, None)) visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return trace_solution(node, parents) for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited, parents) return None # Merges sorted streams new and visited. New contains pairs of # key + value (just the keys are compared), visited contains just # keys. # # Returns a sorted stream of keys that were just present in new, # another sorted stream containing the keys that were present in either or # both of new and visited. Also adds the keys + values to the parents # stream for keys that were only present in new. def merge_sorted_streams(new, visited, parents): out_todo, out_visited = Stream(), Stream() while visited or new: if visited and new: visited_head = visited.peek() new_head = new.peek()[0] if visited_head == new_head: out_visited.add(visited.pop()) new.pop() elif visited_head < new_head: out_visited.add(visited.pop()) elif visited_head > new_head: out_todo.add(new_head) out_visited.add(new_head) out_parents.add(new.pop()) elif visited: out_visited.add(visited.pop()) elif new: out_todo.add(new.peek()[0]) out_visited.add(new.peek()[0]) out_parents.add(new.pop()) return out_todo, out_visited 

Dies ermöglicht es uns, beide Ansätze in Bezug auf Laufzeit und Arbeitssätze zu nutzen, erfordert jedoch mehr sekundären Speicherplatz. Darüber hinaus stellt sich heraus, dass in Zukunft aus anderen Gründen eine separate Kopie der besuchten Staaten nützlich sein wird, gruppiert nach Tiefe.

Tauschen

Ein weiteres Detail wird im Pseudocode ignoriert: Es gibt keinen expliziten Code für die Festplatten-E / A, sondern nur die abstrakte Stream-Schnittstelle. Stream kann ein Dateistream oder ein Array im Speicher sein, aber wir haben dieses Implementierungsdetail ignoriert. Stattdessen erstellt der Pseudocode ein Speicherzugriffsmuster, das eine optimale Nutzung der Festplatte ermöglicht. In einer idealen Welt würde dies ausreichen, und der Rest könnte vom virtuellen Speichersubsystem des Betriebssystems übernommen werden.

Dies ist jedoch zumindest unter Linux nicht der Fall. Irgendwann (bevor der Arbeitsdatensatz auf Speichergröße komprimiert werden konnte) wurde das Programm in etwa 11 Stunden ausgeführt, und die Daten wurden hauptsächlich auf der Festplatte gespeichert. Dann ließ ich das Programm anonyme Seiten verwenden, anstatt sie in Dateien zu speichern, und wählte eine Auslagerungsdatei von ausreichender Größe auf demselben Laufwerk aus. Drei Tage später ging das Programm jedoch nur ein Viertel des Weges und wurde im Laufe der Zeit immer langsamer. Nach meinen optimistischen Schätzungen sollte sie den Job in 20 Tagen beenden.

Ich werde es klarstellen - es war der gleiche Code und genau das gleiche Zugriffsmuster . Das einzige, was sich geändert hat, ist, dass der Speicher nicht als explizite Festplattendatei, sondern als Swap gespeichert wurde. Es sind fast keine Beweise dafür erforderlich, dass das Austauschen die Linux-Leistung vollständig zerstört, während dies bei regulären Datei-E / A nicht der Fall ist. Ich habe immer angenommen, dass dies auf die Tatsache zurückzuführen ist, dass Programme RAM eher als Arbeitsspeicher betrachten. Dies ist jedoch nicht der Fall.

Es stellt sich heraus, dass Dateispeicherseiten und anonyme Seiten vom Subsystem der virtuellen Maschine unterschiedlich behandelt werden. Sie werden in separaten LRU-Caches mit unterschiedlichen Ablaufrichtlinien gespeichert. Darüber hinaus scheinen sie unterschiedliche Read / Load-Read-Ahead-Eigenschaften zu haben.

Jetzt weiß ich: Das Tauschen unter Linux wird höchstwahrscheinlich auch unter optimalen Bedingungen nicht gut funktionieren. Wenn Teile des Adressraums wahrscheinlich für einige Zeit auf die Festplatte entladen werden, ist es besser, sie manuell in Dateien zu speichern, als dem Swap zu vertrauen. Ich habe dies erreicht, indem ich meine eigene Klasse von Vektoren implementiert habe, die anfänglich nur im Speicher funktioniert. Nach Überschreiten eines bestimmten Größenschwellenwerts wechselt sie in einer temporären separaten Datei zu mmap.

Komprimierung neuer Zustände vor dem Zusammenführen

In einem vereinfachten Leistungsmodell gingen wir davon aus, dass in jeder Tiefe 100 Millionen neue Bedingungen auftreten würden. Es stellte sich heraus, dass dies nicht sehr weit von der Realität entfernt ist (im komplexesten Puzzle maximal mehr als 150 Millionen einzigartige neue Zustände auf einer Tiefenschicht). Dies ist aber nicht zu messen; Der Arbeitssatz vor dem Zusammenführen ist nicht nur eindeutigen Zuständen zugeordnet, sondern auch allen Zuständen, die für diese Iteration abgeleitet wurden. Diese Zahl erreicht 880 Millionen Ausgangszustände pro Tiefenschicht. Diese 880 Millionen Zustände müssen a) mit einem Direktzugriffsmuster zum Sortieren verarbeitet werden, b) können aufgrund fehlender Sortierung nicht effektiv komprimiert werden, c) müssen zusammen mit dem übergeordneten Zustand gespeichert werden. Dieser Arbeitssatz ist ungefähr 16 GB groß.

Die offensichtliche Lösung: Verwenden Sie eine externe Sortierung. Schreiben Sie einfach alle Status auf die Festplatte, führen Sie eine externe Sortierung durch, deduplizieren Sie sie und führen Sie sie dann wie gewohnt zusammen. Zuerst habe ich diese Lösung verwendet, und obwohl sie das Problem A höchstens beseitigte, konnte ich B und C nicht bewältigen.

Am Ende habe ich einen alternativen Ansatz gewählt: Ich habe die Zustände in einem Array im Speicher gesammelt. Wenn das Array zu groß wird (z. B. mehr als 100 Millionen Elemente), wird es sortiert, dedupliziert und komprimiert. Dies gibt uns ein Paket sortierter Statusläufe, und es gibt keine Duplikate in jedem Lauf, aber sie sind zwischen den Läufen möglich. Grundsätzlich bleibt der Code zum Zusammenführen neuer und besuchter Staaten derselbe; es basiert immer noch auf einem allmählichen Durchgang durch die Bäche. Der einzige Unterschied besteht darin, dass anstatt nur zwei Streams zu durchlaufen, für jeden sortierten Lauf neuer Zustände ein separater Stream vorhanden ist.

Natürlich sind die Komprimierungsraten dieser Läufe von 100 Millionen Zuständen nicht so gut wie die Komprimierung der Menge aller besuchten Zustände. Aber selbst mit solchen Indikatoren wird das Volumen sowohl des Arbeitssatzes als auch die Anforderungen an die Festplatten-E / A erheblich reduziert. Sie benötigen etwas mehr CPU-Ressourcen, um die Prioritätswarteschlange von Threads zu verarbeiten, aber es ist immer noch ein großer Kompromiss.

Platz sparen in übergeordneten Zuständen

Zu diesem Zeitpunkt wird der größte Teil des vom Programm belegten Speicherplatzes für die Speicherung der übergeordneten Zustände aufgewendet, sodass wir nach dem Finden der Lösung den Prozess neu erstellen können. Höchstwahrscheinlich können sie kaum gut zusammengedrückt werden, aber vielleicht gibt es einen Kompromiss zwischen CPU und Speicher?

Wir müssen den Zustand S 'in der Tiefe D + 1 mit seinem Elternzustand S in der Tiefe D verbinden. Wenn wir alle möglichen Elternzustände S' durchlaufen können, können wir prüfen, ob einer von ihnen in der Tiefe D in der besuchten Menge erscheint . (Wir haben bereits viele Besucher erstellt, gruppiert nach Tiefe als praktisches Nebenprodukt der Ableitung von staatlichen / elterlichen Staatsbündeln während der Zusammenführung). Leider funktioniert dieser Ansatz für diese Aufgabe nicht. es ist einfach zu schwierig für uns, alle möglichen Zustände von S für ein gegebenes S 'zu erzeugen. Für viele andere Suchaufgaben könnte eine solche Lösung jedoch funktionieren.

Wenn wir nur Übergänge zwischen Zuständen vorwärts, aber nicht rückwärts erzeugen können, warum dann nicht einfach? Lassen Sie uns iterativ alle Zustände in Tiefe D umgehen und sehen, welche Art von Ausgabezuständen sie erhalten. Wenn ein Zustand am Ausgang S 'ergibt, haben wir ein geeignetes S gefunden. Das Problem bei diesem Plan ist, dass er den Gesamt-CPU-Verbrauch des Programms um 50% erhöht. (Nicht 100%, da wir S im Durchschnitt finden, wenn wir die Hälfte der Zustände in der Tiefe D betrachten).

Daher mag ich keinen der Grenzfälle, aber hier ist zumindest ein Kompromiss zwischen CPU / Speicher möglich. Gibt es irgendwo dazwischen eine akzeptablere Lösung? Am Ende habe ich beschlossen, nicht das Paar (S ', S) zu speichern, sondern das Paar (S', H (S)), wobei H eine 8-Bit-Hash-Funktion ist. Um S für ein gegebenes S 'zu finden, gehen wir erneut iterativ alle Zustände in Tiefe D durch. Bevor wir jedoch etwas anderes tun, berechnen wir denselben Hash. Wenn die Ausgabe nicht mit H (S) übereinstimmt, ist dies nicht der gesuchte Zustand, und wir können ihn einfach überspringen. Diese Optimierung bedeutet, dass kostspielige Neuberechnungen nur für 1/256 Zustände durchgeführt werden müssen, was eine leichte Erhöhung der CPU-Auslastung darstellt, und gleichzeitig die Speichermenge zum Speichern von Elternzuständen von 8-10 Bytes auf 1 Byte reduziert.

Was hat nicht funktioniert oder kann nicht funktionieren

In den vorherigen Abschnitten haben wir uns die Reihenfolge der funktionierenden Optimierungen auf hoher Ebene angesehen. Ich habe andere Dinge ausprobiert, die nicht funktionierten oder die ich in der Literatur gefunden habe, aber entschieden, dass sie in diesem speziellen Fall nicht funktionieren würden. Hier ist eine unvollständige Liste.

Zu diesem Zeitpunkt berechne ich nicht den gesamten Satz neu, der bei jeder Iteration besucht wurde. Stattdessen wurden so viele sortierte Läufe gespeichert, und diese Läufe wurden von Zeit zu Zeit komprimiert. Der Vorteil dieses Ansatzes besteht darin, dass weniger Festplattenschreibvorgänge und CPU-Ressourcen für die Komprimierung verwendet werden. Der Nachteil ist eine erhöhte Codekomplexität und eine verringerte Komprimierungsrate. Anfangs dachte ich, dass ein solches Schema sinnvoll ist, weil in meinem Fall Schreibvorgänge teurer sind als Lesen. Am Ende stellte sich jedoch heraus, dass das Kompressionsverhältnis doppelt so hoch war. Die Vorteile eines solchen Kompromisses liegen nicht auf der Hand, weshalb ich zu einer einfacheren Form zurückgekehrt bin.

Es wurden bereits wenige Untersuchungen zur volumetrischen Breitensuche nach implizit definierten Diagrammen im Sekundärspeicher durchgeführt. Sie können dieses Thema untersuchenaus diesem Artikel von 2008 . Wie Sie vielleicht erraten haben, ist die Idee, Deduplizierung zusammen mit Sortieren + Zusammenführen im Sekundärspeicher durchzuführen, nicht neu. Das Überraschende daran ist, dass es erst 1993 eröffnet wurde. Ziemlich spät! Es gibt später Vorschläge für die Breitensuche im Sekundärspeicher, für die kein Sortierschritt erforderlich ist.

Eine davon bestand darin, Zustände an ganze Zahlen zu binden und eine Bitmap der besuchten Zustände im Speicher zu speichern. In meinem Fall ist dies völlig nutzlos, da die Größen des codierten Zustands im Vergleich zu den wirklich erreichbaren Zustandsräumen sehr unterschiedlich sind. Und ich bezweifle sehr, dass es interessante Probleme gibt, bei denen ein solcher Ansatz funktionieren würde.

Eine weitere ernsthafte Alternative basiert auf temporären Hash-Tabellen. Besuchszustände werden ohne Sortierung in einer Datei gespeichert. Wir speichern die Ausgabe aus Tiefe D in der Hash-Tabelle. Gehen Sie dann iterativ durch die besuchten Zustände und suchen Sie sie in der Hash-Tabelle. Wenn das Element in der Hash-Tabelle gefunden wird, löschen Sie es. Nach dem iterativen Durchlaufen der gesamten Datei verbleiben nur nicht doppelte Elemente darin. Sie werden dann zur Datei hinzugefügt und zum Initialisieren der Aufgabenliste für die nächste Iteration verwendet. Wenn die Ausgabemenge so groß ist, dass die Hash-Tabelle nicht in den Speicher passt, können sowohl Dateien als auch Hash-Tabellen nach denselben Kriterien (z. B. den oberen Statusbits) in Teile unterteilt werden, und jeder Teil sollte separat verarbeitet werden.

Obwohl es Benchmarks gibtDies zeigt, dass der Hash-basierte Ansatz etwa 30% schneller ist als das Sortieren + Zusammenführen, aber es scheint, dass sie die Komprimierung nicht berücksichtigen. Ich habe einfach nicht gesehen, wie sich die Ablehnung der Vorteile der Komprimierung rechtfertigen kann, deshalb habe ich nicht einmal mit solchen Ansätzen experimentiert.

Ein weiterer Forschungsbereich, der Beachtung verdient, war die Optimierung von Datenbankabfragen. Es sieht aus wie. dass die Deduplizierungsaufgabe stark mit dem Datenbank-Join zusammenhängt, der genau das gleiche Dilemma zwischen Sortierung und Hashing aufweist. Offensichtlich können einige dieser Studien auf das Suchproblem angewendet werden. Der Unterschied kann darin bestehen, dass die Ausgabe der Join-Datenbank temporär ist, während die Ausgabe der BFS-Deduplizierung bis zum Ende der Berechnung gespeichert wird. Dies scheint das Gleichgewicht der Kompromisse zu verändern: Jetzt geht es nicht nur um die effizienteste Verarbeitung einer Iteration, sondern auch um die Erstellung des optimalsten Ausgabedatenformats für die nächste Iteration.

Fazit

Damit ist mein Bericht über das abgeschlossen, was ich aus einem Projekt gelernt habe, das allgemein mit brutaler Gewalt auf andere Suchaufgaben anwendbar ist. Die Kombination dieser Tricks ermöglichte es, das Lösungsvolumen für die komplexesten Rätsel des Spiels von 50 bis 100 GB auf 500 MB zu reduzieren und die Kosten reibungslos zu erhöhen, wenn die Aufgabe den verfügbaren Speicher überschreitet und auf die Festplatte geschrieben wird. Außerdem ist meine Lösung 50% schneller als eine naive Deduplizierung von Zuständen basierend auf Hash-Tabellen, selbst für Rätsel, die in den Speicher passen.

Snakebird kann bei Steam , Google Play und im App Store gekauft werden . Ich empfehle es jedem, der sich für sehr komplexe, aber ehrliche Rätsel interessiert.