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.
[ Parent
| on HN ]
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.