5 ms·

> writing a garbage collector has been harder than I expected. I hear that from everyone. I am looking to write one in the future, so interested to see how thi

> writing a garbage collector has been harder than I expected. I hear that from everyone. I am looking to write one in the future, so interested to see how this went. > One reason for this is the unusual set of requirements: it's moving, precise, and written almost entirely in portable C++. We use it for both a little hand-written code and a lot of generated code. I understand the portability requirement, but I wonder why it was required to be precise and moving.

chubot 6y ago
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/i8u96f/implementations_of_copying_garbage_collector/ 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 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#garbage-collection-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)
- celeritascelery 6y ago
  This was a really interesting read! Sent me down a rabbit hole following all the links and references you mentioned. I know you said this is a pretty simple implementation, but it still seems like it was a beast to debug.
ilyash 6y ago
> writing a garbage collector has been harder than I expected. That is exactly why I have chosen to use a library for (shameless plug) Next Generation Shell. Edit: Well, not exactly. I did expect. At the start of the project it looked roughly the same amount of effort as the rest of the language (at least some early version of the language). The library: https://en.wikipedia.org/wiki/Boehm_garbage_collector https://en.wikipedia.org/wiki/Boehm_garbage_collector This decision can be reviewed when performance or other requirements become clear. Meanwhile I have invested relatively small amount of time into integrating the GC library.

chubot 6y ago

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/i8u96f/implementations_of_copying_garbage_collector/ 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 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#garbage-collection-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)

celeritascelery 6y ago
This was a really interesting read! Sent me down a rabbit hole following all the links and references you mentioned. I know you said this is a pretty simple implementation, but it still seems like it was a beast to debug.

ilyash 6y ago

> writing a garbage collector has been harder than I expected. That is exactly why I have chosen to use a library for (shameless plug) Next Generation Shell. Edit: Well, not exactly. I did expect. At the start of the project it looked roughly the same amount of effort as the rest of the language (at least some early version of the language). The library: https://en.wikipedia.org/wiki/Boehm_garbage_collector https://en.wikipedia.org/wiki/Boehm_garbage_collector This decision can be reviewed when performance or other requirements become clear. Meanwhile I have invested relatively small amount of time into integrating the GC library.