JuliaLang/julia — pull request #5227 by carnaval (2013-12-23 19:58:02+00:00)
Title: WIP: Incremental GC

This is work I started when hitting long GC pause in a soft realtime application. No matter how low you can bring the allocation count down (and the language admittedly makes it easy), there is still a point where you must wait for tens of ms which is a pain in, e.g., render code at 60 fps.

To be clear this is only incremental marking, but incremental sweeping should be much easier.
This patch :

- Adds a new gc bit on each type field of each julia object which records if it is scheduled for marking (the so called grey bit)
- Adds a write barrier to all pointer stores to gc-managed slots (in C runtime and codegen)
- Make the GC able to run partial marking phase
- Adds a verifier which can run before each sweep to verify we did not miss a write.

Some points :
- The write barrier is explicit in C code. Most of it looks like :
```
a->b = ...;
gc_wb(a, a->b);
```
This is ugly and could be resolved with a macro (something like ```gc_store(a, b, ...);```) but I was not sold on changing such pervasive syntax.
- The current heuristics are quite bad : the collect interval is simply divided by 10 and partial markings works with an increasing timeout (1ms then 1.3*previous_timeout). I expect some low hanging fruits for efficiency here, if only because I chose those constants arbitrarily ;)
- Performances : nothing is free so there is a perf hit. I believe it could be brought down as I was mainly focused on getting it correct until recently. My measurements are on running the full test suite. It takes about 10% more time to run but the pause times (for the mark phase) goes down from : max 40ms, 95% sub 30ms to max 5ms, 95% sub 2ms.
- Even if low-pause is not a focus point for the julia community ATM, the write barrier can be used to make the GC generational. In fact, you could turn this PR into a poor man's generational GC simply by not reseting the marks at the end of a sweep. I did not experiment in this direction yet, but doing it properly would require the GC to support moving, which is its own can of worms.

To enable, build with -DGC_INC. GC_VERIFY enables the verifier and GC_TIME prints pause timings.

Of course, feedback is much appreciated. Cheers !