15 ms·

This debate has gone round and round for decades. There are no hard lines; this is about performance tradeoffs, and always will be. Perhaps the biggest misconc

This debate has gone round and round for decades. There are no hard lines; this is about performance tradeoffs, and always will be. Perhaps the biggest misconception about reference counting is that people believe it avoids GC pauses. That's not true. Essentially, whereas tracing GC has pauses while tracing live data, reference counting has pauses while tracing garbage. Reference counting is really just another kind of GC. I'd highly recommend perusing this paper for more details: A Unifying Theory of Garbage Collection. https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-garbage.pdf https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-... One of the biggest issues with reference counting, from a performance perspective, is that it turns reads into writes: if you read a heap-object out of a data structure, you have to increment the object's reference count. Modern memory architectures have much higher read bandwidth than write bandwidth, so reference counting typically has much lower throughput than tracing GC does.

kaba0 4y ago
One great example would be a C++ program that runs fast, and then just spends 10s of seconds doing “nothing” while it deallocates shared pointers’ huge object graphs at the end. They really are two sides of the same coin, with tracing GCs being actually correct (you need cycle detection for a correct RC implementation), and having much better throughput. It’s not an accident that runtimes with thousands dev hours are polishing their GC solutions instead of using a much more trivial RC.
- hinkley 4y ago
  I don't know what the current state of the art is, but at one point the answer to GC in a realtime environment was to amortize free() across malloc(). Each allocation would clear up to 10 elements from queue of free-able memory locations. That gives a reasonably tight upper bound on worst case alloc time, and most workflows converge on a garbage-free heap. Big malloc after small free might still blow your deadlines, but big allocations after bootstrapping are generally frowned upon in realtime applications, so that's as much a social problem as a technical one.
  - pclmulqdq 4y ago
    This is normal today inside malloc implementations.
    - hinkley 4y ago
      I think that’s been normal in malloc for some time. I maintain that we should all thank Java, and the hype train around it, for forcing operating systems to implement more robust threading support. Everyone wanted to be able to say they did Java well, and nearly every OS had capital ‘I’ Issues, including Solaris. Boy I bet those closed room arguments were epic. Where GCed languages pulled ahead for a while, particularly Java, was that they had mature concurrent memory allocation before most OSes did, so many people found on early two and four core hardware that malloc started to show up as a bottleneck.
- im3w1l 4y ago
  Fun fact: if you dont do anything important in the destructors you can avoid that delay by intentionally leaking the memory. The os will clean it up when the program exits and it does a better job since it frees the pages rather than looking at your objects one by one.
  - kaba0 4y ago
    Most GCs do exactly that -- they only "work" when absolutely necessary, and their heuristics says that they are getting behind the created garbage. If the program exits shortly after it will just leak the memory. The problem with that in the case of C++ is that you likely only want to leak things used in the end from the main thread, but not "recursively" - the distinction is hard to do.
    - wizofaus 4y ago
      It actually wouldn't surprise me that's the main reason GC often outperforms ARC in real- life software - simply because it's only necessary to actually bother doing GC once memory usage is high and there's a known need to allocate further memory. But couldn't ARC do the same thing in principle - i.e. only bother incrementing/decrementing reference counts when there's likely to be a need to reclaim memory? Even an infinitely running service can just accept it will increase its memory footprint up to a certain threshold then only bother with memory management at that point (I actually suspect SQL server works exactly like this!). For most short-running tools, no MM is required - the OS handles everything.
      - kaba0 4y ago
        As mentioned elsewhere in the thread, the actual reclamation can be done asynchronously, but the most problematic part, namely decrementing a counter atomically is the most problematic part and it can’t just be done later willy-nilly.
- pklausler 4y ago
  It's not marketed as a GC, but exit(2) is fast and effective when used as one.
  - saagarjha 4y ago
    Now you've pushed the job of cleaning up page tables to the OS.
    - chrisseaton 4y ago
      But that’s extremely easy - you go through a linear list once and free them all. You don’t even need to bring the contents from main memory to do it. (Exception is shared pages, not used for heap memory often.)
      - saagarjha 4y ago
        It's definitely easier, because you don't have interior pointers. But it's still work :)
    - jeeeb 4y ago
      The OS would have that job anyway.
    - int_19h 4y ago
      It's optimized for that, so just let it do its job. https://devblogs.microsoft.com/oldnewthing/20120105-00/?p=8683 https://devblogs.microsoft.com/oldnewthing/20120105-00/?p=86...
  - game-of-throws 4y ago
    I wouldn't call it a GC. It's more like an arena allocator, with the arenas managed by the OS :)
goodpoint 4y ago
It's not always a tradeoff: Nim switched from GC to RC and it even increased performance.
waterhouse 4y ago
> Essentially, whereas tracing GC has pauses while tracing live data, reference counting has pauses while tracing garbage. This is pretty trivial to avoid. When your thread finds itself freeing a big chain of garbage objects, you can have it stop at any arbitrary point and resume normal work, and find some way to schedule the work of freeing the rest of the chain (e.g. on another thread). It's much more complex and expensive to do this for tracing live data, because then you need to manage the scenario where the user program is modifying the graph of live objects while the GC is tracing it, using a write or read barrier; whereas for garbage, by definition you know the user can't touch the data, so a simple list of "objects to be freed" suffices. "Reads become writes" (indeed, they become atomic read-modify-writes when multiple threads might be refcounting simultaneously) is a problem, though.
- kaba0 4y ago
  > It's much more complex and expensive to do this for tracing live data But this is what happens in a modern state-of-the-art tracing GC implementation, isn't it?
