Fancy GHCi environment
[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 \usepackage{adjustbox}
17
18 \usepackage[pdfauthor={Joachim Breitner},pdftitle={Haskell Bytes},pdfsubject={Eine Führung durch den Hauptspeicher eines Haskell-Programms}]{hyperref}
19 \usepackage{listings}
20 \usepackage{multicol}
21 \usepackage{ragged2e}
22 %\usepackage[para]{footmisc}
23 \usepackage{fourier}
24 \usepackage{microtype}
25 \usepackage{comment}
26
27 \usepackage{tikz}
28 \usetikzlibrary{shapes.geometric}
29 \usetikzlibrary{calc}
30 \usetikzlibrary{shapes.multipart}
31 \usetikzlibrary{arrows}
32
33 \urlstyle{sf}
34
35 \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.}}
36 \title{Haskell Bytes}
37 %\subject{Die Umsetzung von Haskell durch GHC}
38 \subtitle{Eine geführte Tour durch den Hauptspeicher eines Haskell-Programms}
39 \publishers{MRMCD 12\footnote{\url{http://mrmcd.net/}}, Darmstadt}
40 \date{8. September 2012}
41
42
43 \definecolor{light-gray}{gray}{0.95}
44 \lstdefinestyle{basic}{
45         ,columns=flexible
46         ,basewidth={.365em}
47         ,keepspaces=True
48         ,belowskip=0pt
49         ,backgroundcolor=\color{light-gray}
50         ,frame=single
51         ,xleftmargin=2em
52         ,xrightmargin=2em
53         ,basicstyle=\small\sffamily
54         ,stringstyle=\itshape
55 }
56 \lstdefinestyle{shell}{
57         ,style=basic
58         ,basicstyle=\footnotesize\ttfamily
59 }
60 \lstdefinestyle{haskell}{
61         style=basic
62         ,language=Haskell
63         ,literate=
64                 {ö}{{\"o}}1
65                 {ä}{{\"a}}1
66                 {ü}{{\"u}}1
67         ,texcl=true
68         ,showstringspaces=false
69         ,keywords={module,where,open,import,using,renaming,to,data,let,in,with}
70 }
71
72 \newcommand{\mylabel}[1]{\raisebox{2em}[0pt][0pt]{\makebox[0pt][l]{\makebox[\linewidth][r]{\color{gray}{\sffamily #1}\hspace{2em}}}}\ignorespaces}
73 \lstnewenvironment{haskell}{\lstset{style=haskell}}{\mylabel{Haskell}\pagebreak[2]}
74 %\lstnewenvironment{ghci}{\lstset{style=haskell}}{\mylabel{GHCi}\pagebreak[2]}
75 \lstnewenvironment{shell}{\lstset{style=shell}}{\mylabel{Shell}\pagebreak[2]}
76
77 \begingroup
78 \gdef\savedgt{>}%
79 \catcode`\>=\active%
80 \catcode`\^^M=\active%
81 \gdef\foo{%
82 \catcode`\>=\active%
83 \catcode`^^M=\active%
84 \def > ##1^^M{\savedgt{} \li!##1!\par}%
85 \def ^^M{\par}%
86 }%
87 \endgroup
88
89 \newlength{\mylength}
90 \newenvironment{ghci}{
91 \par
92 \setlength{\mylength}{\linewidth}
93 \addtolength{\mylength}{-4em}
94 \strut\hspace{2em}\hspace{-\fboxsep}\begin{adjustbox}{minipage={\mylength},valign=b,margin*=\fboxsep,bgcolor=light-gray,frame}%
95 \begingroup
96 \small\ttfamily%
97 \foo
98 }{
99 \endgroup
100 \end{adjustbox}%\par
101 \adjustbox{lap=-\width}{\color{gray}{\sffamily GHCi}\hspace{\fboxsep}\hspace{\fboxrule}}
102 \par
103 }
104 \newcommand{\inputhaskell}[1]{\lstinputlisting[style=haskell]{#1}\mylabel{Haskell}}
105 \newcommand{\li}{\lstinline[style=haskell]}
106
107
108 \begin{document}
109
110 \maketitle
111
112 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:
113 \begin{haskell}
114 main = do
115     input <- getContents
116     putStrLn $ "I read " ++ show (length input) ++ " bytes."
117     putStrLn $ "The last line is:"
118     putStrLn $ last (lines input)
119 \end{haskell}
120 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!
121
122 Ein anderes, klassiches Beispiel für unerwartetes Laufzeitverhalten ist der folgende Code, der die länge einer Liste zählt:
123 \lstinputlisting[style=haskell,linerange=3-6]{Count.hs}\mylabel{Haskell}
124 Im Interpreter sehen wir, dass der Code unnötig viel Speicher verbraucht und dann mit einem Stack Overflow abbricht:
125 \begin{ghci}
126 *Count> let x = count 0 [0..100000000]
127 *Count> x
128 Just *** Exception: stack overflow
129 \end{ghci}
130
131 Manchmal aber überrascht uns Haskell auch positiv. Wenn wir, wieder beim ersten Programm, die dritte Zeile löschen und
132 \begin{haskell}
133 main = do
134     input <- getContents
135     putStrLn $ "The last line is:"
136     putStrLn $ last (lines input)
137 \end{haskell}
138 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
139
140 \section{Die Akteure}
141
142 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}.
143
144 Bevor wir nun in den Speicher eines Haskell-Programms reinschauen überlegen wir noch, was denn jeweils zu so einer Funktion gespeichert werden soll.
145 \begin{itemize}
146 \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!
147 \item Welcher Konstruktor: Ja, das muss man speichern, zumindest für Typen mit mehreren, etwa bei \li-data Maybe a = Just a | Nothing-.
148 \item Die Parameter des Konstruktors: Natürlich!
149 \item Bei Funktionen: Der Code der Funktion.
150 \item Nicht vergessen bei Funktionen und Thunks: Freie Variablen!
151 \end{itemize}
152
153 \subsection{Konstruktoren}
154
155 Schauen wir mal an was wir vorfinden, wenn wir mit GHCi etwas rumspielen, und fangen mit einer einfachen Zahl an:
156 \begin{ghci}
157 *Utils> let eins = 1 :: Int
158 *Utils> viewClosure eins
159 0x00007f9c7a3337f8: 0x0000000040502608 0x0000000000000001
160 \end{ghci}
161
162 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.
163
164 Wie sieht es mit Zeichen, also Charakters aus?
165 \begin{ghci}
166 *Utils> let zett = 'z'
167 *Utils> viewClosure zett
168 0x00007f9c7a0e8238: 0x0000000040502548 0x000000000000007A
169 \end{ghci}
170 Auch diese benötigen zwei Wörter, also 16 statt einem Byte! 
171
172 Kommen wir nun zu algebraischen Datentypen, und packen \li-eins- in \li-Just-:
173 \begin{ghci}
174 *Utils> let jeins = Just eins
175 *Utils> viewClosure jeins
176 0x00007f9c7b082710: 0x00000000420DC920 0x00007f9c7a3337f8
177 \end{ghci}
178
179 Beachte dass im Wert \li-Just eins- keine Kopie von \li-eins- gespeichert ist, sondern eine Referenz drauf.
180 %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 
181
182 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.
183 \begin{ghci}
184 *Utils> let hallo = "hallo"
185 *Utils> viewListClosures hallo
186 0x00007f9c7ba21fa0: 0x0000000040502668 0x00007F9C7BA21F91 0x00007F9C7BA21F70
187 0x00007f9c7ba21f90/1: 0x0000000040502548 0x0000000000000068
188 0x00007f9c7ba77b18: 0x0000000040502668 0x00007F9C7BA77B09 0x00007F9C7BA77AE8
189 0x00007f9c7a1a9768/1: 0x0000000040502548 0x0000000000000061
190 0x00007f9c7ba405f0: 0x0000000040502668 0x00007F9C7BA405E1 0x00007F9C7BA405C0
191 0x00007f9c7ba405e0/1: 0x0000000040502548 0x000000000000006C
192 0x00007f9c7ba83f38: 0x0000000040502668 0x00007F9C7BA83F29 0x00007F9C7BA83F08
193 0x00007f9c7ba83f28/1: 0x0000000040502548 0x000000000000006C
194 0x00007f9c7ba55a20: 0x0000000040502668 0x00007F9C7BA55A11 0x00007F9C7BA559F0
195 0x00007f9c7a01e840/1: 0x0000000040502548 0x000000000000006F
196 0x0000000040507e70: 0x0000000040502648
197 \end{ghci}
198 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.
199
200 An der Stelle will ich demonstrieren warum man in GHC keinen Zugriff auf die eigentlichen Pointer haben sollte:
201 \begin{ghci}
202 *Utils> System.Mem.performGC
203 *Utils> viewListClosures hallo
204 0x00007f9c7a1510a8: 0x0000000040502668 0x00007F9C7A151389 0x00007F9C7A151372
205 0x00007f9c7a151388/1: 0x0000000040502548 0x0000000000000068
206 0x00007f9c7a151370: 0x0000000040502668 0x00007F9C7A1516F1 0x00007F9C7A1516DA
207 0x00007f9c7a1516f0/1: 0x0000000040502548 0x0000000000000061
208 0x00007f9c7a1516d8: 0x0000000040502668 0x00007F9C7A151AC1 0x00007F9C7A151AAA
209 0x00007f9c7a151ac0/1: 0x0000000040502548 0x000000000000006C
210 0x00007f9c7a151aa8: 0x0000000040502668 0x00007F9C7A151ED9 0x00007F9C7A151EC2
211 0x00007f9c7a151ed8/1: 0x0000000040502548 0x000000000000006C
212 0x00007f9c7a151ec0: 0x0000000040502668 0x00007F9C7A150211 0x0000000040507E71
213 0x00007f9c7a150210/1: 0x0000000040502548 0x000000000000006F
214 0x0000000040507e70: 0x0000000040502648
215 \end{ghci}
216 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.
217 \begin{center}
218 \includegraphics[width=.6\linewidth]{GC.png}
219 \end{center}
220
221 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:
222 \begin{shell}
223 $ ./HelloGC 
224 0x00007f16c0d04270/2: 0x000000000049B1C8 0x00007F16C0D04261 0x00007F16C0D04240
225 0x00007f16c0d04260/1: 0x000000000049B128 0x0000000000000068
226 0x00007f16c0d162b0/2: 0x000000000049B1C8 0x00007F16C0D162A1 0x00007F16C0D16280
227 0x00007f16c0d162a0/1: 0x000000000049B128 0x0000000000000061
228 0x00007f16c0d262b0/2: 0x000000000049B1C8 0x00007F16C0D262A1 0x00007F16C0D26280
229 0x00007f16c0d262a0/1: 0x000000000049B128 0x000000000000006C
230 0x00007f16c0d362b0/2: 0x000000000049B1C8 0x00007F16C0D362A1 0x00007F16C0D36280
231 0x00007f16c0d362a0/1: 0x000000000049B128 0x000000000000006C
232 0x00007f16c0d462b0/2: 0x000000000049B1C8 0x00007F16C0D462A1 0x00007F16C0D46280
233 0x00007f16c0d462a0/1: 0x000000000049B128 0x000000000000006F
234 0x00000000006fb188/1: 0x000000000049B1A8
235 0x00007f16c0dfd4b8/2: 0x000000000049B1C8 0x00000000006FBAD1 0x00007F16C0DFD51A
236 0x00000000006fbad0/1: 0x000000000049B148 0x0000000000000068
237 0x00007f16c0dfd518/2: 0x000000000049B1C8 0x00000000006FBA61 0x00007F16C0DFD552
238 0x00000000006fba60/1: 0x000000000049B148 0x0000000000000061
239 0x00007f16c0dfd550/2: 0x000000000049B1C8 0x00000000006FBB11 0x00007F16C0DFD56A
240 0x00000000006fbb10/1: 0x000000000049B148 0x000000000000006C
241 0x00007f16c0dfd568/2: 0x000000000049B1C8 0x00000000006FBB11 0x00007F16C0DFD582
242 0x00000000006fbb10/1: 0x000000000049B148 0x000000000000006C
243 0x00007f16c0dfd580/2: 0x000000000049B1C8 0x00000000006FBB41 0x00000000006FB189
244 0x00000000006fbb40/1: 0x000000000049B148 0x000000000000006F
245 0x00000000006fb188/1: 0x000000000049B1A8
246 \end{shell}
247 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. 
248
249 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.)
250
251 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.
252
253 \subsection{Funktionen}
254
255 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:
256
257 \inputhaskell{FunClosures.hs}
258 was zu folgender Ausgabe führt:
259 \begin{shell}
260 $ ghc --make FunClosures.hs -O && ./FunClosures  1 2 3
261 0x00000000006f3090/2: 0x0000000000420DD8
262 0x00000000006ef7f0/1: 0x0000000000406408
263 0x00007f73f8d0e880/2
264 0x00007f73f8d10348/1: 0x0000000000406498 0x00007F73F8D0E882
265 \end{shell}
266 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-. 
267
268 \subsection{Thunks}
269
270 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-
271 \begin{haskell}
272 infList f x = f x : infList f x
273 l = infList (+19) 23
274 \end{haskell}
275 mittels
276 \begin{ghci}
277 Prelude InfLists> :script /home/jojo/.cabal/share/ghc-vis-0.1/ghci
278 Prelude Inflists> :vis
279 Prelude Inflists> :switch
280 Prelude Inflists> :view l
281 \end{ghci}
282 und klicken auf dem entstehenden Baum herum. Wichtige Beobachtungen:
283 \begin{itemize}
284 \item Die Liste scheint sich tatsächlich unendlich unendlich abzurollen.
285 \item Der Wert 42 wird jedes mal neu berechnet und neu gespeichert.
286 \end{itemize}
287
288 Schön ist es jetzt auch noch
289 \begin{haskell}
290 l2 = map negate l
291 \end{haskell}
292 anzuschauen und zu beobachten, wie die Auswertung der einen Liste die andere beeinflusst.
293
294 \begin{center}
295 \includegraphics[width=0.4\linewidth]{vis-output1.pdf}
296 \end{center}
297
298 Zum Vergleich nehmen wir diese Funktion für unendliche Listen, die -- semantisch -- das gleiche macht:
299 \begin{haskell}
300 infList2 f x = let l = f x : l in l
301 \end{haskell}
302 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!
303
304 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.
305
306 \begin{center}
307 \includegraphics[width=0.2\linewidth]{vis-output2.pdf}
308 \end{center}
309
310 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: 
311 \begin{ghci}
312 *Count> :script /home/jojo/.cabal/share/ghc-vis-0.1/ghci
313 *Count> :vis
314 *Count> :switch
315 *Count> let x = count 0 [1..5]
316 *Count> :view x
317 \end{ghci}
318 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.
319
320 Besser ist folgender Code:
321 \lstinputlisting[style=haskell,linerange=8-10]{Count.hs}\mylabel{Haskell}
322 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):
323 \begin{ghci}
324 *Count> let x = count2 0 [1..100000000]
325 *Count> x
326 100000000
327 \end{ghci}
328 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.
329
330
331 \section{Der Info-Pointer}
332
333 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:
334
335 \def\ux{2.8cm}\def\uy{0.6cm}
336 \begin{center}
337 \begin{tikzpicture}[x=\ux, y=\uy,
338         word/.style={shape=rectangle, draw, minimum width=\ux, minimum height=\uy}
339         ,halfword/.style={shape=rectangle, draw, minimum width=0.5*\ux, minimum height=\uy}
340         ,>=latex]
341 \draw (0,0) rectangle +(1,1) node[midway] (ip) {Info-Pointer}
342     ++(1,0) rectangle +(1,1) node[midway] {Pointer}
343     ++(1,0) rectangle +(1,1) node[midway] {Pointer}
344     ++(1,0) +(0.1,0.4) node {$\cdots$}
345     ++(0.2,0) rectangle +(1,1) node[midway] {Nicht-Pointer}
346     ++(1,0) rectangle +(1,1) node[midway] {Nicht-Pointer}
347     ++(1,0) +(0.1,0.4) node {$\cdots$};
348
349 \begin{scope}[yshift=-0.7cm, xshift=1.2*\ux]
350 \draw
351   (0,0) node[word] (tbl) {Code-Pointer}
352 ++(-0.25,-1) node[halfword] {\#ptr} ++(+0.5,0) node[halfword] {\#nptr} ++(-0.25,0)
353 ++(-0.25,-1) node[halfword] {Typ} ++(+0.5,0) node[halfword] {SRT} ++ (-0.25,0)
354 ++(0,-1) node[word] {ggf. Konstruktor}
355 ++(0,-1) node[word] {ggf. Stelligkeit};
356 \end{scope}
357 \draw[*->] (ip.south) |- (tbl.west);
358 \draw[*->] (tbl.east) -- ++(1.5cm,0) node[right] (code) {Entry code};
359 \draw (code) ++(-0.5,-1) -- ++(0,1.5) -- ++(1,0) -- ++(0,-1.5);
360 \end{tikzpicture}
361 \end{center}
362
363 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.
364
365 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.
366
367 \begin{center}
368 \begin{tikzpicture}[x=\ux, y=\uy,
369         word/.style={shape=rectangle, draw, minimum width=\ux, minimum height=\uy}
370         ,halfword/.style={shape=rectangle, draw, minimum width=0.5*\ux, minimum height=\uy}
371         ,>=latex]
372 \draw (0,0) rectangle +(1,1) node[midway] (ip) {Info-Pointer}
373     ++(1,0) rectangle +(1,1) node[midway] {Pointer}
374     ++(1,0) rectangle +(1,1) node[midway] {Pointer}
375     ++(1,0) +(0.1,0.4) node {$\cdots$}
376     ++(0.2,0) rectangle +(1,1) node[midway] {Nicht-Pointer}
377     ++(1,0) rectangle +(1,1) node[midway] {Nicht-Pointer}
378     ++(1,0) +(0.1,0.4) node {$\cdots$};
379
380 \begin{scope}[yshift=-0.7cm, xshift=1.2*\ux]
381 \draw
382   (0,0) node[word] {ggf. Konstruktor}
383 ++(0,-1) node[word] {ggf. Stelligkeit}
384 ++(-0.25,-1) node[halfword] {\#ptr} ++(+0.5,0) node[halfword] {\#nptr} ++(-0.25,0)
385 ++(-0.25,-1) node[halfword] {Typ} ++(+0.5,0) node[halfword] {SRT} ++ (-0.25,0)
386 ++(0,-1) node[word,draw=none] (code) {Entry code};
387 \end{scope}
388 \draw[*->] (ip.south) |- (code.west);
389 \draw (code) ++(-0.5,-1) -- ++(0,1.5) -- ++(1,0) -- ++(0,-1.5);
390 \end{tikzpicture}
391 \end{center}
392
393
394 \section{Das Primzahlensieb}
395
396 Falls es die Zeit erlaubt will ich noch einem weiteren Programm bei der Ausführung zuschauen, nämlich dieser bekannten, sehr eleganten Definition der Primzahlen:
397 \inputhaskell{Sieve.hs}
398 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:
399
400 \begin{center}
401 \includegraphics[width=0.2\linewidth]{vis-output-sieve.pdf}
402 \end{center}
403
404 \section{Fazit}
405
406 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.
407
408 \section{Referenzen}
409
410 \begin{itemize}
411 \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}
412 \item Das GHC-Wiki beschreibt die aktuelle Implementierung am pragmatischten, insbesondere \url{http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects}.
413 \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.
414 \item Das Video habe ich mit Synfig erstellt. (\url{http://www.synfig.org/})
415 \end{itemize}
416
417
418 \end{document}
419