Garbage Collection in a Large Lisp System (1984) [pdf]
dl.acm.org
dl.acm.org
https://github.com/sbcl/sbcl/blob/master/doc/internals-notes...
https://applied-langua.ge/~hayley/swcl-gc.pdf
build with
./make.sh --without-gencgc --with-mark-region-gc (on x86-64/Linux and x86-64/macOS only at the moment).That's a fun benchmark to have. Seems like gencgc is better than the new GC anyway wrt pause times?
>Very few objects survive garbage collection in Kandria, with less than a megabyte surviving out of a 200 megabyte nursery.
From this sentence I'm going to guess that Kandria performs a lot of per-frame allocations. Having a bump-pointer arena for this which is reset per-frame would probably be quite nice.
The Acknowledgements section is crazy haha, with mentions such as Cliff Click (OG Hotspot JIT compiler architect) and Larry Masinter (Xerox PARC Interlisp) along with the nice SBCL and Kandria devs.
At that time the GC didn't compact, and so much time was wasted scavenging and sweeping the old objects. Old objects aren't contiguous due to not moving objects, though we try to avoid reading from the heap; we only twiddle metadata tables when sweeping and only read objects that we must scan for old->new references while scavenging. Here that wasn't sufficient:
> As a result, scavenging took 2.9 milliseconds on average, tracing took 1.9 milliseconds, and sweeping took 1.6 milliseconds.
Ideally scavenging and sweeping would take much less time than tracing. I think it should behave better now with compaction, but haven't benchmarked; and my approach to benchmarking Kandria is pretty sloppy in any case.
> Having a bump-pointer arena for this which is reset per-frame would probably be quite nice.
Indeed SBCL has support for arenas (though AIUI no stable user-facing interface at the moment), but it still takes some effort to work out what goes in the arena, and the current interface in SBCL also requires all libraries to know about arenas which isn't great for retrofitting.
> The Acknowledgements section is crazy haha, with mentions such as Cliff Click (OG Hotspot JIT compiler architect) and Larry Masinter (Xerox PARC Interlisp) along with the nice SBCL and Kandria devs.
I can't take much of the blame for much of the design; much of it was collaborated in the #lispcafe channel on Libera, which ostensibly is the "off topic" channel. Well. Also worth mentioning that Cliff Click also worked on parallel/concurrent GC and other parallel algorithms, so he was most helpful with interpreting the performance of this GC.
I’m not sure I’d want to implement forwarding pointers without hardware support for transparency.
(The mutator also won't ever see forwarding pointers regardless, if you have a STW GC. And if that GC works.)
Examples:
The whole v8 lineage of VMs, and SpiderMonkey followed shortly thereafter
Java Hotspot and most fast alternatives
Femtolisp used to bootstrap Julia is a moving GC with no generations
Forwarding is not really a problem, the algorithm is well known
Rooting is a difficult problem in many contexts — both C and webassembly.
You need precise rooting to implement moving GC, that’s the main implementation issue
(On my phone, sorry no links)
https://www.oilshell.org/blog/2022/10/garbage-collector.html
https://www.oilshell.org/blog/2023/01/garbage-collector.html
AFAIK, the Cheney algorithm is the only way to do copying/moving GC. It's tiny and elegant, and I took a picture of it for a contributor:
https://app.oilshell.org/picdir/resize?name=193n849__4477C23...
The GC handbook explanation was better than anything I found online, including in wikipedia.
But GC handbook is also not engineering-focused (see blog posts). It surprisingly difficult to write a GC -- I have new respect for this problem!
As mentioned, we ended up going to a non-moving collector, mainly because debugging is harder, it breaks tools, and it involves even more rooting. And rooting problem is hard, especially in C/C++.
The GCs in C++ like v8 and SpiderMonkey are a bit hard to read -- it is almost like a special dialect of C++. I found the plain C femtolisp and es shell easier to read. And some toy examples on Github, but many of them (even from engineers I know to be great) were VERY incomplete, and not designed in context.
Don't trust an example GC that hasn't been used in production! It probably has bugs or a bad API for rooting!
femtolisp is probably the closest thing to "small" and "used in production" that I found (since it's used to bootstrap Julia)
I understand it’s not a problem to make forwarding work, but making it not suck doesn’t seem easy. My impression from the literature was that a moving collector requires either an O(heap) pause + write barrier (to rewrite all pointers at once), or a read barrier (to catch stale pointers on the fly), and neither of these options is all that pleasant—read barriers in particular are often decried as expensive.
On the other hand, the articles doing the decrying are usually using a SPARC or the like as their reference point for up-to-date powerful hardware, so I’ve no idea how true any of this is in today’s superscalar world.
- you don't want the 2x space overhead for your entire heap
- I don't know that any copying/moving GCs are incremental. You just collect the young objects all at once -- the CLR says they aim to make it cost as much as a page fault.
I don't know the common policies offhand, but I imagine the young generation is like 512 KB to 4 MB, so it will fit in caches. The whole point is bump allocation and locality
I don't have experience with GCs where the mutator dereferences through a pointer -- my impression is that's rare, but I'm not sure.
In the normal Cheney collector, the forwarding pointers are only used during the algorithm itself. It has to update pointers for the mutator, but after that, the mutator does normal dereferencing.