Go Tricolor Algorithm Explained

In this article we are going to learn about how tricolor algorithm works and its process of working.

The operation of the Go garbage collector is based on the tricolor algorithm.

Please not that the tricolor algorithm is not unique to Go and can be used in other programming languages.

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 writer barrier. This means that when a Go program runs, the Go scheduler is responsible for the scheduling of the application and the garbage collector. This is as if the Go scheduler has to deal with a regular application with multiple goroutines!

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 algorithms is that it divides the objects of the heap into three different sets according to their color, which is assigned by the algorithm. It is now time to talk about the meaning of each color set. This objects of the black set are guaranteed to have pointers to any object of the white set.

However, an object of the white set can have pointer to an object of the black set because this has not effect on the operation of the garbage collector. The objects of the gray set might have pointes to some objects of the white set. Finally. The objects of the white set are the candidates for garbage collection.

Please not that no object can go directly from the black set to the white set, which allows the algorithm to operate and be able to clear the objects on the white set. Additionally, no object of the black set can directly point to an object of the white set.

So when the garbage collection begins, all objects are white and the garbage collector visits all the root objects and colors them gray. The roots are the objects that can be directly accessed by the application, which includes global variables and other things on the stack. These objects mostly depend on the Go code of a particular program.

After that, the garbage collector picks a gray object, makes it black, and starts looking at whether that object has pointers to other objects of the white set. This means that when a gray object is being scanned for pointers to other objects, it is colored black. If that scan discovers that this particular object has one or more pointers to a white object, it puts that white object in the gray set. This process keeps going for as long as there exist objects in the gray set. After that, the objects in the white set are unreachable and their memory space can be refused. Therefore, at this point, the elements of the white set are said to be garbage collected.

Please note that if an object of the gray set becomes unreachable at some point in a garbage collection cycle, it will not be collected at this garbage collection cycle but in the next one! Although this is not an optimal situation, it is not that bad.

During this process, the running application is called the mutator. The mutator runs a small function names write barrier, which is executed each time a pointer in the heap is modified. If the pointer of an object in the heap is modified, which means that this object is now reachable, the write barrier colors it gray and puts it in the gray set

The mutator is responsible for the invariant that no element of the black set has a pointer to an element of the white set. This is accomplished with the help of the write barrier function. Failing to accomplish this invariant will ruin the garbage collection process and will most likely crash your program in a pretty bad and undesirable way!

Go garbage collection can also be applied to variables such as channels. When the garbage collector finds out that a channel is unreachable, which is when the channel variable cannot be accessed anymore, it will free its resources even if the channel has not been closed.

Go allows you to manually initiate garbage collection by putting a runtime.GC() statement in your Go code. However, have in mind that runtime.GC() will block the caller and it might block the entire program, especially if you are running a very busy Go program with many objects. This mainly happens because you cannot perform garbage collections while everything else is rapidly changing, as this will not give the garbage collector the opportunity to clearly identify the members of the white, black, and gray sets. This garbage collection status is called a garbage collection sage-point.

Note that the Go garbage collector is always being improved by the Go team. They are trying to make it faster by lowering the number of scans it needs to perform over the data of the three sets. However, despite the various optimizations, the general idea behind the algorithm remains the same.

myblog

Thanks for reading