Hacker News Reader

Reference counting does not scale to multi-threaded programs well. Keeping reference counts up to date across multiple threads is maddeningly and frightenly hard to do efficiently. By the time you correctly solve the concurrent update problem for essentially every access the program does, you have a very complicated memory management system that incurs overhead on every single operation. Compare that with a GC that imposes overhead (usually) only on writes to objects, not "writes" to the stack or local variables going out of scope. Reference counting also incurs overhead for reading from objects. Empirical studies have shown that reads outnumber writes 10x to 1 usually. Why would you consider it to be just a _bit_ slower?

And of course reference counting pauses. Killing one object (its count dropping to zero) may cause a chain reaction of objects whose reference counts to drop to zero and need to be cleaned up. The difference is that you now suffer work proportional to the _dead_ data of the program. In comparison, a tracing GC does work proportional to the _live_ objects.

Great explanation! Thanks!

> Reference counting does not scale to multi-threaded programs well. Keeping reference counts up to date across multiple threads is maddeningly and frightenly hard to do efficiently.

Is this not just a matter of using an atomic reference count?

Yes, but atomics are pretty slow.

I guess, but that doesn't seem that bad.

> maddeningly and frightenly hard to do efficiently.

It definitely doesn't seem maddening or frightening. I'm not saying a GC isn't stricly better (because I'm unsure either way) but arc doesn't seem like some awful thing.

> Killing one object (its count dropping to zero) may cause a chain reaction of objects whose reference counts to drop to zero and need to be cleaned up.

That chain is trivial to interrupt and resume later. Compare that to interrupting any mark based GC.

You probably mean minimal latency, not maximum throughput. GC generally has higher throughput at the cost of latency and higher peak memory usage. :)

Parallel GC's throughput is limited by how hard the parallel thread is working as described in the article and which was the point.

But he's comparing to reference counting, where you pay a substantial throughput penalty round-tripping to RAM (especially if atomic) and don't get the benefit of a bump allocator.

I've seen it repeated many times that GC has higher latency, but is there a benchmark? Imagine writing a Mac app, once with refcounting, and once with GC, and seeing which one has the longer pause time.

I can think of cases where GC has better latency, like deallocating a huge linked list. That will introduce a higher latency with refcounting and with manual deletion (like C) compared to GC, where the main thread doesn't need to block while traversing the list. Or does such a case not happen much in practice?

You mainly notice it in mobile apps, since you want silky smooth 60fps scrolling there. A pause longer than 5 or 10ms can easily cause you to drop a frame.

Hard to attribute that to GC.

Why hard? On Android, the GC will print a log entry telling you how long it took!

In my experience, aside from badly-written algorithms that just do too much work on the wrong thread, the main causes of momentary glitches are GC and I/O. Unfortunately you have limited control over those in application code (just using too much memory can cause some I/O churn). On mobile, the GPU drivers are often badly written and will give you random hiccups that can ultimately be traced back to I/O.

Not to turn this into an Apple vs Android battle, I hope, but I think this is an important point that is often overlooked -- Apple's hardware and software designs are really well-targeted to minimize those kind of glitches. They don't use GC and they always use very fast (AKA expensive) flash memory. So whatever else their flaws, Apple devices tend to have smoothly-animated UIs.

Oops, you're right! I think I had in mind something like "guaranteed throughput" but "consistent low latency" is definitely a better way to put it.

This is an insightful comment. Thanks. I wonder how things would change if a second core was sitting idle anyway, like in a mobile app that does everything on the main thread. Would it then make sense to utilise the second core for greater performance? Imagine memory isn't a problem — some phones have plenty of memory, like 6GB on a OnePlus.

Unrelated to all the above, and related to your point about uncollected cycles not being a problem with refcounting, it does impose an overhead, like remember to use weak pointers to delegates in Objective-C. It's not as seamless to the programmer as GC. You can argue that it is (not) worth it, but there's no question it's more work for the programmer.

Apple's phones tend to have less memory, and fewer (but faster) cores. Along with Objective-C's reference counting, I think those are very smart choices for typical mobile app workloads.

In principle having lots of cores available is great, but in practice it's hard to utilise them effectively without also using tons of memory and/or battery.

There are cycle collecting reference counting algorithms, that due a limited trace within a subset of the object graph to detect and remove cycles.

I am still not clear on why Apple didn't go that direction.

Reference counting will still potentially pause though, when freeing large graphs of objects.

Yeah, but the pause is completely deterministically in control of your program.

Doing cycle collection basically ends up as hard as full GC right? Annotating with weak is not a big deal.

> The pause is completely deterministically in control of your program.

In theory. In practice, the programmer may not be able to reproduce the pause to diagnose and fix it, or it may not bubble up to the top of the priority list. Whereas with a GC, this problem may not occur at all in the first place.

The question is whether such cases (large object graph or linked list) occur often enough in practice to be worth bothering about.

> Doing cycle collection basically ends up as hard as full GC right?

Not really. Yes you do need to have the ability to trace the object graph. But the actual algorithm isn't that bad.

I implemented this in C++ (for "fun" for a pet language VM i wrote) 15 years ago: http://researcher.watson.ibm.com/researcher/files/us-bacon/B...

That's interesting! I also implemented that algorithm for cycle collection (https://github.com/bjourne/c-examples/blob/master/libraries/...) and I found that like the GP states that it wasn't worth it. The problem was that there so many objects that were potentially part of garbage cycles that it required scanning a too large part of the heap.

Cycle detection took about 70% as long a full mark and sweep collection so I didn't think it was worth it considering how complicated the algorithm was. Is your implementation open source? If so, I'd love to see it and compare results.

I guess it's technically open source but it's old (15 year old C++) and based heavily on the pseudo-code in the paper and also tied heavily into the interpreter I was working on. I didn't do a lot of performance testing either.

The interpreter I was working on was for a language which was image-based and persistent, I guess much like a Smalltalk, etc. Reference counting was handy for aiding in determining when objects should be pages to/from the disk image and what should be in cache.

I think performance would depend a lot on the usage pattern of the object graph. My system also used a lot of immutable data. The only mutable structures were the objects that properties and methods hung off of, and hash tables.

In practical terms, are there even many cases where cycles are desirable? The only case I can think of is threads (two threads communicating with each other). Most cycles I have seen even in GC'd languages were bad designs.

https://en.m.wikipedia.org/wiki/Dancing_Links is one.