13 ms·

A pretty naive question: what is the advantage of garbage collection over just reference counting? It seems one benefit is handling circular references, but ev

• chc4 4y ago
  Handling circular references is pretty important! Things like closing over an environment in a scripting language usually creates a cyclic reference, for example (stack frame contains a closure, which contains a reference to...the parent stack frame), or any graph-like data structures. There is also just a cost to maintaining reference counts, which may be expensive if you are cloning and dropping values very often. A garbage collector can mean that cloning or destroying a reference has zero cost instead, along with batching destructors like you mentioned. I'd also like to point out that technically reference counting is a garbage collection scheme! You can even use a cycle collector that runs occasionally over reference counted objects in order to free unreachable cycles; Python for example does this!
  • kragen 4y ago
    in ur-scheme i put the variables that are captured by closures into heap-allocated cells; both the original stack frame and the closures contain pointers to these cells, eliminating the circular references, but adding an additional indirection step to accessing those variables theoretically this gives you more precise garbage collection, but it does give the collector more allocations to worry about it also allows you to use a traditional stack for your stack, rather than a bunch of heap-allocated things, and that's probably a win
• pkd 4y ago
  There is a great discussion of the trade-offs in this podcast episode with Stephen Dolan, who works on Ocaml. Link to the start of the relevant section in the transcript: https://signalsandthreads.com/memory-management/#000752 https://signalsandthreads.com/memory-management/#000752
• jonhohle 4y ago
  You’ve never needed a doubly linked list, tree that could be traversed in either direction or a graph?
  • vore 4y ago
    You can generally make do with weak references. For a doubly-linked list, you can make the backwards pointer weak.
• ufo 4y ago
  Circular references is a big one. There are also performance advantages though. Reference counting turns operations that would normally be just a memory read into a read+write, because of the need to update reference counts. You also need more bookkeeping space: a garbage collector only needs a bit or two per object, while a reference count needs several bits (up to a full word in the worst case).
• eternalban 4y ago
  GCs can be integrated with allocators to give you memory management. GCs can (not all do) 'move' live objects to compact memory giving better locality and thus performance. GC is applied by runtime and is systemic. If runtime is bug free so are the memory management bits of your code. Less code also reduces probability of bugs and lack of explicit memory management naturally reduces lines of code. I think the reasonable questions are along the lines of 'when is it not a good idea to use a GC?'. Things like performance, restrictions its places on languages, explicit memory management, and also restrictions on what you can do in your code. The Boehm GC here, for example, has a limited sense of what are 'references' -- it only knows pointers -- so any kind of object composition scheme that is not based on pointers (or mushes pointers like XOR linked list) is seen as 'data' by the GC and could cause bugs.
• ajross 4y ago
  > A pretty naive question: what is the advantage of garbage collection over just reference counting? It's not that naive, and the unpopular answer is "not much". A good modern GC, faced with a usage paradigm that it expects (this part is important!), is almost certainly going to be faster. It's indeed safe from circular reference leaks. Generational collectors can often compact memory better and have a smaller footprint for the same data. Those are all real advantages. But they come at the cost of outrageous complexity and code footprint. A reference counter is probably more than an 80% solution for almost any reasonable application, and it's something college kids write in 15-20 lines in their intro course.
  • astrange 4y ago
    Reference counting also usually has lower peak memory and scans less memory so is friendlier when you have either battery power or swap, ie, any non-server use case.
  • rwmj 4y ago
    Practically, someone else writes the garbage collector, so the supposedly "outrageous" complexity isn't an actual issue. Also I wouldn't say the complexity is much different from any other issue writing a programming language.
    • ajross 4y ago
      That's true for the case of simple apps that use a single runtime. Lots and lots of work is done "in Java" or "in Go". Lots more, including most of the largest and most complicated[1] apps, require synthesis of lots of tools from lots of sources. Those apps need to work very hard to get their heaps to play nicely with each other, and the tuning required by modern collected runtimes tends to blow up in strange ways. [1] And especially including the ones targetted by the Boehm collector in the linked github. Also apps for which Rust (which famously eschews a collected heap) tends to be proposed.
  • kaba0 4y ago
    A very naive tracing GC is not more complex either, and is absolutely in the ballpark of “college kids”.
• gumby 4y ago
  Another is amortization of bookkeeping: reference counting must be managed every time you record or remove a pointer while the GC does the tracing. So depending on your usage one may be faster than the other. Another is the opportunity to do the GC on another thread (careful!), or just when you have nothing else to do, meaning your hot path can be faster. Plus the very important case of circular or doubly linked structures that you mentioned.