- pjmlp 4y ago
  And so it becomes a simple tracing GC implementation, while one keeps calling it RC to feel good.
arcticbull 4y ago
RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from bottom to top once in a while. RC limits itself to modifying only relevant objects, whereas GC reads all objects in a super cache-unfriendly way. Yes, an atomic read-modify-write is worse than a read, but it's not worse than a linked-list traversal of all of memory all the time. And of course, not all kinds of object lend themselves to garbage collection - for instance, file descriptors, since you can't guarantee when or if they'll ever close. So you have to build your own reference counting system on top of your garbage collected system to handle these edge cases. There's trade-offs, yes, but the trade-off is simply that garbage collected languages refuse to provide the compiler and the runtime all the information they need to know in order to do their jobs - and a massive 30 year long effort kicked off to build a Rube Goldberg machine for closing that knowledge gap.
- klodolph 4y ago
  > RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from time to time. Depends on the GC algorithm used. Various GC algorithms only trace reachable objects, not unreachable ones. Reference counting does the opposite, more or less. When you deallocate something, it's tracing unreachable objects. One of the problems with this is that reference counting touches all the memory right before you're done with it. > And of course, not all kinds of object lend themselves to garbage collection - for instance, file descriptors, since you can't guarantee when or if they'll ever close. So you have to build your own reference counting system on top of your garbage collected system. This is not a typical solution. Java threw finalizers into the mix and everyone overused them at first before they realized that finalizers suck. This is bad enough that, in response to "too many files open" in your Java program, you might invoke the GC. Other languages designed since then typically use some kind of scoped system for closing file descriptors. This includes C# and Go. Garbage collection does not need to be used to collect all objects. > There's trade-offs, yes, but the trade-off is simply that garbage collected languages refuse to provide the compiler and the runtime all the information they need to know in order to do their jobs - and a massive 30 year long rube goldberg machine was built around closing that gap. When I hear rhetoric like this, all I think is, "Oh, this person really hates GC, and thinks everyone else should hate GC." Embedded in this statement are usually some assumptions which should be challenged. For example, "memory should be freed as soon as it is no longer needed".
hinkley 4y ago
What is your read on the lack of discussion of escape analysis? My own read on this is that it blurs the line with deferred collection/counting, because you could either use it to complement deferral making it cheaper, or avoid deferral because you're getting enough of the benefits of deferral by proving objects dead instead of discovering that they are dead.
- pjmlp 4y ago
  Likewise it means that heap allocation on a tracing GC never took place and the object was allocated on the stack, or if small enough, on registers.
im3w1l 4y ago
If you use refcounted pointers for everything then you'd be better off with a proper gc. But at least in the programs I see, 99% of objects are not refcounted , and that is reserved for a tiny majority of objects with especially tricky lifetimes.
- eru 4y ago
  Nowadays good compilers can handle many of these non-tricky lifetimes statically, too.
- ncmncm 4y ago
  This is the key. Using std::shared_ptr in a performance-sensitive context (e.g. after startup completes) is code smell. Using pointers as important elements of a data structure, such that cycles are possible at all, is itself code smell. A general graph is usually better kept as elements in a vector, deque, or even hash table, compactly, with indices instead of pointers, and favoring keeping elements used near one another in the same cache line. Overuse of pointers to organize data tends to pointer-chasing, among the slowest of operations on modern systems. Typical GC passes consist of little else but pointer chasing. But the original article is completely, laughably wrong about one thing: an atomic increment or decrement is a remarkably slow operation on modern hardware, second only to pointer chasing. Systems are made fast by avoiding expensive operations not dictated by the actual problem. Reference counting, or any other sort of GC, counts as overhead: wasting time on secondary activity in preference to making forward progress on the actual reason for the computation. Almost invariably neglected or concealed in promotion of non-RC GC schemes is overhead imposed by touching large parts of otherwise idle data, cycling it all through CPU caches. This overhead is hard to see in profiles, because it is imposed incrementally throughout the runtime, showing up as 200-cycle pauses waiting on memory bus transactions that could have been satisfied from cache if caches had not been trashed. If a core is devoted to GC, then sweeps would seem to cycle everything through just that core's cache, avoiding trashing other cores' caches. But the L3 cache used by that core is typically shared with 3 or 7 other cores', so it is hard to isolate that activity to one core without wastefully idling those others. Furthermore, that memory bus activity competes with algorithmic use of the bus, slowing those operations. Another way GC-dependence slows programs is by making it harder, or even impossible, to localize cost to specific operations, so that reasoning about perforce becomes arbitrarily hard. You lose the ability to count and thus minimize expensive operations, because the cost is dispersed throughout everything else.
