3 ms·

Chris Lattner on garbage collection vs. Automatic Reference Counting (2017), https://news.ycombinator.com/item?id=31139610 https://news.ycombinator.com/item?id=

Chris Lattner on garbage collection vs. Automatic Reference Counting (2017), https://news.ycombinator.com/item?id=31139610 https://news.ycombinator.com/item?id=31139610 See also “A unified theory of garbage collection” by Bacon, Cheng, and Rajan (OOPSLA ’04) for a discussion of how tracing and RC essentially compute the least and greatest fixed points, respectively, of the “roots and referents” function (the difference between the two being the reference cycles), and of course the Garbage Collection Handbook by Jones, Hosking, and Moss (CRC, 2012), which includes both tracing and RC in its definitions of GC and draws comparisons (barrier costs, heap fragmentation, etc.). (These are both bog-standard references, the thread above has people know much more about this talking about ideas that aren’t 20 years old.)

KMag 5y ago
Excellent answer. I would just add a brief summary, that naive reference counting does work proportional to the rate at which references are created and destroyed, and naive tracing collectors do work proportional to either the full heap size or the number of live objects on the heap. Note that as a rule of thumb, tracing garbage collectors need about twice as much memory as live objects, to avoid frequent heap scans. Non-delayed reference counting only keeps around live objects, which can significantly reduce memory usage. If you have a huge number of live objects that you need to keep around, but infrequently have references to them created (e.g. very large caches), then reference counting is going to out-perform tracing collection, particularly if some of those infrequently used objects might be paged out and you're not using card marking to sometimes avoid needing to trace the paged-out objects. It's convenient that these use cases also tend to work well with reference counting's generally lower peak memory requirements. On the other hand, if you're rapidly creating and destroying objects, or often updating references, tracing may perform better. Moving collectors (at least using moving or compacting collectors for the young generation) can use bump allocation, resulting in much faster object allocation. The Garbage Collection Handbook goes into nearly countless variations, hybridizations, and optimizations on these basic collectors. For over a decade, I helped maintain Goldman's Slang language. Some components had bog standard mark-and-sweep collector, but most of the language uses reference counting. The language uses tight integration with the SecDb globally distributed NoSQL database and pervasively locally caches database objects and memoizes method calls on those objects. I'm sure naive reference counting isn't optimal for the Slang use case, but it's easy to implement and isn't actually that far from optimal. (When I first started at Goldman, some parts of the language used an implementation of Bacon's cycle-detecting concurrent reference counting collector, but there was some rare corner case where someone missed a reference count change on the C++ side, and after a while of trying to find the missing reference count, we just replaced that component with a non-generational mark-and-sweep collector.) (There was a publish-subscribe system that would watch the SecDb transaction logs, so applications could subscribe for cache invalidation notifications. With huge caches, you don't want to use database polling for cache invalidation.)

KMag 5y ago

Excellent answer. I would just add a brief summary, that naive reference counting does work proportional to the rate at which references are created and destroyed, and naive tracing collectors do work proportional to either the full heap size or the number of live objects on the heap. Note that as a rule of thumb, tracing garbage collectors need about twice as much memory as live objects, to avoid frequent heap scans. Non-delayed reference counting only keeps around live objects, which can significantly reduce memory usage. If you have a huge number of live objects that you need to keep around, but infrequently have references to them created (e.g. very large caches), then reference counting is going to out-perform tracing collection, particularly if some of those infrequently used objects might be paged out and you're not using card marking to sometimes avoid needing to trace the paged-out objects. It's convenient that these use cases also tend to work well with reference counting's generally lower peak memory requirements. On the other hand, if you're rapidly creating and destroying objects, or often updating references, tracing may perform better. Moving collectors (at least using moving or compacting collectors for the young generation) can use bump allocation, resulting in much faster object allocation. The Garbage Collection Handbook goes into nearly countless variations, hybridizations, and optimizations on these basic collectors. For over a decade, I helped maintain Goldman's Slang language. Some components had bog standard mark-and-sweep collector, but most of the language uses reference counting. The language uses tight integration with the SecDb globally distributed NoSQL database and pervasively locally caches database objects and memoizes method calls on those objects. I'm sure naive reference counting isn't optimal for the Slang use case, but it's easy to implement and isn't actually that far from optimal. (When I first started at Goldman, some parts of the language used an implementation of Bacon's cycle-detecting concurrent reference counting collector, but there was some rare corner case where someone missed a reference count change on the C++ side, and after a while of trying to find the missing reference count, we just replaced that component with a non-generational mark-and-sweep collector.) (There was a publish-subscribe system that would watch the SecDb transaction logs, so applications could subscribe for cache invalidation notifications. With huge caches, you don't want to use database polling for cache invalidation.)