\chapter{Ans"atze zur Optimierung objektorientierter Sprachen}
\label{History}


Das Abstraktionsmodell in objektorientierten Programmiersprachen ist
eine  
Strukturierung der Datentypen in eine Klassenhierarchie und der 
damit verbundene Vererbungs\-mechanismus. Methoden werden dynamisch zur Laufzeit
gebunden, da erst durch die Empf"anger\-klasse bestimmt werden kann,
welche Implementierung einer Botschaft zum Empf"anger\-objekt pa\3t.
Dieser Aspekt von objektorientierten Programmiersprachen  ist eine {\em Abstraktionsh"urde}
f"ur optimierende "Ubersetzer, denn zur "Ubersetzungszeit ist
nur die Signatur des durch eine \mbox{Klasse} realisierten abstrakten
Datentyps bekannt. Klassen- oder Modul\-"uber\-greifende Optimie\-rungen sind zur
"Ubersetzungszeit ausgeschlossen.
Referenzen "uber Abstraktions\-h"urden hinweg k"onnen in
objektorientierten
Sprachen erst w"ahrend der
Laufzeit aufgel"ost  und m"ussen immer wieder neu gekn"upft werden,
da die Empf"angerklasse einer Botschaft sich von Aufruf zu Aufruf "andern kann.
Dieser Vorgang verl"auft naiv implementiert erheblich langsamer als ein statisch gebundener
Funktionsaufruf, da s"amtliche Oberklassen nach der passenden Implementierung
durchsucht werden m"ussen. Selbst in der Sprache C++, in der
ein lauff"ahiges Klassen\-system einmal vor der Laufzeit gebunden
wird, erfordern Methodenaufrufe in vielen Implement\-ierungen drei Indirektionen zum
Auffinden der passenden Methoden\-implementierung. 
In einer rein objektorientierten Sprache
wie TooL, in der in fast jedem Ausf"uhrungsschritt ein Methodenaufruf 
stattfindet, bedeutet der Aufwand des dynamischen Methoden\-aufrufs
einen erheblichen Effizienzverlust.
Neben diesem direkten Nachteil zeigt sich ein in\-direkter negativer
Effekt: die vielen Methodenaufrufe an ungewisse Ziele erschweren 
Optimierungen oder schlie\3en diese g"anzlich aus.

Sind die Ziele von Methodenaufrufen allerdings eindeutig aufl"osbar, stehen 
funktions\-"uber\-greifenden Optimierungen ausgel"ost durch
Funktionsexpansion ({\em inlining})
nichts im Wege. \mbox{Allen} Strategien zur Aufl"osung von Referenzen ist 
gemeinsam, da\3 versucht wird, \mbox{Information} "uber  Klassen 
von Ausdr"ucken zu gewinnen. In den folgenden Abschnitten werden Ans"atze
zur Gewinnung von Klasseninformation beschrieben, die zum einen Einflu\3
auf die vorliegende Arbeit haben, und zum anderen mit den Techniken
des TooL-Optimierers verglichen werden sollen.


\section{Klassenabsch"atzung}


\begin{figure}[tbph]
\begin{center}
\leavevmode
\epsfxsize=5.5cm
\epsffile{typepred.eps}
\end{center}
\caption{Einfache Klassenabsch"atzung}
\label{typepred}
\end {figure}

F"ur einen Satz an Basisselektoren wie {\sf \sfrontq +,*,-\sbackq} usw. sind
Empf"angerklassen mit einer sehr hohen Wahrscheinlichkeit absch"atzbar.
In \cite{Kra83} wird festgestellt, da\3 in Smalltalk 90\% aller
Aufrufe von Methoden mit dem Selektor {\sf \sfrontq +\sbackq} an Objekte der Klasse {\sf
SmallInteger} gerichtet sind. "Ahnliches gilt f"ur andere arithmetische 
und logische Selektoren; auch hier sind die Empf"angerobjekte mit sehr 
hoher Wahrscheinlichkeit Exemplare von {\sf SmallInteger} bzw. {\sf Boolean}.
W"ahrend der Ausf"uhrung von Methodenaufrufen mit diesen speziell
gekennzeichneten Selektoren kann ein Klassentest
erfolgen. Ist dieser erfolgreich, wird eine primitive Operation
direkt ohne Methodenaufruf ausgef"uhrt; im anderen Fall einer
unerwarteten Empf"anger\-klasse
ist ein regul"arer Methodenaufruf erforderlich.
Dieses Verfahren hei\3t Klassen\-absch"atzung ({\em \mbox{type}
prediction})
und ist in Abbildung \ref{typepred}
angedeutet.

Durch Klassenabsch"atzung k"onnen die Kosten des dynamischen Methodenaufrufs
f"ur einige Basisselektoren bei erfolgreicher Klassenvorhersage
auf den wesentlich geringeren Aufwand
einer Vergleichsoperation und eines bedingten Sprungs reduziert werden.

Schon in dem mikrocodierten Interpreter f"ur Smalltalk-76 \cite{Ingalls78}
wird eine  Klassenabsch"atzung bei der Interpretation von Basisselektoren
durchgef"uhrt.
In dem Smalltalk-"Ubersetzer f"ur konventionelle
Rechnerarchitekturen von
Deutsch und Schiffman  \cite{DeSchi84}  werden bei der "Ubersetzung
des Smalltalk-Bytecodes in Maschinencode Methodenaufrufe
durch  Klassenabsch"atzung vermieden.
Mittlerweile geh"ort diese Technik zu
einer vielfach eingesetzten Optimierung f"ur objektorientierte Sprachen,
z.B. in SELF \cite{Ungar87} und  Smalltalk \cite{DeSchi84,Ungar87a,Gawecki91}.

\section{Inline Caching}

Einige Smalltalk-"Ubersetzer verwenden eine zentrale Hashtabelle als Methodencache,
in den ein Zeiger auf den aufgefundenen Code eines Methodenaufrufes 
eingetragen wird. Der Hashindex wird durch eine sehr einfache Funktion
aus dem Methodenselektor und der Empf"angerklasse berechnet, z.B. durch
Addition des Selektors mit dem Klassenindex modulo
der Tabellen\-gr"o\3e.
F"ur erneute Aufrufe einer gegebenen Kombination von Selektor und Empf"anger\-klasse 
wird der Aufwand des dynamischen Methoden\-aufrufs im Idealfall 
auf die Berechnung des Hashindex
und Schl"ussel\-vergleichs
verringert.
Ein Vergleich von Hashfunktionen f"ur das Caching von Methoden in
Smalltalk-Systemen ist in \cite{Kra83} zu finden.

\begin{figure}[tbh]
\begin{center}
\leavevmode
\epsfxsize=10cm
\epsffile{inlinecache.eps}
\end{center}
\caption{Prinzip des Inline-Caching}
\label{inlinecache}
\end {figure}


Ausgehend von der Feststellung, da\3  Empf"angerklassen an Aufrufpositionen
weitgehend konstant bleiben, wurde in dem Deutsch-Schiffman-System der Methodencache
in den ausf"uhrbaren Code integriert ({\em inline caching}): 
Ein zur Laufzeit auftretender Methodenaufruf wird nach dem dynamischen 
Auffinden der passenden Methode an der Aufrufstelle ersetzt durch eine
Klassen"uberpr"ufung und einen Sprung an den aufgefundenen Code. 
Die Integration des Methoden\-caches in den ausf"uhrbaren Code ersetzt den 
Aufwand der Hash\-verwaltung durch einen einfachen Klassentest.
Diese Idee ist in Abbildung \ref{inlinecache} skizziert.
Auch das Inline-Caching wird in verschiedenen Systemen eingesetzt, z.B. in dem
SELF-"Ubersetzer von Chambers \cite{Chambers92} oder dem
Smalltalk-"Ubersetzer f"ur einen dedizierten
Smalltalk-RISC-Prozessor SOAR \cite{SOAR84}.



Um Aufrufe mit wechselnden Empf"angerklassen "ahnlich effizient zu gestalten, wurde
in \cite{Hoelzle94} der Inline-Cache zu einem polymorphen Inline-Cache 
weiterentwickelt; der Grundgedanke ist in Abbildung \ref{PIC}
dargestellt.
F"ur eine bestimmte Zahl von Empf"angerklassen werden Klassentests in den Code
eingef"ugt,
und somit lassen Methodenaufruforte mit variier\-enden Empf"angerklassen
trotz Polymorphismus optimierte Methodenaufrufe zu.
Zus"atzlich bildet der integrierte Cache in SELF eine wichtige Informationsquelle,
die f"ur dynamische Optimierungen zur Laufzeit ausgenutzt wird. Ein
polymorpher
Inline-Cache stellt
zusammen mit einem Methodenaufrufz"ahler ein Laufzeitprofil dar, das
zwei Arten von  Information an einen Optimierer liefert:
Erstens zeigt ein integrierter Cache an, an welchen Stellen eine Methoden\-integration
 m"oglich wird ("uberall, wo Aufrufe
durch einen Prozeduraufruf realisiert sind), und zweitens werden
Hinweise dar"uber gegeben,
wo eine Methodenintegration besonders effektiv werden k"onnte (Aufrufpositionen mit einer hohen 
Aufrufdichte). 


