Fork/Join und andere Optimierungen von Algorithmen

In den letzten Jahren ist die Geschwindigkeit einzelner CPU-Kerne kaum noch gestiegen. Stattdessen steigt die Anzahl der Kerne, Laptops haben heutzutage oft acht Kerne (ok, vier echte, der Rest ist nur Hyperthreading). Selbst in Smartphones sind vier Kerne inzwischen Standard. Will man solche Rechner auslasten, muss man  parallele Programme einsetzen.

In diesem Artikel werde ich ein kleines Brettspiel als Anwendung für Parallelprogrammierung und andere Optimierungen verwenden, eine dreieckige Variante von Solitaire . Die Frage ist: Wie viele verschiedene Lösungsvarianten existieren für ein Spielbrett? Der Fokus des Artikels wird auf verschiedenen Optimierungstechniken liegen, nicht nur dem Fork/Join-Framework. Es wird sich zeigen, dass neben der Parallelisierung in diesem Fall andere Techniken überlegen sind.

Aufgabenbeschreibung

Im Artikel geht es um Solitaire auf einem dreieckigen Brett der Kantenlänge n. Ein Brett der Kantenlänge fünf (n = 5) sieht vor dem ersten Zug folgendermaßen aus:

          x
         x x
        x o x
       x x x x
      x x x x x

In der Startstellung ist das mittlere Feld in der dritten Reihe leer. Ein gültiger Zug besteht aus einem Sprung in einer der sechs möglichen Richtungen über einen Stein, welcher dadurch entfernt wird. Das Zielfeld muss vor dem Zug natürlich frei sein. Nach dem ersten Zug könnte das Brett also folgendermaßen aussehen:

          x
         x x
        x x x
       x o x x
      x o x x x

Wenn sich nur noch ein Stein aus dem Brett befindet, ist das Spiel gelöst. Für verschiedene Startpositionen (bei gleicher Kantenlänge) existiert eine unterschiedliche Anzahl von Lösungen, eine schöne Untersuchung findet man auf Dan O’Briens Puzzle Solution Page. Dort wurde die Anzahl der verschiedenen Lösungen auch mit einem Java-Programm untersucht, jedoch immer für n = 5.

Hat man erst mal eine Klasse geschrieben, die das Spielbrett repräsentieren kann und in der Lage ist, aus einer Stellung die Folgendstellungen zu ermitteln, besteht die restliche Logik nur noch aus einer kleinen, rekursiven Methode:

1long countSolutions(Board start) {
2      if (start.isSolution()) {
3          return 1;
4      } else {
5          long count = 0;
6          for (Board board : start.nextPositions()) {
7              count += countSolutions(board);
8          }
9          return count;
10      }
11  }

(Den kompletten Source-Code als Eclipse-Projekt gibt es übrigens als ZIP .)
Für ein Brett mit Kantenlänge fünf benötigt die Methode ca. eine Zehntel Sekunde zum Ermitteln der 1550 verschiedenen Lösungen. Klingt nicht danach, als wenn hier großer Optimierungsbedarf besteht. Wie sieht es also für größere Kantenlängen aus? Bei Kantenlänge sechs dauert es schon länger. Viel länger. Zwar nicht solange wie die Berechnung von 42, aber immerhin noch ca. 30 Stunden. Es existieren 29.235.690.234 verschiedene Lösungen für diese Brettgröße. Deswegen ist der Rückgabewert auch ein long und kein int.

Woher kommt dieser große Unterschied, obwohl das Brett doch kaum größer ist? Die Anzahl der möglichen Positionen für ein Brett der Kantenlänge n ist 2^(n * (n+1)/2). Es handelt sich also um eine Exponentialfunktion mit einer quadratischen Funktion im Exponenten…

Fork/Join

