I disagree.
IMO the reason is simplicity, most languages don’t want to burden programmers with lifetimes and/or soft references.
Rust and Swift, both high-performance languages targeting specific niches, chose differently. Both largely for reasons of predictability, lower latency, lower memory use (which you admitted above) as well as lower memory trashing.
I'm talking about languages that already use a GC as the primary heap management mechanism. Any kind of GC algorithm, whether tracing or refcounting, frees developers from thinking about lifetimes, but languages that primarily rely on GC and care about performance almost always pick tracing.
The only languages that choose a refcounting GC are either those that care little about performance (Python) or those that don't rely heavily on GC (Rust).
> Both largely for reasons of predictability, lower latency, lower memory use
Refcounting offers worse latency, worse predictability [1] (compared to modern low-latency tracing GCs, like ZGC), and worse throughput; it does offer a significantly lower memory footprint. The reason Rust chose refcounting is primarily because it doesn't rely on the GC heavily and so it might as well use a crude GC (and enjoy the lower effort of implementing it as well as the lower footprint), as a crude refcounting GC is usually better than a crude tracing GC.
Furthermore, an sophisticated tracing GC is not a great fit for languages like Rust or C++ because it requires a more elaborate code generation and some "magical" mutator thread behaviour, when low-level languages like the generated code to be as close to the source code as possible. This isn't so much predictability of performance, but predictability of the generated code and the behaviour of mutators (in terms of lowering the surprise of "why is my thread doing _that_ now?" when observed at a low level). For example, with ZGC, a mutator thread may find itself moving an object when accessing it; this is surprising at a low level -- which may not be a good fit for a low-level language -- even though it ends up offering better performance predictability overall. On the other hand, a mutator thread doing work freeing memory with a refcounting GC when it's dropping a reference to it may offer worse latency and worse predictability overall, but it's not as surprising at a lower level in the sense that it's easy to understand why it's doing that.
As for Swift, I think it picked a refcounting algorithm because it cares about memory footprint (most Swift applications run in memory-constrained environments) and because some unique language features allow to reduce the cost of refcounting sufficiently for a simple refcounting GC to be acceptable.
[1]: Again, not in principle (as both refcounting and tracing can converge to a similar behaviour) but as practiced by most refcounting GCs in industry use.
Not true. The creators of Swift chose RC exactly for performance reasons: low memory footprint AND low latency.
//edit: ah, you actually admitted it at the end. So you’re contradicting yourself.
If someday there's some advancement in refcounting that makes it better (or even as good but with significantly lower footprint), you'll see all languages that currenly use tracing switch quickly. For the time being, though, tracing is winning.
These days, tracing collectors offer better throughput, latency and predictability than refcounting, while refcounting offers better footprint. That's the main tradeoff, and I mentioned some secondary ones (re ease of implementation and low-level "surprises") before.
A tracing GC, by definition, traces. (Not to mention that tracing keeps the live objects alive.)
My important-to-me application has a large amount of "live forever" memory and, at any one time, a fairly small amount of memory used by short-lived objects. However, it allocates and then discards those objects very frequently.
Let's say that it has 100MB of "live-forever" and, at any one time, 1MB of transient objects. Moreover, the vast majority of the pointers in the 100MB are to other parts of "live-forever."
A GC-based approach will allocate Nx1MB of transient objects and then trace the pointers in that 100MB to free all but the currently in use 1MB of transient objects. The vast majority of the traces are a waste of time, but GC can't know that. Moreover, it will tromp through the address space, trashing the cache.
A ref-counting approach will have two RMWs for every pointer assignment and the objects modified will almost certainly be in the cache.
It's not clear that those RMWs will cost more than tracing that 100MB.
Note that the 1MB is probably in L3. If N is large enough to keep the number of traces down, the Nx1MB will cache-fault like crazy. (Remember that the 100MB is also subject to caching.) That 1MB won't use more pages than the Nx1MB.
It can, it does, and you've basically described generational collection. Generational GCs try to only trace through recently allocated objects, and only bother with old ones if they can't free enough memory. Not wasting time on unnecessary traces is much of the point of generational GCs.
More modern GCs like OpenJDK's G1 go some steps further. They're region-based, and they keep track of inter-region pointers that tell them the likelihood that a region may benefit from compaction.
> A ref-counting approach will have two RMWs for every pointer assignment and the objects modified will almost certainly be in the cache.
A tracing GC does that without any bookkeeping. An object born and dead between young-gen collections will never even make its existence known to the GC (generational GCs usually only need to learn about an object's existence once it's promoted); it will never have been visited and traced. The old objects would not have been traced either (in that interim) if few enough young objects survive.
In fact, in such ideal situation where some fixed number of objects live forever and some large number of objects are continuously allocated and die, a generational GC will effectively need to do nothing: the old objects will have been promoted into the old generation, and the GC won't have to ever look at them again if there's always sufficient RAM, while the young objects will be allocated by a pointer bump, and when it reaches the end the GC will wake up and want to start tracing, but will find that all the roots still point into the old generation, so the young generation will simply disappear (i.e. the allocation pointer will be reset to the beginning). The GC in this case requires zero operations (well, except for some fixed number required to notice it has nothing to do).
> It's not clear that those RMWs will cost more than tracing that 100MB.
It's clear that they cost more than not tracing it, which is what a generational GC won't do.
> Note that the 1MB is probably in L3. If N is large enough to keep the number of traces down, the Nx1MB will cache-fault like crazy
That prompt reclamation has some benefits on locality is true, but so does compaction. The problem isn't so much cache faults (because we're talking about writes, which fill up the write buffer, not reads that cause stalls) but exhausting the memory buffer. This can and does happen with super-high allocation rates (which makes it an interesting problem), and indeed the memory bus's bandwidth is sometimes the limiting factor on throughput, but we're talking about allocation rates that far exceed those that common refcounting GCs can deal with anyway.
It's been well established by now that tracing GCs offer better performance than (crude) refcounting GCs, which is why they're the choice of every high-performance language that heavily relies on GC. The price you pay for modern tracing GCs is in memory footprint and in cost of implementation. There is, however, constant research in GC, and some advances in refcounting might make it more appealing, but we're talking about sophisticated implementations that are comparable in complexity to tracing.
Hence, generational collection is in practice only a constant factor improvement. That’s why not even all state of art uses it. E.g. Golang doesn’t.
Generations do not fundamentally fix the property of GC mentioned by the parent poster you’re replying to, because eventually the full heap will be scanned anyways, as it is virtually impossible to keep the promotion rate down to zero. It only delays that moment.
There is also non zero price to pay for maintaining generations. And also tuning generational GCs is much harder than non generational. It’s not a clear win.
But the whole point of tracing collectors is that even then scanning the whole heap is proportional in cost to the size of the working set, and so the amortized cost goes to zero with increase in RAM. Scanning the working set is still cheaper than tracking all references constantly. In fact, throughput wise it's a winning algorithm -- a doubling of RAM leads to a halving of cost.
I'm not claiming that tracing collectors always lead to optimal memory management, but the ones that are in common use are, in practice, much better than the refcounting collectors in common use except for footprint.
> And also tuning generational GCs is much harder than non generational.
There's no more tuning on the collectors of the last couple of years (I'm talking about ZGC and generational ZGC).
that is why you need to be careful not to needlessly update your reference count for temporaries. managing memory is not free. generational garbage collection avoids a lot of thought but it demands more memory.
Hence, even if per object the cost of RC may be higher than tracing, the fact that there are 1000x fewer objects to manage makes RC a huge win. I guess Swift is also not that stupid and doesn't update the references every time a temporary is created, etc.
Sure, that's why they can get away with an inefficient GC.
> Hence, even if per object the cost of RC may be higher than tracing, the fact that there are 1000x fewer objects to manage makes RC a huge win.
The "win" here is not RC at all but the fact that there's little reliance on GC and, of course, it's not really a "win" but something you buy by giving up on something else (i.e. a tradeoff), in this case abstraction ability (memory management details cannot be hidden as implementation details), and giving that up increases maintenance costs. So to get the footprint savings you have to pay -- either with performance, if you rely heavily on a refcounting GC, or with maintenance cost, if you don't. To get the performance you can choose to pay for RAM or for more development hours, but either way -- you have to pay.
Tracing GCs manage not to do any work for the vast majority of objects, those with trivial lifetimes -- they, too, don't manage the vast majority of objects (the allocator just bumps a pointer and the GC is never even aware of the existence of most of objects) -- by not freeing dead objects promptly which comes at the cost of spending more RAM.
In other words: good footprint, good performance, good abstraction (i.e. lower maintenance costs) -- pick two and pay by giving up on the third. C++/Zig/Rust pick the first two, Java/C#/Go pick the last two, and I guess Python picks the first and last.
There are, of course, other nuances; e.g. most refcounting GCs in common use leak memory as they are too crude to handle cycles, and not all tracing GCs are state-of-the-art.
The SGCL repository contains the source code for this benchmark that uses the tracked pointers: https://github.com/pebal/sgcl/blob/main/examples/treap/treap...
Only D language is close to the result, the rest of the GC languages are several times slower.
(clang on Windows)
raw pointers: 149ms
tracked pointers: 181ms
All the people working on Java at Sun/Oracle, on Go at Google and at C# at Microsoft (who, BTW, have written most of these languages' runtimes in C++) spent years and years designing elaborate and sophisticated algorithms that are worse than a crude implementation of a 50-year-old GC algorithm because we want to spend tens of millions of dollars and decades of work to give our users worse results? In your mind, what was it that possessed everyone designing high-performance language runtimes for non-memory-constrained environments over the past three decades, at unrelated projects that compete with one another, to all choose variants of a worse algorithm despite all of those variants being several orders of magnitude more costly to develop than what you believe is the better algorithm?
When someone comes up with a more performant GC algorithm than tracing -- we'll all switch to it. Who knows? It may be some sophisticated form of refocounting, but it ain't simple refcounting.
I'm not interested in the amount of money companies invest in developing garbage collection systems, I'm interested in code performance. Are you aware of any other absolutely zero pause GCs?
You mean lower footprint overhead; higher performance overhead. But that was my point: Higher-level, high-performance languages that rely on good abstraction -- like Java, C# and Go -- need a better-performing GC, which is why they choose tracing, and pay for it with more footprint. In terms of performance, tracing used in industry beats refcounting as used in industry.
> I'm interested in code performance
Sure, but you have to pay for: either with a higher footprint or with higher maintenance costs.
> Are you aware of any other absolutely zero pause GCs?
The ones I know of are ZGC and Azul's C4, which preceded ZGC by some years but was not open-sourced. ZGC isn't some obscure technology, BTW. It is currently running most of Netflix's workload, and probably other very large companies.
(Also, ZGC, does no collection work in pauses; it does pause threads to synchronise a state transition but for durations similar to those that the OS also pauses threads for).
Both ZGC and Azul C4 pause threads. SGCL never pause threads, so it can collect garbage more often and more efficiently.
As their goal was a language that would be very popular, and given that languages that heavily rely on GC have many times more users than languages that don't, it doesn't seem that they were wrong, at least not about the centrality of GC (although, "value types" and arrays-of-structs are coming to Java).
> SGCL never pause threads, so it can collect garbage more often and more efficiently.
I can't examine the algorithm right now and I couldn't find a paper describing it (so I can't tell you if it's one of the algorithms we've tried), but if you believe you have a more efficient GC than those in the JDK, feel free to plug it in and test. If you're right, you'll have many millions of users and the overall impact of that algorithm on the software industry would be much greater than it would as a C++ GC.
One of the reasons why your intuition is not so straightforward is that a tracing GC needs to do no work whatsoever when the number of references is zero. One of the common ways to teach the basics of GC is by starting out as looking at tracing and refcounting as duals: refcounting needs to work to free objects, while tracing works to keep them alive. If you thinking in terms of what work needs to be done to promptly determine when an object becomes garbage, then you're already not thinking in terms of tracing, because tracing never actually needs to learn about when an object becomes garbage (this isn't actually true when they do reference processing, but that's another story).
Or, if you want to think about it another way, in a tracing collector there are already only two cases no matter how many pointers there are to an object: reachable or not, i.e. the same one and zero as in your case, only there isn't even a need to ever set the counter to zero.
However, in principle tracing and refcounting can be quite similar (https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/unifie...) in their behaviour, but in practice most refcounting GCs in industry use are crude, and don't match the performance of tracing GCs in common use, which are quite sophisticated.