Chris Lattner on garbage collection vs. Automatic Reference Counting (2017)

I develop languages full time, and it's clear to me that RC will make massive strides forward in the next decade, for a few reasons:

1. First-class regions allow us to skip a surprising amount of RC overhead. [0]

2. There are entire new fields of static analysis coming out, such as in Lobster which does something like an automatic borrow checker. [1]

3. For immutable data, a lot of options open up, such as the static lazy cloning done by HVM [2] and the in-place updates in Perceus/Koka [3]

Buckle up yall, it's gonna be a wild ride!

[0] https://verdagon.dev/blog/zero-cost-refs-regions

[1] https://aardappel.github.io/lobster/memory_management.html

[2] https://github.com/Kindelia/HVM

[3] https://www.microsoft.com/en-us/research/publication/perceus...

I agree with a lot of what he says.

He gets something subtly wrong though: GC barriers are waaaaay cheaper than ARC, in the limit when you optimize them. Libauto had expensive barriers, but as Chris said, it’s not super interesting since it was overconstrained. But the production high-perf GCs tend to have barriers that are way cheaper than executing an atomic instruction. JSC’s GC has barriers that basically cost nothing, and that’s not unusual. It’s true that low latency GCs tend to have barrier overheads that are higher than high throughput GCs, but even then, the cost isn’t anything like atomic inc/dec. The barrier overhead in RTGCs is often around 5-15% except for the esoteric algorithms nobody uses.

Also, GCs trivially give you safety even if you race to store to a pointer field. ARC doesn’t, unless you introduce additional overheads.

Does what I say mean that ARC is bad? Heck no, ARC is super impressive. But it does mean that it’s a good idea to weigh ARC versus GC as a determinism versus speed decision, and accept that if you chose ARC, you lost some speed.

Oh but ARC also let’s you do CoW better than what a GC could give you, so for some languages ARC is a speed win over any possible GC because it’ll let you do fewer copies. I think that’s true in Swift. But if you don’t have CoW then GCs are def faster.

I find this whole conversation frustrating or somewhat confusing because it's a weird distinction: Reference counting is garbage collecting. It's not a mark & sweep or generational tracing collector, but it's a collector. And in fact it even traces, though the tracing is explicit (in the form of the declaration or management of references.)

My copy of the Jones/Lins Garbage Collection book I'm looking at on my shelf makes this quite explicit, the chapter on reference counting makes it clear it's one form of garbage collection.

When I was messing with this stuff 20 years ago, that was my understanding of it, anyways.

There are advantages and disadvantages to reference counting. I think some of the confusion in terminology and some of the frustrations (or opposite) here comes from the rather awkward way that Objective-C implements reference counting as something you have to be explicitly aware of and careful about, even with ARC. My brief stint doing iOS dev made this clear to me.

But I've used (and written) programming languages that had transparent automatic garbage collection via reference counting, and the programmer need not be aware of it at all, esp if you have cycle detection & collection (or alternatively, no cycles at all). And, there are compelling RC implementation that are capable of collecting cycles just fine (albeit through a limited local trace.)

Anyways, he's right that RC can be better for things like database handles etc. Back in the day I/we used reference counting for persistent MUDs/MOOs, where the reference counts were tracked to disk and back, 'twas nice and slick.

I think ref-counting is interesting, but I look at it as sort of like Level 3 self-driving cars where you almost don't have to pay attention but sometimes you really do. That's almost worse than Level 0 because humans are very bad at partial attention.

With GC, assuming your program can accept the slight level of non-determinism and latency, you don't think about deallocation at all. There are just objects and references, and that is the extent of your mental model. That simplicitly frees up a lot of mental energy to focus on your problem domain.

With ARC, you get determininstic deallocation and (maybe) better latency. Those are nice, and critical for some kinds of programs. And you mostly don't have to think about deallocation. Except that thanks to cycles, you can create actual memory leaks where you have completely inaccessible objects that live in the heap forever. And, in order to avoid this, you have to know when and where to use weak or unowneded references. Once you throw closures into the mix, it becomes very easy to accidentally create a cycle.

So ARC gives you more language complexity (strong, weak, and unowned references, closure capture lists, etc.). And there is a subtle property that you must always maintain in your program that is not easily found through static analysis. If you fail to maintain this property, you program may slowly leak memory in ways that rarely show up in tests but will cause real problems to programs running in the wild.

Most of the programs I write don't need finalizers much and can afford a little latency. I relish being able to use closures freely even inside classes. For that kind of code, I strongly prefer tracing GC so that I don't have to worry about cycles at all.

