Elise: A Concurrent Garbage Collector for the DOM

A while ago, I needed a garbage collector for a DOM-related project. Using v8 was a no-brainer, since it comes with a built-in GC called cppgc. However, as development went on, I noticed it was rather slow in some scenarios. Sometimes it was so slow that I couldn't ignore it. At first, I tried tuning its configuration and removing as many unnecessary wrappers as I could, but the improvement was very limited. So I started looking into the structure of cppgc. It turns out v8 has more than one GC. cppgc is the one for DOM objects, while the JavaScript side has its own GC. The two are integrated into a unified heap so they can work with each other, which means cppgc has to make some compromises. For example, generational collection is disabled, and huge chunks of sweeping happen on the main thread. But one of the main blockers for me is conservative stack scanning. The project I'm working on also needs to work with Wasmtime. Given its philosophy and design decisions, I think a precise GC is a must. So eventually, I decided to build a new GC from the ground up. Introducing Elise: a concurrent garbage collector for the DOM.

Precise Garbage Collection

The main design decision behind Elise is, of course, that it's a precise GC. The mutator runs in operations (Heap::mutate), and no GC happens inside one. So a Gc<'gc, T> is a raw pointer branded with the operation's lifetime, nothing scans the stack, and roots are explicit (Persistent<T>). Pointers are also compressed: each heap reserves a 4 GiB cage, and an edge (Member<T>) is a 32-bit offset into it. Finalizers can't touch the heap. Native data lives in External<T> (dropped on a sweeper thread) or LocalExternal<T> (dropped on the heap's thread). Since finalizers can't reach other GC objects, it won't read an object that has already been collected. Here's an example of what it looks like:

use std::cell::Cell;
use elise::{GcObject, Heap, HeapOptions, Member, Persistent};

#[derive(GcObject)]
struct Node {
    parent: Member<Node>,
    id: Cell<u32>,
}

let mut heap = Heap::new(HeapOptions::default());

// ── Operation 1 ─────────────────────────
let root = heap.mutate(|cx| {
    let parent = cx.alloc(NodeInit { parent: None, id: Cell::new(1) });
    let child  = cx.alloc(NodeInit { parent: Some(parent), id: Cell::new(2) });

    // `parent` and `child` are raw pointers: used directly here, and no GC
    // runs while the operation does.
    assert_eq!(child.parent.get(cx).unwrap().id.get(), 1);

    // To leave the operation, an object is registered as a root.
    Persistent::new(cx, child)
});
// ── Safepoint: the operation is over, a GC may run here ──

// ── Operation 2 ─────────────────────────
heap.mutate(|cx| {
    let child = root.get(cx);            // read back from the root
    let parent = child.parent.get(cx).unwrap();
    assert_eq!(parent.id.get(), 1);      // `parent` lives: `child` points to it
});

And the best part is that the 'gc lifetime prevents the pointer from moving out of its scope. The example below is already rejected at compile time:

let leaked = heap.mutate(|cx| {
    // Returns the raw pointer itself: its `'gc` is the closure's, so this
    // doesn't compile.
    cx.alloc(NodeInit { parent: None, id: Cell::new(1) })
});

Generational, with a Non-Moving Old Generation

Elise has a new generation and an old generation. New objects go to a nursery collected by a parallel scavenger. An object that survives its first scavenge stays in the nursery; one that survives a second is promoted to the old generation. The old generation uses mark-sweep and is never compacted.

Regarding fragmentation: on DOM workloads, picking pages to evacuate the way V8 does frees almost no pages, because allocation after a sweep refills the free slots of the fullest pages first. On these workloads, fragmentation isn't a problem, so I didn't build moving compaction.

Allocation sites can also be pretenured: once a site has allocated at least 100 objects in the nursery and 80% or more of them survived their first scavenge, later allocations from that site go straight to the old generation. The decision is withdrawn if a full GC finds fewer than 10% of the site's old objects still alive.

Concurrent Marking and Sweeping

Elise’s old generation is mark-sweep. Both phases run on worker threads alongside the mutator, which pauses only briefly to start and finish a cycle. A cycle starts at a safepoint once the old generation reaches half its limit: a scavenge empties the nursery, the objects the roots point to are marked, and the workers take over the rest. It ends at the first safepoint after they finish.

Because the mutator keeps changing the graph, a worker could miss a live object, for instance when an edge moves from an unscanned object to a scanned one. Elise prevents this with a snapshot-at-the-beginning (SATB) barrier: before an edge is overwritten, its old target is marked. Objects allocated during marking are alive too, since each free range is marked as a whole when it's taken, so allocation does no extra work. V8 and cppgc mark the new value instead, which leaves less floating garbage but means rescanning the roots and the stack at the end. In Elise, the stack holds no pointers at a safepoint, so SATB keeps the final pause short, at the cost of collecting objects that die during marking one cycle late.

Sweeping reads only the mark bitmaps: a single worker works out each page's free ranges without touching the objects, and the mutator applies the results at later safepoints. One worker is enough, since sweeping a page takes less time than waking a thread. If allocation can't find a swept page of the right size, the mutator sweeps one itself.

Soundness

All APIs of Elise are safe, but we still need to use unsafe internally. To prove Elise's correctness, several tools and features are made. Elise has a heap verifier(HeapOptions::verify) which switched on in tests and fuzzing, walks the heap again from the roots after every collection with code that shares nothing with the marker or the scavenger, and checks the mark bits, the pages’ accounting and the remembered sets. The protocol for marking together with a JS engine was model-checked exhaustively in TLA+. The search over a page’s bitmap is proved correct in Verus. On top of these, the collector is fuzzed, its parallel code runs under loom and shuttle, and its tests run under Miri.

Performance

The full benchmark results are in the repository's benchmark report, but they're written in Traditional Chinese. Here's a shorter summary in English.

Against cppgc

Time spent in GC when replaying the allocations of real pages (main thread, ms):

cppgc has no young generation, so the gap is widest where most objects die young.

Against V8's Own GC

The same object graphs (main thread, ms):

Longest Single Pause

All times are in milliseconds. There's no ratio here, because what matters is whether a pause fits in a frame (16.7 ms).

Overall, Elise outperforms cppgc in many ways, and it can work with both V8 and Wasmtime. That said, there are still some compromises to be made. The young generation is still disabled when working with V8, since its JS objects aren't movable. Joining V8's unified heap also adds some overhead. But these issues are all on the JS side; working with Wasmtime is a much simpler story. And I believe there's still plenty of room for improvement.

At the time of writing, Elise is at version 0.3. I plan to release 1.0 by the end of the year. Stay tuned, and see you soon!