How does tricolor garbage collection work?
Golang’s garbage collector uses a “tricolor” algorithm. This means it divides the heap objects into three sets: black, white, and grey. Initially, all objects are white, and as the algorithm proceeds, objects are moved into the grey and then black sets, in such a way that eventually the orphaned (collectible) objects are left in the white set, which is then cleared. An important property of this algorithm is that it can run concurrently with the “mutator” (program).
The meaning of the three sets is this:
Black/grey sets: Definitely accessible from the roots (not candidates for collection).
- Black set: Definitely no pointers to any objects in the white set.
- Grey set: Might have pointers to the white set.
White set: Possibly accessible from the roots. Candidates for collection.
The important invariant is the “tricolor” invariant: no pointers go directly from the black set to the white set. It is this invariant which lets us eventually clear the white set.
More by Jim
- Your syntax highlighter is wrong
- Granddad died today
- The Three Ts of Time, Thought and Typing: measuring cost on the web
- I hate telephones
- The sorry state of OpenSSL usability
- The dots do matter: how to scam a Gmail user
- My parents are Flat-Earthers
- How Hacker News stays interesting
- Project C-43: the lost origins of asymmetric crypto
- The hacker hype cycle
- The inception bar: a new phishing method
- Time is running out to catch COVID-19
- A probabilistic pub quiz for nerds
- Smear phishing: a new Android vulnerability
Tagged . All content copyright James Fisher 2016. This post is not associated with my employer. Found an error? Edit this page.