GWT Performance-Tuning: Optimierung von Arrays

In meinem letzten Beitrag habe ich gezeigt, wie man bei GWT die Performance einzelner Methoden ermitteln kann. Davon ausgehend möchte ich heute an Hand eines Beispieles zeigen, wie man die Performance eines GWT-Programmes deutlich verbessern kann.

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:

Bei dem Beispiel handelt es sich um ein Spiel (Reversi, um genau zu sein, spielt aber für das Beispiel keine Rolle), bei dem der beste Zug des Computers dadurch ermittelt wird, dass alle möglichen Züge des Computers rekursiv durchprobiert werden.  Mit steigender Rechentiefe steigt die Zahl möglicher Züge und damit die Rechenzeit exponentiell an.

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 ist
    private 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:

Die Reihenfolge der Funktionen hat sich geändert. Die drei intensiv an der Arrayerzeugung beteiligten Funktionen wrapArray(), initDims_0 und arraycopy() benötigen zusammen nur noch 34,4% statt wie vorher 46,21%. Die anderen Funktionen benötigen jetzt prozentual mehr Zeit, ist aber auch logisch, da die Summe immer 100% sind. Da wir an den anderen Funktionen nichts geändert haben, bedeutet dies, dass unser Programm effektiv schneller geworden ist. (Mit etwas Mathe ergibt sich, dass das Programm nur noch 82% der bisherigen Rechenzeit braucht oder mit anderen Worten um 22% schneller geworden ist.)

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

Die beiden Funktionen wrapArray() und arraycopy() benötigen zusammen nur noch 11,96%, initDims_0() taucht überhaupt nicht mehr auf, was heißt, diese Funktion benötigt weniger als 0.04%. Für das Array-Handling haben wir jetzt nur noch 12% statt 34,4% oder 46,21%. Dies heißt, dass noch 74.5% der Rechenzeit der Version mit erster Optimierung und 61% der Rechenzeit der ursprünglichen Version benötigt werden oder mit anderen Worten dass das Programm um 34% bzw. 63,6% schneller geworden ist. Dieser Geschwindigkeitsgewinn ist für den Benutzer ganz erheblich bemerkbar, bedeutet aber keine funktionale Einschränkung für ihn.

Fazit:

Arrays sind in Java zwar schnell, nicht aber in GWT. Die Erzeugung neuer Arrays kostet viel Zeit. Der Wechsel auf andere Objekte wie z. B. Listen löst das Problem nicht, da diese meistens ebenfalls intern auf Arrays basieren. Stattdessen sollte im Programmdesign überlegt werden, wie die Anzahl der Array-Erzeugungen gering gehalten wird. Dies betrifft nur Arrays, die in oft durchlaufenen Programmteilen erzeugt werden. Es spricht aber nichts gegen die eher statische Verwendung einer auch größeren Anzahl von Arrays.