I would like to learn the important concepts behind garbage collector design. My priority is conceptual clarity, not runtime efficiency. In particular, I would like to know:What data structures are used in a garbage collector?How much overhead per object is acceptable?What triggers the garbage collection process?How stopping the world is actually implemented?
What should be kept in mind when writing a garbage collector?
design;garbage collection
Read the garbage collection wikipage then the GC handbook. Perhaps also the old P.Wilson uniprocessor GC surveyI'm not sure that your question makes a lot of sense. In practice, a GC is tightly related to the language implementation (or the bytecode virtual machine) it is targeting. Real world GC for compiled languages require deep cooperation between compiler and GC.Some few GCs are conservative, they suppose that everything which looks like a pointer may be a GC-ed pointer. A typical example is Boehm conservative garbage collector, but its implementation is tricky. I believe that coding conservative GCs is practically quite tricky (you need to deeply understand how the address space is managed on your computer).Most GC are precise, they need to know exactly all the pointers (to GC-ed values) on the call stack. This is often language specific. You could have C++ classes or C macros for that, like in my qish GC (which is a generational copying GC).I would study several toy Scheme implementations, they usually have a GC.your questionsWhat data structures are used in a garbage collector?I'm not sure it is relevant. You just need to be able to traverse the pointers for local variables (on some call stack, either the machine call stack or more frequently your interpreter's call stack), and you need to scan every pointer in your values (or GC-ed objects). Of course, your GC-ed object may have some (language specific) data structure. And some GCs have complex data structures for efficiency reasons (answering quickly to the two main questions: what are the local pointers in this call frame? what are the pointers in this object or GC-ed value).How much overhead per object is acceptable?Define what you mean by overhead. Some GC-s don't have per object overhead (especially because the language may bring its own overhead -i.e. metadata, class pointer, vtable- which can partly be reused by the GC). They can have a system-wide overhead (e.g. naive copying GC are using only half of the memory).What triggers the garbage collection process?It depends. Usually the object allocator could trigger GC, e.g. get some memory and if none is available, do a GC.How stopping the world is actually implemented.Stop the world is a property of GCs (the simplest ones, which complete the GC while application code -a.k.a. mutator- is stopped).missing questionsYou forgot several questions.What is a closure, and why functional languages want a GC? Read also about continuations....How to make a multi-threaded friendly GC?These questions are documented.Notice that GC are conceptually easy (they are just scanning entirely a graph of references). A naive mark-and-sweep GC for a language whose implementation you know intimately (e.g. that you are implementing right now) is very easy to code (a few dozens or hundreds of lines). What is hard is to debug them and to implement efficient GCs.A mark&sweep GC is conceptually very easy:keep a mark flag or bit in every GC-ed value; allocate values with the mark bit clearedbe able to iterate on every values (even the dead ones). You could e.g. allocate fixed-size values in a big array, or manage a linked list or a vector of (pointers, internal to the GC, to) them.code a recursive marking routine (which avoid marking twice by skipping already marked values)mark all the local and global variables, and recur the marking routine (mark phase)delete every non-marked value (sweep phase)Copying (notably generational copying) or compacting GC are a bit more complex. You'll probably need to understand what is a write barrier and you'll need to implement it. Debugging a GC could be painful. With a recent gdb, you could use watchpoints and script the debugger in Python.practical adviceCode a tiny interpreter (e.g. of some tiny Lisp, or some language with closures or objects) and code the GC at the same time, while reading some GC books.