3.7 GC

1. What Is GC?

GC.md (the related note has not been published yet)

2. Why Is GC Needed?

GC.md (the related note has not been published yet)

2.1. Problems with GC

2.1.1. Memory Leaks

Go Memory Leaks

2.1.2. STW

Use tri-color marking to reduce GC STW time.

3. How Garbage Collection Works

3.1. GC Triggers

• Active trigger
  • Call runtime.GC to trigger GC. This call blocks until the current GC finishes.
• Passive triggers, in two ways:
  1. Timer. If the system monitor sees that no GC has happened for more than two minutes (runtime.forcegcperiod), it forces a GC.
  2. Pacing algorithm. GC is triggered when the memory growth ratio exceeds a certain value within a period of time.

3.2. GC Process

1. Mark Setup (requires STW), enable the Write Barrier.
2. Mark using the tri-color marking algorithm (concurrent).
3. Mark Termination (requires STW), disable the write barrier.
4. Sweeping (concurrent).

3.3. Evolution of Golang GC

3.3.1. Traditional Mark-and-Sweep Algorithm

• It has two phases:
  • Mark: starting from root objects, DFS through reachable objects and mark them.
  • Sweep: unmarked objects are garbage and are reclaimed.
• It has several disadvantages:
  • STW: STW is required before marking and lasts until marking is finished.
  • Memory fragmentation.

3.3.2. Tri-Color Mark-and-Sweep Algorithm

• Tri-color marking improves the STW problem of traditional mark-and-sweep.
• It also has two phases:
  • Mark: starting from root objects, BFS through all objects. Objects whose traversal is complete are marked black, objects being traversed are gray, and unreachable objects are white.
    • White objects (possibly dead): objects not visited by the collector. At the beginning of collection, all objects are white. At the end of collection, white objects are unreachable.
    • Gray objects (wavefront): objects that have been visited by the collector, but one or more pointers inside them still need to be scanned because they may still point to white objects.
    • Black objects (confirmed alive): objects that have been visited by the collector and all of whose fields have been scanned. No pointer in a black object can directly point to a white object.
    • 
  • Sweep: unmarked (white) objects are garbage and are reclaimed.
• Without STW, there is a problem when GC and user threads execute concurrently: an object that is not garbage may be reclaimed. For example:
  1. Gray object A references white object B.
  2. Black object C references white object B.
  3. Gray object A removes its reference to white object B.
  4. Because black object C has already been marked black and will not be scanned again, white object B is still referenced but gets reclaimed.
• From the situation above, there are two conditions that can cause this error:
  • Condition 1: a white object is attached under a black object.
  • Condition 2: the gray object simultaneously loses that white object.
• Eliminating either condition solves the problem, so two approaches are introduced:
  • Strong tri-color invariant (for condition 1): no black object points to a white object. If a white object is attached under a black object, change the white object to gray.
  • Weak tri-color invariant (for condition 2): all white objects referenced by black objects are protected by gray objects. If a white object is attached under a black object, it must also be referenced by a gray object on another path.

3.3.3. Write Barrier

3.3.3.1. Insertion Barrier

To implement the strong tri-color invariant, an insertion barrier is introduced: when object A references object B, object B is marked gray. This also introduces a new problem: root objects on the stack need to be re-scanned.

3.3.3.2. Deletion Barrier

To implement the weak tri-color invariant, a deletion barrier is introduced: when a deleted object is gray or white, it is marked gray. This also introduces a new problem: an object that is already garbage may not be reclaimed until the second GC.

3.3.3.3. Hybrid Write Barrier

The hybrid write barrier combines insertion and deletion barriers.

1. When GC starts, DFS-scan all objects on the stack and mark them black (there is no second repeated scan afterward, so STW is not needed for that re-scan).
2. During GC, any new object created on the stack is black.
3. A deleted object is marked gray.
4. An added object is marked gray.

4. Golang Memory Leaks

Go Memory Leaks

5. GC Tuning

GC tuning.md (the original link is no longer valid)

5.1. How to Observe GC

1. GODEBUG=gctrace=1

package main

func allocate() {
	_ = make([]byte, 1<<20)
}

func main() {
	for n := 1; n < 100000; n++ {
		allocate()
	}
}

• Observe GC

go build -o main
GODEBUG=gctrace=1 ./main

• Log

gc 2 @0.001s 2%: 0.018+1.1+0.029 ms clock, 0.22+0.047/0.074/0.048+0.34 ms cpu, 4->7->3 MB, 5 MB goal, 12 P

• Interpretation

gc 2    the second GC cycle
0.001   0.001 seconds after the program started
2%      CPU utilization during this GC cycle
0.018   STW time at the beginning of marking (wall clock)
1.1     concurrent marking time during marking (wall clock)
0.029   STW time at mark termination (wall clock)
0.22    STW time at the beginning of marking (CPU time)
0.047   mark-assist time during marking (CPU time)
0.074   concurrent marking time during marking (CPU time)
0.048   GC idle time during marking (CPU time)
0.34    STW time at mark termination (CPU time)
4       actual heap size at the beginning of marking
7       actual heap size at the end of marking
3       size of objects marked live at the end of marking
5       predicted heap size at the end of marking
12      number of Ps