Wenn man das Fork/Join-Framework kennt (wenn nicht: Fork/Join tutorial lesen) erkennt man, dass es wie die Faust aufs Auge auf das Problem passt. Mit wenigen Zeilen lässt sich die Berechnung initialisieren:

1ForkJoinPool pool = new ForkJoinPool(numThreads);
2  RecursiveSolver root = new RecursiveSolver(startBoard, sequential);
3  solutions = pool.invoke(root);

Dazu braucht man noch eine kleine Klasse für die Tasks:

1class RecursiveSolver extends RecursiveTask {
2  private Board start;
3  private int sequential;
4 
5  public RecursiveSolver(Board start, int sequential) {
6    this.start = start;
7    this.sequential = sequential;
8  }
9 
10  @Override
11  protected Long compute() {
12    int card = start.cardinality();
13    if (card == 1) {
14       return Long.valueOf(1);
15    } else if (card < sequential) {
16       return Long.valueOf(countSolutions(start));
17    } else {
18      List nextPositions = start.nextPositions();
19      List tasks = new ArrayList<>(nextPositions.size());
20      for (Board b : nextPositions) {
21        tasks.add(new RecursiveSolver(b, sequential));
22      }
23      invokeAll(tasks);
24      long count = 0;
25      for (RecursiveSolver rs : tasks) {
26        count += rs.join();
27      }
28      return count;
29    }
30    return Long.valueOf(0);
31  }
32}

Wo im sequentiellen Fall die Rekursion steht, werden hier neue Instanzen von RecursiveTask angelegt. Als weitere Optimierung wechselt der Algorithmus innerhalb eines Threads zur sequentiellen Variante, wenn nur noch eine einstellbare Anzahl von Steinen auf dem Brett vorhanden ist. Somit wird unnötiger Verwaltungsaufwand im Fork/Join-Framework vermieden. Bei meinen Testläufen hat sich acht als gute Grenze für den Wechsel zur sequentiellen Variante herausgestellt.

Auf meinem Laptop (acht Kerne mit Hyperthreading, vier „echte“ Kerne) gestartet, war dieser für die nächsten 7 Stunden und 28 Minuten erst mal gut beschäftigt. Verglichen mit den 30 Stunden für die sequentielle Variante ungefähr ein Faktor von vier, das passt gut zu den vier „echten“ Kernen, perfekter Speedup. Eigentlich könnte man jetzt das Thema ad acta legen.

Ich wollte jedoch nicht nur Bretter mit Kantenlänge fünf und sechs lösen, sondern auch größere Bretter. Wie sieht es beispielsweise für n = 7 aus? Auf meinem Laptop habe ich das nicht ausprobiert. Weder sequentiell noch parallel. Vermutlich wäre das Programm weder in meiner noch in der Lebensdauer des Laptops fertig geworden. Wenn man sich also für größere Bretter interessiert, müssen noch weitere Optimierungen dazukommen.

Caches

Wie in den meisten Brettspielen ergeben sich bei Solitaire nach Änderung der Reihenfolge von Zügen oft identische Stellungen. Speichert man also für eine Stellung ab, wie viele Lösungen es aus dieser Stellung gibt, so muss man es nicht wiederholt berechnen. Dies kann man beispielsweise mittels einer HashMap implementieren. Diese Technik ist in der Spieleprogrammierung auch unter dem Namen Transposition Table bekannt. Damit sie funktioniert, muss die Klasse Board die Methoden hashCode() und equals() implementieren.

Für n = 5 bringt diese Optimierung noch nicht sehr viel, statt 0,1 Sekunden dauert es jetzt nur noch 0,07 Sekunden, das heißt nur noch 70% der Zeit. Für n = 6 ist der Effekt schon beeindruckender, statt 30 Stunden der sequentiellen Implementierung nur noch 0,4 Sekunden, ein Faktor von 270.000. Auch gegenüber der parallelen Variante mit vier Kernen ist die optimierte Variante immer noch um den Faktor 67.500 schneller.

