gc enhancements

[StefanKarpinski]

Some ideas for making GC faster/better:

• Store cached type inference trees in a bytecode format instead of as a Julia objects on the heap.
• Track escape bits (approximate ref counts) for objects, allowing immediate reclamation of unescaped objects.

[JeffBezanson]

GC now 2x faster due to half as many live objects. Another idea:

• Use compacting collector for small objects

[ViralBShah]

Is it also possible for the compiler to insert calls to free objects that are easily proven as temporary in a code block? That would make it possible for them to be reused in the case of loops (with the allocator being aware), and reduce the load on GC in general.

[StefanKarpinski]

That's the idea behind the escape bit tracking. If the object hasn't escaped by the time a function exists, you can free it.

[JeffBezanson]

Here's another idea I plan to implement that also takes advantage of the escape bit.

Observation: a lot of garbage was only ever referenced by the stack. Examples include re-assigned local variables, and temporaries that were only function arguments, as in a+b+c+d.

The vast majority of GC time is in traversing the object graph. So we can do a quick "minor collection" by shallow marking (just setting the mark bit on one object and not recurring inside) objects on the stack, then doing a sweep where we free objects neither marked nor escaped. This will free most young garbage in a fraction of the time, giving most of the benefit of generational collection without needing to move objects.

[StefanKarpinski]

This sounds great, but I don't understand the core of the technique:

So we can do a quick "minor collection" by shallow marking (just setting the mark bit on one object and not recurring inside) objects on the stack, then doing a sweep where we free objects neither marked nor escaped.

Can you expand on that?

[JeffBezanson]

The idea is to be able to free "obvious garbage" without needing to traverse every live object in the system. Every live object is referenced from either the stack or the heap. The escape bit marks the heap-referenced objects (plus some that may be dead). So if we mark just the stack roots (local variables and arguments), every live object is now either marked or has its escape bit set. Objects with neither are the recently-dead, like the first a in this sequence:

a = zeros(n,n)
a = zeros(n,n)

[StefanKarpinski]

Ah, I think I see what you're saying now. This relies on the mark-and-sweep having already occurred and having mark bits still set?

[JeffBezanson]

No. The escape bit is set when an object is referenced from the heap, and stays set for the object's whole life.
I will write a new procedure minor_gc that sets the mark bit on direct stack objects, then does a sweep but only frees objects with neither bit set. Sweep will still un-set any mark bits it finds set, but of course leaves escape bits alone.

[ViralBShah]

What is the current thinking on this one? Implement minor_gc and perhaps other things? Is it possible to have a gc benchmark where such things can be measured?

[JeffBezanson]

Closed by #8699