Stateful garbage collection: only process what changed

A tracing collector pays for the live heap on every cycle: the mark phase rediscovers every reachable object, including the ones that haven't changed since the last collection. Concurrent and generational collectors move that work to other cores or postpone it, but the old generation still has to be traced eventually.

A stateful collector keeps the result of the previous collection and only processes what changed since then. A collection over a million live objects that weren't modified takes a few microseconds. This is the strategy the Valk programming language uses, and its implementation provides the examples and measurements below.

The model#

The state the collector keeps is ownership. An owned object is owned either by the stack or by exactly one reference in another object, so the owner references form a spanning forest of the live heap, rooted at the stack and globals. Every other reference to an owned object is counted. An object that nothing long-lived has claimed yet is new. Because what it tracks is ownership, this kind of collector can also be called an ownership collector.

The state lives in an 8-byte header per object, which holds the ownership state, a few flags and the count, and in the two low bits of every reference field, which mark the reference as owner, counted or not yet processed. Reads mask those bits off.

The compiler emits a write barrier on every store of a reference into an object. A store into a new object is a plain store, because the object is traced as a whole once it's claimed. The first store into an owned object after a collection appends the object to a change log, and a flag in its header makes later stores to it take the fast path. References on the stack aren't counted while the program runs; the stack is scanned at every collection instead.

A collection scans the roots, processes the change log and the references that were overwritten, and claims or releases the subgraphs whose state changed. Owned objects that weren't written to aren't visited, however many there are.

Readers who know the literature will recognise coalescing reference counting with deferred stack references, as in Levanoni and Petrank's collector or LXR. The difference is the owner tree: releasing walks the tree of the released objects, which also frees garbage cycles, and the owned state acts as a sticky mark bit, so the stable heap is never marked again without needing generations or copying.

Two collections, step by step#

The figure runs two collections on a small heap. Between them the program rewrites a few references, creates temporary objects and builds a cycle. Every collection goes through the same phases:

1. Roots. Scan the stack and globals. Objects that newly appear there are claimed; objects that dropped off lose their owner.
2. Change log. Each overwritten reference in a logged object takes away the target's owner, or lowers its count.
3. Release. Every object without an owner is freed, together with everything it owns. The counts that the freed objects held on others are removed on the way.
4. Claim. New references in logged objects claim the objects they point at. A reference to an object that's already owned only adds to its count.
5. Re-claim. A released object whose count is still above zero is referenced from outside, so it's claimed again with everything it owns.

Most of the heap is never visited, and there's no sweep: releasing an object only marks its slot as free again.

Cycles#

Cycles need no separate detector. When the collector claims a structure, the reference it first reaches an object through becomes the owner, and any other reference, including the one that closes a cycle, is only counted. Every cycle therefore contains at least one counted reference.

When the owner reference disappears, the release walk frees the cycle and removes its internal counts. If the cycle is still referenced from outside, the count that's left makes the re-claim phase keep it. Otherwise it stays freed. The figure above shows both: the first collection frees a cycle that nothing else points into, and the second keeps a cycle that's still referenced. Garbage cycles are freed by the same walk that frees any other structure, with no periodic scan.

Short-lived objects#

An object that dies before the next collection never leaves the new state. The collector never marks it, never copies it and never looks for it; the allocator simply hands its slot out again. Generational collectors get a similar effect from their nursery, but they copy the objects that survive. A stateful collector doesn't move objects: one that becomes owned stays where it is and is skipped from then on.

The trade-offs#

The work is proportional to what changed, and sometimes a lot changes at once. Dropping the last reference to a large structure means walking it to release it, and moving a structure under a new owner means releasing it and claiming it again. In the program below, dropping a list of a million nodes makes the next collection take about 14 ms, where a tracing collector would only pay for what's still alive.

Every store of a reference into an object goes through the write barrier. Its fast path is a few instructions, but a program that keeps rewriting references in long-lived objects pays for it on every write.

Everything above concerns memory that belongs to a single thread. Objects shared between threads can change concurrently, so Valk handles them with a separate collector, which is a topic for another article.

Measuring the difference#

The Valk repository includes GC benchmarks with matching programs in Go, D and C#.

The stable-heap scenario keeps 500,000 linked objects alive and forces 500 collections, which isolates the difference in strategy. The tracing collectors mark the same list again every time, at 5 to 8 ms per collection; the stateful collector has nothing to do. The rows it doesn't win are the trade-offs above: freeing a large structure, and rewriting links in a live list. Its largest wins come from many short-lived objects next to a large live set.

The same effect in a few lines: this program keeps a million objects alive and times a few forced collections.

use valk.gc
use valk.time

class Node {
    next: ?Node (null)
}

fn timed_collect() uint {
    let start = time.mono_us()
    gc.collect()
    return time.mono_us() - start
}

fn main() {
    // One million objects that stay alive
    let list = Node {}
    let i = 0
    while i++ < 1_000_000 {
        list = Node { next: list }
    }

    println("first collection: %{timed_collect()} µs")
    println("nothing changed:  %{timed_collect()} µs")

    list = Node { next: list }
    println("one new node:     %{timed_collect()} µs")

    list.next = null
    println("drop the rest:    %{timed_collect()} µs")
}

It prints:

first collection: 392 µs
nothing changed:  5 µs
one new node:     1 µs
drop the rest:    14182 µs

The first forced collection is already cheap, because the collections that ran while the list was being built had claimed most of it.

A stateful collector moves the cost of garbage collection from how much memory is alive to how much memory changes. For programs that keep a large, mostly stable heap, that's the difference between re-proving the whole heap on every collection and not looking at it at all.