And yet languages with tracing GC outperform Swift.

https://github.com/ixy-languages/ixy-languages

Objective-C GC failed to work reliably due to everything C allows to do, and people mixing frameworks compiler without being enabled.

Automating Cocoa's retain/release calls was more reliable, and makes much more sense.

Swift naturally needed to follow the same path to easily interoperate with the Objective-C runtime.

A tracing GC would mean having something like .NET COM Callable Wrapper and Runtime Callable Wrappers, for interoperability with COM, which is a much greater engineering effort.

So naturally reference counting as GC algorithm for Swift makes sense.

Everything else is just cargo cult.

The nice thing about designing your own hardware stack:

>fun fact: retaining and releasing an NSObject takes ~30 nanoseconds on current gen Intel, and ~6.5 nanoseconds on an M1

https://twitter.com/Catfish_Man/status/1326238434235568128

I always took GC for granted until I started coding in Zig more and had to worry about managing my own memory.

One thing that Zig made pretty easy that's been sort of my go-to is using Arena allocations a lot more. It's pretty frequent that for a chunk of code I know I'll be allocating some chunk of memory and working with it, but then once that's finished I won't need it anymore. So just throwing everything into the arena and then freeing the arena afterwards works great, is fast, and is simple.

Are there any garbage collectors that enable this sort of thing? I think it might be vaguely like "generations", but I think even those are inferred and kept track of in greater detail to know when to move between the generations. I'm thinking of somehow earmarking a scope to use its own bit of memory and to not worry about collecting within the scope, and then when you leave the scope being able to free it all.

I'm sure there's more complexities that I'm missing. It's just that dealing with memory manually really makes you realize that the programmer probably easily knows expected lifetimes better than can be inferred. The only GC's I've used have been all "don't worry about memory we'll figure out everything". But maybe you could provide hints or something.

Sadly they didn't discussed the main selling point of GCs (in my opinion). GC can move objects in memory and often does it. It can affect cache locality, so less of cache misses. Moreover no more heap fragmentation. There are different strategies to do that, so theoretically one can choose the best one after the code was profiled. Though practically it may not be an option, because the chosen language gives you a fixed unchangeable implementation of a GC.

I bet that these benefits of GC can be great in some tasks, though I know no real world examples of software explicitly relying on it. Some servers on Java using terabytes of RAM, I think? But no one talks about it. My curiosity have nothing to consume, and it is hungry.

Personally I find ARC really easy to reason about and worth it. Essentially, a strong reference goes to “child” objects, a weak reference goes to “parents” or “siblings”.

You can think of your app’s data structures as a forest. The tree roots are your application and any globals, and the children are their fields, which have more fields, and so on. Sometimes a node stores a reference to something which is not its child/nested field but another node’s: e.g. a view might have a reference to its controller (its parent) another view which is not a subview (its sibling), or even a subview of a subview (descendant). The point is, this other node has a different parent, it already has a strong reference, so inside the child / sibling it’s a weak reference.

Another perspective if your familiar with functional programming, especially if you’ve worked in a language like Haskell that “doesn’t have” references: weak references are conveniences of the object-oriented paradigm which, in the functional paradigm, you would just pass around as function arguments instead. It can be really annoying to update an object without mutation when the object is referenced by other objects - in mutating, object-oriented code, those would be weak references.

I'm basically "whatever" on this. I develop in both Swift and Kotlin. I like the Swift language better. Definitely like the libraries better. But I hate the memory story in Swift. ARC is a half-GC. It's definitely different than malloc/free (which I do a lot of in embedded C land). But the stressing about ownership loops sucks. I like structs and what they enable, but I find myself choosing them over objects sometimes, not because they're the best solution for the problem in front of me, but because ARC sucks. And then after trying to avoid ARC using a struct, I end up biting the bullet and using a class, because sometimes a real object is the better solution. Kotlin's "almost struct" data classes are a better answer IME.

Being a geek who is somewhat into PLT and hobbyist languages, I go back and forth a bit on whether I want a GC or RC in my own hobby lang. For the longest time I was going to go with per-thread heaps that use a simple compacting GC, but only collect on allocation when heap starts running low, so collection wouldn't have to stop threads, the local thread would already be stopped. The plan was to use RC most likely for multithreaded shared objects from a shared heap as a secondary.

