Last week, David Terei lectured about
the compilation pipeline which isresponsible for producing the executablebinaries of the Haskell code you
actually want to run.

Today, we are going to look at an
important piece of C code (blasphemy!)
which is linked against every Haskell
program, and implements some
important functionality (without
which, your code would not runat all!)But ﬁrst, an important question to answer: why should anyone care about a giant blobof C code that your Haskell code looks like? Isn't simply an embarrassing corner of Haskell
that we should pretend doesn't exist?

One reason to study the operation of the RTS is that how
the runtime system is implemented can have a very big
impact on how your code performs. For example, this SO
question wonders why MutableArrays become slower as
you allocate more of them. By the end of the talk, you'll
understand why this is not such an easy bug to ﬁx, and what
the reasons for it are!

Another reason to study the RTS is to understandthe performance characteristics of unusual
language features provided by the language,
such as Haskell's green threads.

In theory, only the semantics of Haskell's multithreading mechanisms should matter, but inpractice, the eﬀiciency and underlying implementation are important factors.

Perhaps after this class you will go work for some big corporation, and never write any more
Haskell. But most high-level languages you will write code for are going to are going to havesome runtime system of some sort, and many of the lessons from GHC's runtime are transferable
to those settings. I like to think that GHC's runtime is actually far more understandable thanmany of these others (we believe in documentation!)

So, this lecture could just be a giant fact dump
about the GHC runtime system, but that would
be pretty boring. While I am going to talk aboutsome of the nuts and bolts of GHC's runtime, I
am also going to try to highlight some "bright ideas"
which come from being the runtime for a purely
functional, lazy language. What does this buy you?
A lot, it turns out!

Let's dive right in. Here's a diagram from the GHC Trac which describes the main "architecture"of the runtime. To summarize, the runtime system is a blob of code that interfaces between
C client code (sometimes trivial, but you can call into Haskell from C) and the actual compiled
Haskell code.

There is a lot of functionality that the RTS packs,
let's go through a few of them.

The storage manager manages the memory used by a Haskell program; most importantly
it includes the garbage collector which cleans up unused memory.

The scheduler is responsible for actually running Haskell code, and multiplexing between
Haskell's green threads and managing multicore Haskell.

When running GHCi, GHC typechecks and translates Haskell code into a bytecode format.
This bytecode format is then interpreted by the RTS. The RTS also does the work ofswitching between compiled code and bytecode.
The RTS sports a homegrown linker, used to load objects of compiled code at runtime.
Uniquely, we can also load objects that were *statically* compiled (w/o -fPIC) by linking
them at load-time. I hear Facebook uses this in Sigma.
A chunk of RTS code is devoted to the implementation of software transactional
memory, a compositional concurrency mechanism.
The RTS, esp. the GC, has code to dump
proﬁling information when you ask
for heap usage, e.g. +RTS -h

In this talk, we're going to focus on the storage
manager and the scheduler, as they are by far themost important components of the RTS. Every Haskell
program exercises them!

Here's the agenda

If you are going to GC in a real world system, then there is basically one absolutely mandatory
performance optimization you have to apply: generational collection. You've probably heard
about it before, but the generational hypothesis states that most objects die young.

This is especially true in pure functional languages like Haskell, where we do very little
mutating a lot of allocating new objects when we do computation. (How else are you going
to compute with immutable objects?!)

Just to make sure, here's a simple example of copying
garbage collection.

The more garbage you have, the faster GC runs.

Roughly, you can think of copying GC as a process which continually cycles between
evacuating and scavenging objects.

With this knowledge in hand, we can explain how generational copying collection works. Let'stake the same picture as last time, but reﬁne our view of the to spaces so that there are now
to regions of memory: the nursery (into which new objects are allocated), and the ﬁrst
generation.

The diﬀerence now is that when we do copying collection,
we don't move objects into the nursery: instead, we *tenure*them into the ﬁrst generation.

In generational garbage collection, we maintain an important invariant, which is that pointers
only ever go from the nursery to the ﬁrst generation, and not vice versa. It's easy to seethat this invariant is upheld if all objects in your system are immutable (+1 for Haskell!)If this invariant is maintained, then we can do a partial garbage collection by only scanningover things in the nursery, and assuming that the ﬁrst generation is live. Such a garbage
collection is called a "minor" garbage collection. Then, less frequently, we do a majorcollection involving all generations to free up garbage from the last generation.

The key points.

Having contiguous memory to allocate from is a big deal:
it means that you can perform allocations extremely
eﬀiciently. To allocate in Haskell, you only need to do anaddition and a compare.

mk_exit()entry:
Hp = Hp + 16;
if (Hp > HpLim) goto gc;
v::I64 = I64[R1] + 1;

I64[Hp - 8] = GHC_Types_I_con_info;
I64[Hp + 0] = v::I64;
R1 = Hp;
Sp = Sp + 8;
jump (I64[Sp + 0]) ();gc: HpAlloc = 16;
jump stg_gc_enter_1 ();}I promised you I would talk about the unique beneﬁts we get for writing an RTS
for Haskell code, and now's the time. I'm going to talk how Haskell's purity canbe used to good eﬀect.

To talk about write barriers, we have to ﬁrst go back to our picture of generations in
the heap, and recall the invariant we imposed, which is that pointers are only allowed to
ﬂow from the nursery to the ﬁrst generation, and not vice versa.

