3 ms·

Treadmill is a "real-time" in-place garbage collection algorithm designed by H. Baker. It is simple, elegant, efficient and surprisingly little known.

• convolvatron 4y ago
  I don't know about little known. a lot of concurrent collector designs take some key points from treadmill, and its was certainly still standard grad school reading if you were in systems 15 years ago. but definitely a must-read if you care about that kind of thing
  • stjohnswarts 4y ago
    I have seen it mentioned before in other articles/implementations of garbage collectors. I think anyone interested in GC will come across, although certainly no as often as ones that are currently popular.
  • hayley-patton 4y ago
    The Dijkstra, Lamport, Martin, Scholten and Steffens "on-the-fly" collector [0] is the most inspirational, I think, with its analogy of "colors" for objects. Baker first designed a serial "real-time" copying collector [1], showing that three areas in copying are equivalent to the colors; then I think the lists of objects in the Treadmill are supposed to correspond to those areas in the copying collector. Instead of moving objects and advancing a scan pointer to change the color of objects, objects are rearranged in the doubly linked-list. [0] https://lamport.azurewebsites.net/pubs/garbage.pdf https://lamport.azurewebsites.net/pubs/garbage.pdf [1] https://plover.com/~mjd/misc/hbaker-archive/RealTimeGC.html https://plover.com/~mjd/misc/hbaker-archive/RealTimeGC.html