CODEWITHSUNDEEP
garbage-collectioncode-generation
Deep Thought
Deep Thought

Reputation: 1249

Efficient GC write barrier in generated C

I'm designing a system that up-front compiles CIL bytecode. In order to keep it relatively simple and also make it very portable, the system will emit C source code (however with all higher-level constructs like OOP factored out) instead of machine code. The intention is that a standard C compiler for the target platform will then be used on that code to get the end product.

Initially I intend to use a very simple GC approach such as stop-the-world. However, while the application doesn't require stellar performance, it does need decent performance, so eventually the GC may need to be changed.

I'm thinking ahead to eventually a more sophisticated GC requiring some sort of write barrier. I've looked at SATB and card marking approaches but I'm not ready to actually plan out a good GC yet. I just don't want to shoot myself in the foot by having the thing emit C source code only to later find that an efficient GC write barrier will demand inline assembly, largely defeating the purpose of emitting C.

So, my question is, can typical write barriers be efficiently implemented in C code? We can assume that the C compiler has a decent optimizer. It's also already a given that the resultant "source code" will be utterly illegible, so clarity doesn't matter.

I'm guessing that - at the expense of bloating the source files even more, - it probably can be done reasonably, but I'd appreciate word from people more experienced in GC design and/or compiler internals.

Upvotes: 2

Views: 1340

Answers (1)

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

I am assuming you want a precise generational moving or copying GC.

You could have a write barrier in C; as an example, both Ocaml and MELT runtimes have generational GC with a write barrier. And qish is a generational copying GC with a write barrier, working with C.

(BTW, MELT is a domain specific language to extend GCC, and it is compiled to C, exactly like you want to do)

A more significant issue is how do you keep local pointers (and how the GC knows about them), that is the precise aspect of your GC. You may want to pack them in some local structure.... But then it could happen that the C compiler (e.g. GCC) is optimizing a bit less.

You might look into the source code of recent versions of MONO, they have a generational copying GC. Look also inside Chicken Scheme (also generating C code).

Notice that your C code generator will have to be changed to fit inside some (or yours) particular GC implementation (because each GC has slightly different invariants and expectations). Take also care of tail recursion (some C compilers, notably recent GCC, may optimize them in limited cases).

In Qish, MELT or Ocaml the write barrier (on the C side) is implemented by some macro (or inline functions) called for each touched pointer. Details are implementation specific. Your C code generator will have to take care of them.

Be careful that multi-threaded GC are difficult to design, and that debugging GC, even simple ones, takes a lot of time and is difficult.

Upvotes: 4

Related Questions