\begin{figure}[tbh]
\begin{center}
\leavevmode
\epsfxsize=12cm
\epsffile{pic.eps}
\end{center}
\caption{Polymorphes Inline-Caching}
\label{PIC}
\end {figure}




\section{Klassenanalyse und Splitting}


\begin{figure}[tbph]
\begin{center}
\leavevmode
\epsfxsize=14cm
\epsffile{split.eps}
\end{center}
\caption{Splitting}
\label{Splitting}
\end{figure}

Ausgehend von Hinweisen oder konkreten Informationen "uber die Klassen
einiger Empf"anger kann ein Analyselauf weitere Empf"angerklassen
offenlegen, etwa durch Inferenzen "uber  Ergebnisklassen von
primitiven Operationen. 
In \cite{JohGraZur88} und \cite{Atkinson86} werden typisierte Varianten
der Sprache Smalltalk
vorgestellt, in denen explizit im Programmtext angegebene
Klasseninformation
in einer Klassenanalyse f"ur weiter\-f"uhrende \mbox{Optimierungen} ausgenutzt wird, die
in den "Ubersetzern statisch vor der Laufzeit erfolgen.
Auch durch Klassenabsch"atzung und Inline-Caching wird Code um Klasseninformation be\-reichert,
die durch eine Klassenanalyse weitere Optimierungen zul"a\3t. Der SELF-"Ubersetzer von 
Chambers \cite{Chambers92} f"uhrt eine Klassenanalyse durch, die einer Datenflu\3analyse
"ahnelt: Klassen\-information in der Form von Mengen von m"oglichen Objektklassen wird
auf Kontroll\-flu\3\-pfaden durch einen Kontroll\-flu\3\-graphen propagiert. Durch 
Verschiebung von \mbox{Code} "uber Vereinigungsknoten des Kontrollflu\3graphen hinaus
({\em splitting}) werden mono\-morphe 
Strecken vergr"o\3ert und wiederholte Klassentests vermieden,
wie das Beispiel in Abbildung \ref{Splitting} andeutet.
Aufgrund der Vielzahl von Klassentests, die durch einfache Klassenabsch"atzung und
Inline-Caching im Code eingef"uhrt werden, ist
die Verschiebung von Code "uber Knoten hinaus eine wirkungsvolle (und
n"otige) Optimierung in den SELF-"Ubersetzern.


