Garbage collection when compiling to C

Question

What are the techniques of garbage collection when compiling a garbage collected language to C? I know of two:

1. maintain a shadow stack that saves all roots explicitly in a data structure

2. use a conservative garbage collector like Boehm's

The first technique is slow, because you have to maintain the shadow stack. Potentially every time a function is called, you need to save the local variables in a data structure.

The second technique is also slow, and inherently does not reclaim all garbage because of using a conservative garbage collector.

My question is: what is the state of the art of garbage collection when compiling to C. Note that I do not mean a convenient way to do garbage collection when programming in C (this is the goal of Boehm's garbage collector), just a way to do garbage collection when compiling to C.

Answer 1

Potentially every time a function is called, you need to save the local variables in a data structure.

No, you don't - you can leave the local variables on the C stack and still iterate through them: put all reference variables in an array and add a pointer to that to a linked list to which you append a node when entering a new stack frame.

Mockup:

struct vm
{
    struct scope *root;
};

struct scope
{
    struct scope *prev, *next;
    size_t size;
    struct ref *refs;
};

void foo(struct vm *vm, struct scope *caller)
{
    struct ref local_refs[42];
    struct scope scope = {
        caller, NULL, sizeof local_refs / sizeof *local_refs, local_refs };

    caller->next = &scope;

    // ...

    caller->next = NULL;
}

However, you'll have to jump through some major hoops if you want to support continuations/non-local jumps. In that case, it's easier to heap-allocate everything.