TL;DR Writing tri-color (actually 4-color) generational garbage collector in C
Previously we’ve talked about manual memory allocation and unraveled some shadows around it. Now let’s talk about automatic memory allocation, more specifically about Garbage Collection. Most if not all modern Programming Languages contain a mechanism that handles allocation of memory automatically at precisely the moment application needs it and deallocation of that memory at the moment it’s not needed anymore. However determining when memory region (or object) is safe to deallocate is not an easy feat as we need to somehow determine if the region is needed or not. And here is where Garbage Collection comes into a play. Simply speaking Garbage Collection is an algorithm that checks entire memory of an application for regions that aren’t referenced anywhere inside application by other memory regions and deallocates these regions because they aren’t needed anymore.
Garbage Collection was invented by John McCarthy back in 1959 for Lisp and is still one of the hottest evolving topics in Computer Science nowadays, especially with Java’s GC becoming more famous with tons of blows and whistles which can be tuned to practically any application memory usage scenario. There are also alternative models to automatic memory handling such as newLisp’s ORO, Rust’s ownership based life cycle management and Objective-C’s ARC but we won’t be talking about those. The cost of checking entire memory region is not a cheap one so people realized ways to make it more reasonable and thus nowadays we have various types of Garbage Collection algorithms. There are tracing garbage collectors and reference counting ones, copying (moving) and non-copying (non-moving) ones, incremental and non-incremental, generational, concurrent, parallel and real-time ones. To learn more about all those types of Garbage Collectors I suggest you try reading The Garbage Collection Handbook which is a fundamental must read handbook for all those interested in the topic. But for rest of you lazy bunch let’s start collecting all the garbage in the world by writing one garbage collector ourselves.