2. go tool trace

package main

func main() {
  f, _ := os.Create("trace.out")
  defer f.Close()
  trace.Start(f)
  defer trace.Stop()
}

• Run go tool trace trace.out

3. debug.ReadGCStats
4. runtime.ReadMemStats

5.2. How to Tune

5.2.1. The Parameter to Adjust Is the GOGC Environment Variable

5.2.2. Increase the Threshold That Triggers GC

5.2.2.1. memory ballast

Specify the minimum heapSize for GC to run. Below this value, GC does not run.

5.2.2.2. Automatically Adjust GCPercent

The standard-library runtime package provides debug.SetGCPercent(int) to adjust the GC target percentage. The default is 100, meaning GC is triggered when heap usage reaches twice the size after the previous GC. Increasing it can reduce GC frequency.

5.2.3. Reduce the Amount of Memory Allocated by User Code

5.2.3.1. Optimize Memory Allocation Speed

package main

import (
  "fmt"
  "os"
  "runtime"
  "runtime/trace"
  "sync/atomic"
  "time"
)

var (
  stop  int32
  count int64
  sum   time.Duration
)

func concat() {
  for n := 0; n < 100; n++ {
    for i := 0; i < 8; i++ {
      go func() {
        s := "Go GC"
        s += " " + "Hello"
        s += " " + "World"
        _ = s
      }()
    }
  }
}

func main() {
  f, _ := os.Create("trace.out")
  defer f.Close()
  trace.Start(f)
  defer trace.Stop()

  go func() {
    var t time.Time
    for atomic.LoadInt32(&stop) == 0 {
      t = time.Now()
      runtime.GC()
      sum += time.Since(t)
      count++
    }
    fmt.Printf("GC spend avg: %v\n", time.Duration(int64(sum)/count))
  }()

  concat()
  atomic.StoreInt32(&stop, 1)
}

• Output

$ go build -o main
$ ./main
GC spend avg: 2.583421ms

Most of the time is spent waiting in the scheduler rather than executing goroutines. Change it to create goroutines batch by batch.

func concat() {
  wg := sync.WaitGroup{}
  for n := 0; n < 100; n++ {
    wg.Add(8)
    for i := 0; i < 8; i++ {
      go func() {
        s := "Go GC"
        s += " " + "Hello"
        s += " " + "World"
        _ = s
        wg.Done()
      }()
    }
    wg.Wait()
  }
}

• Output

$ go build -o main
$ ./main
GC spend avg: 328.54µs

5.2.3.2. Allocate as Little Memory as Possible

5.2.3.3. Reuse Already Allocated Memory

package main

import (
  "fmt"
  "net/http"
  _ "net/http/pprof"
)

func newBuf() []byte {
  return make([]byte, 10<<20)
}

func main() {
  go func() {
    http.ListenAndServe("localhost:6060", nil)
  }()
  
  http.HandleFunc("/example2", func(w http.ResponseWriter, r *http.Request) {
    b := newBuf()

    // Simulate doing some work
    for idx := range b {
      b[idx] = 1
    }

    fmt.Fprintf(w, "done, %v", r.URL.Path[1:])
  })
  http.ListenAndServe(":8080", nil)
}

• Use sync.Pool to reuse memory

package main

import (
  "fmt"
  "net/http"
  _ "net/http/pprof"
  "sync"
)

// Use sync.Pool to reuse the required buf
var bufPool = sync.Pool{
  New: func() interface{} {
    return make([]byte, 10<<20)
  },
}

func main() {
  go func() {
    http.ListenAndServe("localhost:6060", nil)
  }()
  http.HandleFunc("/example2", func(w http.ResponseWriter, r *http.Request) {
    b := bufPool.Get().([]byte)
    for idx := range b {
      b[idx] = 0
    }
    fmt.Fprintf(w, "done, %v", r.URL.Path[1:])
    bufPool.Put(b)
  })
  http.ListenAndServe(":8080", nil)
}

6. References

• Golang GC: Tri-Color Marking and Hybrid Write Barrier - Bilibili
• 5. Full Analysis of Golang Tri-Color Marking + Hybrid Write Barrier GC · Golang Practice Road · KanCloud
• GoLab 2019 - Fabio Falzoi - An insight into Go Garbage Collection - YouTube
• Understanding GC - 9. What Are Write Barriers and Hybrid Write Barriers, and How Are They Implemented? - Go Questions - BookStack
• Go memory ballast: How I learnt to stop worrying and love the heap | Twitch Blog
• How We Saved 70K Cores Across 30 Mission-Critical Services (Large-cale, Semi-Automated Go GC Tuning @Uber)
• Cost Reduction and Efficiency Improvement: a tRPC-Go Plugin That Can Save 30% CPU Resources - KM Platform (internal link removed)
• go - Why ‘Total MB’ in golang heap profile is less than ‘RES’ in top? - Stack Overflow
• CMS and the Tri-Color Marking Algorithm - Zhihu