pornel 4y ago
Saying that both have pauses is a false equivalence to me. It overlooks the difference in how likely this can occur (without large enough object graphs freed from the top it may never be an issue), when this occurs (any time vs on cleanup that may not be latency sensitive), and how much control the programmer has over RC costs (determinism allows to profile this and apply mitigations). RC with borrow checking can avoid a lot of refcount increments. Tracking GC typically needs write barriers, so it’s not free either.
- kaba0 4y ago
  > and how much control the programmer has over RC costs (determinism allows to profile this and apply mitigations). I fail to see how would it be deterministic in a highly dynamic program. Like, imagine a game for example where the user can drag'n'drop different things to a "parent" object. Observability is imo an entirely different axis. > RC with borrow checking can avoid a lot of refcount increments. That's the same thing as escape analysis - with language support many many objects could be effectively "removed" from the guidance of the GC, decreasing load and greatly improving performance. It is a language-level feature, not inherent in the form of GC we do (RC vs tracing)
  - _gabe_ 4y ago
    > Like, imagine a game for example where the user can drag'n'drop different things to a "parent" object. Where is the reference count going to 0 here? Presumably the object you dragged from one parent to another parent just swapped the reference and no ref count ever went to 0 which would have triggered a free. I'm guessing OP meant deterministic as in, "oh when I profile my code and it hits that big lag spike, this occurs in my particle system. Let's swap that to a fixed size static memory allocation instead of RC". Whereas with GC you say, "oh my program has a big lag spike. I wish I could tell why that is, but the code executing at that time may or may not have been the reason GC was collecting then". The only experience I've had trying to get accurate profiling data on memory usage in Java/C# was aggravating to say the least. Also, most games these days (and probably since the beginning of gaming) don't allocate and free stuff randomly. They're most likely using RC on big blocks of memory that are shared among several other game objects. Or RC on several fixed size pools that get used for different components like in an ECS. Or they use RC for things like long living assets that have difficult lifetime management. Honestly, RC and garbage collection are unnecessary in most instances. Most of the time all you need is a unique pointer because you know exactly where the ownership of the object lies. For the edge cases, RC works fine. I guess my biggest complaint is, why rely on a magical algorithm that you have no control over? I've had so many "fun" times trying to force GC to collect at specific points. It's really nice when you can say, "at this point in the program, this ref count will go to 0 and it will free and I don't have to worry about it lagging anything". Rather than "please GC.collect(), actually do something when I call you right here and don't wait another 5 minutes and ignore my pleading".
hamstergene 4y ago
For a unifying term I prefer Automatic Memory Management. One reason is that GC is already universally used to mean only tracing garbage collection, and trying to defend its wider meaning is a pointless uphill battle. Another is that is suits the job much better, because not every AMM technique works by producing garbage then collecting it, you know.
- omginternets 4y ago
  What are these other techniques and what can a technically-literate newcomer like myself read to get acquainted?
- kibwen 4y ago
  If you want to get even more precise, call it automatic dynamic memory management. Automatic static memory management would be something like Rust's scope-based memory reclamation via ownership.
  - pjmlp 4y ago
    Great to confuse more people instead of properly learning about affine type systems.
    - kibwen 4y ago
      There's no confusion here? This is a perfectly natural classification, that satisfies many people's intuition about Rust as having "compile-time GC". If anything, bringing up affine type systems is more liable to confuse people in this context; just because a language has an affine type system doesn't necessarily mean it needs to use it for memory management.
- pjmlp 4y ago
  I just keep feeding them the respective CS literature.
- Someone 4y ago
  > not every AMM technique works by producing garbage then collecting it And the confusing thing is that garbage collection (GC) doesn’t collect garbage, while reference counting (RC) does. GC doesn’t look at every object to decide whether it’s garbage (how would it determine nothing points at it?); it collects the live objects, then discards all the non-live objects as garbage. RC determines an object has become garbage when its reference count goes to zero, and then collects it. That difference also is one way GC can be better than RC: if there are L live objects and G garbage objects, GC has to visit L objects, and RC G. Even if GC spends more time per object visited than RC, it still can come out faster if L ≪ G. That also means that GC gets faster if you give it more memory so that it runs with a smaller L/G ratio (the large difference in speed in modern memory cache hierarchies makes that not quite true, but I think it still holds, ballpark)
cwaffles 4y ago
I disagree with the statement that modern memory architectures have much higher read bandwidth vs write bandwidth. Benchmarks show they are within 30 percent of each other: https://www.techspot.com/images2/news/bigimage/2021/03/2021-03-16-image-44.jpg https://www.techspot.com/images2/news/bigimage/2021/03/2021-... https://www.anandtech.com/show/2525/5 https://www.anandtech.com/show/2525/5
- yxhuvud 4y ago
  While perhaps true, what needs to be compared here is read, vs read + write, no? Just writing isnt enough. And then we are at a factor above 2, assuming no thread contention. If there is contention, it can be a lot higher.
- adrianN 4y ago
  While "write bandwidth" is probably not the right term, writes are more expensive because you need to update caches. If you forked you might need to copy-on-write the page before you can write to it.
deterministic 4y ago
I am the maintainer of a very high-performance JIT compiler for a Haskell like rules programming language used by large enterprises around the world. It uses reference counting + a global optimisation step to reduce the reference count updates to an absolute minimum. The result is compiled code that runs faster than C++ code carefully hand optimised by C++ experts over a 10 year period. There are zero GC pauses. Unless you claim that a C++ alloc/feee call is “garbage collection”. Which is not common terminology. It also (BTW) scales linearly the more cores you throw at it.
- refulgentis 4y ago
  I'm not sure whats being asserted here, could you explain more? This sounds like you're describing a non-stopping GC, and its well understood reference counting is garbage collection. I'm not sure how the rest applies, you're correct, it is possible to write software with just malloc and free.
  - cakoose 4y ago
    Re: "it's well understood reference counting is garbage collection". I think this might just be a terminology thing. There appear to be two ways the terms are categorized: 1. "reference counting" and "garbage collection" are two types of automatic memory management/reclamation. 2. "reference counting" and "tracing garbage collection" are two types of garbage collection. I think mbrodersen is using #1. (Back in the 90s and 2000s I feel like #1 was much more prevalent. But #2 seems to have gained popularity since then. My theory is that whoever started writing the Wikipedia content for this stuff picked #2.)
    - rowanG077 4y ago
      I never understand why people refer to reference counting as garbage collection. It waters down the term so much it becomes essentially useless. Because under that assumptions basically every language has garbage collection in some shape or form.
      - 4y ago
