Typo
[darcs-mirror-talk-mrmcd12-haskell-bytes.git] / HaskellBytes.tex
1 \documentclass[11pt,DIV=12,parskip=half,headings=normal,abstract]{scrartcl}
2
3 \usepackage[T3,T1]{fontenc}
4 \usepackage[utf8]{inputenc}
5 \usepackage[ngerman]{babel}
6 \usepackage{amsmath}
7 \usepackage{amsfonts}
8 \usepackage[standard]{ntheorem}
9 \usepackage{amscd}
10 \usepackage{mathtools}
11 \usepackage{stmaryrd}
12 \usepackage{faktor}
13 \usepackage{enumerate}
14 \usepackage{wrapfig}
15 \usepackage[safe]{tipa} % for \textlambda
16
17 \usepackage[pdfauthor={Joachim Breitner},pdftitle={Haskell Bytes},pdfsubject={Eine Führung durch den Hauptspeicher eines Haskell-Programms}]{hyperref}
18 \usepackage{listings}
19 \usepackage{multicol}
20 \usepackage{ragged2e}
21 %\usepackage[para]{footmisc}
22 \usepackage{fourier}
23 \usepackage{microtype}
24 \usepackage{comment}
25
26 \usepackage{tikz}
27 \usetikzlibrary{shapes.geometric}
28 \usetikzlibrary{calc}
29 \usetikzlibrary{shapes.multipart}
30 \usetikzlibrary{arrows}
31
32 \urlstyle{sf}
33
34 \author{Joachim Breitner\footnote{\href{mailto:mail@joachim-breitner.de}{mail@joachim-breitner.de}, \url{http://www.joachim-breitner.de/}. Diese Arbeit wurde durch ein Promotionsstipendium der \href{http://telekom-stiftung.de/}{Deutschen Telekom Stiftung} gefördert.}}
35 \title{Haskell Bytes}
36 %\subject{Die Umsetzung von Haskell durch GHC}
37 \subtitle{Eine geführte Tour durch den Hauptspeicher eines Haskell-Programms}
38 \publishers{MRMCD 12\footnote{\url{http://mrmcd.net/}}, Darmstadt}
39 \date{8. September 2012}
40
41
42 \definecolor{light-gray}{gray}{0.95}
43 \lstdefinestyle{basic}{
44         ,columns=flexible
45         ,basewidth={.365em}
46         ,keepspaces=True
47         ,belowskip=0pt
48         ,backgroundcolor=\color{light-gray}
49         ,frame=single
50         ,xleftmargin=2em
51         ,xrightmargin=2em
52         ,basicstyle=\small\sffamily
53         ,stringstyle=\itshape
54 }
55 \lstdefinestyle{haskell}{
56         style=basic
57         ,language=Haskell
58         ,literate=
59                 {ö}{{\"o}}1
60                 {ä}{{\"a}}1
61                 {ü}{{\"u}}1
62         ,texcl=true
63         ,showstringspaces=false
64         ,keywords={module,where,open,import,using,renaming,to,data,let,in,with}
65 }
66
67 \newcommand{\mylabel}[1]{\raisebox{2em}[0pt][0pt]{\makebox[0pt][l]{\makebox[\linewidth][r]{\color{gray}{\sffamily #1}\hspace{2em}}}}\ignorespaces}
68 \lstnewenvironment{haskell}{\lstset{style=haskell}}{\mylabel{Haskell}\pagebreak[2]}
69 \lstnewenvironment{ghci}{\lstset{style=haskell}}{\mylabel{GHCi}\pagebreak[2]}
70 \lstnewenvironment{shell}{\lstset{style=basic}}{\mylabel{Shell}}
71 \newcommand{\inputhaskell}[1]{\lstinputlisting[style=haskell]{#1}\mylabel{Haskell}}
72 \newcommand{\li}{\lstinline[style=haskell]}
73
74
75 \begin{document}
76
77 \maketitle
78
79 Haskell ist eine tolle Programmiersprache; ich schätze ihr das alle schon wisst, sonst wärt ihr wohl nicht in meinem Vortrag. Aber manchmal wird man von Haskella auch enttäuscht. Nehmen wir folgenden Code:
80 \begin{haskell}
81 main = do
82     input <- getContents
83     putStrLn $ "I read " ++ show (length input) ++ " bytes."
84     putStrLn $ "The last line is:"
85     putStrLn $ last (lines input)
86 \end{haskell}
87 und füttern ihn mit einer 100MB großen Textdatei. Mit dem Parameter \texttt{-RTS -t} können wir uns Statistiken anzeigen lassen und erfahren, dass das Programm 2521MB Speicher braucht – über 24$\times$ zu viel!
88
89 Ein anderes, klassiches Beispiel für unerwartetes Laufzeitverhalten ist der folgende Code, der die länge einer Liste zählt:
90 \lstinputlisting[style=haskell,linerange=3-6]{Count.hs}\mylabel{Haskell}
91 Im Interpreter sehen wir, dass der Code unnötig viel Speicher verbraucht und dann mit einem Stack Overflow abbricht:
92 \begin{ghci}
93 *Count> let x = count 0 [0..100000000]
94 *Count> x
95 Just *** Exception: stack overflow
96 \end{ghci}
97
98 Manchmal aber überrascht uns Haskell auch positiv. Wenn wir, wieder beim ersten Programm, die dritte Zeile löschen und
99 \begin{haskell}
100 main = do
101     input <- getContents
102     putStrLn $ "The last line is:"
103     putStrLn $ last (lines input)
104 \end{haskell}
105 laufen lassen haben wir plötzlich einen Speicherverbrauch von 2MB – das ist 50$\times$ besser als erwartet! Und dann gibt es ja auch noch die unendlichen Listen in Haskell\dots
106
107 \section{Die Akteure}
108
109 Fragen wir uns also, was ein Haskell-Programm während der Ausführung alles im Speicher vorhalten muss. Zuerst wären da natürlich die eigentlichen \emph{Daten}, also Konstruktoren wie \li-True- oder \li-Just- oder \li-(,)-, die wiederum andere Werte enthalten können. Weiter ist Haskell ja eine funktionale Sprache die sich dadurch auszeichnet, dass man Funktionen selbst wie Daten behandeln kann. Also müssen wir auch \emph{Funktionen} speichern können. Und zuletzt ist Haskell lazy, das heißt es gibt Werte die noch nicht ausgewertet sind. Diese heißen \emph{Thunks}. Das sind schon mal die wichtigsten; allgemein spricht man hierbei von \emph{Closures}.
110
111 Bevor wir nun in den Speicher eines Haskell-Programms reinschauen überlegen wir noch, was denn jeweils zu so einer Funktion gespeichert werden soll.
112 \begin{itemize}
113 \item Der Typ eines Wertes: Der ist tatsächlich nicht nötig! Das Typsystem stellt sicher dass jeglicher Code stets Werte von Typ vorfindet, den er erwartet, er kann also blind drauf vertrauen. Das ist ganz anders als z.B. in Python!
114 \item Welcher Konstruktor: Ja, das muss man speichern, zumindest für Typen mit mehreren, etwa bei \li-data Maybe a = Just a | Nothing-.
115 \item Die Parameter des Konstruktors: Natürlich!
116 \item Bei Funktionen: Der Code der Funktion.
117 \item Nicht vergessen bei Funktionen und Thunks: Freie Variablen!
118 \end{itemize}
119
120 \subsection{Konstruktoren}
121
122 Schauen wir mal an was wir vorfinden, wenn wir mit GHCi etwas rumspielen, und fangen mit einer einfachen Zahl an:
123 \begin{ghci}
124 *Utils> let eins = 1 :: Int
125 *Utils> viewClosure eins
126 0x00007f9c7a3337f8: 0x0000000040502608 0x0000000000000001
127 \end{ghci}
128
129 Wir sehen also dass wir für einen Integer-Wert zwei Worte, die auf meiner Maschine jeweils 8 Bytes groß sind, benötigen. Das zweite speichert offensichtlich die eigentliche Zahl.
130
131 Wie sieht es mit Zeichen, also Charakters aus?
132 \begin{ghci}
133 *Utils> let zett = 'z'
134 *Utils> viewClosure zett
135 0x00007f9c7a0e8238: 0x0000000040502548 0x000000000000007A
136 \end{ghci}
137 Auch diese benötigen zwei Wörter, also 16 statt einem Byte! 
138
139 Kommen wir nun zu algebraischen Datentypen, und packen \li-eins- in \li-Just-:
140 \begin{ghci}
141 *Utils> let jeins = Just eins
142 *Utils> viewClosure jeins
143 0x00007f9c7b082710: 0x00000000420DC920 0x00007f9c7a3337f8
144 \end{ghci}
145
146 Beachte dass im Wert \li-Just eins- keine Kopie von \li-eins- gespeichert ist, sondern eine Referenz drauf.
147 %Das ist aus zwei Gründen wichtig: \li-eins- könnte sehr groß sein, dann will man es natürlich nicht kopieren. Und es gibt Funktionen die mit \li-Maybe a- für beliebige Typen \li-a- arbeiten. Die wissen nicht dass \li-Just eins- ein Integer enthält. Würde man jetzt den Wert direkt reinkopieren wäre 
148
149 Nun wollen wir verstehen, warum unser erstes Beispielprogramm so viel Speicher brauchte. Dazu erinnern wir uns dass der Typ \li-String- in Haskell nur eine Alias für \li-[Char]-, also Listen von Zeichen, ist.
150 \begin{ghci}
151 *Utils> let hallo = "hallo"
152 *Utils> viewListClosures hallo
153 0x00007f9c7ba21fa0: 0x0000000040502668 0x00007F9C7BA21F91 0x00007F9C7BA21F70
154 0x00007f9c7ba21f90/1: 0x0000000040502548 0x0000000000000068
155 0x00007f9c7ba77b18: 0x0000000040502668 0x00007F9C7BA77B09 0x00007F9C7BA77AE8
156 0x00007f9c7a1a9768/1: 0x0000000040502548 0x0000000000000061
157 0x00007f9c7ba405f0: 0x0000000040502668 0x00007F9C7BA405E1 0x00007F9C7BA405C0
158 0x00007f9c7ba405e0/1: 0x0000000040502548 0x000000000000006C
159 0x00007f9c7ba83f38: 0x0000000040502668 0x00007F9C7BA83F29 0x00007F9C7BA83F08
160 0x00007f9c7ba83f28/1: 0x0000000040502548 0x000000000000006C
161 0x00007f9c7ba55a20: 0x0000000040502668 0x00007F9C7BA55A11 0x00007F9C7BA559F0
162 0x00007f9c7a01e840/1: 0x0000000040502548 0x000000000000006F
163 0x0000000040507e70: 0x0000000040502648
164 \end{ghci}
165 Wir sehen nun dass die Liste \li-"hallo"- erst einmal aus einem Closure mit drei Wörtern besteht. Das zweite ist ein Pointer auf ein Closure für \li-'h'- und das dritte ein Pointer auf \li-"allo"-, und so weiter, bis wir bei der leeren Liste \li-[]- angekommen sind. Man beachte die deutlich andere Adresse: \li-[]- gibt es global nur einmal und lebt im statischen Codebereich.
166
167 An der Stelle will ich demonstrieren warum man in GHC keinen Zugriff auf die eigentlichen Pointer haben sollte:
168 \begin{ghci}
169 *Utils> System.Mem.performGC
170 *Utils> viewListClosures hallo
171 0x00007f9c7a1510a8: 0x0000000040502668 0x00007F9C7A151389 0x00007F9C7A151372
172 0x00007f9c7a151388/1: 0x0000000040502548 0x0000000000000068
173 0x00007f9c7a151370: 0x0000000040502668 0x00007F9C7A1516F1 0x00007F9C7A1516DA
174 0x00007f9c7a1516f0/1: 0x0000000040502548 0x0000000000000061
175 0x00007f9c7a1516d8: 0x0000000040502668 0x00007F9C7A151AC1 0x00007F9C7A151AAA
176 0x00007f9c7a151ac0/1: 0x0000000040502548 0x000000000000006C
177 0x00007f9c7a151aa8: 0x0000000040502668 0x00007F9C7A151ED9 0x00007F9C7A151EC2
178 0x00007f9c7a151ed8/1: 0x0000000040502548 0x000000000000006C
179 0x00007f9c7a151ec0: 0x0000000040502668 0x00007F9C7A150211 0x0000000040507E71
180 0x00007f9c7a150210/1: 0x0000000040502548 0x000000000000006F
181 0x0000000040507e70: 0x0000000040502648
182 \end{ghci}
183 Der gleiche Wert, plötzlich woanders! GHC verwendet standardmäßig einen kopierenden Garbage-Collector – alle noch benötigten Werte werden in einen komplett neuen Speicherbereich kopiert und der alte am Stück freigegeben. Das ist schneller und genauer als z.B. Referenzen zu zählen, aber dafür braucht man auch doppelt so viel physischen Speicher. Und für die denen ein Bild mehr als tausend Worte sagt habe ich das noch als \href{run:GC.webm}{Video} visualisiert.
184 \begin{center}
185 \includegraphics[width=.6\linewidth]{GC.png}
186 \end{center}
187
188 Es gibt noch einen weiteren Effekt den man hier jetzt gesehen hätte, würden wir das Programm wirklich ausführen (und nicht im Interpreter laufen lassen). Dann wäre die Ausgabe nämlich:
189 \begin{shell}
190 $ ./HelloGC 
191 0x00007f16c0d04270/2: 0x000000000049B1C8 0x00007F16C0D04261 0x00007F16C0D04240
192 0x00007f16c0d04260/1: 0x000000000049B128 0x0000000000000068
193 0x00007f16c0d162b0/2: 0x000000000049B1C8 0x00007F16C0D162A1 0x00007F16C0D16280
194 0x00007f16c0d162a0/1: 0x000000000049B128 0x0000000000000061
195 0x00007f16c0d262b0/2: 0x000000000049B1C8 0x00007F16C0D262A1 0x00007F16C0D26280
196 0x00007f16c0d262a0/1: 0x000000000049B128 0x000000000000006C
197 0x00007f16c0d362b0/2: 0x000000000049B1C8 0x00007F16C0D362A1 0x00007F16C0D36280
198 0x00007f16c0d362a0/1: 0x000000000049B128 0x000000000000006C
199 0x00007f16c0d462b0/2: 0x000000000049B1C8 0x00007F16C0D462A1 0x00007F16C0D46280
200 0x00007f16c0d462a0/1: 0x000000000049B128 0x000000000000006F
201 0x00000000006fb188/1: 0x000000000049B1A8
202 0x00007f16c0dfd4b8/2: 0x000000000049B1C8 0x00000000006FBAD1 0x00007F16C0DFD51A
203 0x00000000006fbad0/1: 0x000000000049B148 0x0000000000000068
204 0x00007f16c0dfd518/2: 0x000000000049B1C8 0x00000000006FBA61 0x00007F16C0DFD552
205 0x00000000006fba60/1: 0x000000000049B148 0x0000000000000061
206 0x00007f16c0dfd550/2: 0x000000000049B1C8 0x00000000006FBB11 0x00007F16C0DFD56A
207 0x00000000006fbb10/1: 0x000000000049B148 0x000000000000006C
208 0x00007f16c0dfd568/2: 0x000000000049B1C8 0x00000000006FBB11 0x00007F16C0DFD582
209 0x00000000006fbb10/1: 0x000000000049B148 0x000000000000006C
210 0x00007f16c0dfd580/2: 0x000000000049B1C8 0x00000000006FBB41 0x00000000006FB189
211 0x00000000006fbb40/1: 0x000000000049B148 0x000000000000006F
212 0x00000000006fb188/1: 0x000000000049B1A8
213 \end{shell}
214 und wir sehen dass nach dem Garbage Collector die Closures für das \li-'l'- identisch sind (beide zeigen nun auf \li-0x00000000006FBB11-) und im statischen Codebereich liegen. Das ist eine Optimierung speziell für \li-Char-s im ASCII-Bereich und für \li-Int-s mit Betrag bis zu 16. 
215
216 Nun müssten wir den Speicherverbrauch von \li-string- abschätzen können. Wir haben 100000000 Bytes, die jeweils in einem \li-Char- abgespeichert werden. Da die aber alle aus dem ASCII-Bereich sind, kosten sie nichts. Die Liste selbst jedoch braucht für jede Zelle drei Wörter á 8 Bytes, das sind fast die beobachteten 2521MB Speicherverbrauch. (Warum nicht das Dopplete? Weil der Garbage Collector nicht immer den gesamten Speicher kopiert sondern ihn in Generationen aufteilt – was wir hier nicht weiter vertiefen wollen.)
217
218 An dieser Stelle sollte klar sein dass sich der eingebaute \li-String--Datentyp \emph{nicht} für schnellen und speichereffizienten Code eignet. Es gibt Alternativen, allen voran \li-ByteString- für rohe Bytes und \li-Text- für Unicode-Text.
219
220 \subsection{Funktionen}
221
222 Wenden wir uns nun der nächsten Art von Closures zu, nämlich Funktionen. Weil es hier interpretiert recht anders als kompiliert funktioniert lasse ich folgendes Programm laufen:
223
224 \inputhaskell{FunClosures.hs}
225 was zu folgender Ausgabe führt:
226 \begin{shell}
227 $ ghc --make FunClosures.hs -O && ./FunClosures  1 2 3
228 0x00000000006f3090/2: 0x0000000000420DD8
229 0x00000000006ef7f0/1: 0x0000000000406408
230 0x00007f73f8d0e880/2
231 0x00007f73f8d10348/1: 0x0000000000406498 0x00007F73F8D0E882
232 \end{shell}
233 Einfache Funktionen liegen im statischen Code-Bereich und enhalten genau einen Pointer irgendwo hin. Das gilt auch für lokal definierte Funktionen. Interessant ist die Funktion \li-h-. Diese verwendet einen Wert (\li-a-) aus einer lokalen Variable. Das heißt der Code für \li-main- legt eine neue Funktionen-Closure auf dem Heap an, die zwei Wörter groß ist: Ein Verweis auf den statischen Code und eine Referenz auf den Wert von \li-a-. 
234
235 \subsection{Thunks}
236
237 Das wars erstmal von den Funktionen und wir wenden uns Thunks zu, die in gewisser weise nichts anderes sind als Funktionen ohne Parameter. Da es jetzt langsam kompliziert wird schauen wir uns nicht mehr den Speicher direkt an, sondern verwenden \li!ghc-vis!, ein Tool das Dennis Felsing in seiner Bachelorarbeit bei mir gerade entwickelt. Wir probieren folgenden Code im Modul \li-InfLists-
238 \begin{haskell}
239 infList f x = f x : infList f x
240 l = infList (+19) 23
241 \end{haskell}
242 mittels
243 \begin{ghci}
244 Prelude Inflists> :script /home/jojo/dokumente/Uni/WM/arbeiten/lazy-vis/vis/ghci
245 Prelude Inflists> :vis
246 Prelude Inflists> :switch
247 Prelude Inflists> :view l
248 \end{ghci}
249 und klicken auf dem entstehenden Baum herum. Wichtige Beobachtungen:
250 \begin{itemize}
251 \item Die Liste scheint sich tatsächlich unendlich unendlich abzurollen.
252 \item Der Wert 42 wird jedes mal neu berechnet und neu gespeichert.
253 \end{itemize}
254
255 Schön ist es jetzt auch noch
256 \begin{haskell}
257 l2 = map negate l
258 \end{haskell}
259 anzuschauen und zu beobachten, wie die Auswertung der einen Liste die andere beeinflusst.
260
261 \begin{center}
262 \includegraphics[width=0.4\linewidth]{vis-output1.pdf}
263 \end{center}
264
265 Zum Vergleich nehmen wir diese Funktion für unendliche Listen, die -- semantisch -- das gleiche macht:
266 \begin{haskell}
267 infList2 f x = let l = f x : l in l
268 \end{haskell}
269 und untersuchen \li-l3 = infList2 (+19) (23::Int)- mit \li-:view-. Tatsächlich wird hier die Cons-Zelle und die 42 nur jeweils einmal berechnet, danach zeigt der Tail der Liste wieder auf die Liste selbst. Auf diese Weise schafft es Haskell tatsächlich, eine unendliche Listen in endlich viel Speicher zu speichern!
270
271 Leider sind solche selbstbezüglichen Datenstrukturen fragil, wenn man sie „ändern“ will; schon ein einfaches \li-map negate l2- zerstört die Struktur, wie man hier gut sehen kann.
272
273 \begin{center}
274 \includegraphics[width=0.2\linewidth]{vis-output2.pdf}
275 \end{center}
276
277 An dieser Stelle will ich wieder auf das zweite Beispiel vom Anfang zurückkommen. Jetzt können wir mit \li!ghc-vis! dem Stack Overflow auf den Grund gehen: 
278 \begin{ghci}
279 *Count> :switch
280 *Count> let x = count 0 [1..5]
281 *Count> :view x
282 \end{ghci}
283 Wir sehen ganze viele Thunks, die nacheinander die \li-0- modifizieren. Das sind eben die Thunks, die für \li-(+1)- stehen. Macht ja auch Sinn: Bevor wir die Zahl nicht benötigen, wird keine Berechnung ausgeführt. Trotzdem muss die Berechnung ja gespeichert werden. Klickt man auf einen der Thunks, kollabiert der Turm darunter in einem Rutsch.
284
285 Besser ist folgender Code:
286 \lstinputlisting[style=haskell,linerange=8-10]{Count.hs}\mylabel{Haskell}
287 Der Operator \li-$!$- sorgt dafür, dass das Argument (hier \li-n+1-) ausgewertet wird, bevor die Funktion (hier \li-count2-) aufgerufen wird. Dadurch wird stets nur eine Zahl, und kein Thunk, übergeben. Es tritt kein Stack Overflow auf, der Speicherverbrauch ist Konstant (und mit \li!ghc-vis! gibt es nichts zu sehen):
288 \begin{ghci}
289 *Count> let x = count2 0 [1..100000000]
290 *Count> x
291 100000000
292 \end{ghci}
293 Nur der Ehrlichkeit halber: Bei diesem einfachen Programm hätte der Compiler das auch selbst gemacht, wenn ich die Funktion nicht durch das \li-Just- künstlich nicht-strikt im Argument gemacht hätte.
294
295
296 \section{Der Info-Pointer}
297
298 Zum Schluss will ich noch darauf eingehen, was das erste Wort jedes Closures ist. Ihr habt vielleicht schon beobachtet, dass es stets in den statischen Code-Bereich zeigt. Und euch ist sicher schon aufgefallen, dass die Information, welcher Konstruktor das denn gerade ist, oder wo der ausführbare Code einer Funktion steht, ja noch irgendwo stehen muss. All das, und noch viel mehr, versteckt sich hinter dem Info-Pointer:
299
300 \def\ux{2.8cm}\def\uy{0.6cm}
301 \begin{center}
302 \begin{tikzpicture}[x=\ux, y=\uy,
303         word/.style={shape=rectangle, draw, minimum width=\ux, minimum height=\uy}
304         ,halfword/.style={shape=rectangle, draw, minimum width=0.5*\ux, minimum height=\uy}
305         ,>=latex]
306 \draw (0,0) rectangle +(1,1) node[midway] (ip) {Info-Pointer}
307     ++(1,0) rectangle +(1,1) node[midway] {Pointer}
308     ++(1,0) rectangle +(1,1) node[midway] {Pointer}
309     ++(1,0) +(0.1,0.4) node {$\cdots$}
310     ++(0.2,0) rectangle +(1,1) node[midway] {Nicht-Pointer}
311     ++(1,0) rectangle +(1,1) node[midway] {Nicht-Pointer}
312     ++(1,0) +(0.1,0.4) node {$\cdots$};
313
314 \begin{scope}[yshift=-0.7cm, xshift=1.2*\ux]
315 \draw
316   (0,0) node[word] (tbl) {Code-Pointer}
317 ++(-0.25,-1) node[halfword] {\#ptr} ++(+0.5,0) node[halfword] {\#nptr} ++(-0.25,0)
318 ++(-0.25,-1) node[halfword] {Typ} ++(+0.5,0) node[halfword] {SRT} ++ (-0.25,0)
319 ++(0,-1) node[word] {ggf. Konstruktor}
320 ++(0,-1) node[word] {ggf. Stelligkeit};
321 \end{scope}
322 \draw[*->] (ip.south) |- (tbl.west);
323 \draw[*->] (tbl.east) -- ++(1.5cm,0) node[right] (code) {Entry code};
324 \draw (code) ++(-0.5,-1) -- ++(0,1.5) -- ++(1,0) -- ++(0,-1.5);
325 \end{tikzpicture}
326 \end{center}
327
328 Hier ist noch interessant dass die Parameter eines Konsturktors bzw. die freien Variablen einer Funktion stets so angeordnet sind, dass erst die Zeiger und dann die anderen Werte kommen. Damit kann die Größe und das Layout des Closures in zwei Halbworten gespeichert werden, die sich der Garbage Collector anschaut, ohne eigenen Code für jeden Konstruktor zu benötigen.
329
330 Was aber am häufigsten mit so einem Closure passiert ist, dass er ausgeführt wird. Daher sieht das ganze in Wirklichkeit nochmal anders aus. Der Zeiger im Closure zeigt direkt an den Anfang des Funktionscodes, und der Compiler legt die Tabelle direkt davor. Das ist zwar eine unübliche Mischung von Daten und Code, aber der Compiler darf sowas.
331
332 \begin{center}
333 \begin{tikzpicture}[x=\ux, y=\uy,
334         word/.style={shape=rectangle, draw, minimum width=\ux, minimum height=\uy}
335         ,halfword/.style={shape=rectangle, draw, minimum width=0.5*\ux, minimum height=\uy}
336         ,>=latex]
337 \draw (0,0) rectangle +(1,1) node[midway] (ip) {Info-Pointer}
338     ++(1,0) rectangle +(1,1) node[midway] {Pointer}
339     ++(1,0) rectangle +(1,1) node[midway] {Pointer}
340     ++(1,0) +(0.1,0.4) node {$\cdots$}
341     ++(0.2,0) rectangle +(1,1) node[midway] {Nicht-Pointer}
342     ++(1,0) rectangle +(1,1) node[midway] {Nicht-Pointer}
343     ++(1,0) +(0.1,0.4) node {$\cdots$};
344
345 \begin{scope}[yshift=-0.7cm, xshift=1.2*\ux]
346 \draw
347   (0,0) node[word] {ggf. Konstruktor}
348 ++(0,-1) node[word] {ggf. Stelligkeit}
349 ++(-0.25,-1) node[halfword] {\#ptr} ++(+0.5,0) node[halfword] {\#nptr} ++(-0.25,0)
350 ++(-0.25,-1) node[halfword] {Typ} ++(+0.5,0) node[halfword] {SRT} ++ (-0.25,0)
351 ++(0,-1) node[word,draw=none] (code) {Entry code};
352 \end{scope}
353 \draw[*->] (ip.south) |- (code.west);
354 \draw (code) ++(-0.5,-1) -- ++(0,1.5) -- ++(1,0) -- ++(0,-1.5);
355 \end{tikzpicture}
356 \end{center}
357
358
359 \section{Das Primzahlensieb}
360
361 Falls es die Zeit erlaubt will ich noch einem weiteren Programm bei der Ausführung zuschauen, nämlich der bekannten, sehr eleganten Definition der Primzahlen:
362 \inputhaskell{Sieve.hs}
363 Hier erkennt man schön die immer länger werdende Liste von Thunks, die jeweils für eine Primzahl deren vielfache aus der Liste entfernt:
364
365 \begin{center}
366 \includegraphics[width=0.2\linewidth]{vis-output-sieve.pdf}
367 \end{center}
368
369 \section{Fazit}
370
371 Damit bin ich am Ende meines Vortrages. Wir haben uns die Mühe gemacht, all die vielen komfortablen Abstraktionsschichten, die uns Haskell bereitstellt, beiseite zu schieben und haben einen ungetrübten Blick auf den Speicher geworfen. Wir haben gesehen dass die Daten doch einigermaßen übersichtlich und effizient gespeichert werden. Wir haben auch gesehen, warum \li-Strings-s so teuer sind und wie man eine unendlich lange Liste in wenigen Bytes speichert. Ich hoffe, dass euch dieser Vortrag hilft besser zu verstehen, warum eure Haskell-Programme so laufen wie sie laufen, und zu wissen, wie ihr sie besser laufen lassen könnt.
372
373 \section{Referenzen}
374
375 \begin{itemize}
376 \item Was wir hier gesehen haben ist in der Wissenschaft als \emph{Spineless, tagless G-machine} bekannt. \url{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.3729}
377 \item Das GHC-Wiki beschreibt die aktuelle Implementierung am pragmatischten, insbesondere \url{http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects}.
378 \item Wir haben hier meine Bibliothek ghc-heap-view (\url{http://hackage.haskell.org/package/ghc-heap-view}) und Dennis Felsing’s \li!ghc-vis! (\url{http://felsin9.de/nnis/ghc-vis/}) verwendet.
379 \item Das Video habe ich mit Synfig erstellt. (\url{http://www.synfig.org/})
380 \end{itemize}
381
382
383 \end{document}
384