Then I started writing Rust and I realized what I think is the same point Lattner has here: Ownership changes everything. If I can declare a single owner most of the time and track that owner, I only have to bump the counter when I add a 2nd (and 3rd, etc.) owner, which isn't nearly as common as single ownership. This gets rid of most of the issues with RC performance (which in naive schemes bumps the counter every time it calls a function and more). RC still can't use bump allocation unfortunately, so any tree building would likely need arenas in addition which is a bummer, but deterministic destruction is a huge bonus, so this is the way I'm leaning atm (if I ever get back to writing it that is!).

In the case of C#, there are very lengthy docs and StackOverflow threads on how to properly use IDisposable -- what you need to use to clean up non-GC-able resources. A great many classes in C# libraries use IDisposable, so outside of pure business logic you end up with a lot of 'using' blocks. I've written a lot of C# code that needs to clean up external resources using Dispose(), and I've had to fix a lot of C# code written by people with a poor understanding of IDisposable and how GC actually works (eg. useless GC.Collect() calls everywhere).

So I think the benefits of deterministic object lifetimes, and it being easy to explain when each object will get cleaned up (all of it, not just the memory), outweighs the marginal benefits of heavyweight Garbage Collection.

Chris makes some points which are interesting in their own right, particularly the one comparing the amount of research which has gone into tracing/copying gc vs rc. But I think there is an unmentioned bias which is worth pointing out. Tracing gc has found massive success in enterprise java applications, which:

- Need to scale in terms of code size and contributor count, and therefore need the modularity afforded by tracing gc

- Need to scale in terms of heap size, and are therefore more likely to run into the pathological fragmentation issues that come from non-compacting gc

- Need the higher throughput afforded by tracing gc

- Generally run on massive servers that have the cores, memory size, memory speed, power budget, and heat dissipation required to support high-quality tracing gc

Contrariwise, swift is a product of apple, a laptop and phone company, and is used to make laptop and phone apps which:

- Are unlikely to ever get really huge (people balk at large downloads)

- May have limited memory, and need to share it with other apps

- Run on battery-powered hardware with little or no active cooling, and so need to attempt to conserve power

No silver bullet, as they say. I implement APL, which absolutely cannot do without reference counting, except perhaps in some novel configurations. I think that for the more usual case of a pointer-chasing language, tracing gc is almost certainly the right choice.

Lastly, however, I would be remiss not to bring up bacon et al, 'A Unified Theory of Garbage Collection'[0], which notes that tracing gc and reference counting are not really opposed to one another, and that a sufficiently advanced implementation of either will approach the other. Lattner mentions barriers (though as a sibling mentions, barriers are an order of magnitude cheaper than reference count twiddling); on the other side of the coin, consider deferred reference counting, one-bit reference counts, ...

The bottom line being that memory management is _hard_, in all cases; a sufficiently robust and general solution will end up being rather complicated no matter what it does; and, again, there is no silver bullet.

0. https://courses.cs.washington.edu/courses/cse590p/05au/p50-b...

I think Chris makes an excellent point that is the mortal flaw of GC-s, anyone who argues about overhead or pauses or throughput is getting it wrong - the problem is determinism, and interaction with native objects.

You cannot reason about when the computer can/will get rid of native objects that are referenced by the GC, and doing so raises a billion of hairy questions, many of them discussed at length in the article.

Why is this important?

This is implies the model of SPA frameworks, which rely on this exact thing, fundamentally cannot be made to work well, since they rely on referencing native objects from JS.

This invalidates the entire way we build GUIs/websites nowadays. I'd say that's a pretty darn important issue.

There are pauseless GCs for Java, e.g. Azul Systems https://www.azul.com/products/components/pgc/ , seems like a winning approach.

> A ton of energy’s been poured into research for garbage collection, particularly since Java has come up. There’s been hundreds of papers written in the academic circles, tons of work in HotSpot and other Java [2:03:30] implementations to do different tweaks and different tunings and different new kinds of algorithms in garbage collecting. That work really hasn’t been done for ARC yet, so really, I think there’s still a a big future ahead.

I disagree strongly; there has been plenty of work in optimising reference counting systems. A quick look through Jones, Moss and Hosking's Garbage Collection Handbook provides many descriptions of high performance reference counting, but they all use deferred reference counting [1], rather than the immediate reference counting that Swift/Objective-C/Apple uses. That Apple is stuck in 1975 does not say much about other reference counting users.

