\chapter{Quantitative Ergebnisse} \label{Benchmarks}

Ein wichtiger Bestandteil einer Arbeit mit 
dem Ziel einer Optimierung oder Effizienz\-steigerung
ist die Durchf"uhrung von Leistungsmessungen,
denn diese fungieren mangels formaler Beweise als Anhaltspunkt
f"ur die Best"atigung oder Widerlegung von Hypothesen
wie \glqq Durch den  Einsatz von markierten Typen, Laufzeitprofiling und 
Strategien zur Elimination von Endrekursion k"onnen die Effizienznachteile
von rein objektorientierten Sprachen deutlich vermindert werden\grqq, oder
\glqq Eine virtuelle Registermaschine ist eine geeignete Ausf"uhrungs\-plattform
und f"uhrt zu geringeren Laufzeiten\grqq.
In diesem Kapitel werden zwei Fragestellungen mit Messungen untersucht:
Wie entscheidend k"onnen die Nachteile von rein objekt\-orientierten Sprachen 
 vermindert werden$\!$ ?
Wie effizient ist eine virtuelle Registerarchitektur f"ur Sprachen 
wie TL oder TooL$\!$ ?

Die Metrik f"ur  Effektivit"at werden  Ausf"uhrungszeiten
verschiedener Testprogramme sein, die mit und ohne Optimierungstechnik
"ubersetzt werden. In diesem Zusammenhang ist es hilfreich, die 
Begriffe Performanz und Performanzsteigerung ({\em speedup}) 
nach \cite{HenPat90} zu pr"azisieren.
Die Performanz ist die Ausf"uhrungsgeschwindigkeit eines Programms als
Kehrwert der Ausf"uhrungszeit:
\begin{eqnarray*}
Performanz = \frac{1}{Ausf"uhrungszeit}
\end{eqnarray*}

Die Performanzsteigerung  einer Optimierung folgt aus der Feststellung,
da\3 Programme durch "Ubersetzung mit  einer Optimierungstechnik
schneller ablaufen als solche, die ohne Optimierungstechnik
"ubersetzt werden:


\begin{eqnarray*}
Performanzsteigerung = \frac{Performanz_{optimiert}}{Performanz_{nicht\; optimiert}}
\end{eqnarray*}



Im folgenden werden anhand der Ausf"uhrungszeiten von Testprogrammen
die Performanzsteigerungen durch den TooL-Optimierer einerseits
und  den Einsatz  der virtuellen Registermaschine andererseits
ermittelt und diskutiert. 

\section{Die Performanz von TooL}


Ziel der Me\3reihen dieses Abschnitts ist nicht nur, 
die Auswirkungen der Optimierungen
festzuhalten, sondern auch ansatzweise Aufschlu\3 dar"uber zu geben,
wie die Performanz von TooL im Vergleich zu anderen Programmiersprachen steht.

Die Auswahl des Testsatzes ist sowohl von pragmatischen Gedanken als auch von
Gesichtspunkten der Aussagef"ahigkeit geleitet. Grunds"atzlich gelten
die Laufzeiten von gr"o\3eren Programmen und echten Anwendungen als
aussagekr"aftiger als die von kurzen Test\-programmen.
Da zum Zeitpunkt dieser Arbeit kaum reale TooL-Anwendungen existieren, \mbox{bilden}
k"unstliche Benchmarks aus der Stanford-Suite den Grundstock 
der Testprogramme. Der Vorteil dieser kurzen Testprogramme liegt
in der allgemeinen Verf"ugbarkeit, so da\3 Vergleiche zwischen Programmiersprachen
eventuell m"oglich sind.
Als Ersatz f"ur reale Anwendungen dienen der Richards-Benchmark, eine
Simulation von Betriebssystemmechanismen mit Funktions\-einheiten, Warteschlangen,
Auftr"agen und einem rudiment"aren Scheduler,
und eine Implementierung eines generischen $n$-dimensionalen W"orterbuchs
\cite{RoeLot93}.
 Durch die Wiederverwendung
von Code in objektorientierten Systemen l"a\3t sich die Gr"o\3e dieser Programme
kaum absch"atzen, was vor allem f"ur TooL als rein
objektorientierte \mbox{Sprache} gilt. Die von C++ nach TooL portierte 
Version des Richards-Benchmarks umfa\3t circa 900 Zeilen TooL-Quelltext,
das $n$-dimensionale W"orterbuch ist circa 2500 Zeilen lang. Beide Programme
\mbox{machen} ausgiebig Gebrauch von verschiedenen Beh"alterklassen aus 
der TooL-Klassenbibliothek, so da\3 deutlich mehr Code zur Ausf"uhrung kommt,
und diese Programme als Testf"alle \mbox{mittlerer} Gr"o\3e gelten
k"onnen.


\subsection{Performanzsteigerungen durch Optimierungen}


Um die m"oglichen Performanzsteigerungen durch das in dieser Arbeit beschriebene
Optimierungsverfahren zu messen, werden f"ur jedes Testprogramm die
Ausf"uhrungszeiten vor und nach der Optimierung gemessen. Die Testf"alle
sind:
\begin{enumerate}
\item
Quicksort von 10000 zuf"alligen Elementen
\item
Bubblesort von 1000 zuf"alligen Elementen
\item
Treesort von 10000 zuf"alligen Elementen
\item
Queens (das Acht-Damen-Problem)
\item
Permutations (stark rekursives Testprogramm aus der Stanford-Suite)
\item
Puzzle (Testprogramm aus der Stanford-Suite)
\item
Richards
\item
nDimDict (Erzeugung eines $n$-dimensionalen W"orterbuchs) 
\end{enumerate}

Nur die Programme {\sf Queens}, {\sf Puzzle}, {\sf Permutations} und
{\sf Richards} erlauben eventuell einen Vergleich mit anderen Programmiersprachen,
da sie explizit als Benchmarks in TooL codiert sind. Die
Sortierverfahren
entstammen der TooL-Beh"alterbibliothek. Daher 
sind sie aus Sicherheits\-erw"agungen
f"ur Bibliothekscode mit
Zusicherungscode und zus"atzlichen Konsistenz\-abfragen erweitert, die 
einen direkten Vergleich mit den einfach codierten Routinen aus der
urspr"unglichen Stanford-Suite unm"oglich machen. Die Messungen der Laufzeiten der
TooL-Programme verliefen unter Einsatz der virtuellen Kellermaschine TVM.
Die Testl"aufe fanden auf einer unbelasteten SparcStation 20 von SUN Microsystems
mit 2 Prozessoren und 256 MB Hauptspeicher statt. Die berichteten Zeiten
sind CPU-Zeiten.

\begin {figure}[tbh]
\centering
\begin{tabular}{|| l | l | l | l ||} \hline
{\em Benchmark}    &  {\em Zeit: TooL (s)}  &  {\em Zeit: TooL optimiert (s)}  &
{\em Performanzsteigerung }\\ \hline
  
   quicksort  &      44.85       &      24.92   & 1.79\\
   bubblesort &      133.1       &      67.63   & 1.97\\
   treesort   &      41.07       &      16.11   & 2.55\\
   perms      &      8.74        &       3.26   & 2.68\\
   queens     &      9.57        &       4.7    & 2.04\\
   puzzle     &      71.36       &      32.12   & 2.22 \\
   richards   &      216.86      &      69.09   & 3.14\\
   nDimDict   &      49.76       &      16.37   & 3.04\\ \hline
\end{tabular}
\caption{Performanzsteigerungen durch Optimierung von TooL-Programmen}
\label{Speedup}
\end {figure}

Die gemessenen Zeiten der Testl"aufe und die Performanzsteigerungen sind in Abbildung
\ref{Speedup} festgehalten. In den nicht-optimierten Programmen wird jede
Operation im Quelltext durch einen Methodenaufruf realisiert. Die aufgefundenen
Implementierungen eines Methoden\-aufrufs werden allerdings in einem zentralen
Methodencache gehalten, um den Aufwand des Aufrufs m"oglichst gering zu halten.
Bei allen L"aufen war der Profiler zugeschaltet.
 Das  Ergebnis dieser Messungen ist:
TooL-Programme, die mit den in dieser Arbeit beschriebenen Techniken optimiert
werden, k"onnen  zwei bis drei mal schneller 
ablaufen als solche,
die ohne Optimierung "ubersetzt werden. Ganz "uberraschend sind diese hohen 
Beschleunigungsfaktoren nicht, denn schon die
Ersetzung der rein objektorientierten Kontrollstrukturen
durch einfache Schleifen im Rahmen der Optimierungen d"urfte einen
gro\3en Teil der Performanzsteigerungen ausmachen.

\begin {figure}[tbh]
\centering
\begin{tabular}{|| l | l | l | l ||} \hline
{\em Benchmark}    &  {\em TooL (Botschaften/s)}  &  {\em TooL optimiert
(Botschaften/s)} & {\em TooL/TooL-opt}\\ \hline


   quicksort  &      136235.65   &            119818.58   & 1.14 \\
   bubblesort &     140902.71    &           103380.85    & 1.36 \\
   treesort   &      112498.98   &             58995.22   & 1.91\\
   perms      &      149084.10   &             83296.93   &  1.79\\
   queens     &      137869.49   &             89076.38   &  1.55\\
   puzzle     &      128011.27   &             84939.07   &  1.51\\
   richards   &      147831.78   &             97438.65   &  1.52\\
   DDimDict   &      155553.05   &             82204.95   &  1.89\\ \hline
\end{tabular}
\caption{Methodenaufrufh"aufigkeiten}
\label{eliminatedSends}
\end {figure}


Es stellt sich die Frage, ob nicht noch bessere Ergebnisse erzielbar sind. Hierzu 
soll der dynamische  Anteil an Methodenaufrufen vor und nach einer Optimierung
untersucht \mbox{werden}.
F"ur jedes Testprogramm wird mit Hilfe eines Aufrufz"ahlers die Zahl der
Methoden\-aufrufe festgehalten, die anschlie\3end durch die Laufzeit
des Programms geteilt wird, um eine Methoden\-aufruf\-h"aufigkeit zu erhalten.
Diese Frequenzen sind in Abbildung \ref{eliminatedSends} 
dargestellt.

Es ist erkennbar, da\3 
die dynamische H"aufigkeit von 
Methodenaufrufen  durch die Optimierungen 
im Durchschnitt 
um einen Faktor von 1,6 verringert wird.
 H"olzle  berichtet, da\3 der 
SELF-"Ubersetzer (SELF93) durch Profiling mit Hilfe eines
polymorphen Inline-Caches und erneuter
"Ubersetzung die Botschaftsfrequenz um einen  Faktor von 3,6
reduziert \cite{Hoelzle94}, also ein 
deutlich besseres Ergebnis als das des TooL-Optimierers.

Ein Grund f"ur diesen Unterschied kann darin liegen, da\3 der TooL-Optimierer
keine Klassen\-absch"atzung durchf"uhrt, w"ahrend das polymorphe Inline-Caching von SELF
als \mbox{eine} generalisierte Klassenabsch"atzung verstanden werden kann.
 Dadurch entgehen dem TooL-Optimierer 
einige M"oglichkeiten, Methodenaufrufe durch Funktionsaufrufe zu ersetzen,
und es treten noch Botschaften wie {\sf \sfrontq +,*,-\sbackq} usw. auf. 
Diese k"onnten durch selektorbasierte Klassen\-absch"atzung eliminiert werden, 
allerdings w"are dann eventuell auch noch eine Splitting-Phase im 
Optimierer notwendig.
Alternativ dazu lie\3e sich das Konzept der markierten \mbox{Typen}, das sich
als eine der Hauptinformationsquellen f"ur den Optimierer herausgestellt hat, 
in den Typinferenzmechanismus
des Typpr"ufungsalgorithmus einf"uhren, so da\3 zum Zeitpunkt der Generierung
des TML-Zwischencodes die Signaturen von allen Bezeichnern offenliegen.
So k"onnen schon bei der Transformation von TooL-AST nach TML-AST einige
Methoden\-aufrufe an Methoden der markierten Typen zum "Ubersetzungszeitpunkt
eliminiert werden.


\subsection{Codezuwachs durch Optimierungen}

Durch die Optimierungsmechanismen dieser Arbeit wird der Code in der Regel gr"o\3er,
da Methoden an ihren Aufruforten integriert und Hilfsfunktionen
wie {\sf while} teilweise mehrfach angelegt werden (wenn diese sich
nicht integrieren lassen). Die Codegr"o\3e l"a\3t sich folgender\-ma\3en
messen:
Nach dem Lauf eines nicht-optimierten Programms kann der
Cache unter Ber"ucksichtigung aller in einem  Funktionsabschlu\3 gehaltenen
Funktionen
traversiert und die gesamte Codegr"o\3e des Programms
(in Bytes) ermittelt werden. Anschlie\3end wird die Optimierung
gestartet und nach einem erneuten Testlauf (um den Cache mit Methoden,
die bei $\theta=0.001$ nicht optimiert werden, zu f"ullen)
kann der Cache wiederholt traversiert werden.
Die Ergebnisse dieser Messungen sind in Abbildung \ref{CodeGrowth}
dargestellt.

Der Code wird im Durchschnitt um den Faktor 1.76 gr"o\3er,
ein Wert, der 
das in Abschnitt \ref{Y-Format} erw"ahnte Problem der
redundant gehaltenen Hilfsfunktionen eines Funktionsabschlusses
relativiert.

Messungen der Codegr"o\3e bei $\theta=0$ zeigen, da\3 in
diesem Fall der Code im Durchschnitt um den Faktor
3.75 w"achst. Der heuristisch gew"ahlte Wert von $\theta=0.001$,
bei dem 90 \% bis 95 \% der Performanzsteigerungen erreicht
werden, scheint sich auch bez"uglich der Codegr"o\3e zu bew"ahren.


\begin {figure}[tbh]
\centering
\begin{tabular}{|| l | l | l | l ||} \hline
{\em Benchmark}    &  {\em Codegr"o\3e: TooL (bytes)}  &  
 {\em Codegr"o\3e: TooL-opt}  &
 {\em TooL-opt/TooL }\\ \hline
   quicksort   &     1139     &         2401 & 2.11\\
   bubblesort  &     1146    &          2404 & 2.10\\
   treesort   &      1217    &          1387 & 1.14\\
   perms      &      1219    &          1389 & 1.14\\
   queens     &      1384    &          2357 & 1.70\\
   puzzle     &      3045    &          3795 & 1.25\\
   richards   &     8495     &        16985  & 2.00\\
   DDimDict   &     10232    &         26697 & 2.61\\ \hline
\end{tabular}
\caption{Codezuwachs durch Optimierungen} 
\label{CodeGrowth}
\end {figure}


 
\subsection{TooL im Vergleich zu TL und Java}

Die Frage nach einem Leistungsvergleich zwischen Programmiersprachen
und "Ubersetzern stellt sich immer wieder und l"a\3t sich in der Regel nicht
einfach durch Messungen beantworten. Besonders schwierig ist
der Vergleich zwischen semantisch m"achtigen Sprachen wie TooL
und g"angigen, einfacheren Sprachen wie C oder C++.
TooL besitzt Eigenschaften wie reine Objektorientierung,
inkrementelle Erweiterung
des Klassengraphen, orthogonaler Persistenz und ein portables
Ausf"uhrungsformat, die in C oder C++ nicht unterst"utzt werden.
Dennoch soll im folgenden nur die Ausf"uhrungsgeschwindigkeit
als Vergleichsgr"o\3e gelten, um einen Eindruck
der absoluten Leistung von TooL-Programmen zu erhalten.



\subsubsection{TooL vs. TL}

Eine ideale Sprache als Vergleichskandidat ist TL, denn  TL und TooL
besitzen einen gemeinsamen architektonischen Ursprung:  Zwischencode,
 Codegenerator, Bytecode, Interpreter und  Laufzeitsystem sind bis auf Erweiterungen
f"ur den Methodenaufruf identisch. So kann die Performanz von TL
als Me\3latte f"ur TooL dienen. Von den Testprogrammen des letzten
Abschnitts sind allerdings nur die explizit als Benchmarks codierten 
Programme sinnvoll. Schon eine zus"atzliche Konsistenzabfrage in einer inneren 
Schleife eines Sortierprogramms w"urde zu irref"uhrenden Aussagen verleiten,
so da\3 kein Vergleich zwischen den Stanford-Sortierverfahren in TL und
den Sortierverfahren aus der TooL-Klassenbibliothek m"oglich ist.

\begin {figure}[tbh]
\centering
\begin{tabular}{|| l | l | l | l ||} \hline
{\em Benchmark}    &  {\em Zeit: TL optimiert (s)}  &  
 {\em Zeit: TooL optimiert (s)}  & {\em Performanzvorteil: TL/TooL}\\ \hline

   perms     &     1.044 &  3.26 & 3.12\\
   queens     &    1.856 &  4.7  & 2.53\\
   puzzle     &   10.98  &  32.12 & 2.93\\
   richards   &   11.05  &  69.09 & 6.25\\ \hline
\end{tabular}
\caption{Performanzvergleich zwischen TooL und TL}
\label{TooLvsTL}
\end {figure}


 

Die Laufzeiten der optimierten TL-Benchmarks sind in Abbildung \ref{TooLvsTL}
 den Laufzeiten der optimierten TooL-Benchmarks gegen"ubergestellt. 
Diese Zahlen zeigen auf, da\3 TooL-Programme zwischen 2.5 und 6.3-mal 
langsamer sein k"onnen als vergleichbare TL-Programme. Diese Werte
geben nur einen ersten Eindruck der Geschwindigkeit von TooL-Anwendungen,
denn es ist zu erwarten, da\3 
Programme, die ausgiebig Gebrauch der Klassenbibliothek 
\mbox{machen}, eher langsamer ablaufen. F"ur die TooL-Version des
Richards-Benchmarks
ist dies der Fall, denn dieser Benchmark ist im TooL-Stil
geschrieben und tr"agt so typischere TooL-Merkmale als z.B. das Acht-Damen-Programm.
Trotz dieses Vorbehalts sind diese Ergeb\-nisse gut, insbesondere da TL
keine objektorientierte Sprache ist und alle Referenzen nach dem Binden
fest verkn"upft sind. 

In \cite{Hoelzle94} wird berichtet, da\3 SELF-Programme
im besten Fall halb so schnell wie C++-Programme
ablaufen k"onnen (was einem  Faktor von 2  entspricht), aber in C++-Programmen 
treten durchaus  noch dynamische Methodenaufrufe auf, so da\3 es denkbar
ist, da\3 SELF im Vergleich zu einer nicht-objektorientierten Sprache 
"ahnlich abschneidet wie TooL.

\subsubsection{TooL vs. Java}

Die Programmiersprache Java \cite{JAVA} besitzt einige Gemeinsamkeiten 
mit TooL und ist deshalb ein weiterer Vergleichskandidat. Java ist
ebenfalls objektorientiert und
wird auch auf einer virtuellen Maschine interpretiert.
Allerdings ist sie nicht rein objekt\-orientiert und auch nicht 
orthogonal persistent wie TooL.
 F"ur diesen 
Performanzvergleich \mbox{werden} nur "ahnlich codierte Benchmarks herangezogen, 
und die Messungen  sollen nur einen \mbox{ersten} Eindruck von dem
Performanzverh"altnis
festhalten.
Die Zahlen in Abbildung \ref{TooLvsJava} \mbox{sprechen} ein deutliches
Urteil: TooL-Programme laufen um eine Gr"o\3enordnung langsamer als
Java-Programme. 
Woher dieser gro\3e Unterschied kommt,  l"a\3t sich ohne einen
genaueren Vergleich der Interpreter, der
Laufzeitsysteme und der Spracheigenschaften nur grob erkl"aren:
Die stichprobenartigen Messungen dieses Kapitels ergeben, da\3
optimierte TL-Benchmarks 2 bis 3-mal langsamer als Java-Benchmarks 
ablaufen. In diesen Java-Benchmarks treten fast keine dynamischen
Methodenaufrufe auf, so da\3 ihre Ablaufmuster n"aher an denen
der TL-Programme liegen. Dieser Faktor von 2 bis 3 mag an den
Kosten der Persistenz liegen, denn jedes Objektspeicherwort
ist mit Tag-Bits versehen, welche die Zugriffe verteuern.
Die TooL-Benchmarks sind um 3 bis 6-mal langsamer als TL-Benchmarks,
was auf  verbleibende Botschaften zur"uckzuf"uhren ist.
Eine einfache Kombination dieser Faktoren ergibt m"ogliche TooL-Java
Verh"altnisse von 6 bis 18, was den gemessenen Werten entspricht.


\begin {figure}[tbh]
\centering
\begin{tabular}{|| l | l | l | l ||} \hline
{\em Benchmark}    &  {\em Zeit: TooL optimiert (s)}  &  
 {\em Zeit: Java (s)}  & {\em Performanzvorteil: Java/TooL}\\ \hline

   perms     &  3.26    & 0.45  & 7.24\\
   queens     & 4.7  &  0.21 & 22.38 \\
   puzzle     & 32.12   & 2.56   & 12.55 \\ \hline
\end{tabular}
\caption{Performanzvergleich zwischen TooL und Java}
\label{TooLvsJava}
\end {figure}


\subsection{Fazit}


Der TooL-Optimierer kann die Laufzeit von TooL-Programmen entscheidend
verringern. Allerdings zeigt der Vergleich mit den Sprachen TL und
Java, da\3  noch Handlungsbedarf 
besteht:

Die allgemeine Klassenanalyse dieser Arbeit, die keine Sonderf"alle
ber"ucksichtigt,
reicht nicht aus, um alle Methodenaufrufe an Basismethoden zu 
eliminieren. Es ist nicht realistisch anzunehmen, da\3 ein
g"anzlich unparteiischer Mechanismus  ausreicht, um auch
die h"aufig vorkommenden Aufrufe der Botschaften {\sf \sfrontq *,-,=\sbackq} usw.
naheliegenderweise entfernen zu k"onnen. 
Als Alternative zur Klassenabsch"atzung kann zur "Ubersetzungszeit
mit Hilfe der markierten Typen ein Satz von h"aufigen Basisselektoren
w"ahrend der Abbildung des TooL-ASTs auf den TML-AST expandiert werden.
 Dieses setzt voraus, da\3 die Typinferenz
der Typ"uberpr"ufung immer vor der "Ubersetzung von TooL nach TML abl"auft (zur Zeit wird
die Typ"uberpr"ufung nur optional durchgef"uhrt). Diese  Expansion
kann sich auf einen Satz von Primitiven beschr"anken und mu\3 nicht unbedingt
Kontrollstrukturen beinhalten. Kontrollstrukturen k"onnen durch allgemeinere
Transformationen w"ahrend  einem Optimierungslauf in effizientere Formen
"uberf"uhrt werden.
Auf jeden Fall w"urde die begrenzte Ausnutzung der Typattribute
im TooL-AST durch die Festlegung einiger Basis\-typen sich anbieten, da
das Typsystem von  TooL diese Optimierungshinweise bereitstellt.





\section{Performanzvergleich zwischen der Registerarchitektur  
und der Kellerarchitektur}

Vor einem eventuellen Einsatz der 
Tycoon Registermaschine TRM als TooL-Plattform soll die
Frage gekl"art werden, wie leistungsf"ahig der Registermaschinencode ist,
denn nur ein deut\-licher Geschwindigkeitsvorteil
w"urde den Aufwand eines Wechsels auf die TRM mit voll\-st"andigem TL-{\em bootstrap} 
rechtfertigen. 

In diesem Abschnitt wird die TRM mit der
Kellermaschine TVM  anhand einer \mbox{kleinen} Reihe von Benchmarks
aus der Stanford-Suite verglichen. Diese Tests wurden in der \mbox{Sprache} TL durchgef"uhrt,
da die Entwicklung von TooL zeitgleich zur  Entwicklung des TRM-Codegenerators 
erfolgte, und der TRM-Interpreter noch keinen Methodenaufruf
unterst"utzt\footnote{Der {\tt send}-Bytecode ist zwar im
Instruktionssatz vorgesehen, dessen Ausf"uhrung aber nicht implementiert.}.
Auch diese Tests erfolgten auf einer unbelasteten SparcStation 20 mit
2 Prozessoren und 256 MB Hauptspeicher.


\subsection{Auswirkung der verschiedenen Interpreterimplementierungen}

Zun"achst soll die Auswirkung der verschiedenen Interpreterimplementierungen betrachtet
werden. Von Interesse ist, ob die Interpreter grundlegende Differenzen 
besitzen, die einen direkten Vergleich unm"oglich machen. Da die Instruktionss"atze
sich sehr stark unterscheiden, wurden 
 die Ausf"uhrungszeiten
von einigen TL-Primitiven statt den Zeiten einzelner
Byte\-code\-befehle gemessen. Diese TL-Primitive k"onnen
als atomare Berechnungseinheiten 
verstanden werden, denn sie bilden den Basissatz von Operationen,
aus denen TL-Programme sich zusammensetzen.


Das Ergebnis der Messung in Tabelle \ref{primBench} l"a\3t den
Schlu\3 zu, da\3 die Interpreter sehr "ahnlich codiert sind und
keine bemerkenswerten Unterschiede bestehen. Die TRM erscheint
leicht schneller f"ur die Ausf"uhrung einzelner Berechnungseinheiten.


\begin {figure}[tbh]
\centering
\begin{tabular}{|| l | l | l ||} \hline
{\em TL-Berechnungseinheit}    &  {\em TRM-Zeit (ms)}  &  {\em TVM-Zeit (ms)} \\ \hline
Binden eines Wertes &  0.02 &    0.04 \\
Anlegen eines Funktionsobjektes  &  0.04 &    0.04 \\
Funktionsaufruf   &  0.04 &    0.06 \\
Tupelerzeugung &  0.06 &    0.06 \\
Tupelreferenz   &  0.04 &    0.06 \\
Konditional       &  0.02 &    0.04 \\
Arrayerzeugung  &  0.04 &    0.04 \\ \hline
\end{tabular}
\caption{Vergleich der Ausf"uhrungszeiten f"ur TL-Grundoperationen}
\label{primBench}
\end {figure}


\subsection{Benchmarks}

Die Ausf"uhrungszeiten der nicht-optimierten Testf"alle aus der Stanford-Suite
sind in Tabelle \ref{fullBench} wiedergegeben. Es ist deutlich erkennbar, da\3
der Code der Registermaschine nicht so schnell wie der Code der Kellermaschine ist;
im Durchschnitt liegt die Leistung der Registermaschine nur bei 95 \% der
Performanz der Kellermaschine.
Der Grund hierf"ur liegt in der Tatsache, da\3 in nicht-optimierten TL-Programmen
auch primitive Operationen in Funktions\-aufrufe "ubersetzt werden. Dadurch hat die
Registerallokation kaum Handlungsspielraum, denn viele Variablen
m"ussen aufgrund der Aufrufdichte im Keller abgelegt werden.
Vor jeder Operation werden zus"atzliche Befehle notwendig,
die Werte von dem Keller in die f"ur Funktionsaufrufe vorgeschriebenen
Register bewegen, und somit f"allt der  erzeugte Maschinen\-code 
weniger kompakt aus  als der Kellermaschinencode.


\begin {figure}[tbh]
\centering
\begin{tabular}{|| l | l | l | l ||} \hline
{\em Benchmark}    &  {\em TRM-Zeit (ms)}  &  {\em TVM-Zeit (ms)}  &
{\em Performanzverh"altnis: TRM/TVM} \\ \hline
quicksort  &         6.98     &    6.68 & 0.96\\
bubblesort &         13.14    &    13.50 & 1.03  \\
treesort   &         2.70  &         2.70  & 1.00\\
queens     &       99.14    &      94.4000 & 0.95\\
permutations   &     3264.80   &    2754.70 & 0.84\\
towers         &     4140.00    &   3766.00 & 0.91 \\ \hline
\end{tabular}
\caption{Vergleich der Ausf"uhrungszeiten der nicht-optimierten Benchmarkprogramme}
\label{fullBench}
\end {figure}



Um die Auswirkung der Registerallokation zu messen, wurden diese Benchmarkprogramme
zus"atzlich durch Expansion ({\em inlining}) der primitiven Funktionen optimiert. In 
Tabelle
\ref{fullBenchOpt} ist
erkennbar, da\3 die Registermaschine
 leicht schneller als die Kellermaschine ist, aber im Durchschnitt nur um den
Faktor 1,05. 

\begin {figure}[tbh]
\centering
\begin{tabular}{|| l | l | l | l ||} \hline
{\em Benchmark}    &  {\em TRM-Zeit (ms)}  &  {\em TVM-Zeit (ms)}  &
{\em Performanzverh"altnis: TRM/TVM} \\ \hline
quicksort  &         3.80     &    3.90 & 1.03\\
bubblesort &         7.10    &       8.30 &  1.17 \\
treesort   &         1.90  &         1.90 & 1.00\\
queens     &         61.00    &      63.80 & 1.05\\
permutations   &     1285.00  &      1407.00 & 1.09\\
towers         &     2785.00   &     2660.00  & 0.96 \\ \hline
\end{tabular}
\caption{Vergleich der Ausf"uhrungszeiten der optimierten Benchmarkprogramme}
\label{fullBenchOpt}
\end {figure}

\subsection{Aufwand der Registerallokation}

Anschlie\3end soll der Zusatzaufwand der Registerallokation w"ahrend der Codegenerierung
festgehalten werden. Das TL-Standardmodul {\sl iter.tm} wurde mit zwei verschiedenen "Uber\-setzern
f"ur die Registermaschine 
"ubersetzt, einer mit  Registerallokation und einer ohne Register\-allokation (Operanden
werden zwar kurz in Register geladen, aber eigentlich im Keller gehalten).
Hier wurden folgende Zeiten f"ur die Codegenerierung gemessen:
\begin{itemize}
\item
Codegenerierung ohne Registerallokation: 10.09 s
\item
Codegenerierung mit Registerallokation:  41.89 s
\end{itemize}
Diese Zeiten entsprechen dem Aufwand der drei zus"atzlichen L"aufe durch den TML-Baum
(Berechnung der Ordnungszahlen, Lebendigkeitsanalyse und Registerzuordnung).


\subsection{Fazit}

Der Code der virtuellen Registermaschine ist nicht
bedeutend
schneller und oft langsamer als der Code der virtuellen Kellermaschine.
Der Hauptgrund hierf"ur ist, da\3 die simulierten
Register keinen Geschwindigkeitsvorteil "uber einem
simulierten Keller bieten. Es zeigt sich, da\3 auch
Code mit recht guten Registerallokationsergebnissen
kaum schneller als Keller\-maschinen\-code ist.
Zus"atzlich ist der Aufwand f"ur die Registerallokation
erheblich h"oher und erfordert folgende Phasen, um ann"ahernd
die gleiche Leistung wie die des simulierten Kellermaschinencodes
zu erreichen:


\begin{enumerate}
\item
Konversion der Abstraktionen in explizite Schritte zum Anlegen von Funktionsobjekten
als weitere TML-Transformation
\item
Optimierung der TML-Repr"asentation
\item
Lebendigkeitsanalyse
\item
Registerzuordnungslauf
\item
Codeerzeugung
\end{enumerate}

Die Codeerzeugung f"ur die Kellermaschine ist einfacher, da nur ein Lauf durch
den Baum n"otig ist, und die funktionale Natur von TML gut zum
Kellerprinzip pa\3t.
Einen Vorteil kann die Registermaschine dennoch besitzen:
Bei einer "Ubersetzung des virtuellen Maschinen\-codes in echten
Maschinencode k"onnen die simulierten Register im Gegensatz zum
Keller\-speicher einfach auf reale
Maschinenregister abgebildet werden.
Ob das zu so deutlich
h"oheren Ausf"uhrungsgeschwindigkeiten f"uhrt, da\3
der Aufwand der Registerallokation sich lohnt, mu\3 allerdings
vorher untersucht werden.

Gemessen an der geringen Performanzsteigerung ist der Aufwand der
Codeerzeugung
f"ur die Registermaschine zu gro\3
und fehleranf"allig, um den vollen
Einsatz der TRM als Ausf"uhrungsplattform f"ur
TooL zu rechtfertigen.


