Machen Sie Java schnell: Optimieren!

Laut dem wegweisenden Informatiker Donald Knuth ist "vorzeitige Optimierung die Wurzel allen Übels". Jeder Artikel zur Optimierung muss mit dem Hinweis beginnen, dass es normalerweise mehr Gründe gibt, nicht zu optimieren als zu optimieren.

  • Wenn Ihr Code bereits funktioniert, ist die Optimierung ein sicherer Weg, um neue und möglicherweise subtile Fehler einzuführen

  • Durch die Optimierung wird das Verständnis und die Wartung von Code tendenziell schwieriger

  • Einige der hier vorgestellten Techniken erhöhen die Geschwindigkeit, indem sie die Erweiterbarkeit des Codes verringern

  • Das Optimieren von Code für eine Plattform kann es auf einer anderen Plattform sogar noch schlimmer machen

  • Es kann viel Zeit für die Optimierung aufgewendet werden, wobei die Leistung nur geringfügig gesteigert wird, und es kann zu verschleiertem Code kommen

  • Wenn Sie übermäßig von der Optimierung des Codes besessen sind, werden Sie hinter Ihrem Rücken als Nerd bezeichnet

Vor der Optimierung sollten Sie sorgfältig überlegen, ob Sie überhaupt optimieren müssen. Die Optimierung in Java kann ein schwer fassbares Ziel sein, da die Ausführungsumgebungen variieren. Die Verwendung eines besseren Algorithmus führt wahrscheinlich zu einer größeren Leistungssteigerung als jede Menge von Optimierungen auf niedriger Ebene und führt unter allen Ausführungsbedingungen mit größerer Wahrscheinlichkeit zu einer Verbesserung. In der Regel sollten Optimierungen auf hoher Ebene in Betracht gezogen werden, bevor Optimierungen auf niedriger Ebene durchgeführt werden.

Warum also optimieren?

Wenn es so eine schlechte Idee ist, warum überhaupt optimieren? Nun, in einer idealen Welt würden Sie nicht. Die Realität ist jedoch, dass das größte Problem bei einem Programm manchmal darin besteht, dass es einfach zu viele Ressourcen benötigt und diese Ressourcen (Speicher, CPU-Zyklen, Netzwerkbandbreite oder eine Kombination) möglicherweise begrenzt sind. Codefragmente, die in einem Programm mehrmals vorkommen, sind wahrscheinlich größenabhängig, während Code mit vielen Ausführungsiterationen möglicherweise geschwindigkeitsabhängig ist.

Mach Java schnell!

Als interpretierte Sprache mit einem kompakten Bytecode taucht die Geschwindigkeit oder das Fehlen eines Bytecodes in Java am häufigsten als Problem auf. Wir werden uns in erster Linie damit befassen, wie Java schneller ausgeführt werden kann, anstatt es auf kleinerem Raum unterzubringen. Wir werden jedoch darauf hinweisen, wo und wie sich diese Ansätze auf den Speicher oder die Netzwerkbandbreite auswirken. Der Fokus wird eher auf der Kernsprache als auf den Java-APIs liegen.

Eine Sache, die wir hier nicht diskutieren werden, ist übrigens die Verwendung nativer Methoden, die in C oder Assembly geschrieben sind. Die Verwendung nativer Methoden kann zwar die ultimative Leistungssteigerung bewirken, geht jedoch zu Lasten der Plattformunabhängigkeit von Java. Es ist möglich, sowohl eine Java-Version einer Methode als auch native Versionen für ausgewählte Plattformen zu schreiben. Dies führt auf einigen Plattformen zu einer Leistungssteigerung, ohne dass die Ausführung auf allen Plattformen aufgegeben werden muss. Aber das ist alles, was ich zum Thema Ersetzen von Java durch C-Code sagen werde. (Weitere Informationen zu diesem Thema finden Sie im Java-Tipp "Native Methoden schreiben".) In diesem Artikel konzentrieren wir uns darauf, wie Sie Java schnell machen können.

90/10, 80/20, Hütte, Hütte, Wanderung!