• wbl 4y ago
  A reference counting implementation traces garbage, and has operations on every pointer deletion. A GC traces only live objects, and never operates on a deletion of a pointer. That can make it much more efficient for programs with much allocation and pointer manipulation.
  • KerrAvon 4y ago
    That’s theory, though — has any implementation ever achieved that?
    • wbl 4y ago
      The basic semispace collector does. The big issue with GC is the space required and tail latency but often people forger the latency of malloc.
      • pkolaczk 4y ago
        The latency of malloc is nothing compared to latency of even the best low-pause tracing GCs. Several orders of magnitude difference. Malloc/free typically run in tens of nanoseconds. Low pause GCs tend to pause for milliseconds (and this is already considered a success). Also the nature of pauses is different. A GC pauses everything. A malloc/free call only blocks the thread that called them. Threads that never allocate anything are never disturbed.
        • pebal 4y ago
          Only compacting GCs need to pause application. It is possible to implement GC without pauses.
          • pkolaczk 4y ago
            Yes, it is, but not without a cost. High throughput, no pauses, low memory overhead - pick two. However, stack-based allocation + statically inferred memory management + a tiny addition of reference counting only where needed (like in C++ or Rust) can easily get you all of those features in one program.
• vkou 4y ago
  A linked list is a reasonably common data structure, and will not be collected by a simple reference counting GC. Any data structure where child objects retain references to their parents (which is very common) would have this property.
  • KerrAvon 4y ago
    Which is why reference counting systems like Apple’s ARC have explicit weak reference support.
    • pjmlp 4y ago
      Which many programmers get wrong and lead to crashes, specially when they think they are clever than compiler optimizations. There is a WWDC talk about this for a reason.
• pkulak 4y ago
  I always thought it was the extra bookkeeping at runtime that was the drawback. Think of some tight loop that’s passing an object around. Your runtime has to inc and dec an integer (or similar) on every touch. Plus, you’re adding to the size of every object. A generational GC may never even touch 90% of all objects, since they don’t make it out of the eden generation. So you trade off some throughput for no pauses, which is why I imagine Apple prefers it. EDIT: oh, and reference counting is a garbage collector, just a rather simple one.
• adgjlsfhk1 4y ago
  Four reasons: 1. Reference counting scales with number of dead objects while Mark+Sweep typically scales with number of alive objects. This means that if you collect infrequently enough, a GC will have strictly less work to do. 2. RC involves a write whenever the reference count is increased. This means that in multi threaded contexts you need an atomic whenever a new reference is added. This will absolutely destroy performance in multi-threaded apps (this is the main reason why multi-threading in python doesn't exist). 3. RC requires a fairly high amount of metadata (often 32-64 bits per object). Mark sweep on the other hand often only needs a few (e.g. 2) bits per object. This is pretty heavy, especially for languages where everything is an object. 4. Circular references That said there is recent research suggesting that good algorithms can be made by combining RC with mark-sweep (e.g. https://dl.acm.org/doi/10.1145/3519939.3523440 https://dl.acm.org/doi/10.1145/3519939.3523440)
  • ithkuil 4y ago
    The sweep phase scales with the number of dead objects. Copying collectors have the property of scaling with the number of surviving objects, which makes them suitable for the first generation (nursery).
  • ratorx 4y ago
    Do you have any links to Python Atomic RC? I don’t know much about it, but I’d heard that it was the global interpreter lock that prevented multi-threading. I’d be surprised if the overhead of Atomic RC was that much, since it is a common pattern in Rust.
    • adgjlsfhk1 4y ago
      python doesn't have atomic rc. the gil prevents multithreading because experiments into removing the gil and replacing it with atomic reference counting had too high a performance overhead (roughly 2x for single threaded code). this is less of a problem for rust for 2 reasons: ARC is opt in and it's only used for a small fraction of objects, and compilers can do some fancy tricks and delete pairs of increments and decrements if it can prove that they don't cause corruption.
• ithkuil 4y ago
  > what is the advantage of garbage collection over just reference counting? One day a student came to Moon and said, "I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons." Moon patiently told the student the following story: "One day a student came to Moon and said, `I understand how to make a better garbage collector . . . '" Danny Hillis
• kaba0 4y ago
  I will start with a small nitpick: ref counting is a GC algorithm. The answer: tracing GCs have that much better throughput. This is partly due to having to use atomic increments/decrements in multithread environments, which will absolutely kill performance (flush caches, force synchronizations, etc). Another reason which is true even of single-threaded RC is that the work has to be done “on the spot”. Clever compiler tricks can optimize some of it away, but tracing GCs amortize the costs very well (at the cost of more memory usage, there is no free lunch) — if they are moving GCs they can basically use thread-local allocation buffers where allocation can be as cheap as like 4 instructions, and later moving the still used ones out to a different region, and deallocation can be as simple as a flag toggle, now a different region is considered as the used space, the whole of the former one can be considered garbage. Add to it that many parts of this can be made parallel, modern state-of-the-art tracing GCs are really really hard to beat in complex programs. Also, circular references are extremely common in complex programs, that in itself is a huge reason to have at least some hybrid solution (like python).