Optimierung von Java-Programmen

In diesem Abschnitt sollen die Möglichkeiten und Probleme der Optimierung von Java-Programmen durch eine optimierenden Compiler, der nativen Maschinencode erzeugt, dargestellt werden. Dabei zeigt sich zunächst, daß die Bytecode-Repräsentation von Java-Programmen nicht im Hinblick auf optimierende Compiler entworfen wurde. Während der abstrakte Instruktionssatz zur Ausführung durch einen Interpreter durchaus geeignet erscheint, sind wichtige Informationen durch die lineare Repräsentation des Codes und durch unstrukturierten Kontrollfluß stark verschleiert, da die Abbildung von Java-Quellcode auf Bytecode nicht strukturerhaltend ist. Es erfordert aufwendige Analysen, um beispielsweise die Struktur einer for-Schleife und die damit verbundenen Informationen über die Schleifenvariable zu rekonstruieren. Gängige Compileranalysen suchen gar nach spezifischen Bytecodemustern, wie sie von Quellcodecompilern wie javac oder jikes erzeugt werden.

Das nahezu klassische Problem bei der Optimierung objektorientierter Sprachen besteht in ihrem auszeichnendem Mechanismus: in reinen objektorientierten Sprachen (Smalltalk-80, Tycoon-2) sind alle Datentypen Teil einer Klassenhierarchie, die durch einen Vererbungsbeziehung verbunden ist (,,everything is an object``). Alle Operationen auf diesen Datentypen werden durch dynamischen Methodeaufruf, d.h. der empfängertyp-spezifischen Auswahl einer Methode zur Laufzeit, implementiert. Dementsprechend besteht Programmcode dieser Sprachen praktisch ausschließlich aus Methodenaufrufen, die ihren Abschluß in systemeigenen oder extern implementierten Methoden haben.

Java ist im Gegensatz zu den o.g. Sprachen keine reine objektorientierte Sprache. Sie kennt, wie auch C++, sogenannte Basisdatentypen (integer, float, byte, etc.), die es erlauben, Berechnungen mit diesen Typen ohne dynamischen Methodenaufruf zu implementieren. Außerdem ist es in Java möglich, den statische Methodenbindung zu erreichen, indem eine Methode als private, static oder final deklariert wird. Generell gilt aber: wird ein objektorientierter Programmierstil angewendet, tritt auch in Java-Programmen eine hohe Dichte an dynamischen Methodenaufrufen auf. Diese sind aus zwei Gründen relativ ineffizient gegenüber ihren statisch gebundenen Pendants:

1.

Die zu Empfänger und Signatur der Nachricht passende Methode muß zunächst gefunden werden. Dazu wird in einer ,,naiven`` Implementierung die Methodentabelle der Empfängerklasse und ihrer Superklassen nach der entsprechenden Nachricht durchsucht. Findet die Maschine hier keinen Eintrag, so wird eine entsprechende Ausnahme ausgelöst. Bei einer solchen ,,naiven`` Lösung wird also bei jedem Versenden einer Nachricht eine große Zahl von Instruktionen ausgeführt.

2.

Der anschliessend ausgeführte Sprung ist indirekt, d.h. er führt an eine berechnete Adresse. Moderne Prozessoren sind hingegen auf eine Vorhersage des Kontrollflusses angewiesen, um die tiefen Pipelines (ihre Ausführungseinheiten) befüllen zu können. Aufgrund schlechter Vorhersagetechniken im Prozessor führt eine hohe Dichte indirekter Sprünge zu häufigem Stillstand der Pipelines[Driesen et al., 1995].

Insbesondere führt jedoch der hohe Anteil an Sprüngen zu sehr kleinen optimierbaren Codeeineheiten. Dies behindert die Anwendung praktisch aller aus dem klassischem Compilerbau bekannten Optimierungen, da diese Seiteneffekte der gerufenen Methoden nicht in Betracht ziehen können und daher viele Optimierungen über Aufrufe hinweg nicht möglich sind.

Diese ,,Grundprobleme`` der Optimierung objektorientierter Sprachen werden seit langem erforscht und es existieren verschiedene Ansätze, um sie zu mildern. Die wichtigsten Techniken sind virtual function tables, inline caching und inlining (für eine genauere Betrachtung siehe [Driesen, 1999]):

