16 ms·
The Garbage Collection Handbook, 2nd Edition
- sadiq 4y agoGreat that there's a new edition of this coming. This is the definitive reference if you work with garbage collectors, it's also very well written.
- NeutralForest 4y agoCool stuff! The last 10 years have seen lots of great languages pushing the field so I'm excited to see what's in the book =)
- ignoramous 4y agoOn a related note, I found ART's implementation of Concurrent copying and compaction GC to be pretty novel. Here's a nice write up detailing how handling page faults in userspace come in handy to accomplish that: https://www.tdcommons.org/cgi/viewcontent.cgi?article=4751&context=dpubs_series https://www.tdcommons.org/cgi/viewcontent.cgi?article=4751&c... (pdf) / https://web.archive.org/web/20230216233459/https://www.tdcommons.org/cgi/viewcontent.cgi?article=4751&context=dpubs_series https://web.archive.org/web/20230216233459/https://www.tdcom... For context, here's a brief overview of the evolution of the Android Runtime Garbage Collector: https://archive.is/Ue6Pj https://archive.is/Ue6Pj
- NobleExpress 4y agoCertainly interesting, but there are no performance numbers mentioned in the white paper comparing userfaultfd to read barriers. So the actual benefit to switching to userfaultfd is unknown (at least in publically accessible documents -- I'm sure Google has done internal performance evaluations). Using page faults (and/or page protection) to perform compaction instead of barriers is a pretty old technique (see the 1988 paper by Appel, Ellis, and Li [1]; see also the Compressor by Kermany and Petrank [2]). But handling page faults were very expensive (at least on Linux) until the addition of userfaultfd recently. [1]: https://dl.acm.org/doi/10.1145/960116.53992 https://dl.acm.org/doi/10.1145/960116.53992 [2]: https://dl.acm.org/doi/10.1145/1133255.1134023 https://dl.acm.org/doi/10.1145/1133255.1134023
- anonymousDan 4y agoWhat is the actual perf benefit of userfaultd (e.g. for write protection)? It sounds interesting but its unclear to me why it would be any faster than a signal handler. Is it just a simpler code path within the kernel? Or is it that the hardware is configured to directly jump to a user space handler without any kernel intervention?
- NobleExpress 3y agoWell page protection is expensive which is why the predominant way to implement concurrent copying/compaction until recently was using read barriers (and still is -- ART seems to be an exception). I will mention that concurrent compacting GCs wouldn't use userfaultfd for write protection, but for read protection (it effectively takes over the job of a read barrier). I personally don't know too much about userfaultfd and how it works internally, but my best guess is that it bypasses heavyweight kernel data-structures and lets the user application handle the page fault. It is obviously better than simply using mprotect, but it is not immediately clear why it would be better than a read barrier (other than code size considerations, which honestly doesn't sound like much of a big deal as the code handling userfaultfd also needs to be brought into the instruction cache). I did find this kernel doc about userfaultfd [1] which might be interesting to read if you're interested (it also does mention that userfaultfd doesn't lock some internal kernel data-structures which gives it a better performance than simply using mprotect, but the implementation details are a bit sparse). [1]: https://docs.kernel.org/admin-guide/mm/userfaultfd.html https://docs.kernel.org/admin-guide/mm/userfaultfd.html
- spapas82 4y ago20 years ago in the programming languages lesson at the university we started learning about OOP using Java and Ada as examples. When the professor started describing Java, a fellow student interrupted him to inform the class that "Java has garbage collection" (and boast of his special knowledge). After that incident his nickname was "the garbage collector"!
- ajdude 4y agoCoincidentally, Ada optionally supports garbage collection in its specifications but it's up to the runtime to implement it.
- pjmlp 4y agoAnd since no implementation has ever supported it, it has been deprecated in ISO Ada 95 and further removed from it on ISO Ada 2012. https://en.wikibooks.org/wiki/Ada_Programming/Pragmas/Controlled https://en.wikibooks.org/wiki/Ada_Programming/Pragmas/Contro...
- admax88qqq 4y agoThere was this project though. https://github.com/Roldak/AGC https://github.com/Roldak/AGC The best part is that it's faster than manual management. People will tell you they need do to malloc and free manually for performance, but when you actually run the numbers GC wins for a majority of use cases.
- vlovich123 4y agoTracing garbage collectors don’t generally win against reference counting connectors, especially when those reference counts are automatically elided via ARC (eg swift and objective C) or because they’re rarely used by means of composition (c++ and rust). Additionally, different kinds of application strategies are better depending on the use case (eg a pool allocator that you bulk drop at the end of some computation). What papers are you referencing showing tracing GCs outperforming things? If it’s just the website, I think it’s an artifact of a micro benchmark rather than something that holds true for non trivial programs.
- cwzwarich 4y agoAnyone know what's new in this edition? Both the publisher's site and the author's site are light on details.
- 29athrowaway 4y ago[flagged]
- frou_dh 4y agoWho is Robert Sewell and why are his preferences interesting?
- hutzlibu 4y agoI think it is a joke and at least to me it is funny, without knowing who that guy is or was.
- mr_00ff00 4y ago1. It’s a joke 2. Many great programmers hold the opinion that Java is horrible. Linus for example. So if Sewell doesn’t seem credible, try the creator of Linux and git.
- saagarjha 4y agoLinus's thoughts on programming languages aren't particularly enlightening either ;)
- pjmlp 4y agoI bet Linus does not get much outside C.
- manuelabeledo 4y ago> Many great programmers hold the opinion that Java is horrible. Could you name a few?
- mr_00ff00 4y agoLinus, Dijkstra, Stroustrup, to name a few. Time has shown OOP is not good.
- 4y ago
- pjmlp 4y agoGreat that is having an update, it is one of the most relevant source of informations for GC algorithms.
- mananaysiempre 4y agoNote that (the first edition of) this book considers reference counting, including variations like deferred reference counting, to be garbage collection (though not tracing garbage collection), and reviews it as well.
- pjmlp 4y agoJust like most relevant computer science sources do, only joe and jane on the street without CS background think otherwise.
- LadyCailin 4y agoBizarre that you can't preorder it yet, you have to wait until June, just to preorder.
- mananaysiempre 4y agoAs a guess, they might want the accounting for preorders to fall into Q3? Is that a thing people do?
- mcculley 4y agoMaybe there is gamesmanship around best seller lists?
- rwmj 4y agoI managed to pre-order it on Amazon UK.
- avinassh 4y agoits available on amazon to pre order - https://www.amazon.com/dp/1032218037 https://www.amazon.com/dp/1032218037
- zzxcvb 4y agoI pre-ordered it from the linked website. Maybe it's only available for certain regions?
- m3kw9 4y agoWho would usually need this book?
- rwmj 4y agoThe first edition is a definitive reference for anyone writing a garbage collector (and by extension, exploring writing a programming language). Also people who are interested in how GCs work. Probably less so for people trying to optimize a program to work with an existing GC (eg. tweaking the JVM), but I suppose knowing the basic principles can help.
- mkl95 4y agoI read the mark-and-sweep GC parts to gain some deeper understanding about Go's garbage collector. Probably the best resource for that kind of stuff other than reading actual code.
- parenthesis 4y agoThis book (the 1st edition) gave me exactly what I needed when writing the garbage collector for my programming language. Besides the great technical content, I found it to be a very enjoyable, readable book.
- whartung 4y agoI’ve written two garbage collectors in my time, neither of which were in a programming language. One was for an in memory cache of data relationships. Another was to clean up soft references with an RDF graph. Neither were, nor needed to be, particularly sophisticated. The cache was a compacting collector, the RDF one was mostly a “connectedness” test, pruning those nodes fallen from the graph. Recall that malloc has a simple garbage collector for its free space, and arguably the level of sophistication that ranks a modern malloc implementation is how it manages its free space. In the end detritus must be identified and resources reclaimed. So you see how GC like systems can occur in divergent areas of work.
- cidd 4y agoRust has left the building
- rwmj 4y agoRust also uses reference counting, probably the worst sort of garbage collection.
- mr_00ff00 4y agoTracing is the worst in terms of performance
- SideQuark 4y agoThat depends. Deallocating a zillion little objects one a a time can be slower than doing them all in a batch.
- _a_a_a_ 4y ago[flagged]
- pjmlp 4y agoNot really, here it is winning hands down over Swift's ARC implementation. https://github.com/ixy-languages/ixy-languages https://github.com/ixy-languages/ixy-languages
- _a_a_a_ 4y agoMet Richard Jones, one of the authors of the book, at its original launch. Very nice guy. Bought the original book and did some heavy reading on it – if you get this book, be prepared to put time into it, it's readable but it's not one you can do a quick skim of – and I really profited from it. It should be required reading for all programmers. (To be clear, I'm referring to the very first version, I haven't read the subsequent versions but given the quality of the first I'd be very surprised if they were any less good). Edit: https://www.cs.kent.ac.uk/people/staff/rej/ https://www.cs.kent.ac.uk/people/staff/rej/ - a jumpoff page for his stuff. Edit2: https://www.cs.kent.ac.uk/people/staff/rej/gcbib/ https://www.cs.kent.ac.uk/people/staff/rej/gcbib/ - "[This] online bibliographic database includes nearly 3,000 garbage collection-related publications. It contains abstracts for some entries and URLs or DOIs for most of the electronically available ones, and is continually being updated. The database can be searched online or downloaded as BibTeX, PostScript, or PDF." Welcome to the ultimate rabbit hole I guess.
- samsquire 4y agoif you need code to understand garbage collection, there is walkthrough of garbage collector and C code at http://maplant.com/gc.html http://maplant.com/gc.html is really helpful. I tweaked it to work on amd64 and started adding register scanning based on what eatonphil's discord people told me to do. https://github.com/samsquire/garbage-collector https://github.com/samsquire/garbage-collector It's not fit for any purpose but more of a learning exercise.
- mananaysiempre 4y agoBob Nystrom (of Game Programming Patterns, Crafting Interpreters, and dartfmt fame) also wrote a tutorial implementation[1], of a precise tracing GC as opposed to a conservative one. Regarding register scanning in a conservative GC, Andreas Kling has made (or at least quoted) the amusing observation[2] that your C runtime already has a primitive to dump all callee-save registers to memory: setjmp(). So all you have to do to scan both registers and stack is to put a jmp_buf onto the stack, setjmp() to it, then scan the stack normally starting from its address. [1] https://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga... [2] https://youtu.be/IzB6iTeo8kk https://youtu.be/IzB6iTeo8kk
- sirwhinesalot 4y agoImplementations are unfortunately allowed to do whatever they want to that jmp_buf, they could xor the contents for all you know. Hopefully no implementation does something silly like that.
- mananaysiempre 4y agoThis seems like a reasonable environmental assumption if you’re already scanning the stack conservatively. I’d be more worried about pointer authentication (AArch64), pointer encryption (Glibc) or perhaps register windows (SPARC, Itanium). Still, as a cheap trick for avoiding assembly it seems to work well enough in non-exotic situations.
- 4y ago
- einpoklum 4y agoI feel the need for garbage collection is a language design mis-feature. That is to say, producing garbage is a language design-mis-feature. To quote Bjarne Stroustrup: > I don't like garbage. I don't like littering. My ideal is to eliminate the > need for a garbage collector by not producing any garbage. That is now > possible. and it's indeed possible. For example It's become pretty much a non-issue in modern C++: https://stackoverflow.com/a/48046118/1593077 https://stackoverflow.com/a/48046118/1593077 (and C++ is not the only example, it's just a prominent example of a language which almost standardized garbage collection, but eventually did not go that way.)
- winrid 4y agoI wouldn't say it's a non issue. I frequently have to tune allocators to fix heap fragmentation in databases...
- sirwhinesalot 4y agoC++ can actually produce quite a bit of garbage unintentionally, it's why linters will remind you often to call std::move. That said I much prefer deterministic resource cleanup even in a janky language like C++ over a tracing GC.
- einpoklum 4y agoIt's true that C++ can trigger a lot of unnecessary copying if one writes carelessly; but that's not the same as garbage, in that both copies are used, and none of them continue living indefinitely without special intervention. But point taken about pass-by-value deficiencies.
- mkl95 4y agoWill there be a PDF / epub option?
- vincent-manis 4y agoIf I'm not mistaken, Routledge uses that VitalSource dreck, so you can only read their ebooks via a dedicated app. I don't buy dead-tree books any more, but I'll make an exception for this one.
- microtherion 4y agoThe previous edition of this book is available on e.g. Apple's bookstore and Kindle. Unfortunately, the new one does not show an eBook option yet. I very much hope that one will be available soon, instead of them holding back the eBook to goose hardcover sales or some other reason.
- daveoc64 4y agoLooks like their ebooks are available through a number of sources: https://www.routledge.com/our-products/ebooks https://www.routledge.com/our-products/ebooks
- Dwedit 4y agoWhat I really want out of a garbage collector is a "Collect" function with a deadline. Pick a max time it's allowed to run before stopping and returning to the program.
- NobleExpress 4y agoReal time GCs exist such as the IBM Metronome GC. Though I'll be honest and say I haven't heard of many real-time GCs other than the Metronome one. Certainly many new GCs have reduced pause times dramatically but that's orthogonal to real-time GC (as you can make pause times infinitesimally small but not let the mutator actually progress).
- deleted 4y ago[deleted]
- pjmlp 4y agoSee PTC and Aicas.
- mananaysiempre 4y agoHere’s a fairly extensive review that mentions some recent research on “real-time” GCs, including one with a lower bound for mutator utilization: https://eschew.wordpress.com/2016/09/02/summarizing-gc/ https://eschew.wordpress.com/2016/09/02/summarizing-gc/.
- bob1029 4y agoI've achieved GC timing that is good enough for real-time competitive game hosting using .NET6+. Worst case over 4 hours of load testing was an 8ms spike. Average 1-2ms. The magic trick is to intentionally collect as often as reasonably possible (i.e. at batch/frame/tick processing boundaries) and avoid using sophisticated GC schemes that involve multiple threads or asynchrony. Oh, and obviously you need to minimize allocations throughout or it won't matter.
- auxym 4y agoNim has exactly that with the GC_step proc. https://nim-lang.org/1.4.0/gc.html https://nim-lang.org/1.4.0/gc.html However recent and future versions (2.0) are moving towards a different approach that is also applicable for deterministic real time systems: ARC, which is basically alloc and free calls inserted automatically by the compiler using static analysis (no "runtime").
- vrglvrglvrgl 4y ago[dead]
- t-3 4y agoI found "A Unified Theory of Garbage Collection" helpful: https://dl.acm.org/doi/10.1145/1035292.1028982 https://dl.acm.org/doi/10.1145/1035292.1028982
- nektro 4y agodarn i thought this was gonna be a book about waste management
- fithisux 4y agoDo we need this book now that we have Rust ??
- dreamcompiler 4y agoThat's like asking "Do we need Go now that we have Rust?"
- fithisux 4y agoExactly that. BTW My comment was ironic.
- mcguire 4y agoNo. Rust has completely consigned all of computer science to the dustbin of irrelevance.
- vincent-manis 4y agoPerhaps someone will rewrite this book (the whole book, not just the code) in Rust.
- rurban 4y agoRust removed its garbage collector and memory safety 9 years ago. Stack overflows and unsafeties are plaguing it since. Reading such a book would be a necessity for rustaceans esp.
- comonoid 4y agoWell, we may use it to re-implement a GC in Rust!
- sirwhinesalot 4y agoI don't know if it is included in the new edition of the book but in case anyone is interested in a modern, highly efficient RC implementation that does not rely on deferring the reference count updates (which kills one of the advantages of RC in the first place), check the Perseus paper. Koka (which uses perseus) is quite competitive with OCaml and Haskell Just search for "perseus reference counting", you'll find it. It uses linear logic to insert explicit "dup/drop" operations and then merges and coalesces them.
- throw10920 4y agoIs there any particular reason you didn't link to the paper itself (https://www.microsoft.com/en-us/research/uploads/prod/2020/11/perceus-tr-v1.pdf https://www.microsoft.com/en-us/research/uploads/prod/2020/1...) or use Microsoft's scuffed version of DOI (MSR-TR-2020-42)? The paper appears to be freely available, so there shouldn't be copyright issues with linking to it...
- sirwhinesalot 4y agoJust that I'm on mobile and am lazy. Thanks for posting it!
- jimsimmons 4y agoApart from the paper are there independent verifications of the technique's performance?
- sirwhinesalot 4y agoThe Roc language uses it too and shows similar performance. It's not magic though, it just takes advantage of RC for various optimizations (like "Functional But In Place") which add up and compensate for the added burden of ref count manipulation.
- throwaway81523 4y agoWow, this really is a new edition that will be available in 2023. The old (2012) edition is excellent. I don't have the impression that a whole lot has changed since then, but an update with all the latest refinements has to be worthwhile to implementers.