Good question, it wasn't technically required. But I did a few experiments/measurements and ended up with the choice of the Cheney algorithm, which is a moving collector, and must be precise.

The Cheney algorithm has a number of nice properties. One is that it can be implemented portably with an 8 byte header on each object, which I think is important. A portable mark and sweep would be at least 16 bytes, maybe 24.

There is some discussion about that here:

https://old.reddit.com/r/ProgrammingLanguages/comments/i8u96...

e.g. I do NOT assume that the heap is an array, because that's an assumption that you can't make in standard C or C++. You have to drop down to a lower level to make that assumption; that's what I mean by portable. It's portable in the same sense that Lua is (but CPython is not, which I discovered by hacking on it a lot). Most GCs use a lot of platform-specific code to be fast, and must be ported between platforms. I wanted to avoid that in Oil, and it makes a big difference. It constrains the problem a lot.

An issue is that Oil is written for correctness, but the tradeoff is a style that allocates a lot of tiny objects, e.g. for the lossless syntax tree: https://www.oilshell.org/blog/2017/02/11.html (In contrast bash and other shells reuse homogeneous structs to represent code, without clear invariants.)

So given all the tiny objects, e.g. 8, 16, or 24 byte objects, the difference between and 8 byte and 16 byte header is significant (I measured).

Also, the Cheney algorithm is proportional to the live set (i.e. there is no sweep). So that seems like a nice property to have for this workload.

I think you can make mark and sweep fast/compact, but you ALSO have to basically write your own allocator, and I didn't want to do that. I did some tests with the system allocator and it was quite slow. On the other hand, the Cheney algorithm naturally uses a bump allocator.

I don't claim this is the best possible solution, but it seems OK so far. One things I've learned is that GCs are full of compromises; it's a very big design space. There "GC handbook" covers some implementation issues (in addition to algorithms), but I think there is a pretty big gap / "practitioner lore".

-----

As for why writing a GC is hard, here is my experience:

1) A GC for C or C++ is significantly different engineering-wise from writing a GC for a language WRITTEN in C or C++ (e.g. CPython). In other words, Oil's GC is for the metalanguage, not the language. This is not covered that well in books IMO; the books mainly talk about algorithms. Applying an algorithm to (a subset of) C++ vs. an interpreter written in C++ is a pretty different engineering job.

2) Lots of people said that finding the root set is the real problem; not the GC algorithm, and I got to experience that first hand.

3) The GC has a large surface area to interact with the rest of the program. In a sense, it's not modular; it's peeking/freeing/moving all over the place, which is harder than writing a modular piece of code.

4) The bugs are nonlocal (i.e. finding the source from the symptom is hard)

I read some of the warnings in this chapter before implementing a GC, and honestly I didn't really get it. After doing it, I get what they are saying (i.e. spending a lot of time in GDB and CLion tracking down non-local memory corruption bugs.)

https://craftinginterpreters.com/garbage-collection.html#gar...

5) For the moving collector, one of the main issues was that I thought turning on ASAN would help enough with the memory bugs. That was not the case; I really needed an #ifdef GC_EVERY_ALLOC, and that flushed out the bugs. In fact the es shell paper even tells you to do that, and I read it, but I failed to do it the first time around. It would have saved me a lot of time if I had followed that advice! ASAN found some bugs, which I thought was enough, but it wasn't.

It's very obvious in retrospect because ASAN only tests the code paths you actually hit, and the GC turns EVERY ALLOCATION into a conditional -- collect or don't collect -- and this means more code paths. But somehow I did not internalize that and had to learn the hard way :)

(I was going to write a blog post about this, but I think that is most of the points! I could demonstrate a few of the tricky bugs I encountered)