virtual function tables (vtables)

reduzieren den Aufwand der Methodenauswahl. Dazu wird den Methoden im Bereich einer Vererbungshierarchie eine fortlaufende Nummer zugewiesen, wobei in jeder Klasse mit der höchsten Nummer der Superklasse begonnen wird. Methoden, die bereits in einer Superklasse deklariert wurden, erhalten keine neue Nummer. Enthält eine Klasse m (ererbte oder implementierte) Methoden, so sind diese von 0..m-1 durchnumeriert. Somit läßt sich eine einfach indizierbare Methodentabelle (vtable) erstellen. Der dynamische Methodenaufruf reduziert sich darauf, die zum Empfänger gehörige vtable zu laden und über den Methodenindex die Adresse der passenden Methode zu erhalten.

inline caching:

Für einen bestimmten Aufrufort wird die Adresse der zuletzt gewählten Methode zusammen mit der Klassen-ID des Empfängers inline, also direkt im erzeugten Code, gespeichert. Soll der Aufruf erneut ausgeführt werden, so wird zunächst die Empfängerklasse mit der zuvor gespeicherten verglichen. Stimmen diese überein, so kann direkt an die zuvor gespeicherte Methodenadresse verzweigt werden. Andernfalls wird eine normale Methodensuche ausgeführt, und das Ergebnis wird an Stelle der alten Daten gespeichert.

inlining:

Kann zur Übersetzungszeit entschieden werden, welche Methode an einer bestimmten Aufrufstelle mit großer Wahrscheinlichkeit aufgerufen werden wird, so kann der Methodenkörper -- unter Beachtung gewisser Einschränkungen -- in den Methodenkörper der aufrufenden Methode eingebettet werden. Diese Methode entspricht im Wesentlichen der Prozedurintegration eines klassischen Compilers, es muß jedoch wie beim inline caching ein Test in den Code integriert werden, ob die zur Übersetzungszeit getroffene Annahme über die Empfängerklasse zutrifft. Anderfall muß eine normale Methodensuche durchgeführt werden.

Vtables erlauben die Durchführung der Methodensuche mit zwei Indirektionen ( $receiver \rightarrow vtable \rightarrow method$). Allerdings wird ein indirekter Sprung ausgeführt, der genannte Probleme im Zusammenhang mit modernen Prozessoren aufweist.

Durch inline caching wird im Erfolgfall nur eine Indirektionen zum Auffinden der Methode benötigt. Noch wichtiger ist aber, daß das folgende Sprungziel dem Prozessor direkt im Maschinencode zur Verfügung steht. Statt indirekter Sprungvorhersage muß das Ergebnis des Klassentests vorhergesagt werden; diese binäre branch prediction wird im Allgemeinen weit besser unterstützt.

Inlining vermeidet im Vergleich zu inline caching noch den Aufwand eines Methodenaufrufes. Zudem wird dabei die zur Verfügung stehende Codeeinheit vergrößert und ermöglicht damit eine bessere Anwendung klassischer Optimierungen. Allerdings muß die resultierende Codegröße in Betracht gezogen werden, weshalb unbegrenzte Anwendung von inlining nicht gewinnbringend ist. Hierzu sind entsprechende Heuristiken anzuwenden, die in Abschnitt 3.2 beleuchtet werden.

Ein weiterer Umstand, der die Optimierung von Java-Programmen durch ein Erzwingen vieler bedingter Sprünge behindert, betrifft die Behandlung von Ausnahmen. Dieser begründet sich aus der Kombination zweier Faktoren:

• Wie die meisten Programmiersprachen mit Ausnahmebehandlung erfordert Java eine präzise Implementierung dieses Mechanismus -- dies ist in [Gosling et al., 1996] wie folgt definiert:

  Exceptions in Java are precise: when the transfer of control takes place, all effects of the statements executed and expressions evaluated before the point from which the exception is thrown must appear to have taken place. No expressions, statements, or parts thereof that occur after the point from which the exception is thrown may appear to have been evaluated. If optimized code has speculatively executed some of the expressions or statements which follow the point at which the exception occurs, such code must be prepared to hide this speculative execution from the user-visible state of the Java program.

  Kurz gesagt, müssen sowohl der Typ einer ausgelösten Ausnahme als auch der Programmzustand den zu erwartenden Größen bei einer sequentiellen Bearbeitung des Quellcodes entsprechen.
