News for hackers. Stuff that matters.
Re:Treadmill garbage collector by H. Baker by oecumena on Monday July 25, 2022 @10:13PM (#32233473)
Treadmill is a "real-time" in-place garbage collection algorithm designed by H. Baker. It is simple, elegant, efficient and surprisingly little known.
Re:Treadmill garbage collector by H. Baker by convolvatron on Monday July 25, 2022 @10:38PM (#32233627)
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

Re:Treadmill garbage collector by H. Baker by hayley-patton on Tuesday July 26, 2022 @12:30AM (#32234252)
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

[1] https://plover.com/~mjd/misc/hbaker-archive/RealTimeGC.html

Re:Treadmill garbage collector by H. Baker by stjohnswarts on Tuesday July 26, 2022 @10:49AM (#32239084)
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.