(Though Lattner only says "ARC", and I believe only Apple calls their refcounting "ARC"; I guess Rust has "Arc" as well, but that is a different thing completely. Else I haven't seen the acronym used elsewhere.)

> But to do that, they use this tricolor algorithm which dramatically lowers throughput, because they’re doing almost exactly the same kinds of operations that ARC is doing.

Concurrent tracing algorithms often log into a local buffer, without synchronisation. Whereas concurrent immediate reference counting performs atomic updates - it's almost exactly the same except for the parts where they really aren't the same.

High performance concurrent RC systems also use local buffers [2] to avoid atomic updates too. Go figure.

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63....

[2] https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/levanon... page 5, figure 2 in particular

> I am totally convinced that ARC is the right way to go upfront. [...] It gives you deterministic behavior[...]

Does it? In a meaningful way? For arc with strong recount>1, which constitutes the main use case in my experience (weaks are unenrgonomic, for one), which means that the deterministic destruction is not meaningful locally, as opposed to the modern manual alternative, RAII, for instance. Am I missing something?

What it means to be a “systems” programming language is a matter of some debate, but there is at least one definition that’s only coherent in a resource management model isomorphic to RAII/ARC.

One data point from the Prodfiler folks was that even if the GC cost to throughput is relatively low, some programs will still spend up to 25% of their time doing garbage collection. This will show up on your cloud bill even if it doesn’t show up to that extent in your performance analysis.

The main thing you need to know about ARC is that you hardly ever need it, so it rarely matters what its performance is. If you find yourself using shared_ptr much, stop.

Also, its susceptibility to cycles doesn't matter, because it is a terrible way to manage graph nodes: just keep them in a vector, with indices instead of pointers.

I’ve never done this personally but I know in some of the languages I’ve used you can turn off garbage collection. If you really cared about the latency, then you couldn’t’t you just manually collect at certain points in the program?

Or you could use a language like D which lets you write a program without the garbage collector when needed. You definitely have less tools when you do that, but if you are in a situation where you know you want to manage memory manually you probably will evaluate that trade off.

What most people seem to forget about this is that if you actually need speed neither of these should be a factor. Heap allocations should be minimal and lifetimes should almost always be known ahead of time.

In C++ you basically never need reference counting, unless you are handing off heap allocations to multiple different threads. In that case you don't know what will finish first and they need to communicate when the allocation isn't being used anymore.

Perhaps the most interesting thing is that it's all moot for the vast majority of applications. If it's done reasonably well, it just won't matter. 'Most' of the time. And for the times it does well, you'd probably be better of finicking away manually with things.

To me Garbage Collection in a language makes it easier to work with than a language without.

As an example C# (GC) and Delphi/Turbo Pascal (No GC). Was involved in two projects where the one made in C# became the successful one.

One of the absolute worst things about Delphi was the lack of GC, which took away developer time better spent elsewhere.

Yes, C# had also other benefits, but having a GC is one of the crucial features to make a language popular.

Off-topic: The discussion in the next section about Chris Lattner's woodworking is interesting.

Had to do a double-take at the title, wondering what the former Duke basketball standout (https://www.youtube.com/watch?v=uH5ltiHSJqE) knew about garbage collection.

So this is a lot of gibberish but let me sum up to you the RC vs. GC:

GC advantages:

* Scales better when done right - cheap allocations simplified code etc.

* Can be heavily concurrent and use multicore

RC advantages:

* Predictable performance

* Uses less RAM

For GUI RCs smaller memory footprint and predictable performance are great. Hence swift uses ARC which is also faster than most RC implementations (which typically have a lot of overhead).

For servers where overall performance matters more than 100% smooth consistency and RAM is cheaper... GCs have some advantages. A GC can run on idle and clean a huge amount of garbage without a problem. It can do so concurrently and leverage the multicore nature of modern CPUs.

This is one of those, right tool for the right case.

I’m personally exhausted by these conversations and you should be too.

ARC was/is a reasonable compromise: no other choice was obviously better. Legacy code is of supreme importance.

But we have a new benchmark for best-in-class now: for all their insufferable Jehova’s witness Jihad approach, and yeah it’s annoying, the Rust people proved linear/affine in production.

I find Carl and Yehuda’s flagrant profiteering in the early days as unpleasant as the next thinking person, but affine/linear is game changing, and it’s time to stop apologizing for why your pet thing can’t do it.

"I'm now a coding monkey but I'm close to becoming a manager".

I really wish managers and aspiring managers would be snapped out of existence. They should be sent to the mines. If a developer does a job interview and they say they actually WANT to become a manager some day, that's the biggest red flag currently known to me. I'd rather hire a drug addict than an aspiring manager.