Initial check-in
authorJoachim Breitner <mail@joachim-breitner.de>
Mon, 3 Sep 2012 12:59:16 +0000 (12:59 +0000)
committerJoachim Breitner <mail@joachim-breitner.de>
Mon, 3 Sep 2012 12:59:16 +0000 (12:59 +0000)
FunClosures.hs [new file with mode: 0644]
GC.sifz [new file with mode: 0644]
GC.webm [new file with mode: 0644]
HaskellBytes.tex [new file with mode: 0644]
HelloGC.hs [new file with mode: 0644]
InfLists.hs [new file with mode: 0644]
SmallChar.hs [new file with mode: 0644]
Utils.hs [new file with mode: 0644]
example.hs [new file with mode: 0644]
string.hs [new file with mode: 0644]

diff --git a/FunClosures.hs b/FunClosures.hs
new file mode 100644 (file)
index 0000000..6c9649e
--- /dev/null
@@ -0,0 +1,13 @@
+import System.Environment
+import GHC.HeapView
+import Utils
+
+main = do
+    let f = map
+    viewClosure f
+    let g toB = toB || not toB
+    viewClosure g
+    a <- getArgs
+    let h = (++ a)
+    print (asBox a)
+    viewClosure h
diff --git a/GC.sifz b/GC.sifz
new file mode 100644 (file)
index 0000000..bc5f70b
Binary files /dev/null and b/GC.sifz differ
diff --git a/GC.webm b/GC.webm
new file mode 100644 (file)
index 0000000..e753180
Binary files /dev/null and b/GC.webm differ
diff --git a/HaskellBytes.tex b/HaskellBytes.tex
new file mode 100644 (file)
index 0000000..02452e2
--- /dev/null
@@ -0,0 +1,271 @@
+\documentclass[11pt,DIV=12,parskip=half,headings=normal,abstract]{scrartcl}
+
+\usepackage[T3,T1]{fontenc}
+\usepackage[utf8]{inputenc}
+\usepackage[ngerman]{babel}
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage[standard]{ntheorem}
+\usepackage{amscd}
+\usepackage{mathtools}
+\usepackage{stmaryrd}
+\usepackage{faktor}
+\usepackage{enumerate}
+\usepackage{wrapfig}
+\usepackage[safe]{tipa} % for \textlambda
+
+\usepackage[pdfauthor={Joachim Breitner},pdftitle={Haskell Bytes},pdfsubject={Eine Führung durch den Hauptspeicher eines Haskell-Programms}]{hyperref}
+\usepackage{listings}
+\usepackage{multicol}
+\usepackage{ragged2e}
+%\usepackage[para]{footmisc}
+\usepackage{fourier}
+\usepackage{microtype}
+\usepackage{comment}
+
+\usepackage{tikz}
+
+\urlstyle{sf}
+
+\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.}}
+\title{Haskell Bytes}
+%\subject{Die Umsetzung von Haskell durch GHC}
+\subtitle{Eine Führung durch den Hauptspeicher eines Haskell-Programms}
+\publishers{MRMCD 12\footnote{\url{http://mrmcd.net/}}, Darmstadt}
+\date{8. September 2012}
+
+
+\definecolor{light-gray}{gray}{0.95}
+\lstdefinestyle{haskell}{
+       language=Haskell
+       ,literate=
+               {ö}{{\"o}}1
+               {ä}{{\"a}}1
+                {ü}{{\"u}}1
+                {ℕ}{{$\mathbb N$}}1
+                {≤}{{$\le$}}1
+                {-}{{\text-}}1
+                {≡}{{$\equiv$}}1
+                {≢}{{$\not\equiv$}}1
+                {∎}{{$\blacksquare$}}1
+                {□}{{$\square$}}1
+                {⟨}{{$\langle$}}1
+                {⟩}{{$\rangle$}}1
+                {→}{{$\rightarrow$}}1
+                {⇒}{{$\Rightarrow$}}1
+                {∸}{{$\stackrel{\bullet}{-}$}}1
+                {∷}{{$::$}}1
+                {∣}{{$\mid$}}1
+                {¬}{{$\neg$}}1
+                {∀}{{$\forall$}}1
+                {⊥}{{$\bot$}}1
+                {λ}{{\textlambda}}1
+                {′}{{'}}1
+        ,columns=flexible
+        ,basewidth={.365em}
+        ,keepspaces=True
+        ,texcl=true
+        ,basicstyle=\small\sffamily
+        ,stringstyle=\itshape
+        ,showstringspaces=false
+        ,keywords={module,where,open,import,using,renaming,to,data,let,in,with}
+       ,belowskip=0pt
+       ,backgroundcolor=\color{light-gray}
+       ,frame=single
+       ,xleftmargin=2em
+       ,xrightmargin=2em
+}
+\lstnewenvironment{haskell}{\lstset{style=haskell}}{}
+\lstnewenvironment{ghci}{\lstset{style=haskell}}{}
+\lstnewenvironment{shell}{\lstset{style=haskell}}{}
+\newcommand{\li}{\lstinline[style=haskell]}
+
+
+\begin{document}
+
+\maketitle
+
+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:
+\begin{haskell}
+main = do
+    input <- getContents
+    putStrLn $ "I read " ++ show (length input) ++ " bytes."
+    putStrLn $ "The last line is:"
+    putStrLn $ last (lines input)
+\end{haskell}
+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!
+
+Manchmal aber überrascht uns Haskell auch positiv. Wenn wir die dritte Zeile löschen und
+\begin{haskell}
+main = do
+    input <- getContents
+    putStrLn $ "The last line is:"
+    putStrLn $ last (lines input)
+\end{haskell}
+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
+
+\section{Die Akteure}
+
+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}.
+
+Bevor wir nun in den Speicher eines Haskell-Programms reinschauen überlegen wir noch, was denn jeweils zu so einer Funktion gespeichert werden soll.
+\begin{itemize}
+\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!
+\item Welcher Konstruktor: Ja, das muss man speichern, zumindest für Typen mit mehreren, etwa bei \li-data Maybe a = Just a | Nothing-.
+\item Die Parameter des Konstruktors: Natürlich!
+\item Bei Funktionen: Der Code der Funktion.
+\item Nicht vergessen bei Funktionen und Thunks: Freie Variablen!
+\end{itemize}
+
+\subsection{Konstruktoren}
+
+Schauen wir mal an was wir vorfinden, wenn wir mit GHCi etwas rumspielen, und fangen mit einer einfachen Zahl an:
+\begin{ghci}
+*Utils> let eins = 1 :: Int
+*Utils> viewClosure eins
+0x00007f9c7a3337f8: 0x0000000040502608 0x0000000000000001
+\end{ghci}
+
+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.
+
+Wie sieht es mit Zeichen, also Charakters aus?
+\begin{ghci}
+*Utils> let zett = 'z'
+*Utils> viewClosure zett
+0x00007f9c7a0e8238: 0x0000000040502548 0x000000000000007A
+\end{ghci}
+Auch diese benötigen zwei Wörter, also 16 statt einem Byte! 
+
+Kommen wir nun zu algebraischen Datentypen, und packen \li-eins- in \li-Just-:
+\begin{ghci}
+*Utils> let jeins = Just eins
+*Utils> viewClosure jeins
+0x00007f9c7b082710: 0x00000000420DC920 0x00007f9c7a3337f8
+\end{ghci}
+
+Beachte dass im Wert \li-Just eins- keine Kopie von \li-eins- gespeichert ist, sondern eine Referenz drauf.
+%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 
+
+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.
+\begin{ghci}
+*Utils> let hallo = "hallo"
+*Utils> viewListClosures hallo
+0x00007f9c7ba21fa0: 0x0000000040502668 0x00007F9C7BA21F91 0x00007F9C7BA21F70
+0x00007f9c7ba21f90/1: 0x0000000040502548 0x0000000000000068
+0x00007f9c7ba77b18: 0x0000000040502668 0x00007F9C7BA77B09 0x00007F9C7BA77AE8
+0x00007f9c7a1a9768/1: 0x0000000040502548 0x0000000000000061
+0x00007f9c7ba405f0: 0x0000000040502668 0x00007F9C7BA405E1 0x00007F9C7BA405C0
+0x00007f9c7ba405e0/1: 0x0000000040502548 0x000000000000006C
+0x00007f9c7ba83f38: 0x0000000040502668 0x00007F9C7BA83F29 0x00007F9C7BA83F08
+0x00007f9c7ba83f28/1: 0x0000000040502548 0x000000000000006C
+0x00007f9c7ba55a20: 0x0000000040502668 0x00007F9C7BA55A11 0x00007F9C7BA559F0
+0x00007f9c7a01e840/1: 0x0000000040502548 0x000000000000006F
+0x0000000040507e70: 0x0000000040502648
+\end{ghci}
+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.
+
+An der Stelle will ich demonstrieren warum man in GHC keinen Zugriff auf die eigentlichen Pointer haben sollte:
+\begin{ghci}
+*Utils> System.Mem.performGC
+*Utils> viewListClosures hallo
+0x00007f9c7a1510a8: 0x0000000040502668 0x00007F9C7A151389 0x00007F9C7A151372
+0x00007f9c7a151388/1: 0x0000000040502548 0x0000000000000068
+0x00007f9c7a151370: 0x0000000040502668 0x00007F9C7A1516F1 0x00007F9C7A1516DA
+0x00007f9c7a1516f0/1: 0x0000000040502548 0x0000000000000061
+0x00007f9c7a1516d8: 0x0000000040502668 0x00007F9C7A151AC1 0x00007F9C7A151AAA
+0x00007f9c7a151ac0/1: 0x0000000040502548 0x000000000000006C
+0x00007f9c7a151aa8: 0x0000000040502668 0x00007F9C7A151ED9 0x00007F9C7A151EC2
+0x00007f9c7a151ed8/1: 0x0000000040502548 0x000000000000006C
+0x00007f9c7a151ec0: 0x0000000040502668 0x00007F9C7A150211 0x0000000040507E71
+0x00007f9c7a150210/1: 0x0000000040502548 0x000000000000006F
+0x0000000040507e70: 0x0000000040502648
+\end{ghci}
+
+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.
+
+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:
+\begin{shell}
+$ ./HelloGC 
+0x00007f16c0d04270/2: 0x000000000049B1C8 0x00007F16C0D04261 0x00007F16C0D04240
+0x00007f16c0d04260/1: 0x000000000049B128 0x0000000000000068
+0x00007f16c0d162b0/2: 0x000000000049B1C8 0x00007F16C0D162A1 0x00007F16C0D16280
+0x00007f16c0d162a0/1: 0x000000000049B128 0x0000000000000061
+0x00007f16c0d262b0/2: 0x000000000049B1C8 0x00007F16C0D262A1 0x00007F16C0D26280
+0x00007f16c0d262a0/1: 0x000000000049B128 0x000000000000006C
+0x00007f16c0d362b0/2: 0x000000000049B1C8 0x00007F16C0D362A1 0x00007F16C0D36280
+0x00007f16c0d362a0/1: 0x000000000049B128 0x000000000000006C
+0x00007f16c0d462b0/2: 0x000000000049B1C8 0x00007F16C0D462A1 0x00007F16C0D46280
+0x00007f16c0d462a0/1: 0x000000000049B128 0x000000000000006F
+0x00000000006fb188/1: 0x000000000049B1A8
+0x00007f16c0dfd4b8/2: 0x000000000049B1C8 0x00000000006FBAD1 0x00007F16C0DFD51A
+0x00000000006fbad0/1: 0x000000000049B148 0x0000000000000068
+0x00007f16c0dfd518/2: 0x000000000049B1C8 0x00000000006FBA61 0x00007F16C0DFD552
+0x00000000006fba60/1: 0x000000000049B148 0x0000000000000061
+0x00007f16c0dfd550/2: 0x000000000049B1C8 0x00000000006FBB11 0x00007F16C0DFD56A
+0x00000000006fbb10/1: 0x000000000049B148 0x000000000000006C
+0x00007f16c0dfd568/2: 0x000000000049B1C8 0x00000000006FBB11 0x00007F16C0DFD582
+0x00000000006fbb10/1: 0x000000000049B148 0x000000000000006C
+0x00007f16c0dfd580/2: 0x000000000049B1C8 0x00000000006FBB41 0x00000000006FB189
+0x00000000006fbb40/1: 0x000000000049B148 0x000000000000006F
+0x00000000006fb188/1: 0x000000000049B1A8
+\end{shell}
+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. 
+
+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.)
+
+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.
+
+\subsection{Funktionen}
+
+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:
+
+\lstinputlisting[style=haskell]{FunClosures.hs}
+was zu folgender Ausgabe führt:
+\begin{shell}
+$ ghc --make FunClosures.hs -O && ./FunClosures  1 2 3
+0x00000000006f3090/2: 0x0000000000420DD8
+0x00000000006ef7f0/1: 0x0000000000406408
+0x00007f73f8d0e880/2
+0x00007f73f8d10348/1: 0x0000000000406498 0x00007F73F8D0E882
+\end{shell}
+
+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-. 
+
+\subsection{Thunks}
+
+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-
+\begin{haskell}
+infList f x = f x : infList f x
+l = infList (+19) 23
+\end{haskell}
+mittels
+\begin{ghci}
+Prelude Inflists> :script /home/jojo/dokumente/Uni/WM/arbeiten/lazy-vis/vis/ghci
+Prelude Inflists> :vis
+Prelude Inflists> :switch
+Prelude Inflists> :view l
+\end{ghci}
+und klicken auf dem entstehenden Baum herum. Wichtige Beobachtungen:
+\begin{itemize}
+\item Die Liste scheint sich tatsächlich unendlich unendlich abzurollen.
+\item Der Wert 42 wird jedes mal neu berechnet und neu gespeichert.
+\end{itemize}
+
+Schön ist es jetzt auch noch
+\begin{haskell}
+l2 = map negate l
+\end{haskell}
+anzuschauen und zu beobachten, wie die Auswertung der einen Liste die andere beeinflusst.
+
+Zum Vergleich nehmen wir diese Funktion für unendliche Listen, die -- semantisch -- das gleiche macht:
+\begin{haskell}
+infList2 f x = let l = f x : l in l
+\end{haskell}
+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!
+
+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.
+
+
+
+\end{document}
+
diff --git a/HelloGC.hs b/HelloGC.hs
new file mode 100644 (file)
index 0000000..8b8d206
--- /dev/null
@@ -0,0 +1,11 @@
+import GHC.HeapView
+import Text.Printf
+import Data.List
+import System.Mem
+import Utils
+
+main = do
+    let hallo = "hallo"
+    viewListClosures hallo
+    performGC
+    viewListClosures hallo
diff --git a/InfLists.hs b/InfLists.hs
new file mode 100644 (file)
index 0000000..322a113
--- /dev/null
@@ -0,0 +1,8 @@
+module InfLists where
+
+infList f x = f x : infList f x
+
+infList2 f x = let l = f x : l in l
+
+l = infList (+19) (23::Int)
+l2 = infList2 (+19) (23::Int)
diff --git a/SmallChar.hs b/SmallChar.hs
new file mode 100644 (file)
index 0000000..1bf07fa
--- /dev/null
@@ -0,0 +1,8 @@
+import GHC.HeapView
+import System.Mem
+
+main = do
+    let hallo = "hallo"
+    mapM_ (\x -> putStrLn $ show x ++ ": " ++ show (asBox x)) hallo
+    performGC
+    mapM_ (\x -> putStrLn $ show x ++ ": " ++ show (asBox x)) hallo
diff --git a/Utils.hs b/Utils.hs
new file mode 100644 (file)
index 0000000..d03470e
--- /dev/null
+++ b/Utils.hs
@@ -0,0 +1,18 @@
+module Utils where
+import GHC.HeapView
+import Text.Printf
+import Data.List
+import System.Mem
+
+viewClosure :: a -> IO ()
+viewClosure a = do
+    (_,w,_) <- getClosureRaw a
+    putStrLn $ show (asBox a) ++ ": " ++ (concat $ intersperse " " $ map (printf "0x%016X") w)
+
+viewListClosures :: [a] -> IO ()
+viewListClosures l@(x:xs) = do
+    viewClosure l
+    viewClosure x
+    viewListClosures xs
+viewListClosures l = do
+    viewClosure l
diff --git a/example.hs b/example.hs
new file mode 100644 (file)
index 0000000..63777e3
--- /dev/null
@@ -0,0 +1,6 @@
+infList f x = f x : infList f x
+
+infList2 f x = let l = f x : l in l
+
+l1 = infList (+19) 23
+l2 = infList2 (+19) 23
diff --git a/string.hs b/string.hs
new file mode 100644 (file)
index 0000000..9562cc1
--- /dev/null
+++ b/string.hs
@@ -0,0 +1,5 @@
+main = do
+    input <- getContents
+--    putStrLn $ "I read " ++ show (length input) ++ " bytes."
+    putStrLn $ "The last line is:"
+    putStrLn $ last (lines input)