When mutation comes into the picture, there's a problem: we can mutate a pointer inan old generation to point to an object in the nursery.

If we perform a minor garbage collection, we may
wrongly conclude that an object is dead, and clear it out

At which point we'll get a
segfault if we try to follow
the mutated pointer.

The canonical ﬁx for this in any generational garbage
collection is introducing what's called a "mutable set",
which tracks the objects which (may) have referencesfrom older generations, so that they can be preservedon minor GCs.

There is a big design space in how to build your mutable sets, with diﬀering trade oﬀs.
If garbage collection is black magic, the design of your mutable set mechanism probably
serves as the bulk of the problem.

For example, if you're Java, your programmers are modifying pointers on the heap
ALL THE TIME, and you really, really, really need to make sure adding something to
the mutable set is as fast as possible. So if you look at, say, the JVM, there are
sophisticated card marking schemes to minimize the number of extra instructions
that need to be done when you mutate a pointer.

Haskell doesn't have manyof these optimizations (simplifying
its GC and code generation)...
and, to a large extent,
it doesn't need them!

Idiomatic Haskell code doesn't mutate. Most executing code is computing or
allocating memory. This means that slow mutable references are less of a "big deal."

Perhaps this is not a good excuse, but IORefs are already pretty sure, because theircurrent implementation imposes a mandatory indirection. "You didn't want to usethem anyway."

Now, it is patently not true that Haskell code does not, under the hood, do mutation:in fact, we do a lot of mutation, updating thunks with their actual computed values.
But there's a trick we can play in this case.

Once we evaluate a thunk, we mutate it to point to the true value precisely once. After thispoint, it is immutable.

Since it is immutable, result cannot possibly become dead until ind becomes dead. So, although
we must add result to the mutable set, upon the next GC, we can just immediately promote itto the proper generation.

Haskell programs spend a lot of time garbage collecting,and while running the GC in parallel with themutators in the program is a hard problem, we canparallelize GC. The basic idea is that the scavenging
process (that's where we process objects which
are known to be live to pull in the things that theypoint to) can be parallelized.

Now, here's a problem. Suppose that you have two threads busily munching away on
their live sets, and they accidentally end up processing two pointers which point to thesame object.

In an ideal world, only one of the threads would actually evacuate the object, and the otherthread would update its pointer to point to its sole copy. Unfortunately, to do this, we'dhave to add synchronization here. That's a BIG DEAL; most accesses to the heap here
have no races and we really don't want to pay the cost of synchronization.

If A is an immutable object, there's aneasy answer: just let the two threads race,and end up with duplicates of the object!
After all, you can't observe the diﬀerence.

By the way, the problem with this was each mutable array is unconditionallyadded to the mutable list, so GC time was getting worse and worse.

For the second part of this lecture, I want to talk about the scheduler.

In case your ﬁnal project doesn't involve any concurrency, it's worth brieﬂy recapping
the user visible interface for threads.

The scheduler mediates the loop between running Haskell code, and getting kickedback to the RTS (where we might run some other Haskell code, or GC, etc...)mk_exit()
entry:
Hp = Hp + 16;
if (Hp > HpLim) goto gc;
v::I64 = I64[R1] + 1;
I64[Hp - 8] = GHC_Types_I_con_info;
I64[Hp + 0] = v::I64;
R1 = Hp;
Sp = Sp + 8;
jump (I64[Sp + 0]) ();gc: HpAlloc = 16;
jump stg_gc_enter_1 ();}So, what is a thread anyway? Very simply, a thread is just anotherheap object! There are a number of metadata associated witha thread, but the most important data is the stack (whichis also heap allocated.) GHC uses segmented stacks, so
if you run out of space in one stack it can just allocate
another stack and link them up.

In a single-threaded Haskell program, these TSO objects are managed by a thread queue.

The lifecycle of the scheduler loop
is we pop a TSO oﬀ the queue andstart running it. Eventually, itgets preempted (either by runningout of memory, getting ﬂaggedby the timer, or blocking) in whichcase we pop out and run the GC orhead to the next thread queue.

Multithreaded operation simply involves allocating one of these schedule loops
to each operating system core you want to run. We refer to a scheduler loop as aHEC.

A useful interpretation of HECs
is that they are locks: a CPU
core can take out a lock on a HEC
in which case no other cores canuse it.

Because garbage collection cannot run
concurrently with Haskell code, the GC
process takes out locks on all HECs toensure they
are not running.

One problem with running multiple scheduler loops
is that their respective event queues can get
unbalanced.

If a core runs out of work to do, it releases
the HEC and goes to sleep.

Every time we come around the schedule loop,a core does a quick check to see if there
are any free HECs. If there are, it snarfs themup, and then distributes some of its own work tothose queues. No heavy synchronization necessary!

This scheme is notvery fair, and you
won't get very good
latency guarantees fromit, but it is great forthroughput.

Here's how bound threads are implemented withHECs.

You want to avoid runningordinary TSOs on boundthreads, since they are the ONLY
thread that can service TSOs
bound to that thread.

Let's talk about how MVars are implemented.

MVars essentially contian another thread queue,the "blocked on this MVar" thread queue. When you block on anMVar, a TSO is removed from the main run queue and put on theMVar queue.

http://ezyang.com/jfp-ghc-rts-draft.pdf