MaulingMonkey 4y ago
> Perhaps the biggest misconception about reference counting is that people believe it avoids GC pauses. That's not true. When I can easily replace the deallocator (thus excluding most non-RC production GCs), I can (re)write the code to avoid GC pauses (e.g. by amortizing deallocation, destructors, etc. over several frames - perhaps in a way that returning ownership of some type and its allocations to the type's originating thread, and thus reducing contention while I'm at it!) I have done this a few times. By "coincidence", garbage generation storms causing noticable delays are suprisingly uncommon IME. As programs scale up and consume more memory, "live data" outscales "garbage" - clever generational optimizations aside, I'd argue the former gets expensive more quickly, and is harder to mitigate. It's also been my experience that tracing or profiling any 'ole bog standard refcounted system to find performance problems is way more easy and straightforward than dealing with the utter vulgarity of deferred, ambiguously scheduled, likely on a different thread, frequently opaque garbage collection - as found in non-refcounted garbage collection systems. So, at best, you're technically correct here - which, to be fair, is the best kind of correct. But in practice, I think it's no coincidence that refcounting systems tend to automatically and implicitly amortize their costs and avoid GC storms in just about every workload I've ever touched, and at bare minimum, reference counting avoids GC pauses... in the code I've written... by allowing me easier opportunities to fix them when they do occur. Indirectly causal rather than directly causal. > if you read a heap-object out of a data structure, you have to increment the object's reference count. This isn't universal. Merely accessing and dereferencing a shared_ptr in C++ won't touch the refcount, for example - you need to copy the shared_ptr to cause that. Rust's Arc/Rc need to be clone()d to touch the refcount, and the borrow checker reduces much of the need to do such a thing defensively, "in case the heap object is removed out from under me". Of course, it can be a problem if you bake refcounting directly into language semantics and constantly churn refcounts for basic stack variables while failing to optimize said churn away. There's a reason why many GCed languages don't use reference counting to optimize the common "no cycles" case, after all - often, someone tried it out as an obvious and low hanging "optimization", and found it was a pessimization that made overall performance worse! And even without being baked into the language, there are of course niches where heavy manipulation of long-term storage of references will be a thing, or cases where the garbage collected version can become lock-free in a context where such things actually matter - so I'll 100% agree with you on this: > There are no hard lines; this is about performance tradeoffs, and always will be.
osigurdson 4y ago
One thing that is particularly strange in C#, is objects can respond to events / delegates after they have gone out of scope. It can be quite a while before the object is actually collected - especially if it ends up on the large object (85K+) heap. This seems like an incredibly leaky abstraction to me. The whole "using" concept is a bit of an abomination as well = though getting better. The issue with GC is it is a fluid implementation detail that is often necessary to understand deeply.
- Matthias247 4y ago
  I don't get that part. If it can receive an event/delegate, it means the object needs to be referenced by another object which invokes the event. If that is the case - how would be eligible for GC at all?
  - btilly 4y ago
    Consider an object referring to a network connection, say to a database. The object may be eligible for garbage collection but still have to respond to events from the network. When it finally gets destroyed, its Destructor method would be called. At which point the thing at the other end of the network is told that it was talking to a zombie. Note that network connections can be expensive for the other end, so this is a horrible design. We put a lot of work in to reliably get rid of connections when not needed. But you still need the fallback of being able to correctly handle programmer oversights.
    - mypalmike 4y ago
      Yeah you can't apply C++ style resource management (specifically, calling close() in destructors or expecting cascading destructors to trigger in sequence) to GC languages. Object lifetime in a GC languages does not generally align with desired resource lifetimes. You have to be explicit. This often means creating your own public close methods when wrapping a resource in a class.
  - Thiez 4y ago
    One far-fetched yet simple example would be an observer/observable pair, where the observable mutates observed properties inside its finalizer. The observable will usually contain a reference to the observer, but not the other way round. So when the observable is dead but the observer (optionally) still alive, when the observables finalizer runs it will send a message to the observer. When our observer is also dead (so the pair is out of scope) it will be a dead object receiving events.
zozbot234 4y ago
> One of the biggest issues with reference counting, from a performance perspective, is that it turns reads into writes: if you read a heap-object out of a data structure, you have to increment the object's reference count. You have to do this if you want deterministic deallocation, because your holding a read-only reference to that object might be exactly what keeps it around for longer. So you need to track that. (Deterministic deallocation also means having to recursively free unreachable objects. That's often described as an arbitrary "pause" behavior in RC systems, but it's actually inherent in the requirement for deterministic behavior. If you don't care about determinism for some class of objects, you can amortize that pause by sending them to a separate cleanup thread.)
pkolaczk 4y ago
Pausing a single thread to release memory is not what is considered a "pause". Even if pausing a single thread could be a problem, you can trivially offload releasing to another thread. A pause is when all application threads get paused. Hence, reference counting does not have a problem of pauses, and tracing often does.
tuetuopay 4y ago
> One of the biggest issues with reference counting, from a performance perspective, is that it turns reads into writes: if you read a heap-object out of a data structure, you have to increment the object's reference count. This is one of the biggest misconception about RC. You need not to increase the refcount just to read the referred data because you already have a reference whose count has been increased when handed down to you. That’s a semantic that’s very well carried off by Rust’s Arc type: the count is inc’ when the Arc is cloned, and dec’ when the cloned Arc is dropped. But you can still get a regular ref to the data since the compiler will be able to enforce locally the borrow, ownership and lifetime rules. For example, in a web server, you might have the app’s config behind an Arc. It gets cloned for each request (thus rc inc’d), read a lot during the req, then dropped (thus rc dec’d) at the end of the handler.
citrin_ru 4y ago
> reference counting has pauses while tracing garbage. Which pauses you are meaning? Reference counting is not free, but there are no long pauses (long compare to GC, e. g. in JVM under certain workloads you can get 100ms pauses).

