% Studienarbeit von Marc Weikard
%
% Universitaet Hamburg
% Fachbereich Informatik
% Arbeitsbereich DBIS
%
% Kapitel: Laufzeitverhalten

\chapter{Das Laufzeitverhalten}
\label{Kap. Laufzeitverhalten}

Nachdem in Kapitel~\ref{Kap. Maschinencode} die Technik der dynamischen Maschinencodegenerierung vorgestellt wurde, erfolgt in diesem Kapitel die Betrachtung des Laufzeitverhaltens. Neben dem Vergleich der Ausf"uhrungsgeschwindigkeit von Interpreter und generiertem Maschinencode, werden auch der Aufwand der Codeerzeugung und die Ver"anderung der Codegr"o"se bewertet.


\section{Performanz}
\label{Abs. Performanz}

F"ur die Messungen wurden, wie bereits in \cite{Kira94}, zwei Standardtestprogramme verwendet, die \s{Standford Suite} und der \s{Richards' Benchmark}.

\s{Richards'} ist ein gr"o"seres Programm, das das Szenario eines Betriebssystems simuliert. Die \s{Stanford Suite} ist eine Sammlung einfacher Programme, die auf verschiedenen Sprachkonstrukten wie rekursiven Funktionen (\s{Perm, Towers, Queens, Tree}) sowie Schleifen und Feldbearbeitung (\s{Puzzle, FFT}) aufbauen:
\begin{tabbing}
\s{Bubble} \quad \= X \kill
\s{Perm}: \> Berechnung aller Permutationen "uber ein Ganzzahlenfeld mit 10 Eintr"agen. \\[.3cm]
\s{Towers}: \> L"osung des Problems der T"urme von Hanoi.\\[.3cm]
\s{Queens}: \> 50 maliges L"osen des 8 Damen Problems.\\[.3cm]
\s{Intmm}: \> Multiplikation zweier 40x40 Ganzahlmatrizen.\\[.3cm]
\s{Mm}: \> Multiplikation zweier 40x40 Flie"skommamatrizen.\\[.3cm]
\s{Quick}: \> Sortierung von 5000 Ganzzahlen mit dem Quicksort-Algorithmus.\\[.3cm]
\s{Bubble}: \> Sortierung von 5000 Ganzzahlen mit dem Bubblesort-Algorithmus.\\[.3cm]
\s{Trees}: \> Sortierung von 5000 Ganzzahlen mit dem Treesort-Algorithmus.\\[.3cm]
\s{FFT}: \> Fast Fourrier Transformation.\\[.3cm]
\s{Puzzle}: \> Iterative Feldbearbeitung.\\[.3cm]
\end{tabbing}
Alle Messungen wurden auf einem \pn{Sun SPARCserver 1000} durchgef"uhrt, wobei auf eine geringe Systemauslastung geachtet wurde, um die Ergebnisse nicht zu verf"alschen. Der TVM-Interpreter wurde mit dem GNU C-Compiler bei maximaler Optimierung (-O2) "ubersetzt, der generierte Code sowohl mit als auch ohne Optimierungen. Zur Zeitmessung diente die Funktion \s{times} aus der Standardbibliothek des Betriebsystems, welche die von einem Prozess verbrauchte CPU-Zeit ermittelt.

Als Objektspeicher kam in allen F"allen die auf dem Haupspeicher operierende und damit schnellste Variante \s{tymem} zum Einsatz, um den Einflu"s der persistenten Datenhaltung auf die Messergebnisse m"oglichst gering zu halten.

\begin{table} 
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|}
\hline
&& \multicolumn{2}{c|}{} &&\\
&& \multicolumn{2}{c|}{dyn.\ Maschinencode} &&\\
Programm & \multicolumn{1}{c|}{Interpreter} & \multicolumn{1}{c|}{ohne Opt.} & \multicolumn{1}{c|}{mit Opt.} & \multicolumn{1}{c|}{\raisebox{0.ex}[1ex][1ex]{\Large $\frac{M}{M_{opt}}$}} & \multicolumn{1}{c|}{\raisebox{0.ex}[1ex][1ex]{\Large $\frac{Int}{M_{opt}}$}} \\
& \multicolumn{1}{c|}{(s)} & \multicolumn{1}{c|}{(s)} & \multicolumn{1}{c|}{(s)} &&\\
& \hspace{1.7cm} & \hspace{1.7cm} & \hspace{1.7cm} & \hspace{1.2cm} & \hspace{1.2cm} \\
\hline
                &         &         &         &      &      \\
