Go's Green Tea GC: Marking Whole Spans Instead of Objects

TL;DR: Go’s Green Tea GC stops marking objects one at a time and starts marking spans one at a time. Each span carries two bitmaps — “marks” (someone pointed at this object) and “scans” (we already looked inside it) — and the GC keeps a FIFO queue of spans that have new marks. When a span is dequeued, the GC computes marks &^ scans, scans exactly those objects, and folds them into the scan bits. Fewer cache misses, fewer metadata lookups, and a scan loop that can eventually be SIMD-vectorised.

Marking a heap is a memory-bound problem disguised as a graph problem. The graph is easy; the memory is not. Every pointer you follow points somewhere else in the heap, and every object you look at has metadata — its type’s pointer bitmap, its span, its mark bits — sitting in a different cache line somewhere else in the heap. A classic mark phase does millions of tiny dependent loads, and the hardware prefetcher cannot help, because the addresses are, by construction, not sequential.

Go has spent years making its allocator smarter about where objects live. The Green Tea GC attacks the other half: instead of arranging the heap to suit the marker, it changes what the marker visits.

This is a walk through the implementation in the Go 1.28 development tree (src/runtime/mgcmark_greenteagc.go and friends).

The experiment switch

Green Tea is not on by default. It is a GOEXPERIMENT, declared in the experiment flags file:

go
// src/internal/goexperiment/flags.go:109
	// GreenTeaGC enables the Green Tea GC implementation.
	GreenTeaGC bool

and resolved into a compile-time constant by the generated pair of files:

go
// src/internal/goexperiment/exp_greenteagc_on.go:5
package goexperiment

const GreenTeaGC = true
const GreenTeaGCInt = 1

go
// src/internal/goexperiment/exp_greenteagc_off.go:5
package goexperiment

const GreenTeaGC = false
const GreenTeaGCInt = 0

The runtime then has two whole implementations of the marking machinery, selected by build tag. mgcmark_greenteagc.go carries //go:build goexperiment.greenteagc; mgcmark_nogreenteagc.go carries the negation. This is not a runtime flag: the shape of the mark phase is baked into the binary, because the two versions have genuinely different data structures.

The idea, in the runtime’s own words

The file opens with the rationale, and it is worth reading verbatim because it explains every structure that follows.

go
// src/runtime/mgcmark_greenteagc.go:7
// The core idea behind Green Tea is simple: achieve better locality during
// mark/scan by delaying scanning so that we can accumulate objects to scan
// within the same span, then scan the objects that have accumulated on the
// span all together.
//
// By batching objects this way, we increase the chance that adjacent objects
// will be accessed, amortize the cost of accessing object metadata, and create
// better opportunities for prefetching. We can take this even further and
// optimize the scan loop by size class (not yet completed) all the way to the
// point of applying SIMD techniques to really tear through the heap.
//
// Naturally, this depends on being able to create opportunities to batch objects
// together. The basic idea here is to have two sets of mark bits. One set is the
// regular set of mark bits ("marks"), while the other essentially says that the
// objects have been scanned already ("scans"). When we see a pointer for the first
// time we set its mark and enqueue its span. 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.
// Later, when we dequeue the span, we find both the union and intersection of the
// mark and scan bitsets. The union is then written back into the scan bits, while
// the intersection is used to decide which objects need scanning, such that the GC
// is still precise.

Three claims in there: batching improves locality, two bitsets are needed to stay precise, and the queue policy must be FIFO. All three show up in the code.

Two bitmaps, stored inside the span

The classic Go GC stores mark bits in a separate heap bitmap (mspan.gcmarkBits), allocated from the heap and read via a span lookup. Green Tea moves them into the span itself, at the very top of the span’s page:

go
// src/runtime/mgcmark_greenteagc.go:66
type spanInlineMarkBits struct {
	scans [63]uint8         // scanned bits.
	owned spanScanOwnership // see the comment on spanScanOwnership.
	marks [63]uint8         // mark bits.
	class spanClass
}

Sixty-three bytes of marks and sixty-three bytes of scans, plus one byte of ownership state and the size class. The struct is 128 bytes (63+1+63+1, padded), which is exactly two cache lines. It lives at the end of the span:

go
// src/runtime/mgcmark_greenteagc.go:180
func spanInlineMarkBitsFromBase(base uintptr) *spanInlineMarkBits {
	return (*spanInlineMarkBits)(unsafe.Pointer(base + gc.PageSize - unsafe.Sizeof(spanInlineMarkBits{})))
}

and the pointer mask for the span sits immediately below it:

go
// src/runtime/mgcmark_greenteagc.go:1098
func spanPtrMaskUnsafe(spanBase uintptr) *gc.PtrMask {
	base := spanBase + gc.PageSize - unsafe.Sizeof(gc.PtrMask{}) - unsafe.Sizeof(spanInlineMarkBits{})
	return (*gc.PtrMask)(unsafe.Pointer(base))
}

So for a small span, the layout of one page is:

text
 0x0000                                       0x2000
  +---------------------------------------------+
  | objects (elemsize * nelems)                 |
  +---------------------------------------------+
  | pointer mask (type bitmap for the size class)|
  +---------------------------------------------+
  | spanInlineMarkBits: scans | owned | marks   |  <- last 128 bytes
  +---------------------------------------------+

That placement is the whole point. When the marker scans a span, the metadata it needs — which words are pointers, which objects are marked, which have been scanned — is in the same page as the objects themselves. Even better, it is in the same page as the objects it is about to scan, so the hardware prefetcher, which is good at sequential page-local access, has a chance to do its job.

Not every span gets this. Only spans small enough that their bitmap fits in the page, and only for object sizes of 16 bytes and up:

go
// src/runtime/mgcmark_greenteagc.go:258
func gcUsesSpanInlineMarkBits(size uintptr) bool {
	return heapBitsInSpan(size) && size >= 16
}

The per-arena bitmap tells the marker, without touching the span header, whether a given page uses this layout:

go
// src/runtime/mheap.go:317
	// pageUseSpanInlineMarkBits is a bitmap where each bit corresponds
	// to a span, as only spans one page in size can have inline mark bits.
	// The bit indicates that the span has a spanInlineMarkBits struct
	// stored directly at the top end of the span's memory.
	pageUseSpanInlineMarkBits [pagesPerArena / 8]uint8

Marks, scans, and the union/intersection trick

Here is the bit-twiddling that makes “scan a whole span” work without losing precision.

When the marker discovers a pointer to an object, it sets that object’s mark bit. It does not scan the object yet. It queues the object’s span.

Later, when the span comes off the queue, the GC needs to know two things: which objects have been marked but not yet scanned (those need scanning now), and which objects have been scanned already (those must not be scanned again — the GC has to be precise about what is live, and re-scanning is at best wasted work and at worst a correctness problem for weak references).

So it computes marks &^ scans, scans exactly that set, and ORs the result into scans:

go
// src/runtime/mgcmark_greenteagc.go:942
	bytes := divRoundUp(uintptr(nelems), 8)
	objsMarked := 0

	// Careful: these two structures alias since ObjMask is much bigger
	// than marks or scans. We do these unsafe shenanigans so that we can
	// access the marks and scans by uintptrs rather than by byte.
	imbMarks := (*gc.ObjMask)(unsafe.Pointer(&imb.marks))
	imbScans := (*gc.ObjMask)(unsafe.Pointer(&imb.scans))

	// Iterate over one uintptr-sized chunks at a time, computing both
	// the union and intersection of marks and scans. Store the union
	// into scans, and the intersection into toScan.
	for i := uintptr(0); i < bytes; i += goarch.PtrSize {
		scans := atomic.Loaduintptr(&imbScans[i/goarch.PtrSize])
		marks := imbMarks[i/goarch.PtrSize]
		scans = bswapIfBigEndian(scans)
		marks = bswapIfBigEndian(marks)
		if i/goarch.PtrSize == uintptr(len(imb.marks)+1)/goarch.PtrSize-1 {
			scans &^= 0xff << ((goarch.PtrSize - 1) * 8) // mask out owned
			marks &^= 0xff << ((goarch.PtrSize - 1) * 8) // mask out class
		}
		toGrey := marks &^ scans
		toScan[i/goarch.PtrSize] = toGrey

		// If there's anything left to grey, do it.
		if toGrey != 0 {
			toGrey = bswapIfBigEndian(toGrey)
			if goarch.PtrSize == 4 {
				atomic.Or32((*uint32)(unsafe.Pointer(&imbScans[i/goarch.PtrSize])), uint32(toGrey))
			} else {
				atomic.Or64((*uint64)(unsafe.Pointer(&imbScans[i/goarch.PtrSize])), uint64(toGrey))
			}
		}
		objsMarked += sys.OnesCount64(uint64(toGrey))
	}
	return objsMarked

The comment says “union and intersection” but the code computes a difference: marks &^ scans. The union of the two sets is marks, and the intersection is marks & scans; the objects that actually need work are the set difference, marks &^ scans. The union of the marks with what was just scanned is written back into scans.

