Friends, you might have noted, but over the last year or so I reallycaught the GC bug. Today's post sums up that year, in the form of atalk I gave yesterday at FOSDEM. It's long! If you prefer video, youcan have a look instead to the at the FOSDEM eventpage.

// APISCM scm\_cons (SCM car, SCM cdr);// Many third-party usersSCM x = scm\_cons (a, b);

So the context for the whole effort is that Guile has this part of itsimplementation which is in C. It also exposes a lot of thatimplementation to users as an API.

SCM x = scm\_cons (a, b);

So what contraints does this kind of API impose on the garbagecollector?

Let's start by considering the simple cons call above. In agarbage-collected environment, the GC is responsible for reclaimingunused memory. How does the GC know that the result of a scm\_conscall is in use?

Generally speaking there are two main strategies for automatic memorymanagement. One is reference counting: you associate a count with anobject, incremented once for each referrer; in this case, the stackwould hold a reference to x. When removing the reference, youdecrement the count, and if it goes to 0 the object is unused and can befreed.

We GC people used to laugh at reference-counting as a memory managementsolution because it over-approximates the live object set in thepresence of cycles, but it would seem that refcounting is comingback.Anyway, this isn't what Guile does, not right now anyway.

The other strategy we can use is tracing: the garbage collectorperiodically finds all of the live objects on the system and thenrecycles the memory for everything else. But how to actually find thefirst live objects to trace?

One way is to inform the garbage collector of the locations of allroots: references to objects originating from outside the heap. Thiscan be done explicitly, as in V8's Handle<>API, orimplicitly, in the form of a side table generated by the compilerassociating code locations with root locations. This is called preciserooting: the GC is aware of all root locations at all code positionswhere GC might happen. Generally speaking you want the side table approach,in which the compiler writes out root locations to stack maps, becauseit doesn't impose any overhead at run-time to register and unregisterlocations. However for run-time routines implemented in C or C++, youwon't be able to get the C compiler to do this for you, so you need theexplicit approach if you want precise roots.

The other way to find roots is very much not The Right Thing. Call itcheeky, call it sloppy, call it yolo, call it what you like, but in thetrade it's known as conservative root-finding. This strategy lookslike this:

uintptr\_t *limit = stack\_base\_for\_platform();uintptr\_t *sp = \_\_builtin\_frame\_address();for (; sp < limit; sp++) { void *obj = object\_at\_address(*sp); if (obj) add\_to\_live\_objects(obj);}

You just look at every word on the stack and pretend it's a pointer. Ifit happens to point to an object in the heap, we add that object to thelive set. Of course this algorithm can find a spicy integer whose valuejust happens to correspond to an object's address, even if that objectwouldn't have been counted as live otherwise. This approach doesn'tcompute the minimal live set, but rather a conservativeover-approximation. Oh well. In practice this doesn't seem to be a bigdeal?

Guile has used conservative root-finding since its beginnings, 30 yearsago and more. We had our own bespoke mark-sweep GC in the beginning,but it's now going on 15 years or so that we switched to the third-partyBoehm-Demers-Weiser (BDW) collector.It's been good to us! It's better than what we had, it's mostly justworked, and it works correctly with threads.

Conservative root-finding does have advantages. It's quite pleasant toprogram with, in environments in which the compiler is unable to producestack maps for you, as it eliminates a set of potential bugs related toexplicit handle registration and unregistration. Like stack maps, italso doesn't impose run-time overhead on the user program. And althoughthe compiler isn't constrained to emit code to clear roots, it generallydoes, and sometimes does so more promptly than would be the case with explicit handle deregistration.

But, there are disadvantages too. The potential for leaks is one, though I have to say thatin 20 years of using conservative-roots systems, I have not found thisto be a problem. It's a source of anxiety whenever a program has memoryconsumption issues but I've never identified it as being the culprit.

The more serious disadvantage, though, is that conservative edgesprevent objects from being moved by the GC. If you know that a locationholds a pointer, you can update that location to point to a new locationfor an object. But if a location only might be a pointer, you can'tdo that.

