Hacker News Reader

> 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.

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.

> 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.

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.

Object pools are not hard, and I certainly used them a lot in game development. That's just a cost of doing business in low-latency programming.

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.

> 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".

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.

> Swift doesn't do this, if I understood what you meant properly.

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.

Swift surely does it, I advise reading a bit of what the compiler actually generates.

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"

https://developer.apple.com/videos/play/wwdc2021/10216/

I'm familiar with it, I wouldn't say Swift previously intentionally lengthened lifetimes for the purposes of having fewer refcount operations.

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.

> 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.

Autorelease is a no-op when using automatic reference counting. (But it was a pretty cool concept back then.)

It isn't. There's an optimization that removes things from the pool sometimes, but it doesn't always work, and it's used to pass back out-params like NSError**.

What you can't do is message autorelease yourself - although of course you can escape that pretty easily.

> 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.

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.

It's not unbounded, but it can be surprisingly high and variable, especially if some of those objects have things like handles to kernel objects and freeing them requires IPC etc.

Still, it usually works out, especially when lowering peak memory increases performance on its own.

> 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;

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.

Yes people have incomplete mental models.

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.

> Something else people often don't realize is that malloc/free aren't instant.

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.