Everything here is done a machine word at a time, with atomic ORs, because other threads may be setting mark bits concurrently. The two masking lines exist because the struct packs two non-bitmap fields into the same 128 bytes: the owned byte sits immediately after the scans array, and the size class immediately after the marks array, so each array’s final word has one byte that is not a bit.

The span queue

The mark queue for Green Tea is not a queue of object pointers. It is a queue of spans.

go
// src/runtime/mgcmark_greenteagc.go:339
type spanQueue struct {
	// head, tail, and ring represent a local non-thread-safe ring buffer.
	head, tail uint32
	ring       [256]objptr

	// putsSinceDrain counts the number of put calls since the last drain.
	putsSinceDrain int

	// chain contains state visible to other Ps.
	//
	// In particular, that means a linked chain of single-producer multi-consumer
	// ring buffers where the single producer is this P only.
	//
	// This linked chain structure is based off the sync.Pool dequeue.
	chain struct {
		// head is the spanSPMC to put to. This is only accessed
		// by the producer, so doesn't need to be synchronized.
		head *spanSPMC

		// tail is the spanSPMC to steal from. This is accessed
		// by consumers, so reads and writes must be atomic.
		tail atomic.UnsafePointer // *spanSPMC
	}
}

A per-P ring of 256 entries, plus a chain of single-producer multi-consumer rings that other Ps can steal from. The producer is always the owning P; consumers are everybody. That asymmetry is what makes the queue cheap: the fast path is a single array store, and the slow path (spilling to the shared chain) is amortised over many puts:

go
// src/runtime/mgcmark_greenteagc.go:388
	const (
		// spillPeriod defines how often to check if we should
		// spill some spans, counted in the number of calls to put.
		spillPeriod = 64

		// spillMax defines, at most, how many spans to drain with
		// each spill.
		spillMax = 16
	)

The queue holds an objptr, which is a packed span base plus object index — 16 bits of index in the low half of a word, so the span base stays page-aligned:

go
// src/runtime/mgcmark_greenteagc.go:823
// objptr consists of a span base and the index of the object in the span.
type objptr uintptr

Only the representative object matters. When a span is queued, the objptr names some object in it, but the scan ignores that particular object and scans the whole span’s pending set.

Ownership: one scanner per span

Two threads must not scan the same span concurrently, or they will duplicate work and race on the scan bits. The owned byte in the inline mark bits is the lock, and it encodes a useful hint: how many mark bits were set since the span was queued.

go
// src/runtime/mgcmark_greenteagc.go:81
const (
	spanScanUnowned  spanScanOwnership = 0         // Indicates the span is not acquired for scanning.
	spanScanOneMark                    = 1 << iota // Indicates that only one mark bit is set relative to the scan bits.
	spanScanManyMark                               // Indicates one or more scan bits may be set relative to the mark bits.
	// "ManyMark" need not be exactly the value it has. In practice we just
	// want to distinguish "none" from "one" from "many," so a comparison is
	// sufficient (as opposed to a bit test) to check between these cases.
)

If a span was queued because exactly one object was marked, there is no point in doing the union/intersection dance — the GC can fast-track that one object directly. The release() call at the top of scanSpan reports which case applies.

Scanning a span

