Hacker News Reader

Comment by raverbashing | Hacker News Reader

I don't get why people do not prefer reference counting, it has more predictable runtime performance

(though of course a swap is a swap - but you can "trigger" it depending on your memory or file access pattern)

Reference counting has high runtime overhead, especially atomic reference counting with multiple threads. If you overwrite a pointer, you'd need to also look up and update two counts and do all that in a manner that is effectively atomic -- and that is complex on current hardware. I've heard that Swift programs could have as much as 40% runtime overhead from ARC.

I still think that reference counting is promising though. First because it meshes well with static analysis memory-management techniques such as inference of uniqueness and borrowing -- that can optimise away RC altogether. (and Swift's compiler already does some of that). I have not seen any work that could optimise away tracing GC in a similar way. Second, because I believe that it would be possible to design hardware with object-memory addressing that would performs atomic reference counting with no additional runtime cost.

That is exactly what escape analysis does, granted the way it is done across implementations varies.

Such hardware has been designed in the past, Lisp machines, Ada machines, the famous iAPX 432 Intel's failure.

ref counting is expensive in multi-threaded applications. Overall it would have worse performance. When it comes to predictability: deallocating a linked list (for instance) would have to deallocate all of the elements. Dealing with reference cycles is also not simple, either.

Honestly some (container) objects makes me think that they should be "parent obj management only"

Linked-list freeing need not all happen in one go. There can be a queue of free-but-not-zeroed, push RC=0 stuff there instead of recurring on referents, anyone doing memory allocation work can pop a few items off that queue and decrement the counts of their referents, etc.

That loses timeliness, adds problem of queue management.

A weird trick I stumbled across years ago is to not strictly pop from the head of the stack/queue -- instead choose randomly from the last N elements of push end of the stack. This seemed to blunt the sort of growth that you get from "visiting wrong". I never did figure out the theory of why this worked.

Overhead per allocation, if you care about that, and reference circles.

Because the industry has plenty of experience with referece counting as the very first GC algorithm, already in the early 1960's, in early Lisp implementations, BASIC, Cedar, and several other languages.

The predictable runtime performance is also a myth, because they never take into account the use of NUMA memory, lock contention, possible stack overflow and stop the world in the case of cascaded deletions in naive implementations.

Lock contention yes, it's fundamentally a RC issue, but makes me think per-thread objects make more sense

I'm not sure most GC implementations worry about the rest neither (as by the several complaints we see going around)

The ones across several JVM implementations (there is a world beyond OpenJDK), and the CLR certainly do.

Yes, and the fact you have to have a "special GC" for your case makes me wonder that those constraints are not so obvious.

(makes me wonder who's buying those - things like Azul, etc)

Places that were doing C++, but found out that the right GC, and JIT compiler, can achieve good enough performance for their business case.

There is nothing "special GC" about it, the failure is to assume there is only one way to implement GC algorithms, as if there is only one way to implement hash tables, tree re-balancing algorithms, .... and then place all languages into the same bucket.

Then we have the modern times with AI driven code generation, where no one cares how their agents are actually doing the work, with what kinds of resource management approaches.

Can you elaborate on how cascaded deletions "stop the world" with reference counting? I understand how GC could lead to arbitrarily large latencies for whatever task triggers that kind of cascaded deletions, but as I understand it, "stop the world" usually means that no threads are allowed to execute application code.

Imagine a graph or tree data structure where the deletion of a node causes a cascade deletion of all child nodes, which also causes a deletion of their children and so on.

This is proportional to the data structure being deleted.

Unless you use techniques to move the deletion into background threads, e.g. C++/WinRT with COM AddRef/Release, the thread will be "blocked" doing busy work cleaning all those nodes, running the cleanup code (destructors, deinit, whatever), node after node.

Yes, that's exactly what I said I understood. When Go (and Java) people say "stop the world" for GC, they mean all goroutines/threads stop, not just one. I don't think you get that with even naive reference counting.

> more predictable runtime performance

Not really, reference counting can cause a single object deallocation to trigger an arbitrarily long chain of deallocations.

Yes but then you can move your deallocation out of the critical path

Variable time yes but you know when you're going to pay it

(I mean yes you can put your gc.run() there as well, but it might not give you the results you want)

Immediate reclamation, yes. There do exist a number of reference-allocation algorithms that performs deferred reclamation similar to how tracing GC does.

Yes, but that still leaves the circular dependency problem.

And tbh I don't think I ever saw a circular dependency in a system

I'm not saying they don't exist of course (or that GC/RC shouldn't cater for them) but it's a very specific use case

A doubly linked list already creates a circular dependency.

True (especially if it's a circular one) but those can be weakrefs/softrefs

There do exist algorithms for resolving them, and that process can too be deferred, but also restricted to subgraphs and only when cycles are possible.

> it has more predictable runtime performance

Not that much more. Drop the last reference to e.g. a tree and you're doing an arbitrary amount of work to free it, right there. People resort to hacks like sending messages to "freeing threads" dedicated to that.

the work is predictable and the amount not arbitrary

By that standard, all gc work is predictable and the amount not arbitrary.

no, it is not. A gc won't run at the end of the scope when the reference is droped. And if it runs, the amount of work is unknown.

It is also unknown how much work will be performed if ARC goes out of scope.

if the arc is the last: the data structure is destructed and deallocated + atomic check

if the arch is not the last: atomic check

You might lose 100 ns or 300 ms. When? Nobody knows. You lose nothing when going out of scope with GC.

as a programmer you know and you can even control it by designing the appropriate scope and moving between scopes

> You lose nothing when going out of scope with GC.

actually, you don't know

Yes, I can, e.g. by implementing deferred deallocation, which is a primitive GC form.

> actually, you don't know

I know because I’ve verified it.

> Yes, I can, e.g. by implementing deferred deallocation, which is a primitive GC form.

sounds more like a form of manual memory management

Manual management involves an explicit function call. Functions called by a destructor are considered automatic.

How does this relate?

What exactly don't you understand?

how this relates to garbage collectors

Either the size of the data structures created is limited and known, or it isn't. Whether the work is done in a refcount-decrementing recursive descent or a tracing garbage collector doesn't change that part.

a GC still won't run at the end of the scope - it will run at an unknown time and do an unknown* amount of work at the times it is running.

* subset of all allocations until it runs

And a refcounted tree freeing won't necessarily run at the end of the current scope, that depends on what other work is being done currently, and the size of the tree is a subset of all allocations until last user drops it.

and yet whether or not other work is being done currently is in your control, thus predictable (unless you chose to give control out of your hands e.g. by introducing two threads racing against each other); same regarding the subset

Reply on news.ycombinator.com