We're starting.
My name is Andy and I'm here to say we're talking garbage collectors in a really great
way.
This is my talk about WhipIt, which is a new garbage collector for Gile.
So Gile is an imitation of Scheme, as most people know.
But if you looked at it, and you tried to determine its composition, you would notice
that there's a big C library that's part of it.
And it has an API, like we show, like there's a cons function, which is defined as cons,
and it takes some arguments, and it returns a value.
And there's a lot of code inside Gile that uses this API, and a lot of code in external
projects and files that also use this API.
So it's exposed to third-party users.
And Gile is a garbage collected language.
Data is allocated by the garbage collector, and the garbage collector takes responsibility
for freeing it.
And how is this going to work?
So let's say I cons the value, I'm making a new object, I need to include it in the set
of live data, right?
So what's a live object?
A live object is one of the roots, or anything referred to by a live object.
So it's a circular definition.
You compute the fixed point of this computation.
And how are we going to do this?
I'm sorry, I'm getting on to the next slide.
So there are actually three strategies we can use here.
One, we can ref count values, and you know, we used to laugh at this, but it's coming
back in style, actually.
Here you could register the location of this value with the runtime, and unregister it
at some point when it goes out of scope.
And another way we could find this value would be what is called conservative root scanning.
And that's what Gile has done for many, many years now.
And the idea, I don't know, if this is the first time you're hearing this, this is going
to be wild.
You know, like your brain's just going to go poof, because you take the stack, right?
The machine stack.
And you treat every word on it as if, like, it's an integer, you know?
But if it's an integer, which is within the range of the objects managed by the heap,
then we consider this maybe a pointer.
And then we keep those objects alive.
So it's conservative in the sense that it doesn't compute the minimal set of live objects.
It's an over approximation of the live objects.
It seems to work, though, historically.
It's not one of those things you have guarantees on.
It's very strange.
And Gile's very old, 30 years old, I think, today, or not today, but like this year, I
think, something like that.
We're getting older, also.
And since it's very beginning, it had a custom GC, which we inherited from a previous limitation
that Gile was based on, SCM.
And then in the mid-2000s, we added support for proper P threads.
We had other things before.
It was a kind of buggy time, because threads and garbage collectors, it's a very tricky
thing to get right.
And if you just half-hazardly add them together without understanding what you're doing, you
can make some bugs.
When we switch to a third-party collector called the Bohm-Demmers-Weiser collector, I should
have spelled it out here, a lot of these bugs went away, actually, because it takes threads
more into account.
It's better designed in some ways.
And a nice thing when we switch to the Bohm collector is it scans not only stacks, but
also static data segments, P thread keys.
It tries to find all the roots that it might possibly find.
It grovels your system for special magic integers.
And actually, with conservative collection, there are some advantages, and some real advantages.
It is very nice to program with a conservative garage collector.
I work on web browsers, they all have, well, two of the three major ones have precise roots,
and it's a pain getting the handles right.
And I've had bugs, you know, where you forget to register the location of a value, and everything
blows up, but only sometimes, it depends on when the garage collector runs.
And it doesn't constrain the compiler, because the compiler doesn't have to keep track, you
don't have to make the compiler tell the system about where the values are.
And yeah, but on the neighbor side, you might leak values.
We don't know to what extent this is a thing.
It appears to be fine in practice.
We actually don't have a lot of data there.
With the advent of 64-bit address spaces, I think it is less of a problem, though.
Another issue is we can't move values.
If any integer that we ever find during the whole trace of the heap might be a pointer
to a value, we can never compact the heap.
And this is actually a real, it's a real limitation for us in the sense that we can't
use some of the newer, better performing garbage collecting algorithms.
And as a technical constraint, it also constrains the garbage collector from changing.
It's very difficult to change to one of those garbage collector algorithms now, because
we have so much user code, we have so much implementation, and it'll be hard.
But whatever I told you, there is actually a better way.
Because we thought we were at a local maximum.
We couldn't get any better without getting worse for a while.
We wouldn't reach that mountaintop without having to descend into the valley.
But it turns out that you can have conservative roots and move objects and compact the heap.
You can have conservative roots and do a fast bump pointer allocation, which we'll get to
in a minute.
And you can have conservative roots and eventually possibly add more precision to your scan.
And the thing that came along that allowed me to know this was something called Immix.
This is a paper that was published in 2008 by Steve Blackburn, his group.
And it is a new, well, he characterizes in that paper a new class of fundamental GC algorithms.
So you have basically four things you can do when you're doing a GC.
You can have what's called mark compact, meaning find the live objects, and then slide them
all to one side of the same space.
So within the space that you found the objects in, you slide them all to one side.
You have mark sweep, find all the objects, and then collect all the holes into, these
are the holes that are two words long, and these are the holes that are three words long,
and these are the holes, like that, into free lists.
This is what it's called.
You sweep to a free list.
Mark sweep.
Evacuation, find all the live objects, and as you find them, you copy them somewhere else.
So instead of sliding to part of one space, you get them out of the space entirely.
And that's a semi-space, for example, that's a number of different Java collection algorithms.
And this other new algorithm is mark region.
Find all the holes and bump pointer allocate into them.
As you allocate, you sort of sweep across the space, and you allocate in a bump pointer
fashion into this hole, and then to that hole, and then to that hole, instead of collecting
free lists.
And IMIX is one of these new kind of collectors.
This is a diagram from the paper, the 2008 paper.
IMIX organizes the heap into blocks and lines.
Blocks are about 64 kilobytes in size, should be a multiple of the page size, and lines
for IMIX are 128 bytes.
And as you allocate, here in this diagram, we can see that there are some blocks that
are all full.
Full block, we don't have to do anything about it.
There are some blocks that have some lines which were marked in the previous collection,
and some lines that were not marked in the previous collection.
The lines that are not marked, a set of contiguous lines, is a hole.
You can bump pointer allocate into the holes.
Objects can be part of a line, in which case maybe many objects fit in a line.
They can span multiple lines, but they can't span blocks, okay?
When you allocate, you bump pointer allocate, and you sweep through all the blocks in the
system in the course of that GC cycle.
When you trace, you mark objects in the same way as a mark sweep collector, so there's
a mark bit associated with every object, possibly an object's header, possibly an aside table.
But as you mark them, you also mark lines, the lines that they're on, using address math.
Typically the way this is invented is all these blocks are allocated as part of a line
2 megabyte slabs, basically, and you can use address arithmetic to get to the aside table
of mark bytes for the line.
When you sweep, you do, at the end of collection, there is an eager sweep over all of the line
mark bytes, so the contiguous array of mark bytes for lines, to identify which blocks
are full, which are completely empty, and which are recycled, containing some old data,
and those you would bump pointer allocate into the holes.
The cool thing about it is that IMIX does opportunistic evacuation, so it's not simply
leaving these objects in place.
If it determines that your system needs to be defragmented, then it can choose some set
of blocks to evacuate, and choose some other set of blocks which are already empty to be
evacuation targets.
So it's still a one-pass algorithm over the heap, but instead of marking objects in place,
it tries to put them into an empty block.
And if you do this a couple of times, you'll completely defragment the heap.
And it can fail because parallel markers, and ordering, and alignment issues, and that's
okay if the evacuation fails, you just mark in place.
It's always okay to mark in place, and it's always okay to try to evacuate, evacuation
may or may not succeed.
So when I realize this, that you can mark in place or evacuate, this is something that
is compatible with guile, right?
We can do bump-point allocation now instead of allocating from free lists, which would
improve throughput in guile programs.
We can compact the heap, which is, I mean, I know there are many users here, and python-xyz.scm
is one of the files you have, yes.
I say no more.
So I started a year on this, on this work-in-progress whip GC implementation, hence where the name
comes from.
There are a couple of differences from IMEX.
IMEX has these 128-byte lines, and if just one object on a line is left over, then the
line is kept live, right?
In the next collection, nobody will allocate, nobody will put an object in that line.
It's not a hole, basically.
And for various reasons, I didn't make sense to me, so instead in Whippet, we have 16-byte
lines, so effectively the line mark table is the object mark table.
You only have one mark byte, it's a byte because of parallel markers, and it's a bit more
overhead in terms of space, but maybe it's a bit more parsimonious with memory, we'll
see how it works out.
It's an open question here.
And additionally, with these line mark bytes being more fine-grained, it's a lose to do
an eager sweep over the heap, so we do lazy sweeping, so as you allocate, you just sweep
one block, and then sweep another block, and then sweep another block, like that.
And the good thing about that is that it parallelizes things.
The bad thing is that you don't know how much data was live at the previous collection right
after your collection, because you haven't swept yet.
Yeah, okay.
So some comparisons with Whippet compared to the Bohm collector, and there are a number
of different points here.
So one of them is you can move values.
If every edge in your graph is potentially conservative, then you can't move anything,
because you could find an edge that keeps an object live and doesn't allow moving late
in the trace.
But if you can partition your edges into a set that's conservative and a set that's not
conservative, a set that's precise, you do the conservative ones first, and any object
which isn't reached in that conservative trace is then movable.
So what happens is you mark the stack first, and you mark in place, you don't evacuate.
That is an implicit pin on every object that you mark.
And then you go and you mark the heap, and if you find another object there, you can
evacuate at that point.
And then in Whippet, if we see that the heap is fragmented, we can turn evacuation on,
and if we don't, if we see the heap is not fragmented, we can always mark in place and
not incur the overhead of copying.
There is also explicit pinning for various reasons.
We can shrink the heap, which is nice, because these blocks are multiples of the OS page size,
they're easy to return to the OS whenever we find that a block is empty, and you can
just mark it as being empty, and MAdvise, MAV don't need it, and if you ever need it
again, you can pull it right back in, it's zeroed by the OS.
And additionally, there's a possibility to use adaptive heap sizing techniques, such
as the one that I link here, it's an online algorithm that depends on what's your current
cost of GC and how fast are you allocating.
So a process which sort of stops and goes quiet, gets its memory slowly reduced to the
minimum.
You can fit more on a system.
And we can also do a generational collection, if we want to, using the sticky mark-byte
algorithm, which I link to here, it's described more in that post.
For some programs, it doesn't make a difference, because some data isn't very generation friendly.
This is the case of the first empty GC bench pair over there, where the first bar is Whippet
without generational collection, and the second is with.
But in some cases, it's very effective, like in this, I'm making a bunch of quad trees,
and it pretty much doubles the throughput of the system.
Additionally, with Whippet, we scale a lot better for multiple allocator threads.
In BDW, you have these size segregated free lists, the free lists of size two, three,
four, and that sort of thing, and you need to lock the heap to sweep and find more and
fill those free lists.
In Whippet, you use uncontended atomic ops to obtain the next block, just basically incrementing
a counter, because the blocks are contiguous in these two megabyte slabs, and you sweep
without contention.
So these are two graphs showing the time it takes as problem size increases and number
of mutator threads increases.
So at each step, I'm adding on an additional mutator, an additional thread, doing the same
amount of work.
So with two mutator threads, the heap is twice as big as it was with one, and with eight,
it's eight times as big as it was with one.
So we do expect to see some increase.
What we see is that BDW takes more time, ultimately, like it's at nine seconds with an eight thread
mutator, whereas we're only at three and a half with Whippet, it scales much better when
you're adding allocators.
And this is with a single marker thread, so we expect to see some increase as the problem
size gets larger.
This is, what do you call that?
It's like when you make a quilt, apparently you're supposed to put a part in it that's
incorrect because you don't want to show too much pride in the face of God, right?
It's like a touch of the hand sort of thing.
This is my humility slide showing Whippet being slower than BDWGC on this one machine.
I have no idea what's going on with this because I remeasure it on my other machine.
It looks much better.
But it does point that as you add on marker threads, things improve, although I don't
understand the relative BDW Whippet thing right there, so that's a question.
So with the heap, with twice as much memory as the problem takes, as we add markers, things
get better for both BDW and Whippet, but a little bit better for Whippet.
So ephemerons.
This is weak maps like you have in JavaScript where you have keys associated with value,
but what if value references key?
Can you have a circular reference?
Could the weak reference, does it leak memory?
I don't know.
You people have heard about ephemerons, I would imagine.
You cannot do them in the boom collector.
It's impossible, right?
I've tried a lot and thought about this, but with Whippet we have them.
You really need deep GC integration to implement ephemerons.
Right and precision.
So with BDW, you're always stack conservative.
You're always scanning the heap, the stack for smelly pointers, right, or smelly integers,
integers that could point to the heap.
And it's often configured in such a way that every edge on the heap also is conservative.
And with Whippet we can configure it in a number of different ways.
And probably we're heading down the mid-near term is this conservative scan of the C stack,
precise scan of the scheme stack, and a precise scan of the heap.
So we will be able to get the advantages of motion and compaction and all that.
But we could move to a fully precise stack as well.
And potentially things to get better.
BDW GC is terrible to hack on.
I just counted it's like 15 or 16% CP processor directives.
You can imagine it's probably 90% of the code is covered by if thefts.
It's really, really hard.
Right.
So some more words about how it is that we are, we are, that royal we, right, okay.
Working on getting Whippet implemented in such a way that it could land in Guile and
not break the world because I'm going to make a confession.
I don't maintain software, I develop software, and I throw it over the wallet, I forget about
it.
So if I'm going to get bugs in the garbage collector, that's not, I better not start
because, you know, I'm not going to fix them.
So the repositories here, it is designed to be an embed only library, kind of like an
include style library, but you actually do separate compilation.
But it's something that you include in your source tree because it needs to be specialized
with respect to the program that's using it.
In the case of Guile, Guile will tell Whippet how to put a forwarding pointer in an object,
for example, how to do a precise trace of the heap.
And then we also specify Whippet with respect to the domain.
So what should we scan conservatively, what should we scan precisely, that sort of thing.
There is, we use LTO, and it appears to remove the overhead of the separate compilation,
link time optimization.
I'm actually suspecting LTO for that other graph that I showed you.
So we actually managed to get performance and abstraction at the same time by being
inspired by MMTK.
MMTK is a memory management toolkit, it's fantastic.
It's a library of garbage collectors and technique and experience and knowledge, currently
written in Rust, formerly part of the Jyx research JVM, but now retargeting to open
JDK and V8 and a number of other systems.
We could actually slot this into Guile if we wanted to at some point.
But we have enough information exposed in the API to allow a JIT to use that exposed
information and generate machine code for the fast path for allocation, for example.
And by having like a real abstract barrier between the two sides, we allow both sides
to evolve at their own pace.
And when we think about migrating Guile to Whippet, which is kind of where I want to
go here, I know in the talk description it kind of oversold the item, right, it's like
now we have a new production garbage collector in Guile, it's not there yet.
So this abstract API can be implemented by the current garbage collector being used by
Guile, by the Bohm collector, by the BDW collector.
And so that's going to be the first step, is to switch Guile over to use the new API
but still use the old collector implementation.
And then we can look at switching to Whippet, but that wouldn't require any code changes
ideally in Guile.
I mean, so you have the Whippet API, but then you have the Whippet garbage implementation
algorithm that we were talking about.
There are a lot of variants on the algorithm in Sonali that you can, these are different
ways you can configure Whippet on two different tests, one there's MTGC bench, one there's
quads here.
And going across we can first see serial Whippet, one marker, one marking thread, it's not going
to be parallel marking.
That's the first light blue bar on both of those sides.
And then we have parallel Whippet, four markers in this case is what I was measuring.
It improves things in some cases, a little bit in other cases, minor improvements.
Generational Whippet, collect more recently allocated objects more frequently than older
objects.
Parallel generational Whippet, four markers and generational.
And then after that there's four more bars which are the same thing, but collecting stack
routes conservatively.
The previous one is a precise scan of the stack, the previous four bars and then the
next four bars are conservative scan and as you'll note it actually performs better.
And there are two reasons for this, one conservative scanning can actually reduce the lifetime
of objects if the compiler determines that an object isn't needed at any given point
it can reuse its register or stack slot or what have you, whereas you have to wait for
the unregister part of a registration, deregistration API if you're using precise routes.
And the other thing is that when using this API from C, I don't actually have cooperation
from the compiler where it's going to write out a table of where all the values are.
I have to explicitly say, and now remember this one, okay, now forget it.
And now remember this one, and now forget it.
And that's overhead, right?
And by doing a conservative scan, I remove that overhead.
And then the final two bars, I didn't include generational because it doesn't really make
sense in this context as a fully heap conservative scan.
We increase a lot on this empty GC benchmark because it allocates a very big array and
I don't have the equivalent of point on this allocation that the BDW API gives you.
So we end up tracing all the elements of that really big array, which gives a big spike
over there.
And in the case of quads, we never have large objects, we're always tracing everything anyway
and it doesn't really matter.
But heap conservative does slow you down relative to just having stack conservative.
Right.
And then as a project, it's written in C, which I know is a sin, but Guile has this sort of
odd place in the supply chain of geeks and it's useful to depend on a more minimal set
of things rather than using Rust, for example.
But it's a relatively modern C, uses stethatomic, uses things in a way that are constexpr-ish
in a way that you know that the compiler is going to reduce them down.
It avoids void pointers completely, using instead structs containing a single number,
which gets boiled away by the compiler as well, which can't be cast to each other, you need
explicit conversions, that way you won't confuse a conservative reference with a precise reference
and things like that.
And we don't actually have any API or API concern at all because it's an embedded-only
library.
If something breaks, don't update it.
And it does have a bit of an abstraction for how do you find conservative roots on whatever
your platform is.
It's not so bad, it turns out.
So if we think about when it is that this might reach Guile, then we are, it's when
we can, right, you know, in the end.
This is kind of a side project for me.
I have other side projects, children, you know, so I can't really give an ETA here,
but I would mention that there are a few things to do, and what we might end up with is that
we could get a new release series for Guile, which is I think is what would be required
for this, maybe starting in six months or so, just switching over to the API and staying
with the Balm Collector, and maybe we could release a new stable version in another six
months or really a little bit more.
But we'd have to do a few things for there.
Wipit is done mostly with the exception of actually growing and shrinking the heap, implementing
finalizers, and having an API for checking in with Wipit, checking in with the GC as
to when a mutator should stop, because that's one other thing that the BDW Collector does
is it uses signals to stop all the threads, whereas Wipit relies on periodic save points.
There are trade-offs.
In Guile we'd have to switch over to these save points, I think it's possible.
And I think we would start with a heap conservative Wipit, just because it's the same thing that
we do with the BDW Collector, and then we'd move over to a precise scan of the heap.
When we get to a precise scan of the heap, we have to implement a few things on the Guile
side.
There are some hazards about current uses of the API.
In particular, if a third-party user ever allocates an object and then stuffs something
in it that Guile doesn't know about, is it an integer or is it a pointer to the heap?
And there are a couple of places that people can do that that are unclear.
And we can't allow this if we want to trace the heap precisely and move objects.
So this might require some small API changes and API breaks, because it's a new series,
around this area.
It might be actually time to remove smobs entirely, possibly.
So that's what's actually pushing us to a new major release.
So in summary, Wipit is a new GC, it's a replacement for BDW GC.
It has the potential to reach a new local maximum, the better than BDW.
And I think we can get into Guile 3.2.
I would like to thank particularly the MMTK people for inspiration and discussions, because
it's been really helpful to be able to properly learn about garbage collection over the last
year or so.
I'll leave you with one slide.
When you evaluate a GC, you need to do so with a space-time diagram, because GC is a
function, it's a trade-off between space and time.
So on the x-axis, you should have your heap size as a function of what is the minimum
heap size.
Here, I measured some algorithms at 1.3x, 1.5x, 1.75x, 2, 2.5, 3, 4, 5, and 6, or just
a 5.
I don't know, on the y-axis, you should have whatever you're measuring, be it instructions
retired or wall clock time or memory or something like that, because the heap size is one of
the, and the response to heap size is one of the fundamental trade-offs in GC.
Here we show that actually, we show the BDW collector, a semi-space collector, which is
also implemented behind the Wipit API, and the Wipit algorithm, serial, one marker, one
mutator on this benchmark.
We see performance as we change heap size.
Wipit is the only one that gets to 1.3x.
This is an analytical calculation of how big the heap should be.
It's not measured as to how small I can get anything to run, but it's like what I think
the heap should take.
So it might not precisely be 1.3, it might be one, you know, it's a number in that range.
It can get to the smallest.
It takes a bit of effort to do so.
As you become more parsimonious with your heap, you end up tracing it more.
So the curve goes up on that side, but it's the only one that actually gets to that x-axis
point of view.
And then it quickly passes, and you want these numbers to be low.
That's what you want.
It quickly passes BDW GC, it's only one point where it takes more time than BDW GC, and
that's concerning.
I need to fix that one.
Let me see the green line.
This is a semi-space collector.
Semi-space, as you add memory, it gets easier and easier and easier, right, because it depends
only on the size of the live data.
Whereas WIPPET and BDW need to sweep the heap.
So as you add memory, it sort of plateaus.
It doesn't keep on going down.
I don't know why it goes up at the end.
This is my other little touch of the hand.
I don't know.
That looks like a bug to me.
So that's something I fixed.
Anyway, there's WIPPET.
Thank you for enduring this blathering.
And good luck, everybody, in about 18 months when this starts rolling out to geeks.
Just joking, because I won't be around.
Good.
So I'll take any questions.
Even dumb questions.
That's okay.
Yes, sir?
It seems to me like conservative stack scanning is incompatible with address sanitizer from
LVM or GCC.
So how do you debug address bugs in the GCC?
So the question is, conservative stack scanning seems to be incompatible with address sanitizer
from LVM GCC.
I'm a professional C++ developer, and I work on web browsers.
I don't know what address sanitizer does.
I know it gives me bugs sometimes and tells me things I have to fix, but I don't know
what's going on there.
I should know.
Can you tell us, why is it incompatible?
Basically, every time you access something that wasn't registered properly via malloc,
for example, or aloca, it tells you you're in the red zone or you're in something that
doesn't work.
So to scan your wall stack, only part of it is actually valid.
So the answer is that it only signals warnings if you ever access a value after it's been
freed.
Is that right?
For example, you are in a function and you access something that wasn't.
I think it's actually not a problem because we don't trigger the malloc-free detection
at all.
What makes a complete third-party allocator is if you M-map the page and we're just reading
values from that page, and so it doesn't trigger the particular logic there, which
also means you have no tool support.
You're as wild west with the bugs that go with it, so yeah, I guess that's the answer
there.
Yes, so the question.
How will this affect Geeks users?
Well, this will affect Geeks users in the sense that, one, I hope that when you read
build the system, Geeks launches multiple threads to compile things.
And as we see, there is contention in BDWGC.
It doesn't actually scale very well as you add threads if you have an allocation-heavy
workload.
And so I think that when Guile incorporates WIPIT, Geeks with multiple threads should scale
better.
In addition, we will be able to have better tooling for how understanding the heap and
heap usage, and ideally, be able to place ourselves better on the kind of space-time
trade-off if you need more throughput, give it a bigger heap, also let it shrink.
And that can affect also longer-running demons like the shepherd and things like that.
So it should yield a more robust system.
Yes?
There are some architectures which can be used in 64-bit page.
Would that be a problem with using 16K blocks?
They're actually 64 kilobyte blocks.
So I think I chose the least common multiple or whatever.
It's configurable, but I think the default size is such that they are large enough for
any common architecture.
The question was about page size, is 16 kilobytes big enough for blocks, but it's actually
64 kilobytes.
Yes?
With the collection, would it ever have to stop all threads simultaneously, or do the
threads stop at a different location?
Basically, are there stops in the world?
Yeah.
Yeah, that's a very good question.
I didn't mention this.
So this is a stop-the-world collector.
It's not a concurrent collector with the exception of threads mark their own stacks while other
threads are running.
There's a little bit of concurrency there.
We may add concurrent marking at some point, but you need write barriers for that to work.
And so that would be something to add once generational collection is working, because
you've proven that you have all the write barriers in the right place.
Then write barriers is just like a little piece of code that runs whenever you store
a pointer.
And if write barriers can be used to indicate pointers from old objects to new objects,
helping you do generational collection, they can also be used to mark an object as being
allocated after the concurrent marker has already marked it in that cycle.
I'm not explaining myself very well.
But basically, you need write barriers to be able to have, to be able to minimize the
stop-the-world component of the mark phase.
Does that answer the question?
Yes?
Is this simply guy or complicate the guy with the web assembly?
Oh, yeah.
It's a good question.
So there's a project to compile a guy's web assembly.
I think initially this will probably start by having a guy library produce web assembly
that has its own runtime.
And this could grow to a whole program standalone compiler in which a guy has a library that
takes your guile program and spits out a native binary.
And in that case, that native binary would include WIPPET, embedded in it, instead of
having that native binary then link to the BDW collector.
So the goal would be to produce one binary that's all finished.
Is that it?
Thank you.
Thank you very much.