Das ist ja schon mal recht vielversprechend, also habe ich es direkt mal mit n = 7 ausprobiert. Auf einer „gewöhnlichen“ JVM mit 32-Bit Heap gibt das aber nur einen OutOfMemoryError, die HashMap passt nicht mehr in den Speicher. Da hilft auch kein einfaches -Xmx mehr, es muss zusätzlich per -d64 in den 64-Bit-Modus umgeschaltet werden.

Stop!

Die HashMap ist zwar eine meiner Lieblingsklassen, da sie so schön einfach und schnell ist, manchmal existieren jedoch bessere Varianten, hier das gute alte Array. Eine Stellung des Spiels lässt sich nämlich – zumindest bis n = 7 – auch in einem int speichern, schließlich sind es nur 7*(7+1)/2=28 Felder. Damit hat man den Index. Gespeichert werden in dem Array longs, die jeweils die Anzahl der Lösungen für die Stellung repräsentieren. Für noch nicht untersuchte Stellungen wird -1 abgelegt. Mit n = 7 passt es immer noch nicht in einen 32-Bit-Heap, ist aber sowohl bezogen auf den Speicher als auch auf die Rechenzeit effizienter, zum Beispiel entfällt das Hashing. Für n = 6 benötigt der Algorithmus jetzt nur noch 0,2 Sekunden statt der 0,4 Sekunden mit der HashMap.

Mit einer 64-Bit-JVM könnte man jetzt also n = 7 lösen. Aber vorher gehen wir noch einmal einen Schritt zurück und nehmen an, wir könnten uns die notwendige Speichermenge nicht leisten. Wenn man etwas Debug-Ausgaben einbaut, fällt etwas auf: Für n = 5 und n = 6 findet der Algorithmus ziemlich schnell die ersten Lösungen. Bei n = 7 ist dies anders. Ich hatte das vor etlichen Jahren beobachtet, als ich dieses Problem noch mit C auf einer SUN-Workstation beackert hatte. Auch nach etlichen Minuten war noch keine Lösung gefunden. Daraufhin keimte in mir der Verdacht, dass Solitaire für diese Kantenlänge möglicherweise unlösbar ist. Also schnell das Programm modifiziert und für jede Stellung nur noch ein Bit spendiert: 0 = Stellung noch nicht ausgewertet, 1 = Stellung ausgewertet, unlösbar.

Letzte Woche war ich etwas fauler (mein Laptop hat ja auch mehr Speicher als die alte Workstation) und habe statt eines Bits ein byte spendiert, damit passt das Array immer noch in einen 32-Bit-Heap. Noch eleganter wäre natürlich die Klasse BitSet aus dem JDK gewesen. Nach 34 Sekunden kam die Bestätigung dessen, was ich durch das alte C-Programm schon wusste: Für n = 7 existiert keine Lösung. Mit long auf der 64-Bit-JVM dauert es etwas länger, 37 Sekunden. Dies dürfte an schlechterer Cache-Lokalität durch den höheren Speicherverbrauch und an den größeren 64-Bit Referenzen liegen.

Jetzt wieder parallel

Bisher haben wir zwei total unterschiedliche Optimierungsansätze betrachtet: Parallelität und Caching. Die Frage ist, lassen sie sich für noch bessere Ergebnisse kombinieren? Es ist möglich, die Lösung ist dann aber nicht mehr so einfach und elegant. Die bisherige parallele Variante kam komplett ohne synchronized aus, da die Threads nur auf lokalen Daten arbeiten. Damit ist Schluss, sobald man eine globale Datenstruktur wie ein Array oder eine HashMap einsetzt. Dazu muss man sich noch überlegen, in welcher Granularität man sperrt. Die Struktur komplett zu sperren hat zwei Nachteile:

1. Ein Großteil der Parallelität wird zerstört, wenn alle Threads auf eine Ressource zugreifen
2. Es löst nicht das Problem der doppelten Arbeit: Nachdem ein Thread festgestellt hat, dass eine Stellung noch nicht ausgewertet hat und mit der Arbeit beginnt, könnte ein zweiter Thread die gleiche Stellung auswerten.

Also sollte man feingranularer arbeiten: Ein Lock pro Stellung. Da synchronized immer ein Objekt benötigt, muss mann statt des eingebauten Datentyps im Array jetzt ein Objekt einführen:

1class Value {
2  public Value() {
3    v = -1;
4  }
5  public long v;
6}

Der Rest ändert sich nicht besonders:

1long countSolutions(Board start) {
2  Integer startAsInt = Integer.valueOf(start.asInteger());
3  Value value = cache[startAsInt];
4  synchronized (value) {
5    if (value.v != -1) {
6      return value.v;
7    } else if (start.isSolution()) {
8      value.v = 1;
9      return 1;
10    } else {
11      long count = 0;
12      List nextPositions = start.nextPositions();
13      for (Board board : nextPositions) {
14        count += countSolutions(board);
15      }
16      value.v = count;
17      return count;
18    }
19  } // synchronized
20}

Die Lösung verhindert, dass mehrere Threads eine Stellung bearbeiten. Da Threads hier länger blockiert werden können, sollte man mit mehr Threads als Kernen arbeiten.

Messungen zeigen, dass sich – zumindest für diese Problem – die Kombination aus Caching und Parallelisierung nicht lohnt. Für n = 6 benötigt das Programm eine Sekunde, fünf mal länger als die schnellste sequentielle Variante. Der Aufwand durch die Synchronisierung ist im Vergleich zur Berechnung zu hoch. Dies mag für andere Problemstellungen, in denen die Einzelprobleme komplexer sind, anders sein.

Lessons Learned

Was kann man aus diesen Spielereien lernen? Speziell, wenn man langweilige/interessante Geschäftsanwendungen mit (No)SQL-Databases entwickelt? Nun, ich habe für dieses Experiment erstmalig mit dem Fork/Join-Framework in der Praxis gearbeitet. Meine Schlussfolgerung: Gut dokumentiert, ziemlich einfach zu benutzen. Auch die intern eingebauten Tricks des Frameworks (wie die Arbeit zwischen den Threads verschoben wird) scheinen gut zu funktionieren. Es wäre deutlich aufwändiger gewesen, selbst Threads zu erzeugen und zu verwalten.

Als zweiten Punkt kann man mitnehmen, dass gute Algorithmen wichtig sind. Wichtiger als kleine Optimierungen durch Bitfrickeleien. Mit letzteren holt man nur konstante Faktoren heraus, ein besserer Algorithmus kann jedoch Größenordnungen ausmachen. Gerade bei großen Problemen macht es einen riesigen Unterschied, ob der Aufwand n log(n) oder n^2 beträgt (Hinweis: Sortieralgorithmen).

Der dritte Punkt ist ganz einfach: Am schnellsten ist die Arbeit erledigt, die man überhaupt nicht ausführt. Wenn sie sich jedoch nicht komplett umgehen lässt, so sollte man sie zumindest nicht mehrfach ausführen, stattdessen sollte man einmalig berechnete Ergebnisse zwischenspeichern (caching). Hier war das die Berechnung von Teilbäumen, in Geschäftsanwendungen sind typischerweise die Datenbankoperationen der Zeitfresser. Mit einem guten JPA-Provider im Classpath muss man hier nicht einmal selbst einen Cache implementieren. Stattdessen kann man die Zeit nutzen, den Cache vernünftig zu konfigurieren.