In the end, the ergonomics of conservative collection lead to a kind ofcalcification in Guile, that we thought that BDW was as good as we couldget given the constraints, and that changing to anything else wouldrequire precise roots, and thus an API and ABI change, losing users, andso on.

But it turns out, that's not true! There is a way to have conservativeroots and also use more optimal GC algorithms, and one which preservesthe ability to incrementally refactor the system to have more precisionif that's what you want.

Let's back up to a high level. Garbage collector implementations are assembled from instances ofalgorithms, and there are only so many kinds of algorithms out there.

There's mark-compact, in which the collector traverses the objectgraph once to find live objects, then once again to slide them down toone end of the space they are in.

There's mark-sweep, where thecollector traverses the graph once to find live objects, then traversesthe whole heap, sweeping dead objects into free lists to be used forfuture allocations.

There's evacuation, where the collector does asingle pass over the object graph, copying the objects outside theirspace and leaving a forwarding pointer behind.

The BDW collector used by Guile is a mark-sweep collector, and its useof free lists means that allocation isn't as fast as it could be. Wewant bump-pointer allocation and all the other algorithms give it to us.

Then in 2008, Stephen Blackburn and Kathryn McKinley put out their Immix paper that identifieda new kind of collection algorithm, mark-region. A mark-regioncollector will mark the object graph and then sweep the whole heap for unmarked regions, which can then be reused for allocatingnew objects.

Allocate: Bump-pointer into holes in thread-local block, objects can span lines but not blocks

Trace: Mark objects and lines

Sweep: Coarse eager scan over line mark bytes

Blackburn and McKinley's paper also describes a new mark-region GCalgorithm, Immix, which is interesting because it gives us bump-pointerallocation without requiring that objects be moveable. The diagramabove, from the paper, shows the organization of an Immix heap.Allocating threads (mutators) obtain 64-kilobyte blocks from the heap.Blocks contains 128-byte lines. When Immix traces the object graph,it marks both objects and the line the object is on. (Usually blocksare part of 2MB aligned slabs, with line mark bits/bytes are stored in apacked array at the start of the slab. When marking an object, it'seasy to find the associated line mark just with address arithmetic.)

Immix reclaims memory in units of lines. A set of contiguous lines thatwere not marked in the previous collection form a hole (a region).Allocation proceeds into holes, in the usual bump-pointer fashion,giving us good locality for contemporaneously-allocated objects, unlikefreelist allocation. The slow path, if the object doesn't fit in thehole, is to look for the next hole in the block, or if needed to acquireanother block, or to stop for collection if there are no more blocks.

The neat thing that Immix adds is a way to compact the heap viaopportunistic evacuation. As Immix allocates, it can end up skippingover holes and leaving them unpopulated, and as subsequent cycles of GCoccur, it could be that a block ends up with many small holes. If thathappens to many blocks it could be time to compact.

To fight fragmentation, Immix decides at the beginning of a GC cyclewhether to try to compact or not. If things aren't fragmented, Immixmarks in place; it's cheaper that way. But if compaction is needed,Immix selects a set of blocks needing evacuation and another set ofempty blocks to evacuate into. (Immix has to keep around a couplepercent of memory in empty blocks inreserve forthis purpose.)

As Immix traverses the object graph, if it finds that an object is in ablock that needs evacuation, it will try to evacuate instead of marking.It may or may not succeed, depending on how much space is available toevacuate into. Maybe it will succeed for all objects in that block, andyou will be left with an empty block, which might even be given back tothe OS.

Tying this back to Guile, this gives us all of our desiderata: we canevacuate, but we don't have to, allowing us to cause referents ofconservative roots to be marked in place instead of moved; we canbump-pointer allocate; and we are back on the train of modern GCimplementations. I could no longer restrain myself: I started hackingon a work-in-progress garbage collector workbench about a year ago, andended up with something that seems to take us in the right direction.

What I ended up building wasn't quite Immix. Guile's objectrepresentation is very thin and doesn't currently have space for a markbit, for example, so I would have to have a side table of mark bits. (Icould have changed Guile's object representation but I didn't want torequire it.) I actually chose mark bytes instead of bits because both the Immix linemarks and BDW's own side table of marks were bytes, to allow forparallel markers to race when setting marks.

