Tri-color Garbage Collection is a very common (probably the most common?) variation of Mark-and-Sweep.
The general idea is to have three colors: Black (do not garbage collect), Grey (do not garbage collect, but pointer-chasing still required), White (delete on next garbage collect).
Your objects start on the grey-list. As you process the grey-list, the elements turn black, and the objects they pointed to move from the white-list to the grey-list (for further processing).
The tri-color invariant proves that all objects in the Black-list do NOT have any (direct) elements in the whitelist. So once the grey-list is empty (ie: all objects are either black or white), your mark-phase is over. All objects in the white-list are swept away (in the 2nd phase of mark-and-sweep).
-------------
What is implemented in this blogpost is an incremental mark-and-sweep algorithm: which means that the GC may continue in the background (potentially in parallel) with the main threads of the program.
Incremental is a bit slower / higher-overhead overall, but has less latency. Since the blogpost author is a game programmer, that seems to be a good tradeoff.
The naive implementation is called "Stop the World" (and is implemented in the first half of the blog post). Stop the world has better throughput characteristics, but has the distinct disadvantage of... well... stopping the world until GC is done.
The general idea is to have three colors: Black (do not garbage collect), Grey (do not garbage collect, but pointer-chasing still required), White (delete on next garbage collect).
Your objects start on the grey-list. As you process the grey-list, the elements turn black, and the objects they pointed to move from the white-list to the grey-list (for further processing).
The tri-color invariant proves that all objects in the Black-list do NOT have any (direct) elements in the whitelist. So once the grey-list is empty (ie: all objects are either black or white), your mark-phase is over. All objects in the white-list are swept away (in the 2nd phase of mark-and-sweep).
-------------
What is implemented in this blogpost is an incremental mark-and-sweep algorithm: which means that the GC may continue in the background (potentially in parallel) with the main threads of the program.
Incremental is a bit slower / higher-overhead overall, but has less latency. Since the blogpost author is a game programmer, that seems to be a good tradeoff.
The naive implementation is called "Stop the World" (and is implemented in the first half of the blog post). Stop the world has better throughput characteristics, but has the distinct disadvantage of... well... stopping the world until GC is done.