In der Regel werden 90 Prozent der Ausführungszeit eines Programms für die Ausführung von 10 Prozent des Codes aufgewendet. (Einige Leute verwenden die 80-Prozent / 20-Prozent-Regel, aber meine Erfahrung mit dem Schreiben und Optimieren von kommerziellen Spielen in mehreren Sprachen in den letzten 15 Jahren hat gezeigt, dass die 90-Prozent / 10-Prozent-Formel typisch für leistungshungrige Programme ist, da nur wenige Aufgaben dazu neigen mit großer Häufigkeit durchgeführt werden.) Die Optimierung der anderen 90 Prozent des Programms (wo 10 Prozent der Ausführungszeit aufgewendet wurden) hat keine merklichen Auswirkungen auf die Leistung. Wenn Sie 90 Prozent des Codes doppelt so schnell ausführen könnten, wäre das Programm nur 5 Prozent schneller. Die erste Aufgabe bei der Optimierung des Codes besteht also darin, die 10 Prozent (häufig weniger als diese) des Programms zu ermitteln, die den größten Teil der Ausführungszeit in Anspruch nehmen. Dies ist n'Nicht immer dort, wo Sie es erwarten.

Allgemeine Optimierungstechniken

Es gibt verschiedene gängige Optimierungstechniken, die unabhängig von der verwendeten Sprache angewendet werden. Einige dieser Techniken, wie die globale Registerzuweisung, sind ausgefeilte Strategien zum Zuweisen von Maschinenressourcen (z. B. CPU-Registern) und gelten nicht für Java-Bytecodes. Wir werden uns auf die Techniken konzentrieren, die im Wesentlichen die Umstrukturierung von Code und das Ersetzen äquivalenter Operationen innerhalb einer Methode umfassen.

Kraftreduzierung

Eine Festigkeitsreduzierung tritt auf, wenn eine Operation durch eine äquivalente Operation ersetzt wird, die schneller ausgeführt wird. Das häufigste Beispiel für eine Festigkeitsreduzierung ist die Verwendung des Verschiebungsoperators zum Multiplizieren und Dividieren von ganzen Zahlen mit einer Potenz von 2. x >> 2Kann beispielsweise anstelle von x / 4und x << 1ersetzt werden x * 2.

Eliminierung gemeinsamer Unterausdrücke

Durch die Eliminierung gemeinsamer Unterausdrücke werden redundante Berechnungen entfernt. Anstatt zu schreiben

double x = d * (lim / max) * sx; double y = d * (lim / max) * sy;

Der gemeinsame Unterausdruck wird einmal berechnet und für beide Berechnungen verwendet:

double depth = d * (lim / max); double x = depth * sx; double y = depth * sy;

Code Bewegung

Codebewegung verschiebt Code, der eine Operation ausführt oder einen Ausdruck berechnet, dessen Ergebnis sich nicht ändert oder unveränderlich ist . Der Code wird so verschoben, dass er nur ausgeführt wird, wenn sich das Ergebnis ändern kann, anstatt jedes Mal ausgeführt zu werden, wenn das Ergebnis erforderlich ist. Dies ist am häufigsten bei Schleifen der Fall, kann jedoch auch Code beinhalten, der bei jedem Aufruf einer Methode wiederholt wird. Das Folgende ist ein Beispiel für eine invariante Codebewegung in einer Schleife:

for (int i = 0; i < x.length; i++) x [i] * = Math.PI * Math.cos (y); 

wird

double picosy = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i++)x [i] * = picosy;

Schleifen abrollen

Das Abrollen von Schleifen reduziert den Overhead des Schleifensteuercodes, indem jedes Mal mehr als eine Operation durch die Schleife ausgeführt wird und folglich weniger Iterationen ausgeführt werden. Wenn wir aus dem vorherigen Beispiel wissen, dass die Länge von x[]immer ein Vielfaches von zwei ist, können wir die Schleife wie folgt umschreiben:

double picosy = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i += 2) {x [i] * = picosy; x [i + 1] * = picosy; }}

In der Praxis führt das Abrollen von Schleifen wie dieser, bei denen der Wert des Schleifenindex innerhalb der Schleife verwendet wird und separat inkrementiert werden muss, in interpretiertem Java nicht zu einer nennenswerten Geschwindigkeitssteigerung, da den Bytecodes Anweisungen zum effizienten Kombinieren der " +1"in den Array-Index.

Alle Optimierungstipps in diesem Artikel enthalten eine oder mehrere der oben aufgeführten allgemeinen Techniken.

Den Compiler zum Laufen bringen

Moderne C- und Fortran-Compiler erzeugen hochoptimierten Code. C ++ - Compiler produzieren im Allgemeinen weniger effizienten Code, sind aber immer noch auf dem besten Weg, optimalen Code zu produzieren. Alle diese Compiler haben viele Generationen unter dem Einfluss eines starken Marktwettbewerbs durchlaufen und sind zu fein geschliffenen Werkzeugen geworden, um jeden letzten Leistungsabfall aus dem normalen Code herauszuholen. Sie verwenden mit ziemlicher Sicherheit alle oben vorgestellten allgemeinen Optimierungstechniken. Es gibt jedoch noch viele Tricks, mit denen Compiler effizienten Code generieren können.

