GC is often an umbrella term that includes reference counting.
Almost all serious tracing GCs include some aspect of reference counting, and almost all serious reference counting GCs include some aspect of tracing.
I don't know about the Java world but in Common Lisp GC there's no reference counting whatsoever.
I would bet my house that some implementation of Common Lisp somewhere has a GC that uses card marking, which is a form of reference counting.
With reference counting there are no pauses, and memory is reclaimed immediately. It allows for strongly coupling deallocation with resource cleanup. (The consequence is higher overhead maintaining counts, and leaked reference cycles.)
In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#)
Reference counting is widely considered one strategy of garbage collection (https://en.wikipedia.org/wiki/Garbage_collection_(computer_s...). For that matter, some GCs that are primarily tracing also use ref counts for some portion of the heap, as an optimization (just as some primarily refcounting GCs also run a trace to clean up cycles).
Also, reference counting can certainly result in pauses, when large graphs of interconnected objects are reclaimed. On the upside, you know when a pause might happen. You still don't know for certain without explicitly keeping track of what is about to be freed, which would add additional overhead, and indeed may not be practical or even feasible.
You can't guarantee both of these properties at once, in the general case. Consider a very large tree of objects which are referenced through a single root node, and then that root node becomes eligible for reclamation. For a sufficiently large object graph, either reclamation will require a noticeable pause or some portion of the work will have to be deferred until later.
Using pointers to make up a graph is a choice. It is a thing taught in CS classes, so it may feel comfortably familiar; that does not make it good. I never do.
There are lots of things you can do in GCed language to avoid allocations and avoid running the GC when it matters.
But the thing is, I can switch GC implementation according to my needs.
If throughput is my number 1 concern I can use ParalellGC, if not I can use ZGC. Or G1 if I want something in between (not sure if the paper picks up the huge drop in overhead of G1 in Java 18).
Region-based memory management is commonly used, for example, with per-frame heaps in games, or per-request heaps in servers; but in those cases memory is not reclaimed immediately. The MLKit implements Standard ML with regions instead of garbage collection, though recent versions also have GC.
In practice, manually memory managed languages always conflate memory and other resources. A File object is not just a block of memory, it's also a file descriptor, etc. So you have to run the destructors at the 'right' times and can't just toss the memory. In special cases where you control every allocation, sure, but often that isn't practical.
Also, though, it's very unusual to install an arena allocator as a replacement for malloc and (as a no-op) free — malloc has no way to specify which of possibly several arenas you want to allocate in, arena allocators suck at realloc, and writing an arena allocator that invokes malloc to get its arena is significantly easier than writing one that uses a variety of platform-specific calls depending on compilation options. Instead, you write your own arena allocation functions (h_alloc or apr_palloc or whatever), and then you invoke them explicitly, in your own code. Non-arena-aware library code will just keep invoking malloc as usual.
The case where you might end up with library code invoking your arena allocator is where you supply your allocator as an argument to something — like C++ STL containers or, again, APR pools, for example with apr_pool_create_ex. But that still doesn't mean you have to depend on the allocator to invoke finalizers — after all, the standard library operator new and operator delete don't invoke finalizers, instead relying on other finalizers (destructors) to invoke finalizers and then invoke operator free. That still works — your files still get closed — even if the "operator free" is a nop because you're allocating out of an arena. In that case you don't get the major benefit of arena allocation (fast constant-time reclamation of the whole arena), just the minor ones, no fragmentation and fast constant-time allocation.
A more useful strategy is often to attach your finalizers to the arena instead of allocations within it; in the case of apr_palloc you can do this by creating subpools with apr_pool_create and attaching cleanup functions to them with apr_pool_userdata_set.
Regardless, my claim was more restricted than the one you're arguing against. I claimed that arena allocation can guarantee both that there are no pauses and that memory is reclaimed immediately in this case, where you have an arbirarily large tree of objects that dies at a single point in time, and in many similar cases. This is what wgd was claiming was impossible in their second claim: "For a sufficiently large object graph, either reclamation will require a noticeable pause or some portion of the work will have to be deferred until later." That claim is not true.
As far as I know, however, wgd's first and less general claim is true: there's no way to extend this region-based strategy even to the general case of immediate memory reclamation without losing the constant-time guarantee, much less the even more general case of immediate execution of arbitrary finalizers. (By contrast, reference counting can guarantee immediate memory reclamation and immediate execution of arbitrary finalizers, although at the cost of unbounded pauses, and not in the general case because it can't handle cycles.) Obviously you can't execute an unbounded number of finalizers in constant or even bounded time, or call close() on an unbounded number of file descriptors in constant or even bounded time.
But that doesn't mean you can't reclaim an unbounded number of memory allocations in constant time. You can, it's a useful thing to do, and people do it all the time. If you've fetched an URL from Apache today you've done it yourself, even if you didn't know it.
That's predictable and can be planned for: You can hold onto the reference until you get to a point where the pause is acceptable.
You can't do that in a garbage collected language, because you have no control over when the garbage collector will pause. (In theory your application can explicitly trigger a garbage collection, but in practice such behavior is discouraged.)
How are you reclaiming cycles with no pauses?
It smacks of poor discipline, or poor design.
(Also, in the sense of releasing a cycle, that would be pretty quick, since a typical RC implementation is just going to leak it. Its where a large graph resource graph is successfully ref-counted to 0 that can cause a pause, theoretically, although that's another case I've not seen.)
I'm not a fan of RC, myself. It's space-hungry, it creates unnecessary write traffic, it's unreliable (when you can have cycles), and it's slow. But there are lots of "not sound" and "not general" but "pragmatic" language implementations out there using it, without tracing. In practice, even.
I RC'd a thing in a program, five years back. The program had a linked list in it. Increments and decrements happened on a scale of minutes. I did not agonize over it.
For example, heap allocated closures for functions with non-local references create a cycle when a pointer to the closure is stored in a non-local environment.
You have to be aware that cycles can cause issues and you have to think about the impact of cycles on whatever you're doing.
I don't think this is a particularly fruitful line of discussion to strongly claim that cycles can just be avoided, or worse, that you're an idiot for having them. It's needlessly inflammatory.
Point is just that people get used to whatever they were directed to do for their CS class assignments, and get to thinking it is natural, and even unavoidable.
That something somebody is used to not thinking about is not actually necessary can be a novel and fruitful idea. The cheapest GC is always no GC at all.
> The cheapest GC is always no GC at all.
I kind of chuckle here because the Virgil compiler proves you manifestly right and wrong simultaneously; it's a fully GC'd, semi-functional language with a self-hosted compiler written entirely in the language. Incidentally, in a careful style that doesn't allocate a whole lot or create a lot of garbage. It chooses efficient, C-like data structures for IRs and doesn't waste a lot of time on Java-like armored classes because I am sick of wasting my life on that. It bootstraps in less than 200MB of memory, compiling the entire compiler at full optimization in a single whole program compilation. Because I made the dumbest, simplest Cheney moving GC, without even generations, it doesn't even have a write barrier. But because it only allocates 200MB, when bootstrapping it doesn't even GC once. It's basically a giant, single region that is thrown away at process exit, and the mutator doesn't pay the cost of a single write barrier. (And the funny thing is, GC wouldn't even find that much garbage, because only about half of the heap does actually die, primarily because it's mostly IR that is always reachable--it's a whole program compiler, after all). It's basically your mythical perfect GC just because it has enough memory and I am damn well in my rights to spend it as I have.
I'm going to time this thread out now because I'd rather continue not thinking about memory management until I cycle back on GC work, and I don't really see any evidence that you're listening. Besides, I've said it better with code and the machine seems to happily hum along to my music.
Same with GC. "Stop the world" may be a characteristic of a simple GC, but it's entirely possible to have GC that works by "coloring" objects.
> In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#)
You only need to implement IDisposable if you are dealing with unmanaged resources (ie. non-GC objects). But it's the same with C/C++: you have to call `free()` or `delete`; The difference is that managed resources are auto-released for you.
> With reference counting there are no pauses
You can still have pauses of arbitrary duration with ref counting. When the last reference to an object that is the sole owner of a large graph of other objects gets decremented, the entire object graph must be immediately deallocated. It's possible for a single dereference to trigger an unbounded amount of deallocation.
> and memory is reclaimed immediately.
Most production-quality ref counting implementations defer tracking references on the stack to minimize ref count churn. That significantly improves performance but it means you can no longer claim that the system always reclaims memory "immediately".
> In a garbage collected language you need to explicitly release your resources. (IE, the Dispose pattern that's common in C#)
Managing non-memory resources is orthogonal to tracing versus ref counting. If you choose to tie a resource's lifetime to a piece of memory's lifetime then, yes, the memory manager's deallocation policy becomes user-visible.
I think you would get a lot out of reading "A Unified Theory of Garbage Collection".
Two things:
1. Unbounded may be technically true, but it's really not a hard problem to ensure that time-critical runtime deallocations either rarely happen or are simply never huge chains of objects that release each other. Source: Used C++ & boost::shared_ptr/boost::weak_ptr extensively in game development and never had unexpected jank due to deallocations.
2. There's no actual reason that the full deallocation needs to happen immediately in all reference counting implementations. If you have hard time or latency constraints you could queue up the actual dereferencing and ensure that you only dereference a certain number of objects per time period.
Yes, #2 changes some assumptions about when objects will be dereferenced; in C++ one might rely on guarantees that objects are immediately released along with associated resources. But if you go into a project knowing that it needed to support deferred reference counting, manually releasing critical resources is hardly the worst thing you'd need to do.
Sure, but now you're essentially in the same business as someone using a GC finds themselves where they are tuning the GC, using object pools, etc.
> There's no actual reason that the full deallocation needs to happen immediately in all reference counting implementations. If you have hard time or latency constraints you could queue up the actual dereferencing and ensure that you only dereference a certain number of objects per time period.
Yup, that's a common optimization. But now you have given up the property that destruction happens immediately and deterministically.
My overall point is that the benefits of ref counting are not without cost. There are trade-offs and as you make different ones to improve performance or latency, you quickly discover that your ref counting system starts to take on shades of tracing GC with both the benefits and downsides that that entails.
There's no "tuning of the GC" beyond that, though, unless you count linking in a faster multithreaded malloc library, which is another thing that I've tried.
What's problematic about Java in particular in relation to latency is that Java's libraries can be pointlessly wasteful with regard to allocating garbage. I found that a function that was supposed to call through to a system function that got the system time in milliseconds was somehow allocating an object and discarding it as part of the call. The function returned an integer.
I found this when my Android JNI (C++) app was getting janky because of GC pauses, and I traced the allocation to that function. I wrote a quick JNI function in C++ to call the system and return the integer directly, and the jank went away.
The best GC in the world won't make up for wasteful allocations, and some languages (or their ecosystems?) seem to encourage rampant allocations.
When people say "with reference counting there are no pauses", they are not talking about the bookkeeping cost of releasing the allocations when their last reference is dropped; they are talking about unrelated code (which might for instance be running a tight numerical loop with no allocation or deallocation at all) being arbitrarily stopped.
Also, it's misleading to call the amount of deallocation "unbounded". The amount of deallocation is precisely the size of the graph of objects being released at that point; no more, no less.
Still, it usually works out, especially when lowering peak memory increases performance on its own.
I'm not sure that you can claim that confidently. I have certainly seen many people laboring under the false assumption that ref counting systems always have bounded, small latency when that isn't the case. The latency may be much lower than various other tracing GC alternatives, but I think many people have a simplistic mental model that a ref count decrement only ever leads to a single object being freed.
There is an ah-ha moment when you point out that freeing an object decrements its outgoing references, which can in turn cause a cascade of frees.
> they are talking about unrelated code (which might for instance be running a tight numerical loop with no allocation or deallocation at all) being arbitrarily stopped.
Many GCs will never arbitrarily stop the program in a tight loop that isn't doing allocations, so there's nothing particularly unique about ref counting here.
> Also, it's misleading to call the amount of deallocation "unbounded". The amount of deallocation is precisely the size of the graph of objects being released at that point; no more, no less.
Sure, and a program can build object graphs of arbitrary size. That's what "unbounded" means: there is no pre-defined bound on it.
Something else people often don't realize is that malloc/free aren't instant. Why is de-referring a large object graph slow, well, mostly because free is slow. Why is free slow, because the internals of a malloc can be rather sophisticated. There is probably locking, there may be internal book-keeping like coalescing free regions inside the heap and so on.
If you look at modern GC benchmark workloads, they're often generating gigabytes of allocations per second. Good luck shoving that much work through a typical malloc! Big companies like Google have had to write their own mallocs for a good reason.
True, and the costs vary wildly and are deeply tied into the rest of the memory management strategy.
In a copying collector, free() is essentially free: It takes the same amount of time to free 1 object in the semispace as it does 1,000 objects in the same semispace.
Swift doesn't do this, if I understood what you meant properly. I suppose you might want to defer freeing some things to idle time but it's usually not a problem in my experience. I'm honestly surprised it always comes up.
There's "autorelease pools" in ObjC but they aren't used to move releasing to an idle time, rather it's to handle cases where nobody knows what the precise lifetime of the allocation is. Swift has a better ABI that doesn't have that issue.
I think Swift can take advantage of the fact that many values are purely stack allocated and don't touch the heap or ref counting system at all. It leans pretty heavily on structs and value types.
Other managed languages are more Java-esque in that basically every value is in principle heap allocated. In those, I think it's more valuable to defer ref counting stack references since there are many more of them and they tend to be frequently mutated.
That is why, as Apple decided to fix of their ARC optmizations, they had a talk at WWDC 2021 about ARC gotchas for code that will behave in a different way due to the new optimizations.
"ARC in Swift: Basics and beyond"
It's more like the old version of the optimizations were just heuristics (so they didn't work that well) and the new versions are formally proven, meaning they're more aggressive and found some memory safety holes in C/ObjC APIs.
Autorelease is a no-op when using automatic reference counting. (But it was a pretty cool concept back then.)
What you can't do is message autorelease yourself - although of course you can escape that pretty easily.
In rc/arc you can achieve the same by making release a no-op.
You can't achieve that with reference counting, with malloc/free, or with a non-copying tracing collector. You can achieve it with regions.
On the other hand, you may not need to. Allocating and initializing those objects took O(MN) time, so your program can't get an asymptotic speedup by deallocating them in O(1) time instead of O(MN) time. So it really depends on the constant factors, which nowadays depend strongly on things like cache miss rates and cache line sharing between cores.
While tracing is considered to have better throughput and reference counting to have a lower footprint, as the liked paper shows, they are really on a spectrum of techniques with different tradeoffs.
In strict computer science parlance, refcounting is a kind of GC, but to most people GC refers to "tracing GC" specifically. It's fairly pedantic.
> In a garbage collected language you need to explicitly release your resources.
I assume "resources" here must mean "non-memory resources"? Even still, GC can apply to any kind of resource, it's just most popularly applied to memory (you could have a GC for file handles, for example).
Also, so you know, the user you're replying to knows a thing or two about programming languages.