\s{Perm}        &  3.04 s &  1.44 s &  0.95 s & 1.52 & 3.20 \\
\s{Towers}      &  4.35 s &  2.13 s &  1.49 s & 1.43 & 2.92 \\
\s{Queens}      &  5.75 s &  2.77 s &  1.76 s & 1.57 & 3.27 \\
\s{Intmm}       &  3.55 s &  1.30 s &  0.86 s & 1.51 & 4.13 \\
\s{Mm}          &  5.37 s &  2.86 s &  2.24 s & 1.28 & 2.40 \\
\s{Quick}       &  4.67 s &  1.91 s &  1.38 s & 1.38 & 3.38 \\
\s{Bubble}      & 11.43 s &  4.87 s &  3.12 s & 1.56 & 3.66 \\
\s{Trees}       &  2.65 s &  1.63 s &  1.15 s & 1.42 & 2.30 \\
\s{FFT}         & 12.75 s &  7.11 s &  5.34 s & 1.33 & 2.39 \\
\s{Puzzle}      & 19.65 s &  4.08 s &  3.23 s & 1.26 & 6.08 \\
\s{Richards'}   & 23.58 s & 19.14 s & 13.69 s & 1.40 & 1.72 \\
                &         &         &         &      &      \\
\hline
                &         &         &         &      &      \\
Durchschnitt    &	  &	    &         & 1.42 & 3.22 \\
                &         &         &         &      &      \\
\hline
\end{tabular}
\caption{Performanzmessungen an den Standardtestprogrammen der \s{Stanford Suite} und am \s{Richards' Benchmark}}
\label{Performanz}
\end{center}
\end{table}

Die Laufzeiten des interpretierten Bytecodes und des generierten Maschinencodes werden in Tabelle~\ref{Performanz} gegen"ubergestellt. Es sind die besten Ergebnisse in einer Reihe von mindestests drei Messungen.

Klar zu erkennen ist die gro"se Schwankung beim erreichbaren Geschwindigkeitszuwachs. Die Spanne reicht in der optimierten Version von 1,7 (\s{RichardsÂ}) bis hin zu 6 (\s{Puzzle}) mal schnellerer Ausf"uhrung. Bedingt ist dies durch die in den einzelnen Testprogrammen verwendeten Sprachkonstrukte. Imperativ aufgebaute Programme, die Scheifen und Zustandsvariablen benutzen (z.B. \s{Puzzle, Intmm}), weisen eine deutlich h"ohere Performanzsteigerung auf als Programme mit funktionaler Struktur (\s{Quick, Trees}), deren "uberwiegendes Konstrukt die Rekursion ist. Haupverantwortlich hierf"ur ist das mit jedem TL-Funktionsaufruf notwendige und aufwendige Anlegen eines Ausf"uhrungsrahmens bzw. dessen Abbau mit Beendigung der Funktion. Auch der je nach Testprogramm unterschiedliche Anteil an Objektspeicherzugriffen hat einen Einflu"s auf die Messwerte (siehe Abschnitt~\ref{Abs. Persistenz}). Der Grund f"ur das vergleichsweise schlechte Abschneiden der \s{Fast Fourrier Transformation} (\s{FFT}) und Matrixmultiplikation (\s{Mm}) ist in der fehlenden Unterst"utzung von Flie"skommazahlen durch den TVM-Befehlssatz begr"undet. Flie"skommaarithmetik mu"s "uber die langsame C-Aufrufschnittstelle abgewickelt werden.    

Der generierte Maschinencode profitiert deutlich vom effizienten Optimierer des C-"Ubersetzers. Der Performanzgewinn liegt bei bis zu 50\%, im Gegenzug steigen allerdings die "Ubersetzungszeiten zum Teil erheblich an (siehe Abschnitt~\ref{Abs. Compilezeit}).  

Die benutzten Testprogramme wurden urspr"unglich f"ur konventionelle Hochsprachen (z.B. C) entwickelt und es stellt sich die Frage, inwieweit sich die Ergebnisse auf eine funktionale Sprache wie TL und f"ur persistente Systeme typische Applikationen "ubertragen lassen. Um zu einer groben Absch"atzung zu kommen, wurden in einem Versuch das gesamte in TL implementierte Compiler-Front- und Backend in die dynamische Codegenerierung mit einbezogen (siehe Abschnitt~\ref{Abs. Implementierung}) und die "Ubersetzungszeiten f"ur kleine TL-Ausdr"ucke gemessen. Der Geschwindigkeitszuwachs liegt mit ca. 75\% bis 100\% etwa im Bereich des \s{Richards' Benchmark}.

Die Auswirkungen des dynamischen TML-Optimierers \cite{Kira94}, vor allem der Funktionsexpansion, auf die G"ute des generierten Maschinencodes konnten aufgrund von Fehlern im Zusammenspiel des dynamischen Optimierers mit dem restlichen Compiler Back-End (siehe Abschnitt~\ref{Abs. Implementierung}) nicht genauer untersucht werden. Entsprechend von Hand optimierter Bytecode zeigte sowohl in der Ausf"uhrung durch den Interpreter als auch im Maschinencode eine um den Faktor 1,8 erh"ohte Performanz. Die in Abschnitt~\ref{Abs. Optimierung} vorgestellte Optimierungsm"oglichkeit f"ur den Codegenerator ist sicherlich dazu geeignet, diese Spanne weiter zugunsten des Maschinencodes zu verschieben.    


\section{Einflu"s der Persistenz}
\label{Abs. Persistenz}

Die Notwendigkeit zur persistenten Datenhaltung schafft mit dem Objektspeicher und der TSP-Schnittstelle einen die Geschwindigkeit von Byte- und Maschinencode limitierenden Faktor. Zur Ermittlung des Einflu"s von Objektspeicherzugriffen auf die gesamte Ausf"uhrungszeit eines Programmlaufs wurden die in der Entwicklungsumgebung von \pn{Solaris} \cite{SOL} bereitgestellten Werkzeuge \pn{Profiler} und \pn{Analyzer} benutzt. Der \pn{Profiler} "uberwacht den Ablauf eines Programms und untersucht in kurzen Intervallen (im Bereich weniger ms) dessen Ausf"uhrungszustand, z.B. Programmz"ahler und Stapelspeicher. Die gewonnenen Daten k"onnen mit dem \pn{Analyzer} nach verschiedenen Kriterien ausgewertet werden, u.a. l"a"st sich die Verweildauer f"ur jede Funktion einzeln bestimmen.

\begin{figure}[t]
\begin{center}
\leavevmode
\epsfxsize=8.2cm
\epsffile{Bilder/TVMProfile.eps}
\caption{Profilerlauf f"ur das Testprogramm \s{Queens}}
\label{TVMProfile}
\end{center}
\end{figure}

Die Ergebnisse eines Interpreterlaufs f"ur das Testprogramm \s{Queens} werden in den Abbildungen~\ref{TVMProfile} und~\ref{TSPProfile} dargestellt. Wie zu erkennen ist, nehmen die Objektspeicherzugriffe etwa 6\% der Ausf"uhrungszeit in Anspruch. Hinzu kommen 5\% von den Funktionen des Laufzeitsystems. Da der Maschinencode jedoch nur den Anteil des Interpreters ersetzt, ist ein Geschwindigkeitszuwachs auf mehr als das 10 fache nicht zu realisieren.  

\begin{figure}[b]
\begin{center}
\leavevmode
\epsfxsize=8.2cm
\epsffile{Bilder/TSPProfile.eps}
\caption{Verteilung des Objektspeicherzugriffe f"ur das Testprogramm \s{Queens}}
\label{TSPProfile}
\end{center}
\end{figure}

Eine Reduktion der "uberwiegend lesenden Zugriffe (\s{tsp\_getWord}), z.B. durch die Zwischenspeicherung bereits gelesener Daten in lokalen Variablen, kann nur innerhalb kurzer Programmabschnitte (\e{basic blocks}) stattfinden. Da kein Mechanismus existiert, um die Ausl"osung der Freispeicherverwaltung zu "uberwachen, besteht mit Abgabe des Kontrollflusses die Gefahr, da"s lokal gesicherte Werte (OIDs) ihre G"ultigkeit verlieren.   
 

\section{Aufwand der Codegenerierung}
\label{Abs. Compilezeit}

Neben der Zunahme an Performanz ist der Generierungsaufwand ein f"ur die Beurteilung der Effektivit"at des dynamischen Codegenerators entscheidendes Kriterium. In Tabelle~\ref{Compiletime} werden die Laufzeiten des C-"Ubersetzers f"ur die einzelnen Testprogramme ohne und mit Optimierungen denen des TL-"Ubersetzers gegen"ubergestellt. Die Messungen erfolgten mit dem Unix Kommando \s{time} bzw. der Bibliotheksfunktion \s{times}.

\begin{table}
\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
&& \multicolumn{2}{c|}{} &\\
&& \multicolumn{2}{c|}{C-"Ubersetzer} &\\
Programm & \multicolumn{1}{c|}{TL-"Ubersetzer} & \multicolumn{1}{c|}{ohne Opt.} & \multicolumn{1}{c|}{mit Opt.} & \multicolumn{1}{c|}{\raisebox{0.ex}[1ex][1ex]{\Large $\frac{C_{opt}}{C}$}} \\
& \multicolumn{1}{c|}{(s)} & \multicolumn{1}{c|}{(s)} & \multicolumn{1}{c|}{(s)} &\\
& \hspace{1.7cm} & \hspace{1.7cm} & \hspace{1.7cm} & \hspace{1.5cm} \\
\hline
                &         &         &          &      \\
\s{Perm}        &  3.49 s &  7.30 s &  14.90 s & 2.04 \\
\s{Towers}      &  8.91 s & 15.32 s &  38.14 s & 2.49 \\
\s{Queens}      &  5.00 s & 10.94 s &  26.91 s & 2.46 \\
\s{Intmm}       &  3.62 s & 11.43 s &  23.74 s & 2.08 \\
\s{Mm}          &  3.68 s & 15.81 s &  30.80 s & 1.95 \\
\s{Quick}       &  5.26 s & 15.26 s &  34.35 s & 2.25 \\
\s{Bubble}      &  4.18 s & 13.12 s &  30.82 s & 2.35 \\
\s{Trees}       &  6.24 s & 16.05 s &  32.10 s & 2.00 \\
\s{FFT}         & 20.29 s & 30.59 s & 124.97 s & 4.09 \\
\s{Puzzle}      & 33.24 s & 41.03 s & 322.34 s & 7.86 \\
\s{Richards'}   & 40.95 s & 63.71 s &  99.43 s & 1.56 \\
                &         &         &          &      \\
\hline
                &         &         &          &      \\
Durchschnitt    &         &         &          & 2.83 \\
                &         &         &          &      \\
\hline
\end{tabular}
\caption{"Ubersetzungszeiten der Standardtestprogramme \s{Stanford Suite} und \s{Richards' Benchmark}}
\label{Compiletime}
\end{center}
\end{table}

Im Schnitt verdoppeln sich die "Ubersetzungszeiten mit zugeschalteten Optimierungen, teilweise liegen sie sogar noch h"oher (\s{Puzzle}). Die Zahl der einzelnen Funktionen und damit der Overhead, der durch das Starten des C-"Ubersetzers entsteht, spielt hierbei eine untergeordnete Rolle. Vielmehr steigen die Zeiten mit der Gr"o"se des Quelltextes nicht linear an (Abbildung~\ref{Compile}). Die Dauer f"ur die Erzeugung des Quelltextes liegt im Bereich der Me"stoleranz.   

\begin{figure}
\begin{center}
\leavevmode
\epsfxsize=15cm
\epsffile{Bilder/Compilezeit.eps}
\caption{Anstieg der "Ubersetzungszeiten mit steigender Quellcodegr"o"se}
\label{Compile}
\end{center}
\end{figure}

Der in Abschnitt~\ref{Abs. Caching} beschriebene Laufzeitcache f"ur generierten Code tr"agt wesentlich dazu bei, die Auswirkungen des externen C-"Ubersetzers auf die Systemperformanz zu minimieren, da Bytecodefunktionen w"ahrend eines Systemlaufs in der Regel nur ein einziges Mal in Maschinencode transformiert werden m"ussen. 


\section{Entwicklung der Codegr"o"se}
\label{Abs. Codesize}

Wie bereits aus den in \cite{BDBV94} gemachten Erfahrungen zu erwarten, ist Maschinencode gegen"uber dem kompakten Bytecode mit einer drastischen Erh"ohung des Speicherbedarfs verbunden.

\begin{table}
\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
&&&&\\
\raisebox{-1.4ex}[1ex][1ex]{Programm} & \multicolumn{1}{c|}{\raisebox{-1.4ex}[1ex][1ex]{Funktionen}} & \multicolumn{1}{c|}{\raisebox{-1.4ex}[1ex][1ex]{Bytecode}} & \multicolumn{1}{c|}{\raisebox{-1.4ex}[1ex][1ex]{Maschinencode}} & \multicolumn{1}{c|}{\raisebox{-1.4ex}[1ex][1ex]{\Large $\frac{M}{B}$}} \\
&& \multicolumn{1}{c|}{\raisebox{-1.4ex}[0ex][0ex]{(Byte)}} & \multicolumn{1}{c|}{\raisebox{-1.4ex}[0ex][0ex]{(Byte)}} &\\
& \hspace{1.7cm} & \hspace{1.7cm} & \hspace{1.7cm} & \hspace{1.7cm} \\
\hline
                &    &      &        &        \\
\s{Perm}      &  7 &  378 &  37704 &  99.75 \\
\s{Towers}    & 13 & 1009 &  77752 &  77.06 \\
\s{Queens}    & 11 &  719 &  61144 &  85.04 \\
\s{Intmm}     & 12 &  621 &  61416 &  98.90 \\
\s{Mm}        & 16 &  732 &  83520 & 114.10 \\
\s{Quick}     & 15 &  991 &  77864 &  78.57 \\
\s{Bubble}    & 13 &  823 &  70488 &  85.65 \\
\s{Trees}     & 17 &  841 &  85816 & 102.04 \\
\s{FFT}       & 19 & 2557 & 147016 &  57.50 \\
\s{Puzzle}    & 12 & 4810 & 184560 &  38.37 \\
\s{Stanford}  & 55 & 9817 & 607428 &  61.88 \\
\s{Richards'} & 53 & 3323 & 434532 & 130.76 \\
                &    &      &        &        \\
\hline
                &    &      &        &        \\
Durchschnitt    &    &      &        &  85.80 \\
                &    &      &        &        \\
\hline
\end{tabular}
\caption{Gr"o"senvergleich zwischen Bytecode und dynamischem Maschinencode}
\label{Codesize}
\end{center}
\end{table}

Die in Tabelle~\ref{Codesize} angegebenen Werte beziehen sich auf die Gesamtgr"o"se der f"ur die Testprogramme erzeugten Bibliotheken. Diese beinhalten neben dem eigentlichen Programmcode auch Symbolinformation f"ur den dynamischen Binder, deren Anteil bei kleinen Bibliotheken ($<=$ 10 KB) mit etwa 60 -- 70\%, bei gro"sen Bibliotheken ($>$ 100 KB) mit etwa 30\% anzusetzen ist. 

Die Diskrepanz der Werte aus den Einzelsummen bzw. dem Gesamtpaket der \s{Stanford Suite} ist in der Eigenschaft des TL-"Ubersetzers begr"undet, mathematische und logische Operationen nicht mit festen TVM-Byteinstruktionen zu verbinden, sondern in Basisfunktionen zu kapseln. In den einzelnen Testprogrammen betr"agt der Anteil dieser Funktionen bis zu 50\% der gesamten Dateigr"o"se, im Paket f"allt er erheblich niedriger aus.

Es existieren verschiedene Methoden, den Speicherverbrauch zu verringern:
\begin{itemize}
\item Die in Abschnitt~\ref{Abs. Optimierung} vorgestellte Optimierung erh"oht nicht nur die Performanz, sondern reduziert gleichzeitig die Codegr"o"se.
\item Die Funktionsexpansion ersetzt einen aufwendigen Funktionsaufruf durch ein Primitiv.   
\item Volumin"ose oft genutzte Programmbl"ocke k"onnen in neue Funktionen des Laufzeitsystems verlagert werden.
\end{itemize}
Eine Reduktion der Codegr"o"se ist auch aus Geschwindigkeitsgr"unden w"unschenswert. Moderne Prozessorfamilien (\pn{PowerPC}, \pn{Intel i86}, \pn{SPARC}, \pn{DEC Alpha} etc.) besitzen interne, schnelle Cachespeicher, die einen Gro"steil der Speicherzugriffe abfangen k"onnen und so den Prozessor vom langsamen Haupspeicher entkoppeln. Aufgrund der geringen Gr"o"se dieser Zwischenspeicher (16 -- 64 KB) wird ihre Effizienz, neben der Anzahl und Verteilung von Datenzugriffen, ma"sgeblich von der Programmgr"o"se bestimmt. 