\section{Profilgesteuerte Optimierung} \label{profileValidity}

Information aus vergangenen Programml"aufen kann  Aufschlu\3 "uber
allgemeines Ablaufverhalten und zuk"unftige Programml"aufe geben,
sofern der Beobachtungszeitraum
eine repr"asentative Stichprobe zul"a\3t. Eine gute Stichprobe kann
sich aus dem Profiling von Anwendungsprogrammen ergeben, denn so gewonnene
Daten entsprechen eher den realen Anforderungen an ein Softwaresystem
als Messungen an Testprogrammen. Die Frage der
G"ultigkeit  und der Granularit"at von  Profildaten f"ur die
objektorientierten Sprachen Cecil \cite{Cham93} und C++ wird von \cite{GroDeaGarCha95}
untersucht. Zus"atzlich wird die Wirksamkeit verschiedener Arten von 
Profilinformationen zur Klassenabsch"atzung gemessen. Grove et al. klassifizieren
die Granularit"at von Profilinformation nach der Tiefe einer
beobachteten Aufrufkette ({\em call chain}).
Die gr"obste Einheit stellen Aufrufh"aufigkeiten von
Methoden dar, die "uber alle Aufruforte hinweg gemittelt werden (z.B.
realisiert durch einen Aufrufz"ahler f"ur jede Methode).
Folgen von aufrufortspezifischen H"aufigkeiten geben genauer Aufschlu\3
"uber Aufrufdichten. So tr"agt  ein polymorpher Inline-Cache
zus"atzlich zu den Aufrufh"aufigkeiten auch noch aufrufortspezifische
Information und w"are damit die n"achste Granularit"atsstufe.
Weitere Stufen sind Folgen von Aufruforten im Sinne von
verketteten Aktivierungssegmenten eines Kellers.