kaba0 4y ago

One great example would be a C++ program that runs fast, and then just spends 10s of seconds doing “nothing” while it deallocates shared pointers’ huge object graphs at the end. They really are two sides of the same coin, with tracing GCs being actually correct (you need cycle detection for a correct RC implementation), and having much better throughput. It’s not an accident that runtimes with thousands dev hours are polishing their GC solutions instead of using a much more trivial RC.

hinkley 4y ago
I don't know what the current state of the art is, but at one point the answer to GC in a realtime environment was to amortize free() across malloc(). Each allocation would clear up to 10 elements from queue of free-able memory locations. That gives a reasonably tight upper bound on worst case alloc time, and most workflows converge on a garbage-free heap. Big malloc after small free might still blow your deadlines, but big allocations after bootstrapping are generally frowned upon in realtime applications, so that's as much a social problem as a technical one.
- pclmulqdq 4y ago
  This is normal today inside malloc implementations.
  - hinkley 4y ago
    I think that’s been normal in malloc for some time. I maintain that we should all thank Java, and the hype train around it, for forcing operating systems to implement more robust threading support. Everyone wanted to be able to say they did Java well, and nearly every OS had capital ‘I’ Issues, including Solaris. Boy I bet those closed room arguments were epic. Where GCed languages pulled ahead for a while, particularly Java, was that they had mature concurrent memory allocation before most OSes did, so many people found on early two and four core hardware that malloc started to show up as a bottleneck.
im3w1l 4y ago
Fun fact: if you dont do anything important in the destructors you can avoid that delay by intentionally leaking the memory. The os will clean it up when the program exits and it does a better job since it frees the pages rather than looking at your objects one by one.
- kaba0 4y ago
  Most GCs do exactly that -- they only "work" when absolutely necessary, and their heuristics says that they are getting behind the created garbage. If the program exits shortly after it will just leak the memory. The problem with that in the case of C++ is that you likely only want to leak things used in the end from the main thread, but not "recursively" - the distinction is hard to do.
  - wizofaus 4y ago
    It actually wouldn't surprise me that's the main reason GC often outperforms ARC in real- life software - simply because it's only necessary to actually bother doing GC once memory usage is high and there's a known need to allocate further memory. But couldn't ARC do the same thing in principle - i.e. only bother incrementing/decrementing reference counts when there's likely to be a need to reclaim memory? Even an infinitely running service can just accept it will increase its memory footprint up to a certain threshold then only bother with memory management at that point (I actually suspect SQL server works exactly like this!). For most short-running tools, no MM is required - the OS handles everything.
    - kaba0 4y ago
      As mentioned elsewhere in the thread, the actual reclamation can be done asynchronously, but the most problematic part, namely decrementing a counter atomically is the most problematic part and it can’t just be done later willy-nilly.
pklausler 4y ago
It's not marketed as a GC, but exit(2) is fast and effective when used as one.
- saagarjha 4y ago
  Now you've pushed the job of cleaning up page tables to the OS.
  - chrisseaton 4y ago
    But that’s extremely easy - you go through a linear list once and free them all. You don’t even need to bring the contents from main memory to do it. (Exception is shared pages, not used for heap memory often.)
    - saagarjha 4y ago
      It's definitely easier, because you don't have interior pointers. But it's still work :)
  - jeeeb 4y ago
    The OS would have that job anyway.
  - int_19h 4y ago
    It's optimized for that, so just let it do its job. https://devblogs.microsoft.com/oldnewthing/20120105-00/?p=8683 https://devblogs.microsoft.com/oldnewthing/20120105-00/?p=86...
- game-of-throws 4y ago
  I wouldn't call it a GC. It's more like an arena allocator, with the arenas managed by the OS :)

goodpoint 4y ago

It's not always a tradeoff: Nim switched from GC to RC and it even increased performance.

waterhouse 4y ago

> Essentially, whereas tracing GC has pauses while tracing live data, reference counting has pauses while tracing garbage. This is pretty trivial to avoid. When your thread finds itself freeing a big chain of garbage objects, you can have it stop at any arbitrary point and resume normal work, and find some way to schedule the work of freeing the rest of the chain (e.g. on another thread). It's much more complex and expensive to do this for tracing live data, because then you need to manage the scenario where the user program is modifying the graph of live objects while the GC is tracing it, using a write or read barrier; whereas for garbage, by definition you know the user can't touch the data, so a simple list of "objects to be freed" suffices. "Reads become writes" (indeed, they become atomic read-modify-writes when multiple threads might be refcounting simultaneously) is a problem, though.

kaba0 4y ago
> It's much more complex and expensive to do this for tracing live data But this is what happens in a modern state-of-the-art tracing GC implementation, isn't it?
pjmlp 4y ago
And so it becomes a simple tracing GC implementation, while one keeps calling it RC to feel good.

arcticbull 4y ago

RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from bottom to top once in a while. RC limits itself to modifying only relevant objects, whereas GC reads all objects in a super cache-unfriendly way. Yes, an atomic read-modify-write is worse than a read, but it's not worse than a linked-list traversal of all of memory all the time. And of course, not all kinds of object lend themselves to garbage collection - for instance, file descriptors, since you can't guarantee when or if they'll ever close. So you have to build your own reference counting system on top of your garbage collected system to handle these edge cases. There's trade-offs, yes, but the trade-off is simply that garbage collected languages refuse to provide the compiler and the runtime all the information they need to know in order to do their jobs - and a massive 30 year long effort kicked off to build a Rube Goldberg machine for closing that knowledge gap.

klodolph 4y ago
> RC may turn reads into writes, but of course, GC ends up having to go through literally every piece of memory ever from time to time. Depends on the GC algorithm used. Various GC algorithms only trace reachable objects, not unreachable ones. Reference counting does the opposite, more or less. When you deallocate something, it's tracing unreachable objects. One of the problems with this is that reference counting touches all the memory right before you're done with it. > And of course, not all kinds of object lend themselves to garbage collection - for instance, file descriptors, since you can't guarantee when or if they'll ever close. So you have to build your own reference counting system on top of your garbage collected system. This is not a typical solution. Java threw finalizers into the mix and everyone overused them at first before they realized that finalizers suck. This is bad enough that, in response to "too many files open" in your Java program, you might invoke the GC. Other languages designed since then typically use some kind of scoped system for closing file descriptors. This includes C# and Go. Garbage collection does not need to be used to collect all objects. > There's trade-offs, yes, but the trade-off is simply that garbage collected languages refuse to provide the compiler and the runtime all the information they need to know in order to do their jobs - and a massive 30 year long rube goldberg machine was built around closing that gap. When I hear rhetoric like this, all I think is, "Oh, this person really hates GC, and thinks everyone else should hate GC." Embedded in this statement are usually some assumptions which should be challenged. For example, "memory should be freed as soon as it is no longer needed".

hinkley 4y ago

What is your read on the lack of discussion of escape analysis? My own read on this is that it blurs the line with deferred collection/counting, because you could either use it to complement deferral making it cheaper, or avoid deferral because you're getting enough of the benefits of deferral by proving objects dead instead of discovering that they are dead.

pjmlp 4y ago
Likewise it means that heap allocation on a tracing GC never took place and the object was allocated on the stack, or if small enough, on registers.

im3w1l 4y ago

If you use refcounted pointers for everything then you'd be better off with a proper gc. But at least in the programs I see, 99% of objects are not refcounted , and that is reserved for a tiny majority of objects with especially tricky lifetimes.

eru 4y ago
Nowadays good compilers can handle many of these non-tricky lifetimes statically, too.
ncmncm 4y ago
This is the key. Using std::shared_ptr in a performance-sensitive context (e.g. after startup completes) is code smell. Using pointers as important elements of a data structure, such that cycles are possible at all, is itself code smell. A general graph is usually better kept as elements in a vector, deque, or even hash table, compactly, with indices instead of pointers, and favoring keeping elements used near one another in the same cache line. Overuse of pointers to organize data tends to pointer-chasing, among the slowest of operations on modern systems. Typical GC passes consist of little else but pointer chasing. But the original article is completely, laughably wrong about one thing: an atomic increment or decrement is a remarkably slow operation on modern hardware, second only to pointer chasing. Systems are made fast by avoiding expensive operations not dictated by the actual problem. Reference counting, or any other sort of GC, counts as overhead: wasting time on secondary activity in preference to making forward progress on the actual reason for the computation. Almost invariably neglected or concealed in promotion of non-RC GC schemes is overhead imposed by touching large parts of otherwise idle data, cycling it all through CPU caches. This overhead is hard to see in profiles, because it is imposed incrementally throughout the runtime, showing up as 200-cycle pauses waiting on memory bus transactions that could have been satisfied from cache if caches had not been trashed. If a core is devoted to GC, then sweeps would seem to cycle everything through just that core's cache, avoiding trashing other cores' caches. But the L3 cache used by that core is typically shared with 3 or 7 other cores', so it is hard to isolate that activity to one core without wastefully idling those others. Furthermore, that memory bus activity competes with algorithmic use of the bus, slowing those operations. Another way GC-dependence slows programs is by making it harder, or even impossible, to localize cost to specific operations, so that reasoning about perforce becomes arbitrarily hard. You lose the ability to count and thus minimize expensive operations, because the cost is dispersed throughout everything else.

pornel 4y ago

Saying that both have pauses is a false equivalence to me. It overlooks the difference in how likely this can occur (without large enough object graphs freed from the top it may never be an issue), when this occurs (any time vs on cleanup that may not be latency sensitive), and how much control the programmer has over RC costs (determinism allows to profile this and apply mitigations). RC with borrow checking can avoid a lot of refcount increments. Tracking GC typically needs write barriers, so it’s not free either.