Then, given that you have a contiguous table of mark bytes, why notremove the idea of lines altogether? Or what amounts to the same thing, why not makeline size to be 16 bytes and do away with per-object mark bits? You can then bump-pointer into holes in the markbyte array. The only thing you need to do to that is to be able to cheaplyfind the end of an object, so you can skip to the next hole whilesweeping; you don't want to have to chase pointers to do that. Butconsider, you've already paid the cost of having a mark byte associatedwith every possible start of an object, so if your basic objectalignment is 16 bytes, that's a memory overhead of 1/16, or 6.25%; OK.Let's put that mark byte to work and include an "end" bit, indicatingthe end of the object. Allocating an object has to store into the markbyte array to initialize this "end" marker, but you need to write themark byte anyway to allow for conservative roots ("does this addresshold an object?"); writing the end at the same time isn't so bad,perhaps.

The expected outcome would be that relative to 128-byte lines, Whippetends up with more, smaller holes. Such a block would be a prime targetfor evacuation, of course, but during allocation this is overhead. Or,it could be a source of memory efficiency; who knows. There is somescience yet to do to properly compare this tactic to original Immix, butI don't think I will get around to it.

While I am here and I remember these things, I need to mention two moredetails. If you read the Immix paper, it describes "conservative linemarking", which is related to how you find the end of an object;basically Immix always marks the line an object is on and the nextone, in case the object spans the line boundary. Only objects largerthan a line have to precisely mark the line mark array when they aretraced. Whippet doesn't do this because we have the end bit.

The other detail is the overflow allocator; in the original Immix paper,if you allocate an object that's smallish but still larger than a lineor two, but there's no hole big enough in the block, Immix keeps arounda completely empty block per mutator in which to bump-pointer-allocatethese medium-sized objects. Whippet doesn't do that either, insteadrelying on such failure to allocate in a block to cause fragmentationand thus hurry along the process of compaction.

Having a fine-grained line mark array means that it's no longer a win todo an eager sweep of all blocks after collecting. Instead Whippetapplies the classic "lazy sweeping" optimization to make mutators sweeptheir blocks just before allocating into them. This introduces a delayin the collectionalgorithm:Whippet doesn't find out about e.g. fragmentation until the whole heapis swept, but by the time we fully sweep the heap, we've exhausted itvia allocation. It introduces a different flavor to the GC, notentirely unlike original Immix, but foreign.

Right! With that out of the way, let's talk about what Whippet gives toGuile, relative to BDW-GC.

If all edges in the heap are conservative, then you can't move anything,because you don't know if an edge is a pointer that can be updated orjust a spicy integer. But most systems aren't actually like this: youhave conservative edges from the stack, but you can precisely enumerateintra-object edges on the heap. In that case, you have a known set ofconservative edges, and you can simply visit those edges first, markingtheir referents in place instead of evacuating. (Marking an objectinstead of evacuating implicitly pins it for the duration of the currentGC cycle.) Then you visit heap edges precisely, possibly evacuatingobjects.

I should note that Whippet has a bit in the mark byte for use inexplicitly pinning an object. I'm not sure how to manage who isresponsible for setting that bit, or what the policy will be; thecurrent idea is to set it for any object whose identity-hash value istaken. We'll see.

With the BDW collector, your heap can only grow; it will never shrink(unless you enable a non-default option and you happen to have verrrylow fragmentation). But with Whippet and evacuation, we can rearrangeobjects so as to produce empty blocks, which can then be returned to theOS if so desired.

In one of my microbenchmarks I have the system allocating long-liveddata, interspersed with garbage (objects that are dead after allocation)whose size is in a power-law distribution. This should produce quitesome fragmentation, eventually, and it does. But then Whippet decidesto defragment, and it works great! Since Whippet doesn't keep a whole2x reserve like a semi-space collector, it usually takes more than oneGC cycle to fully compact the heap; usually about 3 cycles, from what Ican see. I should do some more measurements here.

Of course, this is just mechanism; choosing the right heap sizingpolicyis a different question.

wingolog.org/archives/2022/10/22/the-sticky-mark-bit-algorithm

Card marking barrier (256B); compare to BDW mprotect / SIGSEGV

