Das Performance-Handbuch: Softwareimplementierung und Performance

Zurück zu Design und Performance | Hoch zu Inhaltsverzeichnis | Vor zu Implementierung von Datenbankanwendungen

Die Implementierung - endlich. Meist ist der Programmierer derjenige, der die mangelnde Performance vorgeworfen bekommt. Dass dies nicht immer richtig ist, haben wir bereits betrachtet. Dieser Abschnitt wird an einem einfach nachzuvollziehenden Beispiel die grundlegenden Überlegungen darlegen.

Vor- und Nachteile

Implementation bedeutet zwangsweise das Arbeiten mit Typen, Objekten, Methoden, Variablen, etc. Ziel ist es, Beispiele und (teilweise) Anleitungen zu geben, wie die Performance durch gute Implementierung erhöht werden kann. Es ist nicht (mehr) Ziel, wesentliche Designentscheidungen zu treffen oder auf Native Programmierung umzuschwenken. Performante Implementierungstechniken können jedoch Auswirkungen auf das Design haben. Die Optimierung der Performance innerhalb der Implementierung ist der Standardfall. Innerhalb der Implementierung können Sie die größten Performancegewinne erreichen. Sie müssen jedoch darauf achten, das kein Trashcode entsteht. Eine Änderung der Implementation zieht im Gegensatz zur Optimierung von System und Umgebung zudem immer auch ein Testen der Anwendung nach sich.

Sie haben bei der Implementierung gewisse Optimierungsmöglichkeiten, welche unabhängig von der verwendeten Programmiersprache sind bzw. für viele Programmiersprachen zutreffen.

Grundwissen

Es gibt viele Faustregeln, deren Beachtung Ihnen helfen können. Wichtig ist insbesondere der Algorithmus. Die Optimierung / Änderung eines Algorithmus kann Ihnen eine bessere Performance bringen als die Summe aller anderen Optimierungen zusammen. Hierbei ist natürlich zu beachten, wo Sie die Performance erhöhen wollen. Anhand eines Beispiels werden wir hier ein bisschen Licht ins Dunkel bringen. Wir werden uns dazu der allseits beliebten Primzahlenberechnung widmen.

Zuerst einmal erstellen wir ein Quelltext, welcher die Aufgabe der Ermittlung und der Ausgabe der Primzahlen bis zu 100.000 funktional erledigt. Dies sollte immer der erste Schritt sein, einen Algorithmus zu entwickeln, welcher die Machbarkeit aufzeigt. Das Beispiel selbst wird für die Zeitmessung mit dem JDK 1.3 incl. Client HotSpot ausgeführt.