kaba0 4y ago
> and how much control the programmer has over RC costs (determinism allows to profile this and apply mitigations). I fail to see how would it be deterministic in a highly dynamic program. Like, imagine a game for example where the user can drag'n'drop different things to a "parent" object. Observability is imo an entirely different axis. > RC with borrow checking can avoid a lot of refcount increments. That's the same thing as escape analysis - with language support many many objects could be effectively "removed" from the guidance of the GC, decreasing load and greatly improving performance. It is a language-level feature, not inherent in the form of GC we do (RC vs tracing)
- _gabe_ 4y ago
  > Like, imagine a game for example where the user can drag'n'drop different things to a "parent" object. Where is the reference count going to 0 here? Presumably the object you dragged from one parent to another parent just swapped the reference and no ref count ever went to 0 which would have triggered a free. I'm guessing OP meant deterministic as in, "oh when I profile my code and it hits that big lag spike, this occurs in my particle system. Let's swap that to a fixed size static memory allocation instead of RC". Whereas with GC you say, "oh my program has a big lag spike. I wish I could tell why that is, but the code executing at that time may or may not have been the reason GC was collecting then". The only experience I've had trying to get accurate profiling data on memory usage in Java/C# was aggravating to say the least. Also, most games these days (and probably since the beginning of gaming) don't allocate and free stuff randomly. They're most likely using RC on big blocks of memory that are shared among several other game objects. Or RC on several fixed size pools that get used for different components like in an ECS. Or they use RC for things like long living assets that have difficult lifetime management. Honestly, RC and garbage collection are unnecessary in most instances. Most of the time all you need is a unique pointer because you know exactly where the ownership of the object lies. For the edge cases, RC works fine. I guess my biggest complaint is, why rely on a magical algorithm that you have no control over? I've had so many "fun" times trying to force GC to collect at specific points. It's really nice when you can say, "at this point in the program, this ref count will go to 0 and it will free and I don't have to worry about it lagging anything". Rather than "please GC.collect(), actually do something when I call you right here and don't wait another 5 minutes and ignore my pleading".

hamstergene 4y ago

For a unifying term I prefer Automatic Memory Management. One reason is that GC is already universally used to mean only tracing garbage collection, and trying to defend its wider meaning is a pointless uphill battle. Another is that is suits the job much better, because not every AMM technique works by producing garbage then collecting it, you know.

omginternets 4y ago
What are these other techniques and what can a technically-literate newcomer like myself read to get acquainted?
kibwen 4y ago
If you want to get even more precise, call it automatic dynamic memory management. Automatic static memory management would be something like Rust's scope-based memory reclamation via ownership.
- pjmlp 4y ago
  Great to confuse more people instead of properly learning about affine type systems.
  - kibwen 4y ago
    There's no confusion here? This is a perfectly natural classification, that satisfies many people's intuition about Rust as having "compile-time GC". If anything, bringing up affine type systems is more liable to confuse people in this context; just because a language has an affine type system doesn't necessarily mean it needs to use it for memory management.
pjmlp 4y ago
I just keep feeding them the respective CS literature.
Someone 4y ago
> not every AMM technique works by producing garbage then collecting it And the confusing thing is that garbage collection (GC) doesn’t collect garbage, while reference counting (RC) does. GC doesn’t look at every object to decide whether it’s garbage (how would it determine nothing points at it?); it collects the live objects, then discards all the non-live objects as garbage. RC determines an object has become garbage when its reference count goes to zero, and then collects it. That difference also is one way GC can be better than RC: if there are L live objects and G garbage objects, GC has to visit L objects, and RC G. Even if GC spends more time per object visited than RC, it still can come out faster if L ≪ G. That also means that GC gets faster if you give it more memory so that it runs with a smaller L/G ratio (the large difference in speed in modern memory cache hierarchies makes that not quite true, but I think it still holds, ballpark)

cwaffles 4y ago

I disagree with the statement that modern memory architectures have much higher read bandwidth vs write bandwidth. Benchmarks show they are within 30 percent of each other: https://www.techspot.com/images2/news/bigimage/2021/03/2021-03-16-image-44.jpg https://www.techspot.com/images2/news/bigimage/2021/03/2021-... https://www.anandtech.com/show/2525/5 https://www.anandtech.com/show/2525/5

yxhuvud 4y ago
While perhaps true, what needs to be compared here is read, vs read + write, no? Just writing isnt enough. And then we are at a factor above 2, assuming no thread contention. If there is contention, it can be a lot higher.
adrianN 4y ago
While "write bandwidth" is probably not the right term, writes are more expensive because you need to update caches. If you forked you might need to copy-on-write the page before you can write to it.

deterministic 4y ago

I am the maintainer of a very high-performance JIT compiler for a Haskell like rules programming language used by large enterprises around the world. It uses reference counting + a global optimisation step to reduce the reference count updates to an absolute minimum. The result is compiled code that runs faster than C++ code carefully hand optimised by C++ experts over a 10 year period. There are zero GC pauses. Unless you claim that a C++ alloc/feee call is “garbage collection”. Which is not common terminology. It also (BTW) scales linearly the more cores you throw at it.

refulgentis 4y ago
I'm not sure whats being asserted here, could you explain more? This sounds like you're describing a non-stopping GC, and its well understood reference counting is garbage collection. I'm not sure how the rest applies, you're correct, it is possible to write software with just malloc and free.
- cakoose 4y ago
  Re: "it's well understood reference counting is garbage collection". I think this might just be a terminology thing. There appear to be two ways the terms are categorized: 1. "reference counting" and "garbage collection" are two types of automatic memory management/reclamation. 2. "reference counting" and "tracing garbage collection" are two types of garbage collection. I think mbrodersen is using #1. (Back in the 90s and 2000s I feel like #1 was much more prevalent. But #2 seems to have gained popularity since then. My theory is that whoever started writing the Wikipedia content for this stuff picked #2.)
  - rowanG077 4y ago
    I never understand why people refer to reference counting as garbage collection. It waters down the term so much it becomes essentially useless. Because under that assumptions basically every language has garbage collection in some shape or form.
    - 4y ago

MaulingMonkey 4y ago

