Thematisch geht es um das Tuning von Java-Arrays in GWT.
Werfen wir noch mal einen Blick auf die Ausgangslage, d. h. die von Firebug ermittelten Ausführungszeiten:
Die fünf Funktionen mit dem höchsten Verbrauch an Rechenzeit sind wrapArray(), initDims_0, arraycopy(), $istErlaubt() und $pr(). Dabei sind die von mir geschriebenen Funktionen $istErlaubt() und $pr() elementar an der Überprüfung der Stellungen beteiligt, es war also zu erwarten, dass sie weit vorne in der Liste auftauchen. Die anderen drei Methoden stammen jedoch aus der GWT-Bibliothek. Ein kurzer Blick in den von GWT erzeugten JavaScript-Code (mit Option "pretty" erzeugt) zeigt, dass alle drei Funktionen beim Erzeugen von Arrays verwendet werden
Arrays, die ja eigentlich nicht gut in das Konzept der Sprache Java passen, da sie keine normalen Objekte sind, sind dennoch in den Java-Sprachstandard aufgenommen worden, da sie von der virtuellen Maschine sehr effizient ausgeführt werden können. Dies scheint für den von GWT erzeugten JavaScript-Code nicht zu gelten. Letztlich verwundert dies nicht, denn JavaScript-Arrays sind zwar flexibel, aber eher langsam und konzeptionell anders als Java-Arrays.
1. Optimierung: Zweidimensionale Arrays zu eindimensionalen Arrays
Das in dem Beispiel betrachtete Programm implementiert ein Spiel, welches auf einem Brett von acht mal acht Feldern gespielt wird. Die logischste Implementierung der Definition im Programmcode istprivate Farbe spiel[][];
(Farbe gibt an, wem der auf dem Feld befindliche Stein gehört; ist für das Beispiel ohne Bedeutung), der Zugriff auf einzelne Elemente erfolgt über
wert = spiel[reihe][spalte];
Das Programm legt in großem Umfang neue Arrays an, z. B. bei jeder zu prüfenden Stellung im Spiel.
Zweidimensionale (oder entsprechend mehrdimensionale) Arrays in Java haben die Besonderheit, dass jede Reihe unterschiedlich viele Spalten enthalten kann. Ein Zweidimensionales Java-Array ist also ein Array von Arrays, bei denen die Länge nicht festgelegt ist. (Im Gegensatz dazu hat in C jede Reihe gleich viel Spalten, was bei Verlust an Flexibilität den Zugriff beschleunigt. Ein C-Array ist auch nur ein einziges Objekt.) Diese Flexibilität wird hier aber nicht gebraucht, sondern sie ist sogar schädlich, da sie die Anzahl zu erzeugender Objekte erhöht, und gerade diese Objekte (die einzelnen Arrays der Reihen) sind in JavaScript nur kostspielig zu erzeugen. Das zeigt sich auch im Java-Code schon, z. B. bei der Kopie eines solchen Arrays
spiel = new Farbe[8][8];
for (int s = 0; s < 8; s++) {
System.arraycopy(original[s], 0, spiel[s], 0, 8);
}
(und da haben wir mit arraycopy auch schon eine der Funktionen, die viel Rechenzeit verbraucht).
Für die Optimierung habe ich jetzt die zweidimensionalen Arrays in eindimensionale Arrays umgewandelt, statt 8x8 Elemente jetzt 64 Elemente.
Aus der Variablendefinition wird jetzt
private Farbe spiel[];
der Zugriff wird mit der statischen Funktion
public static final int xy(int x, int y) {
return y * ANZAHL_REIHEN + x;
}
zu
wert = spiel[Brett.xy(reihe, spalte)]
(Der zusätzliche Funktionsaufruf kostet übrigens keine Performance, da er von GWT in Inline-Code umgewandelt wird.)
Die Kopie eines Arrays wird dadurch deutlich schlanker:
spiel = new Farbe[64];
System.arraycopy(original, 0, spiel, 0, 64);
Wesentlich ist jedoch, dass für ein Spielfeld (eine zu prüfende Stellung) nur noch ein JavaScript-Array und nicht mehr acht angelegt werden müssen.
Eine erneute Messung der Ausführungszeiten in Firebug ergibt jetzt folgendes Bild:
2. Optimierung: Arrays recyclen
Mit der letzten Optimierung wurde zwar bereits eine erhebliche Verbesserung erreicht, aber 34,4% für das Array-Handling sind immer noch viel. Für eine weitere Optimierung ist ein Blick auf den Algorithmus im Programm notwendig.Das Programm berechnet den besten Zug im Spiel, indem mögliche Stellungen rekursiv durchprobiert werden. Je weiter die Berechnung in die Tiefe geht, desto mehr potentielle Stellungen gibt es. Für jede durchprobierte Stellung werden Arrays angelegt, die nach durchprobieren der Stellung wieder verworfen werden. Es werden also viele Arrays erzeugt, pro rekursiver Rechentiefe wird aber (pro Variable) nur ein Array wirklich benutzt.
Die Lösung für die Optimierung besteht nun darin, dass eine gewisse Anzahl von Arrays in einem Puffer vorgehalten werden, bei Bedarf hieraus eine Instanz angefordert wird und diese auch wieder explizit freigegeben wird.
So wird im Konstruktor aus spiel = new Farbe[64]; jetzt
spiel = neuFarbe64();
Man sollte daran denken, dass das Array jetzt nicht frisch initialisiert ist, sondern irgendwelche zufälligen Werte enthalten kann.
Zusätzlich wird eine Art Destruktor gebraucht (der Begriff ist hier nicht ganz korrekt, es handelt sich nicht um einen vom System automatisch aufgerufenen Destruktor [finalize() von Java ist nicht geeignet, da der Aufruf zu spät kommt], sondern eine Funktion, die explizit aufgerufen werden muss zum Freigeben der Ressourcen - danach darf die Instanz nicht mehr benutzt werden).
public void freigeben() {
if (spiel != null) {
freigebenFarbe64(spiel);
spiel = null;
}
/* weitere Ressourcen werden hier freigegeben */
}
Angewendet sieht das dann so aus:
Stellung neueStellung = new Stellung(...);
/* mache irgendetwas mit der Instanz neueStellung */
neueStellung.freigeben();
/* die Instanz neueStellung darf nicht mehr benutzt werden.
Jetzt fehlen nur noch die zwei Methoden zum Verwalten des Ressourcen-Pools:
private static Farbe farbe64Array[][] = new Farbe[MAX_RECHENTIEFE + n][];
private static int farbe64Zeiger = 0;
private static Farbe neuFarbe64()[] {
if (farbe64Zeiger > 0) {
return farbe64Array[--farbe64Zeiger];
} else {
return new Farbe[64]; /* erstmalige Erzeugung */
}
}
private static void freigebenFarbe64(Farbe array[]) {
assert array.length == 64;
assert farbe64Zeiger < farbe64Array.length;
farbe64Array[farbe64Zeiger++] = array;
}
Die Namensgebung lässt schon darauf schließen, dass für jeden optimierten Arraytyp ein eigenes Methodenpaar nötig ist.
Der Code ist jetzt leider weniger Java-like und etwas schwerer lesbar. Daher sollte es jetzt auch zu einer Verbesserung der Performance kommen, damit sich der Aufwand gelohnt hat.
Eine Messung ergibt diese Werte
einfach gestartet werden und produziert
Grafiken, die hübsch anzusehen sind, leider jedoch wenig für uns
geeignete Informationen bieten.
