Real-Time Garbage Collection Is Real

Studying garbage collection is a wonderful education in algorithm engineering. Despite decades of work, there is no "best" GC algorithm. Instead, there are different points on the space of optimizing for space/throughput/latency/completeness/etc. Moreover, the various algorithms are linked by deep correspondences (e.g. Bacon's result that all collectors lie on a spectrum between pure tracing and pure reference counting, and that things like generational collection are hybrids.)

our running programs may exceed the amount of space we want them to take The majority of real-time systems are the small embedded ones where both speed and size are usually highly constrained, so this doesn't look as useful as it may seem. It's well known that GC overhead decreases with increasing available memory, so the result shouldn't be so surprising. A relevant phrase I've heard is "garbage collection is free only if memory is worth nothing." Limiting the amount…