• In Java-Programmen kann eine Vielzahl von Sprachkonstrukten aufgrund implizit assoziierter Laufzeittests eine Ausnahme auslösen. Dazu zählen Tests auf die Null-Referenz im Fall von Methodenaufrufen und Feldzugriffen, Index-Überprüfungen bei Array-Operationen, arithmetische Fehler und andere.

Stellt man Ausnahmen als zusätzliche Kanten im Kontrollflußgraph dar, so erhält man einen Graphen mit vielen relativ kleinen basic blocks, die für sich wenig Gelegenheit zur Optimierung bieten.

Ein Beispiel verdeutlicht das Problem: In Abbildung 2.3 wird eine Methode in Java-Code (i) und in einer optimierten Zwischenrepräsentation^2.1 (ii) dargestellt. Der Ausdruck 1/c in (i-4) ist schleifenkonstant; seine Auswertung sollte daher vor der Schleife erfolgen. Darstellung (ii) verdeutlicht jedoch die Abhängigkeit der Instruktion (ii-7) von (ii-5). Enthielte nämlich a an erster Position null, so muß korrekterweise eine NullPointerException ausgelöst werden, und keine ArithmeticException im Falle von c == 0. Wäre die Länge von a beispielsweise gleich 0, so dürfte ein Nullwert von c gar keine Ausnahme nach sich ziehen.

Abbildung: Darstellung einer Java-Methode in unoptimierter Form (i) und in einer optimierten Zwischenrepräsentation (ii)

Ein ähnliches Problem erwächst theoretisch aus der Definition des Java-Speichermodells [Gosling et al., 1996]. Wie in Abschnitt 2.3.2 näher erläutert, ist das Speichermodell schwer verständlich, widersprüchlich und verhindert die Generierung effizienten Codes, da die Umordnung von Instruktionen durch den Compiler stark eingeschränkt sind.

Allerdings wird die aktuelle Spezifikation praktisch von jeder VM verletzt -- darüber hinaus ist ein neues Speichermodell in der Entwicklung. Insofern stellt das aktuelle Java Memory Model kein faktisches Problem für die Implementierung von Optimierungen dar.

Ist es gelungen, durch geeignete Techniken die Abstraktionseinheiten ausreichend zu vergrößern, so ist eine anschließende Optimierung nach klassischen Techniken eines Compiler-Backends möglich. Diese Techniken verfolgen dabei drei Ziele:

1.

Es wird versucht, redundante Berechnungen zu vermeiden. Wird ein Ausdruck in einer Funktion mehrfach ausgewertet, so kann dies durch Zwischenspeicherung des Ergebnisses vermieden werden.

2.

Der Zugriff auf den Hauptspeicher zum Auslesen von Daten stellt bei der Ausführung in modernen Prozessoren einen wachsenden Engpaß dar. Auch moderne Architekturen mit pipelines können dieses Problem nur mildern. Indem optimierter Code Register verwendet und in einem geeigneten Zugriffsmuster auf den Cache zugreift, werden die Zugriffe auf den Hauptspeicher minimiert.

3.

Superskalare Prozessoren verfügen über mehrere Ausführungseinheiten, die parallel Aufgaben ausführen können. Um die Parallelität dieser Architekturen auf Instruktionsebene besser auszunutzen, müssen die Abhängigkeiten der einzelnen Instruktionen voneinander verringert werden.

Die verwendeten Optimierungen umfassen Techniken wie ,,Constant Folding and Propagation``, ,,Algebraische Vereinfachungen``, ,,Common Subexpression Elimination``, ,,Loop Unrolling,,, ,,Software Pipelining`` und Registerallokation (siehe dazu Anhang B).

Insgesamt läßt sich festhalten, daß die Optimierung eines Java-Programms aus den beiden Komplexen der objektorientierten Optimierung und der klassischen Compiler-Optimierung besteht. Erst wenn das durch dynamische Methodenaufrufe und Besonderheiten der Java-Sprachdefinition [Gosling et al., 1996] hervorgerufene Problem kurzer optimierbarer Einheiten gelöst ist, können die klassischen Optimierungen greifen. Der dynamische Compiler einer virtuellen Maschine muß diese beiden Komplexe implementieren, um effizienten Code zu generieren.