F"ur Optimierungen durch Klassenabsch"atzungen erweisen sich  einfache (nicht verkettete)
aufrufortspezifische
Informationen am n"utzlichsten, da diese  eine gezielte Methoden\-integration erm"oglichen,
gefolgt von den einfachen gemittelten 
H"aufigkeiten.
Die G"ultigkeit von Profildaten bleibt nach den Messungen von \cite{GroDeaGarCha95}
"uber l"angere Zeitr"aume und "uber verschiedene Programmversionen hinweg
erhalten, so da\3 Profiling ein wirkungsvolles Werkzeug zur Optimierung
von objektorientierten Sprachen zu sein scheint.

Laut \cite{CutConKirMor94} stellen Programmiersysteme mit orthogonaler
Persistenz und Reflektion
wie das Tycoon-System
eine geeignete Umgebung dar, um Profiling ohne gr"o\3ere Schwierigkeiten
zu integrieren. In der Arbeit von Cutts et al. wird die polymorphe
persistente Sprache Napier-88 \cite{Napier88} um die M"oglichkeit,
Code aufgrund von Information in Laufzeitprofilen erneut zu "ubersetzen,
erweitert. Auf diese Weise werden mehrere Code\-versionen einer
Prozedur erzeugt, unter denen in Abh"angigkeit von Laufzeitbedingungen
ausgew"ahlt wird. Die Entwicklung des Codebestands nimmt evolution"are
Z"uge an, denn nach einer Optimierung kann das Laufzeitverhalten weiter
in einem Profil festgehalten werden. 
Nicht mehr ben"otigte Codesegmente (weil z.B. nur noch die
optimierte Version aufgerufen wird) k"onnen aus dem System herausfallen.




\section{Empf"angerspezifische "Ubersetzung}

Der Einsatz eines zentralen oder integrierten Methodencaches erlaubt die
effektive Optimierungs\-technik der empf"anger\-spezifischen "Ubersetzung 
({\em customization}) \cite{ChaUng89} \cite{Gawecki91}. Da nach einem Klassentest oder einer Hashberechnung
die Empf"angerklasse \mbox{eines} Methodenaufrufs bekannt ist, kann aus der
aufgerufenen Methode eine auf die Empf"angerklasse zugeschnittene Version 
erzeugt werden, die daraufhin in den Methodencache eingetragen wird.
In dieser speziellen Version einer Methode lassen sich alle
Methoden\-aufrufe an den Empf"anger {\sf self}
durch statische Funktionsaufrufe oder expandierte Codefragmente
({\em inlining}) ersetzen, da die Klasse von {\sf self} f"ur diese
Methodenversion bekannt ist.

Dem Nachteil der Redundanz der auf verschiedene Empf"angerklassen
 zugeschnittenen Code\-versionen stehen die erweiterten 
Optimierungsm"oglichkeiten gegen"uber. Gerade in rein objekt\-orientierten
Sprachen, in denen auch Exemplarvariablen eines Objekts "uber
Botschaften an {\sf self} referenziert werden, ist die empf"angerspezifische "Ubersetzung
eine effektive Optimierung.
In Systemen mit dynamischer "Ubersetzung wird nur der aktuell ben"otigte
Code im Cache gehalten und bei Bedarf erneut "ubersetzt, so da\3 der
Speicherverbrauch der spezialisierten Methodenversionen begrenzt ist.