Wo man selbst Hand anlegen muss, existieren einige hilfreiche Klassen, die (Implementierungs)Arbeit einsparen helfen. HashMap und Array, so wie sie hier verwendet wurden, sind keine echten Caches, ihnen fehlt die Fähigkeit, Dinge zu vergessen. Aber im JDK existieren weitere hilfreiche Klassen zum Thema: Nicht wirklich geeignet ist die WeakHashMap, deren Einträge verwirft der Garbage Collector, allerdings ohne jede Kontrolle durch den Programmierer. Besser ist da oft einen echter LRU-Cache, der ganz einfach mit Hilfe der Klasse LinkedHashMap realisiert werden kann, man muss dazu nur die Methode removeEldestEntry() überladen (Details finden sich im zugehörigen Javadoc).

Will man noch mehr Kontrolle über seinen Cache haben, sollte man sich den Google Guava Cache ansehen. Bei ihm können Einträge auch zeitgesteuert oder basierend auf den Kosten eines Eintrags entfernt werden, wobei man das Maß für die Kosten selbst bestimmen kann.

Ein Punkt wurde hier überhaupt nicht betrachtet: Die Analyse des Codes mittels eines Profilers. In diesem einfachen Beispiel war auch so klar, wo die Zeit verbraucht wurde.

Anhang

Es überrascht, dass für n = 7 keine einzige Lösung existiert. Man kann sogar beweisen, dass für alle n mit n modulo 3 = 1 keine Lösung existiert. Es folgt eine kurze Skizze des Beweises.

Zuerst werden die Felder des Spielfeldes in zwei Varianten mit Werten markiert:

     1                1
    1 0              0 1
   0[1]1            1[1]0
  1 1 0 1          1 0 1 1
 1 0 1 1 0        0 1 1 0 1
0 1 1 0 1 1      1 1 0 1 1 0

Das Feld in eckigen Klammern ist die Stelle, bei der am Spielanfang kein Stein steht. Für jede Stellung lässt sich nun eine Funktion berechnen: Summe der Feldwerte, auf denen ein Stein steht modulo zwei.

Für n = 6 ist die Zahl der Einsen auf dem Brett gerade. Da das initial leere Feld jedoch auch mit einer Eins belegt ist, ist der Funktionswert sowohl für die linke als auch für die rechte Variante der Markierung eins.

In einer Zeile oder in den beiden Diagonalen betrachtet wiederholt sich das Muster 1 1 0. Ein Zug auf dem Muster verändert nie das Ergebnis der Funktion: Gerade bleibt gerade, ungerade bleibt ungerade.

Dies gilt natürlich nicht nur für einen Zug, sondern auch über ein ganzes Spiel hinweg. Da für beide oben gezeigten Feldmarkierungen die Startposition als Funktionswert eins hat, muss am Ende des Spiels der übrig bleibende Stein für beide Feldmarkierungen auf einem mit eins markierten Feld stehen.

Für n = 5 und n = 6 kann man dies mit einer leichten Modifikation des Programms alle Felder ermitteln, auf denen bei den gefunden Lösungen der letzte Stein steht:

    o
   o o
  o o o
 o o o o
o o x o o

Bei n = 5 kommt also nur ein Feld heraus, bei n = 6 mehr:

     x
    o o
   o x o
  x o o x
 o o x o o
o x o o x o

Wenn n modulo 3 = 1 gilt, dann ist auch die Feldanzahl modulo drei gerechnet eins. Erweitert man die beiden oben gezeigten Muster für größere n so sieht man, dass für die n mit n modulo 3 = 1 in der Ecke unten rechts und links immer eine Eins Steht. Das Brett enthält also eine n/3 von 1 1 0 Gruppen und eine zusätzliche Eins. Zusammen mit dem leeren Feld am Start auf einer Eins führt dies zum Funktionsergebnis null. Der letzte Stein muss daher auf einer Null stehen, für das linke und rechte Muster. Da es aber keine Felder gibt, die in beiden Mustern eine Null enthalten, kann es für diese n keine Lösung geben.

Wäre es nicht gemein, das Spiel mit Kantenlänge sieben auf den Markt zu bringen?