next up previous contents
Next: Diskussion Up: Globale Analyseverfahren Previous: Class Hierarchy Analysis   Inhalt


Escape Analysis

Da Java die nebenläufige Programmausführung in mehreren Threads unterstützt, müssen Datenstrukturen, die von mehrern Threads nebenläufig verwendet werden können, in kritischen Abschnitten durch Synchronisation geschützt werden. Dies ist der Grund, weshalb beispielsweise die Java-Klasse java.util.Vector mit Hilfe von Sychronisationen threadsicher implementiert wurde.

Jedoch ist nicht jede Verwendung von java.util.Vector eine Nebenläufige, wie aus dem in Abbildung 3.7 dargestellte Beispiel aus [Whaley and Rinard, 1999] ersichtlich wird. Es zeigt, wie durch globale Analyse thread-lokale Objekte identifiziert werden; dies sind Objekte, die nur von einem Thread erreichbar sind. Auf derartigen Objekten kann einen Synchronisation entfallen, da Konflikte durch nebenläufigen Zugriff ausgeschlossen sind.

Abbildung 3.7: Beispiel eines einfache Servers
\begin{figure}
\begin{center}
\begin{verbatim}1: public class Server extends Th...
...1: } catch (IOException e) {}
22: }
23: }\end{verbatim} \end{center}\end{figure}

Im Beispiel wird ein einfacher Server implementiert, der eingehende Verbindungen auf einer ServerSocket annimmt. Für jede neue Verbindung wird in Zeile 14 ein neuer ServerHelper-Thread erzeugt und gestartet. Danach wird durch Suche in dem Vector connectorList geprüft, ob bereits eine Verbindung zu dem neuen Client besteht und ggf. die Variable duplicateConnections erhöht.

Durch Analyse der geschilderten Methode Server::run und der beiden Methoden Vector::indexOf und Vector::addElement, die mit dem Empfänger connectorList aufgerufen werden, kann der Optimierer beweisen, daß ein in connectorList gespeichertes Objekt dem erzeugenden Thread nicht entfliehen kann - es also nicht thread escaping ist. Dies bedeutet, daß unter keinen Umständen ein anderer Thread als der erzeugende eine Referenz auf das von connectorList referenzierte Objekt erhalten kann.

Das Beispiel illustriert noch eine weitere Eigenschaft: Normalerweise werden in Java nur Exemplare der Basisdatentypen (int, long, boolean, etc.) auf den Stack alloziert, während alle Objekte (d.h. Instanzen einer Java-Klasse) generell auf dem Heap angelegt werden. Dadurch können Refenzen auf Objekte, die innerhalb einer Methode angelegt wurden, in globalen Variablen abgelegt werden, wodurch sie weiterhin erreichbar und lebendig bleiben.

Wenn ein Objekt jedoch nicht den Aufruf der Methode überlebt, in der es erzeugt wurde, d.h. es von keiner Root im System erreichbar ist, nachdem die Ausführung der Methode beendet wurde, so könnte dieses Objekt auch im Stackframe des entsprechenden Methodenaufrufes angeleget werden.

Dies kann von Vorteil sein, da in der Regel selbst bei sogenannter ,,schneller`` Heap-Allokation (s. Abschnitt 4.1) eine reine Stack-Allokation performanter als die Heap-Allocation in einem von einem vom Garbage Collector kontrollierten Heap ist. Dies liegt zum einen darin begründet, daß bei einer Heap-Allokation, zumindest gelegentlich, eine Synchronisation über das Heap-Lock erfolgen muß; zum anderen muß seltener eine Garbage Collection ausgeführt werden, wenn weniger Objekte auf dem Heap angelegt werden. Dabei muß allerdings ein übermaßiges Wachsen des Stacks vermieden werden, weshalb eine Stack-Allokation innerhalb einer Schleife üblicherweise vermieden wird.

Wie oben kann auch hier durch Analyse der genannten Methoden Server::run, Vector::indexOf und Vector::addElement bewiesen werden, daß die Lebensdauer eines in connectorList gespeicherten Objektes durch die Ausführung der erzeugenden Methode begrenzt ist - es also nicht method escaping ist.

Der Optimierer könnte also die Methode Server::run folgendermaßen modifizieren:

1.
Obwohl die Methoden Vector::indexOf und Vector::addElement als synchronized deklariert sind, kann jegliche Synchronization an dem von connectorList referenzierten Objekt unterlassen werden.
2.
Das in Zeile 11 erzeugte Objekt, das der Variablen connectorList zugewiesen wird, kann auf dem Stack im Rahmen des aktuellen Methodeaufrufes alloziert werden, da es mit Verlassen der Methode Server::run unerreichbar wird.

Nun stellt sich die Frage, wie eine Analyse vorzugehen hat, um zu beweisen, daß ein bestimmtes Objekt o von keinem anderen Threads als dem erzeugenden erreichbar wird. Prizipiell muß bewiesen werden, daß o:

Soll o auf den Stack alloziert werden so muß zusätzlich bewiesen werden, daß es nicht durch den Bytecode areturn den Bereich seiner erzeugenden Methode verläßt.

Es existieren mittlerweile eine große Zahl von Implementierungen einer escape analysis für Java [Blanchet, 1999,Bogda and Hölzle, 1999,Choi et al., 1999,Whaley and Rinard, 1999]. Sie alle führen eine intraprozedurale kontext-insensitive Datenflußanalyse [Muchnick, 1997] durch, deren Ergebnis in kompakter Form für eine interprozedurale Analyse verwendet wird. Dabei werden im Falle von Rekursionen in der Regel konservative Annahmen gemacht, um eine akzeptabele Performance zu erhalten. Alle genannten Implementierungen verwenden einen statischen Compiler und erreichen damit eine Performanceverbesserung des ausgeführten Java-Programmes von 7 bis 40 %.

Wie bereits angedeutet, stellt die Komplexität des Algorithmus bei allen globalen Analysen ein entscheidendes Problem dar. Bei Verwendung des ersten veröffentlichten Algorithmus zur escape analysis [Park and Goldberg, 1992] stieg der Zeitaufwand exponentiell mit der Größe des analysierten Programms.

Es kann davon ausgegangen werden, daß alle der oben genannte Algorithmen für Java in polynomieller Zeit arbeiten, Ergebnisse einer Komplexitätsanalyse und Performanzmessung des Algorithmus werden allerdings nur von [Blanchet, 1999] genannt. Der Zeitaufwand für die Analyse eines Programms steigt demnach maximal quadratisch mit seiner Größe - in der Praxis wurde aber nur ein lineares Wachtum festgestellt. Dabei wurde die Kompilationszeit im Mittel um 34% erhöht. Diese Zahlen lassen eine Integration einer escape analysis in einen dynamischen Compiler möglich erscheinen.


next up previous contents
Next: Diskussion Up: Globale Analyseverfahren Previous: Class Hierarchy Analysis   Inhalt

2001-02-28