Javac, JITs und native Code-Compiler

Der Optimierungsgrad, javacder beim Kompilieren von Code zu diesem Zeitpunkt ausgeführt wird, ist minimal. Standardmäßig wird Folgendes ausgeführt:

  • Konstante Faltung - Der Compiler löst alle konstanten Ausdrücke auf, die i = (10 *10)kompiliert werden i = 100.

  • Verzweigungsfaltung (meistens) - unnötige gotoBytecodes werden vermieden.

  • Begrenzte Eliminierung von totem Code - Für Anweisungen wie wird kein Code erzeugt if(false) i = 1.

Das Optimierungsniveau, das javac bietet, sollte sich wahrscheinlich dramatisch verbessern, wenn die Sprache reift und Compiler-Anbieter auf der Grundlage der Codegenerierung ernsthaft miteinander konkurrieren. Java erhält gerade Compiler der zweiten Generation.

Dann gibt es Just-in-Time-Compiler (JIT), die Java-Bytecodes zur Laufzeit in nativen Code konvertieren. Einige sind bereits verfügbar, und obwohl sie die Ausführungsgeschwindigkeit Ihres Programms drastisch erhöhen können, ist der Optimierungsgrad, den sie ausführen können, eingeschränkt, da die Optimierung zur Laufzeit erfolgt. Ein JIT-Compiler befasst sich mehr mit der schnellen Generierung des Codes als mit der Generierung des schnellsten Codes.

Native Code-Compiler, die Java direkt zu nativem Code kompilieren, sollten die höchste Leistung bieten, jedoch auf Kosten der Plattformunabhängigkeit. Glücklicherweise werden viele der hier vorgestellten Tricks von zukünftigen Compilern ausgeführt, aber im Moment ist ein wenig Arbeit erforderlich, um den Compiler optimal zu nutzen.

javacbietet eine Leistungsoption, die Sie aktivieren können: Aufrufen der -OOption, damit der Compiler bestimmte Methodenaufrufe inline:

javac -O MyClass

Durch Inlining eines Methodenaufrufs wird der Code für die Methode direkt in den Code eingefügt, der den Methodenaufruf ausführt. Dadurch entfällt der Overhead des Methodenaufrufs. Bei einer kleinen Methode kann dieser Overhead einen erheblichen Prozentsatz ihrer Ausführungszeit ausmachen. Beachten Sie, dass nur Verfahren , wie sie entweder erklärt private, staticoder finalkann für inlining, weil nur statisch durch den Compiler behoben diese Methoden in Betracht gezogen werden. Außerdem werden synchronizedMethoden nicht inline. Der Compiler integriert nur kleine Methoden, die normalerweise nur aus einer oder zwei Codezeilen bestehen.

Leider haben die 1.0-Versionen des Javac-Compilers einen Fehler, der Code generiert, der den Bytecode-Verifizierer nicht bestehen kann, wenn die -OOption verwendet wird. Dies wurde in JDK 1.1 behoben. (Der Bytecode-Prüfer überprüft den Code, bevor er ausgeführt werden darf, um sicherzustellen, dass er keine Java-Regeln verletzt.) Er integriert Methoden, die auf Klassenmitglieder verweisen, auf die die aufrufende Klasse nicht zugreifen kann. Zum Beispiel, wenn die folgenden Klassen mit der -OOption zusammen kompiliert werden

Klasse A {private static int x = 10; public static void getX () {return x; }} Klasse B {int y = A.getX (); }}

Der Aufruf von A.getX () in Klasse B wird in Klasse B so eingefügt, als ob B wie folgt geschrieben worden wäre:

Klasse B {int y = Ax; }}

Dies führt jedoch dazu, dass die Generierung von Bytecodes auf die private Ax-Variable zugreift, die im Code von B generiert wird. Dieser Code wird einwandfrei ausgeführt, aber da er gegen die Zugriffsbeschränkungen von Java verstößt, wird er vom Prüfer bei IllegalAccessErrorder ersten Ausführung des Codes markiert .

