Well, thank you all, thank you everybody for coming.
This is a talk about whip it, which is a garbage collector library, which I've been working
on as a potential and hopeful replacement for the garbage collector library used in Gile.
And in this talk, I have one big part, and one medium part, and one tiny part.
The big part is the big idea, which I try to explain what's going on with this thing.
And then we're going to look a bit of what do we win effectively, like what changes in
Gile and potentially other systems by switching to whip it, and then some forward-looking statements.
So, starting off with a big idea, it's kind of like I said in the top title, whip it is a
practical memory management upgrade, so memory manager, that's upgrade, for Gile and beyond.
And we're going to break this down and kind of keep repeating it and looking into the individual
parts. And so, first of all, it is a memory manager, meaning it is a garbage collector,
it is something that takes care of allocating and reclaiming memory in your program.
And ideally, it preserves a property that you never reference memory that's unused.
You eliminate use after free bugs by using a garbage collector system, and it efficiently reclaims memory,
so it keeps the system fast. But before we go in, I like to give a little bit of texture.
Like when you go into a store and you want to touch something and see how it feels, you know.
We're going to touch the API a little bit and see what it means to embed
whip it into our programs. So, I just have like three slides here. This is a minimal
get up and running with whip it. It's a tiny C library that goes in your source stream.
It's not something you dynamically link to. There's sort of, we're declaring our general
some parameters as GC and it function. But notably, I want to say that we declare a heap type,
which is opaque to the user, and a mutator type. Every thread has a mutator. Every
part of your program that allocates has a pointer on a mutator. And when you create a new thread,
you create a new mutator from your heap. And there's a opaque set of options that
actually parses parameters for the GC from like a command line or an environment variable or
something like this. And we can also collect statistics, have a set of callbacks, that the
garbage sector will invoke when it starts collection. So you can do histograms and things like this.
So once you've called GC in it, you've made your heap. You now have an initialized heap
and mutator, and then you can allocate, and you allocate by passing in the mutator with the
size. And of course, it returns a voice star because it's a C. It's a couple of the deeper options.
For example, here we can allocate some options and then set some values. In this case,
we'll just set some things from the environment. It's my analogy to control the parallelism of
the mutator or the heap size. The growth policy, or you can have it fixed, or you can allow
to grow, or you dynamically increase it when your mutators allocating more, and then try to shrink
the heap when it's reached a steady state. The embedded actually provides a definition of how do you
enumerate the edges that point into the graph of live objects. So this struck GC mutator roots
is actually provided by the embedded, meaning the guyel, in this case, instead of whip it. And
it's a guyel who attaches roots to a particular mutator, and then the collector will be able to
trace those. We'll see that in a minute. And additionally, if you have a generational collector
configuration, you need to have right barriers. Right barriers are tiny bits of code that run
when you mutate a field in an object that help the garbage collector keep its internal accounting
of, for example, if it's trying to partition objects into two sets, and you mutate one of the
edges, it might need to move an object into one set or into another set. Whip it is generally
a cooperative safe point system, so the mutator will have to every allocation is a potential
garbage collection point, but if you go through a long period without allocating, you might need
to emit a safe point, and all of these have like fast paths and slow paths, and the fast
paths in the inline and such. And for some collectors, you might need to like pin an object.
That's a general shape of the API. And then on the embedded side, which is typically not something
users have to do so much, but it is for each embedding, you need to implement the kind of
the hooks into how to trace the graph essentially. So if you get an object, how do you
the better implements a GC trace object function only one of them for the whole program,
that needs to be able to trace any kind of object, so you need to be able to
introspect somehow on this object, and that is up to the host. The garbage collector does not
impose any restriction or requirement on the representation of objects as
purely in better concern, and you call a visit function for each field, essentially on it,
passing some data, the usual thing. Same for how do you trace and mutate the roots?
And this leaves it completely up to the embedded as to whether you have handles, stack maps,
what your strategy is for tracking roots, and making it possible for the collector to
enumerate all the edges into the graph. That's all the code that I'm actually going to show in this
presentation. So it is a memory manager, has a general feel, it slots into your source
tree, and I'm designing it with a particular use case in mine, which is Gile. Gile is a very old,
it's like what 33, 2, could be 40 years old depending on how you count it. And it has a garbage
collector that is the boom, Denver's Weiser garbage collector, a conservative garbage collector,
works very well, but it's old, and there are better things to do now. And there are things we
would like that the boom collector does not give us. We would like to be able to do allocation,
like bump pointer allocation instead of previous allocation. We would like to have some features
that are impossible to implement in the boom collector, like a femrons. We would like to have
keep growth and shrinking. We would like to have more control over the overall size of the heap,
more visibility into the dynamics of a program and a better and a heap usage,
or to be able to control things a bit better. And we would also like to be able to
experiment with different collector algorithms, actually. There are a few different algorithms out there
and a few different ways you can compose spaces. And there's no global optimum here. And so
it may be that an embedded needs to choose a particular allocator for a particular workload. And that's
that's how it should be. And with it, this choice is done in compile time, because we want to compile
time specialization of the collector to the embedded and of the embedded to the particular collector
configuration. It's not an dynamic thing like in Java, that would be that would essentially require
jit compilation for good performance and have more warm up and such. This is a different point
of the design space. So as something for a guy, we would like all of these things, but we have
to be able to get there from where we are. And where we are is a funny place. We still have
a fair amount of C code. We still have a lot of effectively. We don't explicitly add each
route, each reference from like a local variable that points to a garbage collected object. We
don't put them anywhere. They're just on the stack. And we rely on the boom collector to essentially
look at each word on the stack and see if it might point to an object. We actually support this
use case. In an effort to provide a path from where we are to where we would like to be. And
we're going to be evaluating, like whether this is a useful strategy to keep or whether we should
move off to what's called precise routing, which is a possibility, but we don't look at
about that later. So the idea is that whip it is like a load bearing abstraction.
But because it's in the load bearing part of this abstraction is the API. And the fact that it's
supported by this load bearing point allows us to pivot. So if in gal we switch to whip it,
we can start with behavior that's very close to what the current collector does. And over time,
we can change things to enable different configurations and more performance. So the first
collector that we're going to try in gal after the boom collector that I would like to try
is this MMC collector because it supports conservative routes from the stack and conservative
routes from global heap sections and optionally even conservative edges between objects.
And so in the whip it library, there are a few collectors, collectors are configurations of spaces.
There are three main collectors, like three main collector variants. One of them is the MMC collector,
the mostly marking collector. It mostly marks objects, sometimes it can copy and evacuate objects.
So that's where the name comes from. And it's composed of two spaces.
The space we call the novel space and the large object space or the low space.
And the novel space, this is the one that if you were here a couple of years ago when I presented
first about whip it, I was very excited about because this MX design allows for
improved performance and bump pointer allocation and optional allocation and optional
conservative routes. And I was just so excited and made this prototype. And at that time whip it was
essentially just this space. And in these interseeding two years whip it has become more of a collector
or a family of particular collectors but like an embeddable library. That's the essential
difference relative to a couple of years ago besides performance and bugs and features and stuff.
Like we've gone really from prototype to something that is pretty much ready right now.
And the novel space has some memory overhead, not 12 percent, because it records a bite for
per granule or yes. And a granule is 16 bytes. So 12 percent or 6 percent.
You're 6 percent isn't it? It's how it is actually. No.
That's yeah, right. It's 6 percent. It supports pinning which is an pinning permanently
maybe because you really need this object not to move. You can't be sure that the references to it
will allow moving for whatever reason. And it can also pin routes of preventive moving.
The routes that come in from conservative routes, the ones you might not know that actually refer to an object
or not, those objects can't move because we're not sure if the edge coming in is relocatable or not.
But then if you can precisely trade the inter-teap edges then you can move everything else,
which is a pretty interesting possibility. And it's also absolutely generational using what's
called a sticky market algorithm. And then larger objects are never moved.
They're allocated with M map effectively. And when they get freed they go on a free list
that after a couple seconds if that free list entry hasn't been reused, gets returned to
the OS. So we're trying to minimize virtual memory traffic here. And it's optionally
generally generational as well. That's probably the space that's going to be the main one for
for a guy although we'll see. And whip it is an upgrade, I think, not just for a guy
itself, but also potentially for other systems. So I'm building it with guy on the mind,
but I also want to target other small languages, which is I think some folks in here,
that when you build a system, you've got a lot to build. You have the compiler and you want to build
the GC, I mean, you want to build everything, right? I'm speaking from projection, right?
But you don't want to have so much time. And so it would be nice to be able to just include
something that you know works and you know stretches farther to the state of the art than
something like the bone collector. And I think we're going to be able to do this,
especially in system, new systems often have precise roots. And so one of the possibilities
that whip it gives you is a fully copying collector or a fully moving collector. So this is
another new one relative to a couple of years ago. This is a parallel copying collector.
It's a large object space, or managed just as before. And then the copy space is a blocks
structured space. It's stopped the world, but highly parallel and high parallel for mutators as well.
When a mutator needs to allocate more memory, it does bump-pointing allocation in, I think,
they're 128 kilobyte blocks. But when it runs out, it gets a new one. It's all locked free. So it
scales very well to us. And it's always compacting. And of course, it has 100% overhead because
it's a copying collector. When you copy, you need to reserve all its space. We also have a
generational configuration here. So instead of having a copy space and a large object space,
we have a copy space and a copy space and a large object space. But because it's generational,
you can limit the size of the nursery, and you can limit it ahead of time. And so you can
you can do a number of tricks to make it cheap, to test whether an object is in the nursery or
the old generation. This needs to be tuned. It's a relatively recent thing. And tuning
generational GCs is very tricky. But what it does have is, and this is the same thing for
the generational configuration of the most e-marking collector. And it has a very precise
right barrier. So it precisely records fields that point into the new generation. It's not a
it's not a barrier that marks any object within this block, for example. It's really precise fields
the field logging might vary, so it's called. Yep, very good. In this collector, objects stay
around in the nursery for one cycle, and then they get promoted up if they survive. And finally,
this is a third major collector that is in the whip it is the whip at API, but with the bump
collector behind it. And this mostly works, though, I mean it works, but it has a difference relative
to other collector configurations, and it's not cooperative. If you're familiar with the bump
collector, it's an amazing hack, but it stops a world by sending signals to processes. So you
can be stopped anywhere. You're in better SV a little bit more ready with regards to being able to
trace its roots at any point. But the other nice thing with the bump collector is you don't necessarily
need to implement GCC trace object there, because we don't we don't actually call that. We allow
the bump collector to conservatively track all edges there. Right, all right, um, practical memory
management upgrade for gone beyond. So practical on on that side, I say this for embedding, I say
it's not just for Gile, and this is not anything. How do you test this? I wanted to have these
properties that it's embed only, it's not something you link to, you include in your source
street, and it has no dependencies. It's it's C for better and for worse. I think we all know the
advantages and trade backs there, and it's something you can hack on. And the thing I've been
working on to test this, I know something else. The other ones, you're going to find it funny.
It's another scheme of meditation. I wrote a special scheme of meditation. It's not a great one.
It just compiles to see, and the whole purpose is to test whip it in its different configurations.
Because writing, um, when you when you have a garbage collector like this, you don't actually
want to write, um, you don't, the embedded shouldn't really have C programs. It should be a language
of meditation, and it's compiler and runtime should ensure the property that like you enumerate all
the, all the, all the roots, like handles all your stack mapping and stuff. And, and what I had before
was like manually written C programs that, uh, that were the micro benchmarks, and, and whiffle allows
me to write scheme programs that, that there are the benchmarks. Still micro micro benchmarks,
it's kind of where we are, but, um, and I also wanted to test like explicit handle registration
versus stack maps and things like this. Um, motivation was testing, and, like I say, it's
got many, many bugs. Um, so foreguld itself. Here is, here's, here's a plan, as I present to
the little, right? The plan is, uh, first, uh, switch dial to use the whip at API, right? Every,
everywhere you would call the bone collector instead, call the whip at API, and thread the
mutator through everywhere that you need, like the sort of thing. Um, but, but use the bone
collector behind it, so we're not actually changing behavior. And then, let's switch over to
the mostly marking collector with conservative roots. Maybe even conservatively tracing the heap,
we'll see. Um, ideally you would want to implement GC trace objects so that we, we get compaction on
these benefits. And then, uh, potentially add support for a generational collection. We'll see what
this buys this, uh, in a bit, but it requires right barriers. So we have to be, we have to be careful
about this. Uh, existing dial users don't have these right barriers in their code for it. There's
mathematics here. And then maybe, you know, maybe we can switch to, uh, mostly marking the novel
space and the old generation and then a copying, uh, nursery, which would be a very conventional,
and, and more or less, they are configuration. Um, and I, I should mention here, uh, I've been
working on this over the past few months, along with, uh, spritly work. Um, and, and my work on,
on with it is been sponsored by it and on that. So I appreciate that very much. Thank you.
Um, there's more. But yeah, great. Uh, all right. So, and, and, and it's for, for Gallen beyond,
I have a few more things I want to do, like WebAssembly to see, but like WebAssembly with GC, and,
and you embed this as it's, uh, as a garbage collector, so that way we can run actually standalone,
programs, compiled from skiing to WebAssembly. Uh, and I'm, I'm also targeting okay, I'm on our
issues like that. Right. So what do we get? Right? I don't know if it's top line or bottom line,
I'm not sure how people do accounting, but, um, what we can expect more or less is for a given
memory size, uh, we can improve throughput, um, could be 20%, you know, maybe an accident, 40,
sometimes it's actually quite a lot, but, sometimes it's literally a bit, you know, that's a general
range. And then also, uh, we can, uh, end up with systems that use less memory, right? Um,
that add a given throughput, you can use less memory. Let's see. It's going to be a bunch of graphs,
I'm going to go through them faster than, you know, is recommended, but here we go. All these graphs
are, are, are space time graphs, right? This is how you evaluate the GC, because the GC is a
fundamental space time trade off. Uh, the more heat you give it, uh, the less time it takes,
essentially. And so you expect to see a, a curve like this is like the, this is a heat size multiplier
from the x-axis. As you get towards like a one, one times live variable size, then you're going
to be collecting all the time because you have very little space to work in. And as you have more space,
then the collector can do better. Uh, the green line, uh, is the most e-marking collector,
for, um, this one particular benchmark, it's an employer standard, uh, Gabriel benchmark. Um,
the blue is the bone collector, and then the orange is the parallel cotton collector, and they're
a little bit compressed here, um, because we see a couple things. One, uh, the most e-marking
collector allows us to access these smaller heat sizes that we cannot get in the other collectors,
right? Nobody else, they, they all fail at this size. This is setting in fixed heat size.
Two, we are, we are more, we do better than, then the bone collector at every point here,
and the bone collectors at the blue line lowers better. And then, uh, if you switch to another
garbage collection algorithm, like a copy and collector, which has different performance characteristics,
it beats the most, mostly marking collector at larger heat sizes, which is what we expect.
So if you have a workloads like you need maximum throughput, and you have a lot of memory,
then you might want to configure your collector to use the parallel cotton collector, for example.
And we see similar things in, like, uh, this other, uh, tests here, uh, this is a partial value
error test. Um, again, most e-marking collectors doing, you know, pretty good, looks like we actually
cross here with, with the bone collector it seems. Um, and, uh, all those tests before we're with one
mutator, uh, if you have eight, this is on my laptop with, uh, eight cores, 16 threads. Uh, if you have
threads, then you see a similar graph, and, and where, you know, we, if a pretty good, uh,
advantage here is between four, four and six seconds here, uh, for the bone collector versus MC,
there in this sort of tail of that graph. Um, and, and some of the things for, for, for P about,
right, uh, you might want to ask some questions, right, because, you know, there's a lot of narratives
about garbage collection about, you know, what is actually good. You know, people like statements,
and, and you know, know of his marketing or not, and says, another one of the goals of whip, it
is be able to use the same system, but different configurations and see what, um, how do things
before him? Like, uh, I have found two things. One, conservative root finding is quite fine, right?
It's not actually a problem in these micro benchmarks. Um, and two, uh, general, generational GC is very
complicated. It can decrease throughput in my current tuneings, which might not be optimal. They certainly
reduce pause time, which I'm not going to show, uh, but, you know, that there's a two things.
Okay. So this is first, um, three different configurations for the mostly market collector,
uh, on this one micro benchmark that's, I think, with eight new traders, this one's probably about,
uh, gigabyte heap or something like that. Um, as you can see, uh,
all three mostly follow the same shape. Uh, the blue here on the top, the dark blue, is a configuration
in which all edges are, are conservative. The lighter blue is a configuration in which
edges into the graph from the stack are conservative, but, uh, edges within the heap graph are trace
precisely. And then the red here on the bottom is a, is a precise one. It's almost in different
between the stack conservative versus stack precise, uh, configurations. And, and there is a difference
between the fully conservative. It's, it's, it's less good. It's not a huge difference, right?
So it is something that you can accept. If engineering wise, that's, that's a configuration you need,
same graph, different test. Um, generational collectors. We're not winning. We're not winning currently.
The, uh, here is my whole heap collector and for some reason, my generational configuration
of the Mercy Martin collector is, is, is not as good in terms of throughput. This can be a
possible result, um, but it's, it's, it's a little bit of aplexing in some way. So there's
still some investigation to do here. And I have a similar difference for the leg generational
copy collector, um, which has different characteristics because the, the Mercy Martin collector,
the nursery is the entire heap size versus, for the copying collector, the nursery is, it's just
two megabytes per, per active mutator. Um, so there's more investigation to do here. It's a little bit,
I, I, I don't fully understand these things. Um, but the, the, the conclusion I'm taking is that
general GC is coming, generational GC is a little bit complicated, to, to, to, to, to, to, which is, I
think, uh, mostly well, then. Finally, future. Um, finally going to slam it in a go. I think it's
about this month or so, I'm going to start tacking on that. Um, maybe, you know, maybe, um,
the other language runtime, you know, which talk, I should, we should see, uh, how we're doing.
Eventually, I would like to do concurrent marking, uh, so that you have the tiny pause times,
sub-millisecond for the, for the, for the minor GCs. And then when it comes time for the major GC,
you've already marked most of the graph concurrently. And so you have to, you can minimize that pause time.
Um, and then there are other, um, things I would like to investigate this card structure,
algorithm called Lixer that uses, uh, some reference counting for the all-generation for a
prompt recognition of the, all-generation code. Um, yeah, that's it. So, there we are. And,
right out. Okay. That's what actually means. Thank you.
Boy, we went straight into that. Didn't make. Yeah. Thanks for, thanks for coming along.
Any, any questions?
Say what?
What pointers?
Colored pointers. What is a colored pointer?
Oh, yeah. We are not planning to use colored pointers, because I don't want to impose
that kind of requirement on, uh, on the, on the collector. Uh, sorry, I'm on the, on the
and better. It's an interesting possibility, but it's, it's, it's not within scope. Yeah.
Another one. Dave?
Yeah, I sure, uh, I know you folks have a, in the stop, but I'm interested in, uh, graph stop times times.
Does I mention today how with it, uh, forms for some real time applications, video data.
See me later today. Okay. All right. Everyone, please squeeze in. We're going to have a full house.
In the middle of this, there are a question.
If you're writing in rust, you should use mmtk instead of whip it. And if you're writing in
zig, I don't, I don't know what facilities exist for, for the sort of C source code. It's, it's
really not appropriate. I would say. Yeah. Sorry, the question is whether rust and zig should
use whip it and the answer is no. In, in rust specifically, I'm TK's good option and in, in zig.