The Tricolor Algorithm
Let’s learn about the tricolor algorithm in Go.
The operation of the Go GC is based on the tricolor algorithm. Note that the tricolor algorithm is not unique to Go and can be used in other programming languages as well.
Introduction to the tricolor algorithm
Strictly speaking, the official name for the algorithm used in Go is the tricolor mark-and-sweep algorithm. It can work concurrently with the program and uses a write barrier. This means that when a Go program runs, the Go scheduler is responsible for the scheduling of the application as well as the GC, which also runs as a goroutine. This is as if the Go scheduler must deal with a regular application with multiple goroutines!
Note: The core idea behind this algorithm came from Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens and was first illustrated in a paper named On-the-Fly Garbage Collection: An Exercise in Cooperation.
The primary principle behind the tricolor mark-and-sweep algorithm is that it divides the objects of the heap into three different sets according to their color, which is assigned by the algorithm and can be black, gray, or white. The objects of the black set are guaranteed to have no pointers to any object of the white set ...