Dieser Fehler macht die -OOption nicht unbrauchbar, aber Sie müssen vorsichtig sein, wie Sie sie verwenden. Wenn es für eine einzelne Klasse aufgerufen wird, kann es bestimmte Methodenaufrufe innerhalb der Klasse ohne Risiko einbinden. Es können mehrere Klassen zusammengefügt werden, solange keine potenziellen Zugriffsbeschränkungen bestehen. Und ein Teil des Codes (z. B. Anwendungen) unterliegt nicht der Bytecode-Überprüfung. Sie können den Fehler ignorieren, wenn Sie wissen, dass Ihr Code nur ausgeführt wird, ohne der Überprüfung unterzogen zu werden. Weitere Informationen finden Sie in meinen Javac-O-FAQ.

Profiler

Glücklicherweise verfügt das JDK über einen integrierten Profiler, mit dessen Hilfe ermittelt werden kann, wo Zeit in einem Programm verbracht wird. Es verfolgt die in jeder Routine verbrachte Zeit und schreibt die Informationen in die Datei java.prof. Verwenden Sie zum Ausführen des Profilers die -profOption, wenn Sie den Java-Interpreter aufrufen:

java -prof myClass

Oder zur Verwendung mit einem Applet:

java -prof sun.applet.AppletViewer myApplet.html

Es gibt einige Einschränkungen bei der Verwendung des Profilers. Die Profilerausgabe ist nicht besonders leicht zu entschlüsseln. In JDK 1.0.2 werden die Methodennamen auf 30 Zeichen gekürzt, sodass einige Methoden möglicherweise nicht unterschieden werden können. Leider gibt es mit dem Mac keine Möglichkeit, den Profiler aufzurufen, sodass Mac-Benutzer kein Glück haben. Darüber hinaus enthält die Java-Dokumentseite von Sun (siehe Ressourcen) nicht mehr die Dokumentation für die -profOption. Wenn Ihre Plattform diese -profOption jedoch unterstützt , können entweder HyperProf von Vladimir Bulatov oder ProfileViewer von Greg White zur Interpretation der Ergebnisse verwendet werden (siehe Ressourcen).

Es ist auch möglich, Code zu "profilieren", indem explizites Timing in den Code eingefügt wird:

long start = System.currentTimeMillis(); // do operation to be timed here long time = System.currentTimeMillis() - start;

System.currentTimeMillis()Gibt die Zeit in 1/1000 Sekunde zurück. Einige Systeme, wie z. B. ein Windows-PC, verfügen jedoch über einen Systemtimer mit einer geringeren (viel geringeren) Auflösung als eine 1 / 1000stel Sekunde. Selbst eine 1 / 1000stel Sekunde ist nicht lang genug, um viele Operationen genau zu planen. In diesen Fällen oder auf Systemen mit Timern mit niedriger Auflösung kann es erforderlich sein, die Zeit festzulegen, die benötigt wird, um den Vorgang n- mal zu wiederholen, und dann die Gesamtzeit durch n zu dividieren , um die tatsächliche Zeit zu erhalten. Selbst wenn eine Profilerstellung verfügbar ist, kann diese Technik nützlich sein, um eine bestimmte Aufgabe oder Operation zeitlich zu steuern.

Hier einige abschließende Hinweise zur Profilerstellung:

  • Stellen Sie den Code immer vor und nach dem Vornehmen von Änderungen ein, um sicherzustellen, dass Ihre Änderungen zumindest auf der Testplattform das Programm verbessert haben

  • Versuchen Sie, jeden Timing-Test unter identischen Bedingungen durchzuführen

  • Entwickeln Sie nach Möglichkeit einen Test, der nicht auf Benutzereingaben beruht, da die unterschiedlichen Benutzerreaktionen dazu führen können, dass die Ergebnisse schwanken

Das Benchmark-Applet

Das Benchmark-Applet misst die Zeit, die für die Ausführung einer Operation Tausende (oder sogar Millionen) Mal benötigt wird, subtrahiert die Zeit, die für andere Operationen als den Test aufgewendet wurde (z. B. den Schleifen-Overhead), und berechnet anhand dieser Informationen, wie lange jede Operation dauert dauerte. Jeder Test wird ungefähr eine Sekunde lang ausgeführt. Bei dem Versuch, zufällige Verzögerungen bei anderen Vorgängen zu vermeiden, die der Computer während eines Tests ausführen kann, führt er jeden Test dreimal aus und verwendet das beste Ergebnis. Es wird auch versucht, die Speicherbereinigung als Faktor in den Tests zu eliminieren. Aus diesem Grund sind die Benchmark-Ergebnisse umso genauer, je mehr Speicher für den Benchmark verfügbar ist.