Fundamentals 52 min read

Design and Implementation of Go's Garbage Collector

This article provides an in‑depth overview of Go's garbage collector, covering its design principles, mark‑sweep algorithm, tri‑color abstraction, write‑barrier techniques, incremental and concurrent collection, evolution across Go versions, and detailed implementation details of marking, sweeping, and memory reclamation.

Sohu Tech Products

Apr 8, 2020

Design and Implementation of Go's Garbage Collector

The article introduces the Go runtime's garbage collector (GC), explaining that beyond allocating heap memory, a GC is required to reclaim unused objects. It outlines the historical evolution of Go's GC from a simple stop‑the‑world (STW) collector in v1.0 to the sophisticated concurrent, tri‑color, and incremental collector used today.

Design Principles

Go's GC uses a classic mark‑sweep algorithm with a tri‑color abstraction (white, gray, black) to track object reachability. The collector starts by marking root objects, then repeatedly processes gray objects, turning them black and marking their children gray, before finally sweeping unmarked (white) objects.

Mark‑Sweep Algorithm

The basic two‑phase process consists of:

Mark phase – traverse reachable objects and color them black.

Sweep phase – reclaim memory occupied by white objects.

Tri‑Color Invariant

To reduce pause times, Go maintains the tri‑color invariant using write barriers. Two variants are combined into a mixed write barrier :

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:
        shade(ptr)
    *slot = ptr

This ensures that any pointer update during concurrent marking preserves the invariant, preventing dangling pointers.

Incremental and Concurrent Collection

Go splits GC work into small time slices, allowing the mutator (application) to run concurrently. The runtime launches background mark workers per processor, classified into three modes: gcMarkWorkerDedicatedMode – dedicated GC workers. gcMarkWorkerFractionalMode – workers that run only when GC CPU utilization is below the target. gcMarkWorkerIdleMode – workers that run when the processor is idle.

Background Mark Worker

func gcBgMarkWorker(_p_ *p) {
    // ... park and wake logic ...
    for {
        gopark(...)
        // select work based on gcMarkWorkerMode
        gcDrain(&_p_.gcw, flags)
    }
}

Work Pool

Mark work is stored in a per‑processor gcWork structure with two buffers (wbuf1, wbuf2). Workers pull objects from the local buffer, steal from the global pool when empty, and push newly discovered gray objects back.

Scanning Objects

func gcDrain(gcw *gcWork, flags gcDrainFlags) {
    // loop over work buffer, call scanobject on each gray object
    // respect preemption, idle, and fractional modes
}

Pause and Resume

GC pauses the world using runtime.stopTheWorldWithSema, which preempts all processors, then resumes with runtime.startTheWorldWithSema. During the pause, root scanning and initial marking are performed.

Assist Marking

When a goroutine allocates memory during the concurrent mark phase, it may need to help the collector. Each goroutine tracks gcAssistBytes. If the assist balance goes negative, the goroutine performs assist work:

func gcAssistAlloc(gp *g) {
    // compute debt, possibly steal from global credit
    // call gcDrainN to perform marking work
}

If the global credit is insufficient, the goroutine parks and waits for background workers.

Mark Termination

When all work queues are empty, runtime.gcMarkDone signals the end of marking, disables write barriers, wakes assisting goroutines, and transitions to the _GCmarktermination phase.

Memory Reclamation

After marking, the sweep phase reclaims memory. The function runtime.sweepone iterates over spans, frees completely white spans, and returns reclaimed pages:

func sweepone() uintptr {
    // pop a span, check sweepgen, call s.sweep()
    // update reclaim credit
}

Conclusion

The Go garbage collector combines classic algorithms with modern techniques—tri‑color marking, mixed write barriers, incremental and concurrent collection, and assist marking—to achieve low‑latency pauses (often sub‑millisecond) while maintaining high throughput. The article provides source links for deeper exploration.