Green Tea GC: inside the implementation

This is Part 2 of a series on Go’s Green Tea garbage collector. Part 1 covers the core insight. Part 3 covers benchmarking. Part 4 covers SIMD acceleration in Go 1.26.

In Part 1, I explained the insight: work with spans, not objects. Now let’s look at how that’s actually implemented.

I find that understanding the data structures helps internalize why something works. When a teammate asks “why is Green Tea faster?”, being able to sketch spanInlineMarkBits on a whiteboard is worth more than memorizing benchmarks.

The core data structure: inline mark bits

Each small object span stores mark and scan bits at the end of the 8 KB span:

type spanInlineMarkBits struct {
    scans [63]uint8         // objects already scanned
    owned spanScanOwnership // tracks mark count for fast-path
    marks [63]uint8         // objects discovered (marked)
    class spanClass         // size class info
}

This 128-byte structure is the heart of Green Tea. Let’s break it down:

marks: Set when a pointer to an object is first discovered. Atomic operations ensure thread safety across GC workers.
scans: Set when the object has been scanned (its pointers followed).
owned: Tracks how many marks have been set (none, one, many). Enables a fast-path when only one object is marked.
class: Size class stored inline, avoiding mspan lookups.

The difference marks - scans tells you what work remains!

Why 63 bytes for marks/scans? An 8 KB span with 16-byte objects (the smallest size class using Green Tea) holds 504 objects. The 63 bytes × 8 bits = 504 bits covers exactly this case. Larger size classes need fewer bits, so 63 bytes handles all supported sizes while staying cache-friendly at 128 bytes total.

Span queues: FIFO, not LIFO

Traditional GC workbufs use LIFO (stack) ordering. Green Tea introduces span queues with FIFO ordering:

type spanQueue struct {
    head, tail     uint32
    ring           [256]objptr        // P-local FIFO ring buffer
    putsSinceDrain int                // triggers periodic spilling

    chain struct {
        head *spanSPMC                // put to this (producer only)
        tail atomic.UnsafePointer     // steal from this (consumers)
    }
}

Each P (processor) has its own span queue. The ring buffer handles the common case. When it fills, spans spill to a single-producer multi-consumer (SPMC) chain for work stealing. The putsSinceDrain counter triggers periodic spilling even when the ring isn’t full, ensuring work becomes available to other Ps.

Why FIFO?

From the source comments:

We track these spans in work queues with a FIFO policy, unlike workbufs which have a LIFO policy. Empirically, a FIFO policy appears to work best for accumulating objects to scan on a span.

LIFO for objects makes sense: you want depth-first traversal to keep related objects in cache. But for spans, FIFO lets them sit in the queue longer, accumulating more marked objects before being scanned.

Think of it this way: if you scan a span immediately after adding it, you might only process one or two objects. If you wait (FIFO), more pointers into that span might be discovered, and you’ll scan ten objects in one cache-friendly pass.

The compact pointer representation

Green Tea needs to efficiently track which span and which object within a span:

type objptr uintptr  // span base | object index

A single word encodes both the span base address (high bits, aligned to 8 KB) and the object index (low bits). No separate allocation needed.

The work priority order

Green Tea adds span queues to the existing work queue hierarchy:

Priority	Queue	Scope	Function
1	Object workbufs	P-local	`tryGetObjFast`
2	Span queue	P-local	`tryGetSpanFast`
3	Object workbufs	Global	`tryGetObj`
4	Span queue	Global	`tryGetSpan`
5	Span stealing	Cross-P	`tryStealSpan`

Note: objects before spans at each scope level. This is intentional. By processing discovered objects first, we give spans time to accumulate more marks.

The scanning algorithm

Step 1: pointer discovery

When the GC finds a live pointer (in tryDeferToSpanScan):

1. Check if span uses inline mark bits (16-512 byte objects).
2. If already marked → return early (common case).
3. Set mark bit atomically: atomic.Or8(&marks[objIndex/8], mask).
4. If noscan object (no pointers) → count bytes, done.
5. Try to acquire span ownership (tryAcquire).
6. If acquired → enqueue span to P-local spanQueue.