The Boehm collector also has a non-default mode in which it usesmprotect and a SIGSEGV handler to enable sticky-mark-bitgenerational collection. I haven't done a serious investigation, but Isee it actually increasing run-time by 20% on one of my microbenchmarksthat is actually generation-friendly. I know that Azul's C4 collectorused to use page protection tricks but I can only assume that BDW'salgorithm just doesn't work very well. (BDW's page barriers haveanother purpose, to enable incremental collection, in which marking isinterleaved with allocation, but this mode is off if parallel markersare supported, and I don't know how well it works.)

Anyway, it seems we can do better. The ideal would be a semi-spacenursery, which is the usual solution, but because of conservative rootswe are limited to the sticky mark-bitalgorithm.Some benchmarks aren't very generation-friendly; the first pair of barsin the chart above shows the mt-gcbench microbenchmark running withand without generational collection, and there's no difference. But inthe second, for the quads benchmark, we see a 2x speedup or so.

Of course, to get generational collection to work, we require mutatorsto use write barriers, which are little bits of code that run when anobject is mutated that tell the GC where it might find links from oldobjects to new objects. Right now in Guile we don't do this, but thisbenchmark shows what can happen if we do.

Another thing Whippet can do better than BDW is performance when thereare multiple allocating threads. The Immix heap organizationfacilitates minimal coordination between mutators, and maximum localityfor each mutator. Sweeping is naturally parallelized according to howmany threads are allocating. For BDW, on the other hand, every time anmutator needs to refill its thread-local free lists, it grabs a globallock; sweeping is lazy but serial.

Here's a chart showing whippet versus BDW on one microbenchmark. On theX axis I add more mutator threads; each mutator does the same amount ofallocation, so I'm increasing the heap size also by the same factor asthe number of mutators. For simplicity I'm running both whippet and BDWwith a single marker thread, so I expect to see a linear increase inelapsed time as the heap gets larger (as with 4 mutators there areroughly 4 times the number of live objects to trace). This test is runon a Xeon Silver 4114, taskset to free cores on a single socket.

What we see is that as I add workers, elapsed time increases linearlyfor both collectors, but more steeply for BDW. I think (but am notsure) that this is because whippet effectively parallelizes sweeping andallocation, whereas BDW has to contend over a global lock to sweep andrefill free lists. Both have the linear factor of tracing the objectgraph, but BDW has the additional linear factor of sweeping, whereaswhippet scales with mutator count.

Incidentally you might notice that at 4 mutator threads, BDW randomlycrashed, when constrained to a fixed heap size. I have noticed that ifyou fix the heap size, BDW sometimes (and somewhat randomly) fails. Isuspect the crash due to fragmentation and inability to compact, but whoknows; multiple threads allocating is a source of indeterminism.Usually when you run BDW you let it choose its own heap size, but forthese experiments I needed to have a fixed heap size instead.

Another measure of scalability is, how does the collector do as you addmarker threads? This chart shows that for both collectors, runtimedecreases as you add threads. It also shows that whippet issignificantly slower than BDW on this benchmark, which is Very Weird,and I didn't have access to the machine on which these benchmarks wererun when preparing the slides in the train... so, let's call this charta good reminder that Whippet is a WIP :)

While in the train to Brussels I re-ran this test on the 4-core laptop Ihad on hand, and got the results that I expected: that whippet performedsimilarly to BDW, and that adding markers improved things, albeitmarginally. Perhaps I should look on a different microbenchmark.

Incidentally, when you configure Whippet for parallel marking atbuild-time, it uses a different implementation of the mark stack whencompared to the parallel marker, even when only 1 marker is enabled.Certainly the parallel marker could use some tuning.

Another deep irritation I have with BDW is that it doesn't supportephemerons.In Guile we have a number of facilities(finalizers,guardians,the symbol table, weakmaps,et al) built on what BDW does have(finalizers,weakreferences),but the implementations of these facilities in Guile are hacky, slow,sometimes buggy, and don't compose (try putting an object in a guardianand giving it afinalizer to seewhat I mean). It would be much better if the collector API supportedephemerons natively, specifying their relationship to finalizers andother facilities, allowing us to build what we need in terms of thoseprimitives. With our own GC, we can do that, and do it in such a waythat it doesn't depend on the details of the specific collectionalgorithm. The exception of course is that as BDW doesn't supportephemerons per se, what we get is actually a weak-key associationinstead, whose value can keep the key alive. Oh well, it's no worsethan the current situation.