> Perhaps the biggest misconception about reference counting is that people believe it avoids GC pauses. That's not true. When I can easily replace the deallocator (thus excluding most non-RC production GCs), I can (re)write the code to avoid GC pauses (e.g. by amortizing deallocation, destructors, etc. over several frames - perhaps in a way that returning ownership of some type and its allocations to the type's originating thread, and thus reducing contention while I'm at it!) I have done this a few times. By "coincidence", garbage generation storms causing noticable delays are suprisingly uncommon IME. As programs scale up and consume more memory, "live data" outscales "garbage" - clever generational optimizations aside, I'd argue the former gets expensive more quickly, and is harder to mitigate. It's also been my experience that tracing or profiling any 'ole bog standard refcounted system to find performance problems is way more easy and straightforward than dealing with the utter vulgarity of deferred, ambiguously scheduled, likely on a different thread, frequently opaque garbage collection - as found in non-refcounted garbage collection systems. So, at best, you're technically correct here - which, to be fair, is the best kind of correct. But in practice, I think it's no coincidence that refcounting systems tend to automatically and implicitly amortize their costs and avoid GC storms in just about every workload I've ever touched, and at bare minimum, reference counting avoids GC pauses... in the code I've written... by allowing me easier opportunities to fix them when they do occur. Indirectly causal rather than directly causal. > if you read a heap-object out of a data structure, you have to increment the object's reference count. This isn't universal. Merely accessing and dereferencing a shared_ptr in C++ won't touch the refcount, for example - you need to copy the shared_ptr to cause that. Rust's Arc/Rc need to be clone()d to touch the refcount, and the borrow checker reduces much of the need to do such a thing defensively, "in case the heap object is removed out from under me". Of course, it can be a problem if you bake refcounting directly into language semantics and constantly churn refcounts for basic stack variables while failing to optimize said churn away. There's a reason why many GCed languages don't use reference counting to optimize the common "no cycles" case, after all - often, someone tried it out as an obvious and low hanging "optimization", and found it was a pessimization that made overall performance worse! And even without being baked into the language, there are of course niches where heavy manipulation of long-term storage of references will be a thing, or cases where the garbage collected version can become lock-free in a context where such things actually matter - so I'll 100% agree with you on this: > There are no hard lines; this is about performance tradeoffs, and always will be.

osigurdson 4y ago

One thing that is particularly strange in C#, is objects can respond to events / delegates after they have gone out of scope. It can be quite a while before the object is actually collected - especially if it ends up on the large object (85K+) heap. This seems like an incredibly leaky abstraction to me. The whole "using" concept is a bit of an abomination as well = though getting better. The issue with GC is it is a fluid implementation detail that is often necessary to understand deeply.

Matthias247 4y ago
I don't get that part. If it can receive an event/delegate, it means the object needs to be referenced by another object which invokes the event. If that is the case - how would be eligible for GC at all?
- btilly 4y ago
  Consider an object referring to a network connection, say to a database. The object may be eligible for garbage collection but still have to respond to events from the network. When it finally gets destroyed, its Destructor method would be called. At which point the thing at the other end of the network is told that it was talking to a zombie. Note that network connections can be expensive for the other end, so this is a horrible design. We put a lot of work in to reliably get rid of connections when not needed. But you still need the fallback of being able to correctly handle programmer oversights.
  - mypalmike 4y ago
    Yeah you can't apply C++ style resource management (specifically, calling close() in destructors or expecting cascading destructors to trigger in sequence) to GC languages. Object lifetime in a GC languages does not generally align with desired resource lifetimes. You have to be explicit. This often means creating your own public close methods when wrapping a resource in a class.
- Thiez 4y ago
  One far-fetched yet simple example would be an observer/observable pair, where the observable mutates observed properties inside its finalizer. The observable will usually contain a reference to the observer, but not the other way round. So when the observable is dead but the observer (optionally) still alive, when the observables finalizer runs it will send a message to the observer. When our observer is also dead (so the pair is out of scope) it will be a dead object receiving events.

zozbot234 4y ago

> One of the biggest issues with reference counting, from a performance perspective, is that it turns reads into writes: if you read a heap-object out of a data structure, you have to increment the object's reference count. You have to do this if you want deterministic deallocation, because your holding a read-only reference to that object might be exactly what keeps it around for longer. So you need to track that. (Deterministic deallocation also means having to recursively free unreachable objects. That's often described as an arbitrary "pause" behavior in RC systems, but it's actually inherent in the requirement for deterministic behavior. If you don't care about determinism for some class of objects, you can amortize that pause by sending them to a separate cleanup thread.)

pkolaczk 4y ago

Pausing a single thread to release memory is not what is considered a "pause". Even if pausing a single thread could be a problem, you can trivially offload releasing to another thread. A pause is when all application threads get paused. Hence, reference counting does not have a problem of pauses, and tracing often does.

tuetuopay 4y ago

> One of the biggest issues with reference counting, from a performance perspective, is that it turns reads into writes: if you read a heap-object out of a data structure, you have to increment the object's reference count. This is one of the biggest misconception about RC. You need not to increase the refcount just to read the referred data because you already have a reference whose count has been increased when handed down to you. That’s a semantic that’s very well carried off by Rust’s Arc type: the count is inc’ when the Arc is cloned, and dec’ when the cloned Arc is dropped. But you can still get a regular ref to the data since the compiler will be able to enforce locally the borrow, ownership and lifetime rules. For example, in a web server, you might have the app’s config behind an Arc. It gets cloned for each request (thus rc inc’d), read a lot during the req, then dropped (thus rc dec’d) at the end of the handler.

citrin_ru 4y ago

> reference counting has pauses while tracing garbage. Which pauses you are meaning? Reference counting is not free, but there are no long pauses (long compare to GC, e. g. in JVM under certain workloads you can get 100ms pauses).