go
// src/runtime/mgcmark_greenteagc.go:844
func scanSpan(p objptr, gcw *gcWork) {
	spanBase := p.spanBase()
	imb := spanInlineMarkBitsFromBase(spanBase)
	spanclass := imb.class
	if spanclass.noscan() {
		throw("noscan object in scanSpan")
	}
	elemsize := uintptr(gc.SizeClassToSize[spanclass.sizeclass()])

	// Release span.
	if imb.release() == spanScanOneMark {
		// Nobody else set any mark bits on this span while it was acquired.
		// That means p is the sole object we need to handle. Fast-track it.
		objIndex := p.objIndex()
		bytep := &imb.scans[objIndex/8]
		mask := uint8(1) << (objIndex % 8)
		if atomic.Load8(bytep)&mask != 0 {
			return
		}
		atomic.Or8(bytep, mask)
		gcw.bytesMarked += uint64(elemsize)
		if debug.gctrace > 1 {
			gcw.stats[spanclass.sizeclass()].sparseObjsScanned++
		}
		b := spanBase + uintptr(objIndex)*elemsize
		scanObjectSmall(spanBase, b, elemsize, gcw)
		return
	}

And then the interesting part: how many of the span’s objects are actually marked? If the span is dense — most of its objects marked — the GC uses a packed SIMD scan that walks the whole span’s worth of pointer words at once. If it is sparse, it walks object by object using the pointer mask.

go
// src/runtime/mgcmark_greenteagc.go:889
	// Check if we have enough density to make a dartboard scan
	// worthwhile. If not, just do what scanobject does, but
	// localized to the span, using the dartboard.
	if !scan.HasFastScanSpanPacked() || objsMarked < int(nelems/8) {
		if debug.gctrace > 1 {
			gcw.stats[spanclass.sizeclass()].spansSparseScanned++
			gcw.stats[spanclass.sizeclass()].spanObjsSparseScanned += uint64(objsMarked)
		}
		scanObjectsSmall(spanBase, elemsize, nelems, gcw, &toScan)
		return
	}

	// Scan the span.
	//
	// N.B. Use gcw.ptrBuf as the output buffer. This is a bit different
	// from scanObjectsSmall, which puts addresses to dereference. ScanSpanPacked
	// on the other hand, fills gcw.ptrBuf with already dereferenced pointers.
	nptrs := scan.ScanSpanPacked(
		unsafe.Pointer(spanBase),
		&gcw.ptrBuf[0],
		&toScan,
		uintptr(spanclass.sizeclass()),
		spanPtrMaskUnsafe(spanBase),
	)

One eighth density is the switch point. Below it, the SIMD path costs more than it saves. Above it, ScanSpanPacked reads the span’s pointer mask and the mark set together and emits the pointers it finds directly into a buffer, using AVX-512 where the CPU has it:

go
// src/internal/runtime/gc/scan/scan_amd64.go:13
func ScanSpanPacked(mem unsafe.Pointer, bufp *uintptr, objMarks *gc.ObjMask, sizeClass uintptr, ptrMask *gc.PtrMask) (count int32) {
	if CanAVX512() {
		return ScanSpanPackedAVX512(mem, bufp, objMarks, sizeClass, ptrMask)
	}
	panic("not implemented")
}

That is the “tear through the heap” endpoint the header comment promised. On amd64 the packed scan requires AVX-512; the HasFastScanSpanPacked() check above is what keeps the runtime from reaching that panic on a CPU without it, falling back to the object-by-object path instead.

What the mark work buffer holds

gcWork is the per-P work holder. In the classic GC it holds two work buffers of individual object pointers. In Green Tea it holds those and a span queue:

go
// src/runtime/mgcwork.go:106
	// spanq is a queue of spans to process.
	//
	// Only used if goexperiment.GreenTeaGC.
	spanq spanQueue

	// ptrBuf is a temporary buffer used by span scanning.
	ptrBuf *[pageSize / goarch.PtrSize]uintptr

ptrBuf is sized to hold one page’s worth of pointers — one pointer per word of a span — so a packed span scan can dump its entire result set without spilling.

The order in which these queues are drained is load-bearing, and the runtime documents it in a table:

go
// src/runtime/mgcwork.go:54
// +----------------------------------------------------------+
// | Priority | Work queue | Restrictions | Function          |
// |----------------------------------------------------------|
// | 1        | Workbufs   | P-local      | tryGetObjFast     |
// | 2        | Span queue | P-local      | tryGetSpanFast    | [greenteagc]
// | 3        | Workbufs   | None         | tryGetObj         |
// | 4        | Span queue | None         | tryGetSpan        | [greenteagc]
// | 5        | Span queue | None         | tryStealSpan      | [greenteagc]
// +----------------------------------------------------------+

Individual objects first, spans second — because scanning individual objects first is what accumulates marks on spans, making the later span scans denser.

Termination under the new scheme

Mark termination still works the same way conceptually: the GC must know that no grey object remains and no new grey object can appear. The ragged barrier — flush every P’s work, then check whether anything new appeared — is unchanged in spirit:

go
// src/runtime/mgc.go:1022
	// Flush all local buffers and collect flushedWork flags.
	gcMarkDoneFlushed = 0
	forEachP(waitReasonGCMarkTermination, func(pp *p) {
		// Flush the write barrier buffer, since this may add
		// work to the gcWork.
		wbBufFlush1(pp)

		// Flush the gcWork, since this may create global work
		// and set the flushedWork flag.
		//
		// TODO(austin): Break up these workbufs to
		// better distribute work.
		pp.gcw.dispose()

		// Collect the flushedWork flag.
		if pp.gcw.flushedWork {
			atomic.Xadd(&gcMarkDoneFlushed, 1)
			pp.gcw.flushedWork = false
		}
	})

What changed is where the marks live and how much work a flush can create. gcw.dispose() now has to flush the span queue too, and set a global bit so other Ps know there is stealable span work:

go
// src/runtime/mgcwork.go:324
	if !w.spanq.empty() {
		w.spanq.flush() // Flush any local work.

		// There's globally-visible work now, so make everyone aware of it.
		//
		// Note that we need to make everyone aware even if flush didn't
		// flush any local work. The global work was always visible, but
		// the bitmap bit may have been unset.
		//
		// See the comment in tryStealSpan, which explains how it relies
		// on this behavior.
		work.spanqMask.set(w.id)
		w.flushedWork = true
	}

Termination also has to account for the fact that a span’s mark bit can be set after the span was scanned. That is exactly what the scans bitmap solves: the object’s mark bit is already set, but its scan bit is not, so the span is still “grey” in the Green Tea sense and gets queued again.

The classic build spells out the same distinction in one line:

go
// src/runtime/mgcwork.go:42
// For objects in the span queue, a grey object is one that is marked
// and has an unset scan bit. A black object is marked and has its scan
// bit set. (Green Tea GC only.)

What this is not

Two things are worth clearing up, because the name invites confusion.

It is not a different collector. Green Tea is still a concurrent tri-colour mark-sweep collector with the same write barrier, the same pacer, the same sweeper. It changes the granularity of the mark phase: object-at-a-time becomes span-at-a-time. Allocation, pacing, sweeping and scavenging are untouched.

It is not “mark while erase”. There is a family of designs where the mark bits are erased during the sweep rather than being cleared separately, and there is a family of designs that group objects into “islands” of connected regions. Neither is what this code does. The bitmaps here are cleared by an explicit sweep of the span (mspan.sweep copies the mark bits into the allocation bits and installs fresh zeroed mark bits), and the grouping unit is the span, not an arbitrary island.

The non-Green-Tea build is still there, and it is still the default. Its tryDeferToSpanScan is a stub:

go
// src/runtime/mgcmark_nogreenteagc.go:25
func tryDeferToSpanScan(p uintptr, gcw *gcWork) bool {
	return false
}

Every pointer found by the scanner in the classic build therefore goes straight to greyobject, which marks the single object and pushes it onto a workbuf. Green Tea’s version, by contrast, sets the mark bit and queues the span.

Trade-offs

What Green Tea buys: the mark phase touches memory a page at a time instead of an object at a time. Mark bits, pointer masks and objects live in the same page. The metadata cost of “is this object marked?” is amortised across every object in the span rather than paid per object. And the dense case has a genuinely SIMD implementation that processes a whole span’s pointer words in parallel.

What it costs: the extra scans bitmap, the per-span ownership byte, and a second work queue per P. The span queue is a FIFO, so marking has a latency characteristic the LIFO workbuf did not have: a span queued early is scanned early, but it may sit in the queue for a while. The fast path is also more complex — a pointer discovered now does not immediately produce a scan, so the GC’s behaviour depends on how densely the workload happens to allocate.

The density cliff: the span scan switches between “walk object by object” and “SIMD over the page” at one-eighth density. A workload that allocates a sparse mix of long-lived and short-lived objects in the same size class will hover around that boundary, where the fast path’s advantage is smallest.

Caveats

Green Tea is experimental. It is behind GOEXPERIMENT=greenteagc, off by default, and the runtime has explicit doubleCheckGreenTea assertions that compare the two bitmaps against each other in debug builds — code that only exists because the design is still being validated.

The benefit depends on your heap. Green Tea is aimed at heaps with lots of small pointer-bearing objects. A heap of large objects, or of noscan byte slices, changes nothing: noscan objects never get scanned at all.

It does not apply to every span. Only spans that satisfy heapBitsInSpan(size) && size >= 16 use inline mark bits. Larger objects, and small spans that need a heap-arena-sized bitmap, still go through the classic path.

The classic path still exists and still works. If you benchmark Green Tea and see no difference, the most likely reason is that your application’s mark phase is dominated by work that neither version changed — root scanning, stack scanning, or the write barrier.

Wrapping up

The one thing to remember: Green Tea does not change what the GC marks, only the order and the granularity in which it looks. One bit per object for “marked”, one bit per object for “already scanned”, a FIFO queue of spans, and a scan pass that can walk a whole page at once.

The part people get wrong: it is not enabled by default. You have to build with GOEXPERIMENT=greenteagc to get any of it, and even then only small pointer-bearing spans take the new path.

What to go do about it: build your benchmark binary twice, once with GOEXPERIMENT=greenteagc and once without, and compare /gc/heap/goal:bytes against wall-clock time and GC CPU fraction. If your heap is full of small structs with pointers, that is where the locality win shows up. If it is full of large buffers, do not bother.