7 ms·
Treadmill garbage collector by H. Baker
- rwmj 4y agoI'm a bit worried about the amount of pointer chasing here. Presumably on modern architectures that would kill cache locality? Or am I missing something?
- kragen 4y agoIIRC the Treadmill has always had appalling constant factors; its appeal is that, unlike any simpler or earlier GC algorithm, it has a worst-case execution time.
- JonChesterfield 4y agoAnyone know of a garbage collector specialised to immutable objects? No old objects containing pointers to new objects and no mutation while scanning hazards.
- CyberDildonics 4y agoWhy would you garbage collect something that is going to change in the first place? By definition there isn't a way to reach it any more.
- Joker_vD 4y agoCheney's copying collector? You're gonna have huge garbage-to-live ratio with immutable objects, and this algorithm is pretty amazing for such scenarios.
- oecumena 4y agoIf there are no pointers from "old" to "new" objects, then there are no cycles and (compiler-assisted) reference counting will handle it.
- oecumena 4y agoTreadmill is a "real-time" in-place garbage collection algorithm designed by H. Baker. It is simple, elegant, efficient and surprisingly little known.
- convolvatron 4y agoI 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 agoI 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 agoThe 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
- teeray 4y agoI thought this was literally a physical garbage collection device made from a repurposed treadmill.
- fitzoh 4y agoYep, was expecting something like Mr. Trash Wheel: https://www.mrtrashwheel.com/ https://www.mrtrashwheel.com/
- travisgriggs 4y agoThis has always been my favorite garbage collector. Not because of any performance benefits; I’ve just always liked the elegance of it. At the dawn of the Squeak Smalltalk era, there was some company (forget which) that did a hybrid Bakers treadmill implementation for some real time stuff. I did a simplistic implementation in C once for an image processing pipeline to manage labeled regions. Once you get it correct, it’s pretty slick. I used a Fibonacci sizer for the different ring sizes.
- drewm1980 4y agoOn my first skim through the article it seemed like objects were getting copied between regions, i.e. when they change color. I guess the key is one of the first sentences "all objects in the heap are organised in a cyclic double-linked list", so there is a layer of indirection, and the circle you see is not the actual address space as I initially assumed, but the linked list. Did I understand correctly?
- jacobn 4y agoYes
- oecumena 4y agoDouble-linked list (Baker calls it "Knuth's double-linked list") allows O(1) insertions and deletions (hence moving) without actually moving objects and without additional indirection. Each object has a header that contains pointers to the next and previous objects in the list. To remove obj from the list do { obj->next->prev, obj->prev->next = obj->prev, obj->next } (I use "parallel assignment" for simplicity), similarly for insertion, see https://en.wikipedia.org/wiki/Doubly_linked_list https://en.wikipedia.org/wiki/Doubly_linked_list . So the circles in the diagram are not actual address space (in the sense that object addresses are not increasing monotonically as you go clockwise), but there is no additional indirection because the header with the forward and backward pointers is part of the object.
- RodgerTheGreat 4y agoIt does mean that in a short period your heap will be a knotted spaghetti of objects with virtually pessimal locality as you chase pointers around the loop.
- oecumena 4y agoThat's true, the worst case is bad. But if mutator locality of reference is reasonable, the scanner will preserve it. After all, Baker rejected his earlier copying design for a reason.
- 4y ago
- nemo1618 4y agoAm I correct in assuming that "no pointer arithmetic" and "read barrier on every pointer access" are the reasons this approach isn't more widely used?
- moonchild 4y agoNo. Most languages with good gcs do not have pointer arithmetic, and many good gcs, especially real-time ones, have a read barrier.
- pjmlp 4y ago.NET, Go, Java, Eiffel and Common Lisp all expose ways to do pointer arithmetic, either via unsafe code blocks, or unsafe runtime APIs. I bet there isn't a language around (with GC) that tops their GC implementations.
- comex 4y agoThe question isn’t whether there’s some way to do arithmetic on raw pointers, but whether you can take a pointer to a subobject and expect the GC to keep the object alive for you. In Go you can do this, but you can’t in Java or C#, I believe.
- pjmlp 4y agoFor .NET, https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/fixed-statement https://docs.microsoft.com/en-us/dotnet/csharp/language-refe... For Java, https://docs.oracle.com/en/java/javase/18/docs/specs/jni/design.html#implementing-local-references https://docs.oracle.com/en/java/javase/18/docs/specs/jni/des... https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/jdk/internal/misc/Unsafe.java https://github.com/openjdk/jdk/blob/master/src/java.base/sha... And as bonus since you didn't ask for it, Eiffel https://www.eiffel.org/doc/solutions/CECIL_-_Eiffel_to_C https://www.eiffel.org/doc/solutions/CECIL_-_Eiffel_to_C
- 4y ago
- gumby 4y ago> In fact, some of the Lisp Machines had garbage collection implemented in hardware and allocated everything including stack frames and binding environments in the heap. I wrote a lot of code for CADR, Symbolics and D-Machine Lispms and I’m not aware of any of them having hardware or microcode GC. That would be crazy anyway. Tagging and other support sure, but you could say that the x86 has hardware support through its pager too. As for stack frames on the heap, think of how important function calling is, and the impact of allocation, cache, etc of such an approach. They all used PDLs like any other machines. Now InterLisp-D did spaghetti the stack when you made a closure, at least for some time. I know this because I triggered it with a pathological case of making thousands of closures, bringing any machine to its knees. But a spaghetti stack is a different thing from allocating frames from the heap.
- gnufx 4y agoFor microcoded GC, also see https://en.wikipedia.org/wiki/Flex_machine https://en.wikipedia.org/wiki/Flex_machine
- oecumena 4y agoThe Scheme-79 chip (https://dspace.mit.edu/handle/1721.1/6334 https://dspace.mit.edu/handle/1721.1/6334) was doing GC in microcode. According to Steel & Sussman it typically spent 80% of time collecting. :-) RMS invented "phantom stacks" to reduce the amount of garbage due to closures, not sure this was ever implemented anywhere.
- gumby 4y agoI forgot about that chip. yeah, I don’t think anyone looked at the phantom stack idea. Perhaps interlisp should have.
- kragen 4y agoGenerational GC might make heap-allocating your activation records a viable option, even if you're not satisfied with CPython levels of performance. I mean in a sense that's what Chicken does, right?
- chc4 4y agoIt says that alloc() is O(1) and thus real-time...but then later on says that advance() must be called k times per alloc in order to avoid exhausting the free space while still having work on the gray list. This makes it not quite real-time; either you call advance() k times inside alloc (which it recommends) in which case it isn't constant latency but variable on the number of reachable objects from the object you are popping from the work list, or you risk running out of heap and have an eventual loop of draining the grey list to flip. In either case that doesn't seem quite as useful as the claimed "alloc is just a pointer chase" and not much better than other GCs that don't claim to be real-time, and makes it soft real-time (upper bound on instructions) not real-time (exact number of instructions); most other incremental GCs also have a bounded set of work they do per operation. It also sounds like it requires a mutex on read barriers for multithreaded programs, which is pretty bad and expensive. Most modern GC read barriers are just setting a bit in a card table, which doesn't require a lock.
- ErikCorry 4y agoAre you sure? Setting a bit in a card table sounds more like a write barrier.
- chc4 4y agoSorry, you're right, I was thinking of write barrier schemes. Off the top of my head I think most non-moving GCs use only write barriers and not read barriers now, though, along with writes being less common than reads, which is maybe even better than what I said. https://webkit.org/blog/7122/introducing-riptide-webkits-retreating-wavefront-concurrent-garbage-collector/ https://webkit.org/blog/7122/introducing-riptide-webkits-ret... for example only uses a write barrier, and so does Lua's tricolor GC. The closest modern analogue would maybe be something like Metronome, which is a moving GC that also advertises as real-time, but has a read barrier they intentionally tried to make very cheap and optimizable - I guess you could also coalesce Treadmill read barriers to only one mutex + color transition for multiple fields of an object all at once, though.
- vidarh 4y agoAs far as I understand it, it's real-time if you don't adjust k dynamically to avoid running out of memory. The heap size you need is R*(1+1/k). So if k=1, then you need to threat a half-full heap as an out-of-memory condition, which is comparable to quite a few GC's. If you set k at e.g. 4 instead, you can use 80% of the heap. If you're ok with losing real-time guarantees you can instead dynamically increase k as needed.
- ulrikrasmussen 4y agoI don't know a lot about GC and didn't know about this before I saw this on HN, but I think it is super elegant. One thing I didn't understand: Are all objects assumed to be exactly the same size? Since allocation is just the move of a pointer, that appears to be the case. But how would that work if one would want to implement Treadmill for a language like Java where object sizes vary?
- oecumena 4y agoVariable size objects are addressed at the very end of the post: "Support for variable-sized objects requires a separate cyclic list for each size...".
- ulrikrasmussen 4y agoThanks, I somehow missed that line.
- ErikCorry 4y agoThat implies that you have to divide up the memory ahead of time into an area for each size? If you get the proportions wrong you will waste memory. Languages with only one object size are not exactly in vogue at the moment, so this is a major limitation.
- thesz 4y agoYou can extend or shrink circular list on the go, depending on needs. You can plan to divide memory ahead of time, but you don't have to.
- vidarh 4y ago> That implies that you have to divide up the memory ahead of time into an area for each size? No, it doesn't, as it maintains linked lists of objects, so you can use any underlying allocator to feed you objects to add to the different linked lists.
- artemonster 4y agoHe also wrote an experimental lisp with linear types, a precursor to Rust borrow system -https://news.ycombinator.com/item?id=20369522 https://news.ycombinator.com/item?id=20369522
- samatman 4y agoI'm put to mind of Mike Pall's design (tragically unwritten) for a quad-color GC for LuaJIT: http://wiki.luajit.org/New-Garbage-Collector#gc-algorithms_quad-color-optimized-incremental-mark-sweep http://wiki.luajit.org/New-Garbage-Collector#gc-algorithms_q... I'm just hearing of the Treadmill for the first time, so I can't compare the design in detail yet, but the two pictures tell a lot of that story.
- masukomi 4y agohonestly thought this was going to be a story about someone who collected / gathered treadmills from landfills.
- stjohnswarts 4y agoI did too but haven't had my coffee yet. I mean I could see someone collecting them and selling them online for a profit or something. They aren't all that hard to fix. I've fixed a couple I found curbside headed for the landfill, fixed them, and sold locally on facebook groups (i wouldn't even attempt to ship a treadmill/elliptical)
- lesuorac 4y agoI thought based on the title it would a be a simple GC that worked similarly to a real treadmill. The GC would move used objects to the front (as if they were running forward). The unused objects would either be moved (or left in place) to the back (as if they stopped running). All memory in the back would be considered free space when alloc-ing. But the article quickly says thats not going to happen since its "in-place" and I have no idea what my idea would be already called.
- Joker_vD 4y agoA mark–compact algorithm? As all copying collectors, it doesn't work really that well with large live sets.