The ownership mechanism is key. Only one worker can “own” a span at a time. When you acquire ownership, you’re promising to scan it. Other workers discovering pointers into that span just set mark bits. They don’t enqueue it again.

Step 2: span scanning

When a span is dequeued (in scanSpan):

1. Release ownership (gets upper bound on marks set).
2. If only ONE mark → fast-track single object scan.
3. Otherwise: merge marks into scans, compute diff (toScan).
4. If dense (≥1/8 objects marked) AND SIMD available → use ScanSpanPacked.
5. If sparse OR no SIMD → use scanObjectsSmall (individual objects).
6. Process resulting pointers, try to defer to span scan again.

The dense/sparse distinction matters for performance. If many objects in a span are live, it’s worth using a more aggressive (potentially SIMD-ready) scanning approach. If only a few are live, iterate over just those.

This is Mechanical Sympathy in action: adapting the algorithm to the hardware’s preferences.

Why only small objects?

Green Tea applies to small objects: 16-512 bytes on 64-bit platforms, 16-128 bytes on 32-bit. (The upper threshold is PtrSize × PtrBits). Larger objects use the traditional per-object approach. Several reasons:

Where the problem is: Small objects are numerous and scattered. Large objects have enough work per object to amortize the cache miss cost.
Structural fit: The inline mark bits structure fits at the end of an 8 KB span. Larger size classes don’t pack neatly.
Future optimization: The packed structure is designed for potential SIMD optimization. Small, regular-sized objects work well with vector operations.

The ownership protocol

Span ownership uses a carefully designed atomic protocol that tracks how many marks have been set:

type spanScanOwnership uint8

const (
    spanScanUnowned  spanScanOwnership = 0
    spanScanOneMark                    = 1 << iota // one mark relative to scans
    spanScanManyMark                               // multiple marks relative to scans
)

These are bit flags that get OR’d together. The states enable an optimization:

Unowned: No marks yet, span not acquired
OneMark: Exactly one object marked. Fast-track it without the merge-and-diff overhead
ManyMark: Multiple objects marked. Do the full scan

When only one object is marked, scanSpan skips the expensive bitset operations and directly scans that single object. This fast path matters because many spans end up with just one or two live objects.

What this looks like in practice

Here’s the flow for a typical pointer discovery:

Worker 1 finds pointer to Object A in Span X
  → Sets marks[A] = 1
  → Acquires span (ownership = OneMark)
  → Enqueues Span X to local spanQueue

Worker 2 finds pointer to Object B in Span X
  → Sets marks[B] = 1
  → Tries to acquire, fails (ownership |= ManyMark, now OneMark|ManyMark)
  → Done (Span X already enqueued)

Worker 1 dequeues Span X
  → Releases ownership, sees value > OneMark (meaning "many")
  → Merges marks into scans, computes diff
  → Scans both A and B sequentially
  → Good cache locality: A and B are in same 8 KB region

Compare to the old approach where Workers 1 and 2 would both enqueue their objects separately, potentially causing two separate cache-miss-heavy passes through similar memory regions.

The code structure

If you really want to read the implementation, here goes nothing:

mgcmark_greenteagc.go:
- spanInlineMarkBits - the core structure
- spanScanOwnership - mark count tracking
- tryAcquire/release - ownership protocol
- tryDeferToSpanScan - pointer discovery
- spanQueue - FIFO span queue
- scanSpan - span scanning
mgcwork.go
- tryGetObjFast/tryGetObj - object queue access
- tryGetSpanFast/tryGetSpan - span queue access (Green Tea)
- tryStealSpan - work stealing (Green Tea)

The fallback file mgcmark_nogreenteagc.go is much simpler: a bunch of stub implementations that route everything through the traditional path.

Next: Part 3: Benchmarking reality check. How to actually test Green Tea on your workload, the benchmarking gotchas that will waste your time, and why DoltHub saw zero improvement in production.