GoSuda

A cup of green tea's leisure that the Go runtime will take away, GreenTea GC

By snowmerak views ...

Why Another New GC?

Why the Existing GC

The current Go GC can be described as follows.

  • Concurrent tri-color mark and sweep
    • Uses a total of three colors (white, gray, black) to track the state of objects.
      • White: objects that have not yet been visited
      • Gray: objects that have been visited but whose child objects have not all been visited
      • Black: objects that have been visited along with all of their child objects
      • Once traversal finishes, all white objects are collected.
    • Uses a Write Barrier to protect memory newly created during GC.
      • The time spent turning the Write Barrier on and off accounts for a significant portion of what is commonly called Stop-The-World (hereinafter STW).
    • This process is performed concurrently.
  • No Compaction
    • Go's GC does not perform compaction.
    • Memory fragmentation may occur.
      • However, objects of 32KB or less utilize the per-P cache of Go's memory allocator to minimize fragmentation.
  • Non-Generational
    • Go's GC does not manage objects by generation.
    • All objects belong to the same generation.
  • Escape Analysis
    • Go uses Escape Analysis to determine whether an object is allocated on the heap or on the stack.
    • Roughly speaking, if a dangling pointer or an interface is used, the object can be regarded as allocated on the heap.

What Matters

The key point is that Go's GC traverses all objects starting from the roots and performs tri-color marking. Summarized in one line, this process can be called a concurrent traversal algorithm over a topologically ordered graph. However, each object is highly likely to reside in a different memory region. To put it simply:

  1. Suppose there are memory regions that are about 32MB apart from each other.
  2. Five objects are allocated in these two memory regions, five objects each.
    1. Objects A, B, and C are in region 1.
    2. Objects D and E are in region 2.
  3. The reference order of the objects is A -> D -> B -> E -> C.
  4. Now, when GC starts, it visits A, then D, then B, then E, then C.
  5. At this point, since A and D reside in different memory regions, moving from visiting A to visiting D requires moving between memory regions.
  6. This process involves moving between memory regions and filling new cache lines, which incurs what is called memory jump cost. A significant portion of the CPU time used by the application can be allocated to this GC work.
  7. This cost continues to occur throughout the duration of GC.

So What's the Problem?

The behavior of this GC is a serious drawback in the following cases.

  • When the core count is high and the memory is large
    • Go's GC is basically performed concurrently.
    • However, if the memory region is wide and objects are scattered, multiple cores will simultaneously traverse objects across diverse memory spaces.
    • In this process, if the bus between the CPU and memory is not sufficiently large, memory bandwidth can become a bottleneck.
    • Furthermore, because the physical distance is real, each traversal step can incur a relatively large delay.
  • When there are many small objects
    • If you operate trees or graphs with deep depth or many children in Go, the GC must traverse all of these objects.
    • In this process, if the objects are distributed across different memory regions, delays occur due to the first reason.
    • Also, when there are many small objects, the GC must traverse all of them, so CPU cores will devote considerable capacity to GC work while GC is running.

To address these problems, the Golang team announced the GreenTea GC.

You No Longer Have Time to Drink More Green Tea

What Takes Away the Green Tea

The area where the fastest solution to the existing GC could be applied appears to be memory locality. That is, placing objects close to one another to minimize memory jumps. However, the patterns of programmers writing code cannot be enforced, and object allocation is unpredictable depending on workflow.

Perhaps for this reason, the approach the Golang team chose is the Memory Span.

What Is a Memory Span?

A memory span is where a relatively large memory region is allocated and small objects are allocated within it. The new GC named GreenTea GC performs garbage collection on these memory spans. Its detailed behavior is nearly identical to the existing tri-color mark and sweep.

How GreenTea GC Works

First, GreenTea GC allocates a memory span. Its size, as described earlier, is a reasonably sized 8KiB. Within it, objects of up to 512 bytes can be allocated. This is about the size at which the node sizes of the tree or graph examples given earlier, or the size of structs that typically escape to the heap, would hardly be larger. Objects of 512 bytes or less are accumulated in this memory span whenever they escape to the heap, and when this memory span becomes full, a new memory span is allocated.

Now, when GC occurs, GreenTea GC queues these memory spans and inspects them sequentially. In this process, GreenTea GC uses scheduling that is nearly similar to the existing GMP model. Areas such as work stealing are also implemented. In any case, a worker that takes a memory span from the queue inspects the internal objects of the memory span assigned to it. In this process, the same tri-color mark and sweep is used.

What Are the Benefits?

Looking broadly, the only real difference from the existing GC in this process is one thing: the unit in which GC is performed at once has changed from objects to memory spans. Because of this, GC has the following benefits.

  • Memory locality: Since objects are gathered within a memory span, memory jumps are minimized when traversing objects. In other words, the CPU cache can be utilized to the fullest.
  • GC performance improvement: By performing GC in units of memory spans, GC works more efficiently in multi-core environments.
  • Memory allocation optimization: Since memory spans are allocated at a fixed size, the overhead of memory allocation is reduced when allocating small objects, and the likelihood of fragmentation decreases. This increases the efficiency of memory deallocation.

In short, from now on we can allocate objects of 512 bytes or less more often and with a lighter mind.

That said, there are some favorable scenarios here as well.

  • Tree/graph structures: cases where fan-out is high and changes rarely occur
    • B+ trees, Tries, AST (Abstract Syntax Tree)
    • Cache-friendly data structures
  • Batch processing: workflows that allocate large volumes of small data
    • Numerous small objects generated by JSON parsing
    • DAO objects from database result sets

In these cases, GreenTea GC can deliver better performance than the existing GC. However, it does not apply to every case, and in particular, when objects are distributed across different memory regions, it is still difficult to expect dramatic performance improvements.

So

The Golang team seems to intend to keep improving the GC over the long term. This GreenTea GC can be regarded as a minor change in a small area and does not replace the existing GC. Nevertheless, GreenTea GC appears to be an interesting case that gives a glimpse of the problems the Golang team faces or anticipates. Although the problem is surprisingly complex, I was also impressed by the attempt to solve it through the addition of a relatively simple concept. Personally, I think it is an interesting case.

GreenTea GC is an experimental feature introduced starting with Go 1.25. It can be enabled by using the GOEXPERIMENT=greenteagc environment variable. Since this feature is still experimental, sufficient testing is required before using it in a production environment.

References