Conservative tracing is a fundamental design feature of the BDWcollector, both of roots and of inter-heap edges. You can tell BDW howto trace specific kinds of heap values, but the default is to do aconservative scan, and the stack is always scanned conservatively. Incontrast, these tradeoffs are all configurable in Whippet. You can scanthe stack and heap precisely, or stack conservatively and heapprecisely, or vice versa (though that doesn't make much sense), or bothconservatively.

The long-term future in Guile is probably to continue to scan the Cstack conservatively, to continue to scan the Scheme stack precisely(even with BDW-GC, the Scheme compiler emits stack maps and installs acustom mark routine), but to scan the heap as precisely as possible. Itcould be that a user uses some of our hoary ancientAPIsto allocate an object that Whippet can't trace precisely; in that casewe'd have to disable evacuation / object motion, but we could stilltrace other objects precisely.

If Guile ever moved to a fully precise world, that would be a boon forperformance, in two ways: first that we would get the ability to use asemi-space nursery instead of the sticky-mark-bit algorithm, andrelatedly that we wouldn't need to initialize mark bytes when allocatingobjects. Second, we'd gain the option to use must-move algorithms for theold space as well (mark-compact, semi-space) if we wanted to. But it'sjust an option, one that that Whippet opens up for us.

Finally, relative to BDW-GC, whippet has a more intangible advantage: Ican actually hack on it. Just as an indication, 15% of BDW source linesare pre-processor directives, and there is one file that has like 150#ifdef's, not counting #elseif's, many of them nested. I haven'tdone all that much to BDW itself, but I personally find it excruciatingto work on.

Hackability opens up the possibility to build more tools to help usdiagnose memory use problems. They aren't in Whippet yet, but there canbe!

OK, that rounds out the comparison between BDW and Whippet, at least ona design level. Now I have a few words about how to actually get thisnew collector into Guile without breaking the bug budget. I try toarrange my work areas on Guile in such a way that I spend a minimum oftime on bugs. Part of my strategy is negligence, I will admit, but partalso is anticipating problems and avoiding them ahead of time, even ifit takes more work up front.

So the BDW collector is typically shipped as a shared library that youdynamically link to. I should say that we've had an overall goodexperience with upgrading BDW-GC in the past; its maintainer (IvanMaidanski) does a great and responsible job on a hard project. It'sbeen many, many years since we had a bug in BDW-GC. But still, BDW isdependency, and all things beingequal weprefer to remove moving parts.

The approach that Whippet is taking is to be an embed-only library:it's designed to be compiled into your project. It's not aninclude-only library; it still has to be compiled, but withlink-time-optimization and a judicious selection of fast-pathinterfaces, Whippet is mostly able to avoid abstractions being aperformance barrier.

The result is that Whippet is small, both in source and in binary, whichminimizes its maintenance overhead. Taking additional strippedoptimized binary size as the metric, by my calculations a semi-spacecollector (with a large object space and ephemeron support) takes about6 kB of object file size, whereas Whippet takes 22 and BDW takes 184.Part of how Whippet gets so small is that it is is configured in majorways at compile-time (choice of main GC algorithm), and specializedagainst the program it's embedding against (e.g. how to patch in aforwarding pointer). Having all API being internal and visible to LTOinstead of going through ELF symbol resolution helps in a minor way aswell.

From a composition standpoint, Whippet is actually a few things.Firstly there is an abstract API to make a heap, createper-thread mutators for a heap, and allocateobjects for a mutator. Thereis the aforementioned embedderAPI,for having the embedding program indicate how to trace objects andinstall forwarding pointers. Then there is some common code (forexample ephemeronsupport).There are implementations of the different spaces:semi-space,largeobject,whippet/immix;and finally collector implementations that tie together the spaces intoa full implementation of the abstract API. (In practice the more iconicspaces are intertwingled with the collector implementations theydefine.)

I don't think I would have gone down this route without seeing someprior work, for examplelibpas,but it was really MMTk that convinced me that it wasworth spending a little time thinking about the GC not as astructureless blob but as a system made of parts and exposing a minimalinterface. In particular, I was inspired by seeing that MMTk is able toget good performance while also being abstract, exposing representationdetails such as how to tell a JIT compiler about allocation fast-paths,but in a principled way. So, thanks MMTk people, for this and so manythings!

I'm particularly happy that the API is abstract enough that it frees upnot only the garbage collector to change implementations, but also Guileand other embedders, in that they don't have to bake in a dependency onspecific collectors. The semi-space collector has been particularlyuseful here in ensuring that the abstractions don't accidentally rely onsupport for object pinning.

The collector API can actually be implemented by the BDW collector.Whippet includes a collector that is a thin wrapper around the BDWAPI, with supportfor fast-path allocation via thread-local freelists. In this way we canalways check the performance of any given collector against an externalfixed point (BDW) as well as a theoretically known point (the semi-spacecollector).

Indeed I think the first step for Guile is precisely this: refactorGuile to allocate through the Whippet API, but using the BDW collectoras the implementation. This will ensure that the Whippet API issufficient, and then allow an incremental switch to other collectors.

Incidentally, when it comes to integrating Whippet, there are somechoices to be made. I mentioned that it's quite configurable, and thischart can give you some idea. On the left side is one microbenchmark(mt-gcbench) and on the right is another (quads). The firstgenerates a lot of fragmentation and has a wide range of object sizes,including some very large objects. The second is very uniform and manyallocations die young.

(I know these images are small; right-click to open in new tab or pinchto zoom to see more detail.)

Within each set of bars we have 10 different scenarios, corresponding todifferent Whippet configurations. (All of these tests are run on my old4-core laptop with 4 markers if parallel marking is supported, and a 2xheap.)

The first bar in each side is serial whippet: one marker. Then we seeparallel whippet: four markers. Great. Then there's generationalwhippet: one marker, but just scanning objects allocated in the currentcycle, hoping that produces enough holes. Then generational parallelwhippet: the same as before, but with 4 markers.

The next 4 bars are the same: serial, parallel, generational,parallel-generational, but with one difference: the stack is scannedconservatively instead of precisely. You might be surprised but all ofthese configurations actually perform better than their precisecounterparts. I think the reason is that the microbenchmark usesexplicit handle registration and deregistration (it's a stack) insteadof compiler-generated stack maps in a side table, but I'm not precisely(ahem) sure.

Finally the next 2 bars are serial and parallel collectors, but markingeverything conservatively. I have generational measurements for thisconfiguration but it really doesn't make much sense to assume that youcan emit write barriers in this context. These runs are slower than theprevious configuration, mostly because there are some non-pointerlocations that get scanned conservatively that wouldn't get scannedprecisely. I think conservative heap scanning is less efficient thanprecise but I'm honestly not sure, there are some instruction localityarguments in the other direction. For mt-gcbench though there's a bigarray of floating-point values that a precise scan will omit, whichcauses significant overhead there. Probably for this configuration tobe viable Whippet would need the equivalent of BDW's API to allocateknown-pointerlessobjects.

I know it's a sin, but Whippet is implemented in C. I know. The thingis, in the Guile context I need to not introduce wild compile-timedependencies, because ofbootstrapping.And I know that Rust is a fine language to use for GCimplementation, so ifthat's what you want, please do go take a look at MMTk! It's afantastic project, written in Rust, and it can just slot into yourproject, regardless of the language your project is written in.

But if what you're looking for is something in C, well then you have topick and choose your C. In the case of Whippet I try to use the limitedabilities of C to help prevent bugs; for example, I generally avoidvoid* and instead wrap pointers or addresses into single-field structsthat can't be automatically cast, for example to prevent a struct gc\_ref that denotes an object reference (or NULL; it's an optiontype) from being confused with a struct gc\_conservative\_ref, whichmight not point to an object at all.

(Of course, by "C" I mean "C as compiled by gcc and clang with -fno-strict-aliasing". I don't know if it's possible to implement even a simple semi-space collector in C without aliasing violations. Can you access a Foo* object within a mmap'd heap through its new address after it has been moved via memcpy? Maybe not, right? Thoughts are welcome.)

As a project written in the 2020s instead of the 1990s, Whippet gets toassume a competent C compiler, for example relying on the compiler toinline and fold branches where appropriate. As in libpas, Whippetliberally passes functions as values to inline functions, and relies onthe compiler to boil away function calls. Whippet only uses the Cpreprocessor when it absolutely has to.

Finally, there is a clean abstraction for anything that'splatform-specific, for example finding the current stackbounds. Ihaven't compiled this code on Windows or MacOS yet, but I am notanticipating too many troubles.

So where does this get us? Where are we now?

For Whippet itself, I think it's mostly done -- enough to start shiftingfocus to some different phase. It's missing some needed features,notably the ability to grow the heap at all, as I've been infixed-heap-size-only mode during development. It's also missingfinalizers. And, something needs to be done to unify Guile's handlingof safepoints and processing of asynchronoussignalswith Whippet's need to stop all mutators. Some details remain.

But, I think we are close to ready to start integrating in Guile. Atfirst this is just porting Guile to use the Whippet API to access BDWinstead of using BDW directly. This whole thing is a side project forme that I work on when I can, so it doesn't exactly proceed at fullpace. Perhaps this takes 6 months. Then we can cut a new unstablerelease, and hopefully release 3.2 withe support for the Immix-flavoredcollector in another 6 or 9 months.

I thought that we would be forced to make ABI changes, if only becauseof some legacyAPIsassume conservative tracing of object contents. But after a discussionat FOSDEM with Carlo Piovesan Irealized this isn't true: because the decision to evacuate or not ismade on a collection-by-collection basis, I could simply disableevacuation if the user ever uses a facility that might prohibit objectmotion, for example if they ever define a SMOB type. If the user wantsevacuation, they need to be more precise with their data types, buteither way Guile is ready.

And that's it! Thanks for reading all the way here. Comments are quitewelcome.

As I mentioned in the very beginning, this talk was really about Whippetin the context of Guile. There is a different talk to be made aboutGuile+Whippet versus other language implementations, for example thosewith concurrent marking or semi-space nurseries or the like. Yetanother talk is Whippet in the context of other GC algorithms. But thisis a start. It's something I've been working on for a while now alreadyand I'm pleased that it's gotten to a point where it seems to be atleast OK, at least an improvement with respect to BDW-GC in some ways.

But before leaving you, another chart, to give a more global idea of thestate of things. Here we compare a single mutator thread performing aspecific microbenchmark that makes trees and also lots of fragmentation,across three different GC implementations and a range of heap sizes.The heap size multipliers in this and in all the other tests in thispost are calculated analytically based on what the test thinks itsmaximum heap size should be, not by measuring minimum heap sizes thatwork. This size is surely lower than the actual maximum required heapsize due to internal fragmentation, but the tests don't know about this.

The three collectors are BDW, a semi-space collector, and whippet.Semi-space manages to squeeze in less than 2x of a heap multiplierbecause it has (and whippet has) a separate large objectspacethat isn't ever evacuated.

What we expect is that tighter heaps impose more GC time, and indeed wesee that times are higher on the left side than the right.

Whippet is the only implementation that manages to run at a 1.3x heap,but it takes some time. It's slower than BDW at a 1.5x heap but betterthere on out, until what appears to be a bug or pathology makes it takelonger at 5x. Adding memory should always decrease run time.

The semi-space collector starts working at 1.75x and then surpasses allcollectors from 2.5x onwards. We expect the semi-space collector to winfor big heaps, because its overhead is proportional to live data only,whereas mark-sweep and mark-region collectors have to sweep, which isproportional to heap size, and indeed that's what we see.

I think this chart shows we have some tuning yet to do. The rangebetween 2x and 3x is quite acceptable, but we need to see what's causingWhippet to be slower than BDW at 1.5x. I haven't done as muchperformance tuning as I would like to but am happy to finally be able toknow where we stand.

And that's it! Happy hacking, friends, and may your heap sizes be everrighteous.