Profiling des Spielagenten mit Eclipse TPTP

Die FAQ zu Avaloqix geben ganz klar die Kriterien bekannt:

Für den Wettbewerb werden Graphen mit 20-60 Knoten genutzt. Pro Knoten gibt es max. 9 Kanten. Zusätzlich gibt es eine Timelimite von 5 sec pro Spielzug.

Leider fehlen die Angaben über die Leistungsfähigkeit der Wettbewerbsmaschine. Ich gehe mal ganz willkürlich davon aus, dass sie nicht langsamer ist oder weniger Speicher hat als mein Laptop und die Resultate nur besser sein können. Eine Geschwindigkeitsoptimierung dürfte also nicht ganz sinnlos sein. Ausserdem wird mein Agent in den ersten paar Zügen nie fertig mit Rechnen und muss abbrechen. Eine Optimierung die hier mehr Spielzüge erlaubt, würden die Gewinnchancen signifikant steigern.

Ausserdem gilt wie überall im Leben: Machs schön und richtig und erst danach schnell.

Benchmarking

Bei einer Geschwindigkeitsoptimierung sollte man immer benchmarken. Das heisst: Die Geschwindigkeit vor und nach der Optimierung nachmessen, so dass man sicher sein kann, dass man in die richtige Richtung optimiert hat. Ebenfalls empfehlenswert ist gezieltes optimieren: Wenn man eine Funktion nur ein bisschen verschnellert, die sehr oft aufgerufen wird, bringt das unter Umständen mehr wie wenn man eine Funktion mit viel Aufwand drastisch verkürzt die nur wenige Male zum Zuge kommt. Man braucht also Daten.

Als Benchmark habe ich – mangels anderer Gegner – ein Spiel gegen den OptimalOneAgent gewählt. Für den Benchmark sollten immer die gleichen Einstellungen gelten, die komfortable Avaloqix Oberfläche erlaubt zum Glück das Festlegen des Spielfeldes mit dem Random Seed.

Es empfiehlt sich auch, Turn Pause zu deaktivieren und End when winner is ovious zu aktivieren.

Profiling

Doch woher die Daten nehmen und nicht stehlen? Dafür zuständig sind sogenannte Profiler. Für Eclipse gibt es einen (einer der versteckten Diamanten) im TPTP-Projekt.

Installation

Bei mir tun Java 1.6 und Eclipse Ganymede 3.4.1 den Dienst. Mit der bebilderten Anleitung habe ich es geschafft, TPTP 4.5.1 zu installieren. Die Einführung (ebenfalls bebildert 🙂 ) gibt einen guten Einstieg.

Verwendung

Wenn die Installation geklappt hat, gibt es beim Ausführbereich einen neuen Button Profile. Unser Benchmark ist etwas speziell, denn es muss ein Programm profiliert werden, das ausserhalb der Eclipseumgebung läuft. Zum Glück stellt dies für den TPTP-Profiler kein Problem dar.
Für unser Benchmark lohnt es sich, eine Konfiguration zu erstellen: ProfileProfile Configurations...External Java Applications. Mittels Test Connection kann festgestellt werden, ob der Profiler auf Empfang ist.

Im Register Main kann mit dem Drücken auf Add JAR... das Avaloqix.jar ausgewählt werden. Die Startmethode wird dabei automatisch gefunden.

Im Register Arguments muss das Installationsverzeichnis von Avaloqix als Working Directory angegeben werden.

Nun wird es interessant. Wir wollen weder das Java-Framework, noch das Spielprogramm, noch den optimalOneAgenten profilen. Wenn alles profiled wird, wird die Ausführung extrem langsam und erzeugt ein grosses Rauschen von Daten. Im Register Monitor darum auf Java Profiling - JRE 1.5 or newerEdit Options gehen.
Hier zuerst ein Avaloqix Filterset erzeugen und die Vorgaben bei Contents of selected filter set ergänzen (die Reihenfolge ist relevant).

Um genauere Zeiten zu erhalten (aber leider die Ausführung zu verfälschen) ganz oben alle verwendeten Framework-Klassen einfügen:

java.util.ArrayList     * INCLUDE
java.util.LinkedList    * INCLUDE
java.util.Queue         * INCLUDE
java.util.ArrayDeque    * INCLUDE
java.util.Arrays        * INCLUDE

Zuunterst:

agentcontroller.*       * EXCLUDE
view.*                  * EXCLUDE
model.*                 * EXCLUDE
agents.OptimalOneAgent* * EXLCUDE

Dann noch Execution Time Analysis aktivieren und nach Gusto konfigurieren.

Der Rest kann so bleiben. Nun kann das Profilen mittels Drücken auf Profile gestartet werden.

Optimierung

Leider geht die Profilierung bei Java 1.5 und höher nur bis auf Methodenlevel. Obwohl im folgenden Bild die Java-Frameworkaufrufe nicht mit aufgezeichnet wurden, zeigt es trotzdem Kandidaten, die sich durch die Aufrufhäufigkeit und/oder die Ausführungszeit auszeichnen.

In diesen Kandidaten kann nun um jede Millisekunde gekämpft werden.

Fazit

Profilieren mit dem TPTP

Profilieren ist immer Overhead. Gerade bei zeitkritischen Applikationen wie dem Avaloqix werden die Resultate verfälscht: Nach 5 Sekunden wird der Spieler abgewürgt, egal ob der Profiler die Zeit konsumiert oder der Spielagent.

Sehr verwirrend war, dass anscheinend die Java Frameworkaufrufe (ArrayList, …) nicht mitgezählt werden bei den Methodenzeiten. Das hatte den paradoxen Effekt, dass ich mehr berechnen konnte als ich auf primitive Arrays umgestellt habe, aber die Funktion länger gebraucht hat. So nebenbei hat die Aktivierung das Spielfeld vollkommen durcheinander gebracht.

Das Filter Set ist nicht sehr intuitiv: Die INCLUDE müssen vor den EXCLUDES stehen wenn bestimmte Packages erlaubt werden sollen in einem mit Wildcards ausgeschlossenen Packageverbund.

Optimieren von Java

Ich habe folgendes gelernt:

  • Reservationen von Arrays sind teuer. Darum: Wenn immer möglich Arrays wiederverwenden. Ein Array mit Werten beschreiben geht ganz flott mittels:
    java.util.Arrays.fill(Array, Wert);
  • Arrays kopieren geht am Schnellsten mit System.arraycopy(). Ich kann die Resultate vom Javaspecialist nur unterstützen: Neu erstellen und kopieren ist im Normalfall schneller als clone():
    res_capacity = new int[size][size]; // Remaining capacity
    for (int i = 0; i < size; i++) {
        System.arraycopy(graphMatrix[i], 0, res_capacity[i], 0, size);
    }
  • ArrayList ist langsam und speicherhungrig. ArrayList ist sehr komfortabel im Gebrauch, aber es ist langsam und sehr speicherhungrig. Ben Christensen hat Versuche gemacht, die ich nur bestätigen kann. Eine eigene Implementation hat dem Ganzen Beine gemacht.
  • Der Compiler inlined nur unter bestimmten Bedingungen. Laut Beschreibung macht der Compiler nur Inlinefunktionen wenn diese final, private, oder static ist und keine lokalen Variablen hat.
  • Tuning ist gefährlich. Durch die Optimierungen konnten plötzlich viel mehr Positionen verarbeitet werden, was dann das Memory in die Knie gezwungen hat.
  • ArrayDeque ist einiges schneller und speicherschonender als eine LinkedList als Queue.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.