Tri-color marking
- Go course
- Expert
- Lesson 8/34
- 4 min
Learn the white, gray, black marking algorithm.
Tri-color marking
Go's GC splits objects into three colors: white (not seen yet, a collection candidate), grey (seen but its references not scanned), black (seen and all its references scanned). Marking starts at the roots:
1. Roots become grey
2. Take a grey object → make its references grey → make it black
3. Stop when no grey is left
4. Everything still white is garbage → sweepIn the end blacks survive and whites are freed.
The invariant
Because the program keeps running during marking, one rule must hold: a black object must never point directly to a white object. Otherwise, since the GC doesn't rescan blacks, the white object would be freed while still alive. The write barrier protects this rule.
Practice Marking simulation
Define a graph with map[string][]string: "kok": {"a"}, "a": {"b"}, "c": {"b"}. Starting from the root, mark reachable nodes using a grey queue and print the number of black nodes (c is garbage).
Starter code
package main
import "fmt"
func main() {
// buraya yaz
}Sample solution
package main
import "fmt"
func main() {
graf := map[string][]string{"kok": {"a"}, "a": {"b"}, "c": {"b"}}
siyah := map[string]bool{}
gri := []string{"kok"}
for len(gri) > 0 {
n := gri[0]
gri = gri[1:]
if siyah[n] {
continue
}
siyah[n] = true
gri = append(gri, graf[n]...)
}
fmt.Println(len(siyah))
}Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Can a grey object remain when marking finishes?
- No; marking ends when no grey is left Correct answer
- Yes, it carries to the next cycle
- Yes, grey objects are freed
- Only large objects
Explanation: Grey means "unfinished work"; the end condition is that every reachable object has turned black.
2 Unscanned color
const (
white = iota
____
black
)const (
white = iota
grey
black
)Explanation: Grey objects are in the work queue; once scanned they turn black.
3 Color and meaning
| Term | Meaning |
|---|---|
Beyaz |
Unseen, garbage candidate |
Gri |
Seen, to be scanned |
Siyah |
Scanned, alive |
Sweeping |
Frees the whites |