public void simplePrimzahlen(){
int i = 4;
boolean isPrim = true;
while (i < 100001){
  for (int j = 2; j < i-1; j++){
    if (i%j == 0){
      isPrim = false;
    }
  }
  if (isPrim){
    System.out.println(" "+i);
  }
  else{
    isPrim = true;
  }
  i++;
}

Ziel aller Optimierungen soll es sein, den Algorithmus zu verbessern oder durch einen günstigeren zu ersetzen. Am günstigsten ist es stets den Algorithmus durch einen besseren zu ersetzen. Da wir jedoch hier das Grundwissen über eine performante Implementierung erweitern wollen, werden wir diesen Schritt später betrachten. Mit unserem Beispiel haben wir die volle Funktionalität abgedeckt. Wir brechen mit etwa 95.000 Millisekunden jedoch keine Geschwindigkeitsrekorde.

Redundanz vermeiden

Ein wichtiger Punkt der OO ist die Vermeidung von Redundanz. D.h. Variablen oder Methoden, welche die gleiche Aufgabe bzw. Inhalt haben sollen auch nur einmal im Modell vorkommen. Aus Performancesicht bedeutet dies jedoch auch, Ausdrücke, mit gleichem Ergebnis bzw. Methoden sollten nur so oft verwendet werden, wie diese auch wirklich benötigt werden. Ziel ist es dabei die bekannte Werte nochmals zu berechnen bzw. Methoden unnötigerweise aufzurufen.

Auf den ersten Blick scheint unsere Anwendung jedoch keine Redundanz zu beinhalten. Ausdrücke wie

//vorher
...
z[0] = a * b + c * d;
z[1] = a * b + e * f;
...

welche wir zu

//nachher
...
double ab = a * b;
z[0] = ab + c * d;
z[1] = ab + e * f;
...

optimieren könnten sind zuerst nicht erkenntlich. Jedoch erkennen wir eine Methode „System.out.println(" "+i);“, welche wir jedes Mal erneut aufrufen. Wir wollen uns zuerst dieser Methode zuwenden. Unter der Voraussetzung, dass wir über genügend Arbeitsspeicher verfügen, bietet es sich an, unser Ergebnis nicht sofort auszugeben, sondern zu sammeln. Nach Beendigung unseres Algorithmus soll dann die Ausgabe erfolgen. Unser geänderter Quelltext sieht nun wie folgt aus:

public void simplePrimzahlen1(){
  int i = 4;
  boolean isPrim = true;
  String ergebnis = "";
  while (i < 100001){
    for (int j = 2; j < i-1; j++){
      if (i%j == 0){
        isPrim = false;
      }
    }
    if (isPrim){
      ergebnis = ergebnis+" "+i+"\n\r";
    }
    else{
      isPrim = true;
    }
    i++;
  }
  System.out.println(ergebnis);
}

Neben dem Speicherverbrauch zu Laufzeit hat sich auch der Bytecode minimal vergrößert. Unsere Berechnung benötigt nunmehr jedoch nur noch etwa 77.000 ms. Dies ist bereits eine erhebliche Einsparung von etwa 20%. In unserer Anwendung ist jedoch noch mehr Redundanz versteckt. Hier gilt es die Schleifen zu optimieren.

Schleifen

Schleifen sind wie gute Bremsen!. Ein Performanceleck in einer Schleife hat meist katastrophale Auswirkungen, da es bei jedem Schleifendurchlauf Ihre Anwendung bremst. Insbesondere innerhalb von Schleifen gilt daher möglichst alle Performancemöglichkeiten zu finden. Wir haben in unserer Primzahlenanwendung durch die Schleife noch eine weitere Redundanz. Innerhalb der for-Schleife berechnen wir für unseren Vergleich von j bei jedem Schleifendurchlauf i-1. Diese Berechnung wird allein bis i den Wert 103 erreicht, also 100 Durchläufe bereits 5050 mal durchgeführt. Es würden jedoch 100 Berechnungen ausreichen. Wenn i den Wert von 203 erreicht hat, hat unsere Anwendung bereits über 20000 statt 200 Berechnungen durchgeführt. Letztendlich führt dies zu etwa 5 Milliarden unnötigen Berechnungen. Dies bremst natürlich nicht nur eine Java-Anwendung aus. Nach einer weiteren Optimierung sieht unser Quelltext nun etwa so aus:

public void simplePrimzahlen2(){
  int i = 4;
  boolean isPrim = true;
  int vergleich;
  String ergebnis = "";
  while (i < 100001){
    vergleich = i-1;
    for (int j = 2; j < vergleich; j++){
      if (i%j == 0){
        isPrim = false;
      }
    }
    if (isPrim){
      ergebnis = ergebnis+" "+i+"\n\r";
    }
    else{
      isPrim = true;
    }
    i++;
  }
  System.out.println(ergebnis);
}

Wir haben die benötigte Zeit weiter verringern können. Beim Hot-Spot-Compiler macht sich diese Optimierungsmethode jedoch im Gegensatz zum Bytecode Interpreter nur gering bemerkbar – wir benötigen jetzt ca. 74.000 ms. Je mehr Iterationen eine Schleife durchführt, desto höher ist der Overhead. Daher ist es sinnvoll Ihre Schleifen auszurollen, sofern die Anzahl der Iterationen bekannt ist. Dies führt aus OO Sicht natürlich zu dem unschönen Effekt, dass Sie Quelltext mit der gleichen Funktionalität mehrfach in Ihrer Klasse haben. Dies ist nicht sehr Wartungsfreundlich.

Weitere Optimierungsmöglichkeiten liegen bei den Zählvariablen versteckt.

Zählschleifen

Die Zählschleife for ist außerdem noch bzgl. des Gesichtspunktes Inkrementierung oder Dekrementierung zu Untersuchen. Grundsätzlich ist der Schleifentest auf 0 besonders schnell auch wenn bei den heutigen Laufzeitumgebungen dies weniger ins Gewicht fällt. Daher sollten Zählschleifen abwärts ausgerichtet sein. Ich empfehle jedoch dringend hier mit der eingesetzten Laufzeitumgebung zu testen. Unterschiede treten hier bei unterschiedlichen Laufzeitumgebungen in allen Varianten auf. Mal ist das Hochzählen, mal das Heranzählen schneller und dann ist auch noch zu unterscheiden, ob es sich um eine Objektmethode oder Klassenmethode handelt. Sofern Sie Ihre Anwendung auch auf Interpretern ausführen müssen, ist es meist günstiger Zählschleifen abwärts zu zählen, da für den Vergleich auf 0 ein spezieller Bytecode z.B. in der Java Laufzeitumgebung vorhanden ist und der Vergleichswert nicht erst vom Methodenstack geholt werden muss.

Das verwenden von Slotvariablen als Zählvariable kann noch ein paar Prozente Geschwindigkeitsgewinn bringen. Innerhalb eine Methode werden die ersten 128 Bit durch Slotvariablen besetzt. Sofern es sich um eine Objektmethode handelt belegt jedoch die Referenz auf das Objekt bereits die ersten 32 Bit. Der verbleibende Speicher wird in der Reihenfolge der Deklaration Ihrer Variablen belegt. Auf diese 128 Bit hat die JVM, dank spezieller Operationen, einen besonders schnellen Zugriff. Es ist daher günstig auch die Zählvariable frühzeitig zu deklarieren. Ein weiterer wichtiger Punkt ist auch der Typ der Zählvariablen. Verwenden Sie für Schleifen nach Möglichkeit immer den primitiven Typ der nativ verwendet wird als Methodenvariable für das Zählen innerhalb einer Schleife. In unseren Beispielen mit einer 32-bit Java Laufzeitumgebung ist dies int. Hierdurch erreichen Sie die beste Ausführungsgeschwindigkeit.

Bei einigen Laufzeitumgebungen kann auch der freie Test zu einem Performancegewinn führen. Dabei verbindet der Compiler den ermittelten Wert gleich mit dem Bindungsflag. Dadurch kann der direkte Vergleich unterbleiben.

In manchen Fällen lässt man die Schleife auch besser auf einen Fehler laufen und wertet das Ergebnis mittels try-catch-finally Block aus. Gute Beispiele dafür sind große Arrays und Collections zu durchlaufen oder größere Dateien einzulesen. Hier wird absichtlich auf einen Fehler, wie EOFException gewartet. Beachten Sie dabei jedoch, dass bei kleineren Schleifen durch das Erzeugen der Exception die Ausführungsgeschwindigkeit verringert wird.

Algorithmus

Nachdem wir uns nun lange genug um schleifenspezifische Optimierungen gekümmert haben, wollen wir uns jetzt dem Algorithmus vornehmen. Dies sollte stets Ihr erster Ansatzpunkt sein. Da die anderen Optimierungsmöglichkeiten jedoch in diesem Fall nicht mehr sinnvoll gewesen wären, haben wir den Punkt zurückgestellt.

Unser Algorithmus bzgl. der Primzahlenberechnung eine Katastrophe! Wir prüfen für jede Ganzzahl, ob es sich um eine Primzahl handelt, obwohl uns bekannt ist, dass nur ungerade Zahlen Primzahlen sein können. Auch das Prüfen per Modulo ist nicht optimiert. Anstatt die Prüfung nur mit Primzahlen kleiner als die Wurzel unserer zu prüfenden Zahl zu arbeiten, prüfen wir für alle Ganzzahlen kleiner unserer zu prüfenden Zahl. Dazu kommt, dass wir die Prüfung selbst dann fortführen, wenn wir bereits festgestellt haben, das es sich um keine Primzahl handelt. Hinsichtlich dieser Punkte werden wir nochmals eine letzte Optimierung unseres Quelltextes vornehmen.

  private IntHashtable ih;
  private int gaussPrimesLength;
public void gaussPrimzahlen(){
  ih = new IntHashtable (0);
  int pos = 0;
  int i = 2;
  StringBuffer buf = new StringBuffer();
  ih.put(pos,2);
  while (i<100001){
    i++;
    gaussPrimesLength = ih.size();
    if (this.isPrimzahlForGauss(i)){
      pos++;
      ih.put(pos,i);
      buf.append(i).append("\n\r");
    }
  }
  System.out.println(buf.toString());
}

private final boolean isPrimzahlForGauss(int candidate){
  for (int i = 0; i<this.gaussPrimesLength;i++){
    if (candidate % this.ih.get(i) == 0){
      return false;
    }
  }
  return true;
}

Unsere jetzige Primzahlenberechnung benötigt nur noch etwa 2.500 Millisekunden (entspricht 2,6% der Zeit des ersten Algorithmus) und kann noch weiter optimiert werden. Für unser Beispiel soll uns diese Zeitspanne jedoch ausreichen. Mit einem guten Mathematikbuch können Sie auch andere Algorithmen ausprobieren. Es wird schnell deutlich, dass die Optimierung des Algorithmus der entscheidende Punkt ist.

Der richtige Datentyp

Wir haben es bereits bei den Schleifen angesprochen. Der richtige Datentyp ist wesentlich. Nutzen Sie stets nicht synchronisierte Daten (im Beispiel also inzwischen StringBuilder statt Stringbuffer) und die Datentypen die am schnellsten durch die Laufzeitumgebung verwendet werden können.

Konstante Ausdrücke

In diesem Abschnitt sind Variablen gemeint, denen ein konstanter Wert zugewiesen wird. Hier sind Optimierungen möglich, indem Sie prüfen, ob unnötige Berechnungen mit diesen Variablen durchgeführt werden. Ziel sollte es sein, konstante Ausdrücke ohne Berechnung zu definieren. So sollte aus

//vorher

...
x = 10;
y = 4 *2398;
... // mehr, ohne dass x sich ändert
x = x + 15;
...

besser

//nachher
...
x = 10:
y = 4 *2398;
... // mehr, ohne dass x sich ändert
x = 25;
...

werden. Hier wird eine unnötige Operation (Addition) vermieden.

Unerreichbaren Quelltext vermeiden

Unerreichbarer Quelltext sollte vermieden bzw. entfernt werden. Damit erhöhen Sie auch die Lesbarkeit Ihres Quelltextes. Der Javacompiler javac bietet mit dem Parameter -o eine gute Möglichkeit unerreichbaren Quelltext bei der Erstellung des Bytecode zu ignorieren.

// if-Bedingung vorher:
boolean wahr = true;
if (wahr){
   x = 1;
}
else{
   x = 2;
}
// if-Bedingung nachher:
   x = 1;

Und eine while(false) Schleife fällt ebenfalls weg

// while-Schleife vorher:
while (false){
  x++;
}
// while-Schleife nachher ;-):

Quelltextverschiebung

Quelltextverschiebung ist ebenfalls ein gute Möglichkeit die Geschwindigkeit Ihrer Anwendung zu erhöhen. Insbesondere innerhalb von Schleifen kann sich diese Überlegung bemerkbar machen. Sofern Sie Quelltext aus der Schleife herausziehen können, muss dieser Teil nicht mehr für jede Iteration durchgeführt werden. Bedenken Sie jedoch, dass Sie hier die Semantik Ihrer Implementierung verändern. Gerade für das Auslösen bzw. werfen von Fehlermeldungen (Exceptions) kann sich die Quelltextverschiebung sowohl negativ, als auch positiv bemerkbar machen. Das folgende Beispiel setzt den Dreisatz um. Dabei wird zuerst die Division durchgeführt, um die Division durch 0 möglichst früh abzufangen.

public double getDreisatz (int oben1, int unten1, int oben2){
  double ergebnis = unten1 / oben1;
  ergebnis *= oben2;
  return ergebnis;
}

Optimierung für bestimmte Anwendungsbereiche

Eine hauptsächlich aus der Spielprogrammierung bekannte Möglichkeit basiert auf dem Prinzip der „Tiles“. Das Konzept soll es ermöglichen mit wenigen Grafiken komplexe Spielebenen zu gestallten ohne gewaltige Grafikressourcen zu benötigen. Die Spielebenen werden dabei aus kleinen Grafiken, den Tiles, aufgebaut, welche alle in einer Datei gespeichert sind.

Die obige Abbildung zeigt ein Beispiel einer solchen Grafikdatei, wie Sie in einem Spiel vorkommt. Grundsätzlich haben dabei die Grafiktiles die gleiche Größe, was jedoch nicht zwingend nötig ist. Ein Tile ist lediglich eine kleine Grafik mit fester Größe und entspricht damit also schon fast der Definition des Interface Icon der Swing-Bibliothek. Dieses eigentlich aus der Spielentwicklung bekannte Prinzip lässt sich jedoch auch in anderem Zusammenhang verwenden, so dass wir später in Zusammenhang mit Swing wieder auf diesen Punkt zurückkommen werden. Programmiersprachenunabhängige Optimierungen sind ein guter Ansatz. Sie erreichen somit eine schnelle Anwendung ohne von Implementation der JVM bzw. des Betriebssystems abhängig zu sein. Auch bei der Umsetzung in eine andere Programmiersprache haben Sie bereits einen performanten Ansatz. Erster Schritt der Optimierung sollte stets das Überdenken des Algorithmus sein. Danach sollten Sie Ihre Schleifen in Verbindung mit der Prüfung auf Redundanz und Quelltextverschiebung prüfen. Erst nach dieser Optimierung sollten Sie in die programmiersprachenabhängige Optimierung einsteigen.

---

Zurück zu Design und Performance | Hoch zu Inhaltsverzeichnis | Vor zu Implementierung von Datenbankanwendungen