19 ms·

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

326 points by Austin_Conlon 4y ago

fay59 4y ago
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.
- Someone 4y ago
  Some programs spend over 50% of their time doing reference counting (http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf), and that will show up I’m your throughput measurements. I expect you can find papers giving numbers in the same ballpark for malloc/free, too. A MVP of JavaScript, for example, that boxes everything, combined with a benchmark that creates a d destroys lots of objects.
twoodfin 4y ago
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.
- melissalobos 4y ago
  This sounds very nice, but just to make sure I understand your meaning: If you have a properly designed "systems" programming language(even if manually managed) you would release resources exactly(or nearly so) at the time when a proper ARC/RAII implementation would. Is that correct for your meaning? If so I fully agree.
  - twoodfin 4y ago
    My point was that if by “systems” programming, you mean prioritizing efficient use of limited system resources (CPU cycles, bytes of memory, … ) then there’s no superior alternative to the precise control & reliability afforded by ARC/RAII.
  - ncmncm 4y ago
    At this late date, a language inadequate to express ARC/RAII is better described as a toy. There is nothing wrong with toys, but they are not to be confused with professional tools. A systems language is, first and foremost, a professional tool.
  - jandrewrogers 4y ago
    It is more subtle than this. Systems programming sometimes involves a resource life cycle that has semantics that map neither to a GC nor RAII/ARC. This is because systems programming often involves the direct management of hardware resources, like storage. For example, while resource acquisition and release may be deterministic, there is no implication that a released resource may be immediately reused or reacquired. This is not pattern most software engineers are used to. The reason for this is that hardware may hold a lingering reference to a software resource even if the software does not -- and hardware doesn't use reference counters or destructors. An arbitrary amount of time may pass between a resource being released in software and that same resource being available for reuse again in software. Many people new to systems engineering make the mistake of reusing a resource that was released but not reusable. Systems programming languages don't just ensure deterministic release of resources, they also need to provide a way to express that the hardware may hold references to objects the software has fully released such that it isn't really released. This is not something the average programmer has to deal with, but this is part of what makes systems engineering different.
cmrdporcupine 4y ago
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.
- melissalobos 4y ago
  > Reference counting is garbage collecting I am drawing a blank on google scholar at the moment, but I recall a very popular paper on exactly this topic of RC as the other side of Tracing GC.
  - hayley-patton 4y ago
    "A unified theory of garbage collection"? https://dl.acm.org/doi/10.1145/1028976.1028982 https://dl.acm.org/doi/10.1145/1028976.1028982
    - melissalobos 4y ago
      Yes! Thank you, I couldn't think of the terms to search for to find this.
invalidname 4y ago
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.
- jandrewrogers 4y ago
  > For servers where overall performance matters more than 100% smooth consistency and RAM is cheaper... GCs have some advantages. I am having a difficult time parsing this in a way that makes sense. Generally speaking, overall performance on servers is a direct product of being able to take strict control of when things happen and minimizing RAM footprint. That "smooth consistency" is how performance happens because there are important classes of software optimization that don't work if this is not a property of your runtime. Similarly, high-performance server architectures are usually not heavily concurrent even on massively multicore systems for good reasons that a GC doesn't address. The only advantage a GC has in this context that I can think of is that it might reduce some types of bugs in some types of code.
  - invalidname 4y ago
    I come from the world of JVM so here we do have multicore servers and you might see a peek where a particular request takes longer but overall the performance will be amazing. This isn't OK for GUI but is great if you have a HUGE server that can chug through tons of data with a huge amount of RAM/cache.
    - panick21_ 4y ago
      But this problem has technically mostly been fixed by Azul and is making its way into open as well, we have ZGC and so on now. Pauses are rather short even with large heaps.
GeekyBear 4y ago
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 https://twitter.com/Catfish_Man/status/1326238434235568128
- astrange 4y ago
  This has nothing to do with custom hardware, it's one of the few differences that's actually due to ARM vs x86. Though, part of it is from being a unified memory SoC.
  - Tagbert 4y ago
    I heard in an interview with Craig Federighi, that in designing the Apple Silicon chips they had looked at specific operations that were frequently used by their OS and software and optimized those on their chips. Reference counting was one of those operations and that was why the speed of that operation was so much faster on Apple Silicon. Sure those other things about unified memory contribute speed to all kinds of operations, but they really focused on some of them to let their hardware and software work well together.
    - astrange 4y ago
      Choosing to use ARM and unified memory is part of designing the SoC, though. There is no magic in the refcount machinery; you can disassemble it and look at it.
- pjmlp 4y ago
  Now try Swift outside that hardware stack.
  - aeldidi 4y ago
    I agree with the sentiment, but does Swift actually see any usage outside of Apple’s own hardware? I think Swift’s reliance on such an optimization is justified since the hardware this optimization is applied to is the main target. While Swift’s approach may be slower in theory, is it actually slower in practice? Just a thought.
pizlonator 4y ago
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.
- vvanders 4y ago
  I think his point about the amount of research done on ARC vs GC was interesting. Only recently have we see things like biased reference counting[1] that can significantly reduce the overhead of ARC. [1] http://iacoma.cs.uiuc.edu/iacoma-papers/PRES/present_pact18.pdf http://iacoma.cs.uiuc.edu/iacoma-papers/PRES/present_pact18....
  - deleted 4y ago
    [deleted]
  - pjmlp 4y ago
    Reference counting is the oldest garbage collection algorithm, it has seen plenty of research. What keeps being overseen is the amount of engineering to make reference counting perform in modern hardware, effectively overlaps with other garbage collection optimizations.
gary_0 4y ago
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.
- 12thwonder 4y ago
  this is a really good benefit of RC codebase. Resource management becomes much more harmonious and easy to follow.
- pjmlp 4y ago
  There are Roslyn analysers for that.
nwatson 4y ago
There are pauseless GCs for Java, e.g. Azul Systems https://www.azul.com/products/components/pgc/ https://www.azul.com/products/components/pgc/ , seems like a winning approach.
- vips7L 4y ago
  ZGC also has sub millisecond pauses
- panick21_ 4y ago
  Yes. And if you read their papers, when they were able to add explicit hardware support they were able to do even better. I really think had vertical companies from the 90s not all died, seriously developing chips for personal computers (phones,laptops) with hardware support for the most important GC features would have been a huge winner. Apple could have done this but they were already bound to Object-C because of Next. Sun had the amazing Self VM in the early 90s already. And they made their own chips as well. But unfortunately they went with Java and instead of making a chip to support GC they tried to make a chip that implemented Java.
  - pjmlp 4y ago
    The amazing Self VM is the genesis of Hotspot anyway. They didn't try, they actually did them, and ARM did that as well.
    - panick21_ 4y ago
      Yeah Sun of course later bought the tech they developed themselves. Totally dumb. What do you mean 'they did them' as far as I know they never did extensions to their main CPU specifically to improve garbage collection.
      - pjmlp 4y ago
        The story between Objective-C, Strongtalk, SELF, Tcl and Java is a bit more complicated than that. No they didn't, but the point was about Java specific CPUs, https://en.m.wikipedia.org/wiki/PicoJava https://en.m.wikipedia.org/wiki/PicoJava And then there was https://www.electronicdesign.com/technologies/digital-ics/article/21771934/hardware-speeds-up-java https://www.electronicdesign.com/technologies/digital-ics/ar...
armchairhacker 4y ago
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.
- fauigerzigerk 4y ago
  > Personally I find ARC really easy to reason about and worth it How do you reason about a closure that captures some stuff and gets passed to a library function? @escaping doesn’t give you enough information to reason about all lifetimes that could possibly matter.
  - hmlongco 4y ago
    Uhh... because I can see what was captured? If I'm overly concerned that a given callback might be held somewhere for all time I'll simply capture a weak reference and be done with it.
nu11ptr 4y ago
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!).
verdagon 4y ago
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 https://verdagon.dev/blog/zero-cost-refs-regions [1] https://aardappel.github.io/lobster/memory_management.html https://aardappel.github.io/lobster/memory_management.html [2] https://github.com/Kindelia/HVM https://github.com/Kindelia/HVM [3] https://www.microsoft.com/en-us/research/publication/perceus-garbage-free-reference-counting-with-reuse/ https://www.microsoft.com/en-us/research/publication/perceus...
- nu11ptr 4y ago
  This. Said much better than my other posts, but this is exactly what I was trying to say. Naive ARC vs GC... a good GC will kill it, so don't make the ARC naive...cheat and find ways to skip most ref. counter bumps. It became amazingly clear when I started coding Rust: you only have to bump ref count when you get a new owner. Most RC objects die with just a few counter bumps. Most objects don't need RC at all (most objects can be single owner). Now imagine a lang (lobster given as an example above) that does this automatically. Sweet spot.
  - nu11ptr 4y ago
    Two more interesting ways to speed it up: - Make threads a "special" tracked API call (for example, like Rust) so that you know when something will or won't be passed between threads. If it never "escapes" the thread, you can use non-atomic ref counts for the lifetime of that object (NOTE: I should add this is something I've been thinking on - I don't know how hard/feasible it is to do in practice) - Use biased RC - don't have link to paper handy, but idea is that most multithreaded objects spend most of their life on one thread and when they are on that thread, can use non-atomic ref counts by using a separate counter. When on any other thread they use an atomic counter. When both counts hit zero, object is destroyed.
ncmncm 4y ago
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.
klabb3 4y ago
> 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?
- verdagon 4y ago
  I'm not sure most people use this technique, but when I was using RC-based systems, I would often assert that an object's refcount was 1 just before I let go of that last reference. Suddenly, we have RAII-like predictable destruction. I even built it into Vale as one of its memory management options called "constraint references" [0] though later switched to generational references which gave us RAII without the halts. I sometimes wonder how far I could have taken that RC + assert model. In my experience, the vast majority of objects even in an RC'd language do have strong refcount = 1. Perhaps we were in different domains though, I was mostly in game dev and app dev. [0] https://verdagon.dev/blog/raii-next-steps https://verdagon.dev/blog/raii-next-steps
- kgeist 4y ago
  I don't think it's quite deterministic because a simple variable going out of a scope can trigger deallocation of a random object tree (which can be large), which you cannot always predict locally (as a programmer) and which can affect performance on a critical path or introduce side effects at unpredictable times, plus the overall possibility of having uncollected cycles - so in the end for a programmer -- who's not willing to manually trace ownerships themselves to understand the behavior in every detail -- it has quite same disadvantages as a tracing GC (deallocation may kick in at "unpredictable" times) with the additional disadvantages such as: fragmentation and poorer memory locality in the long term (no compaction), possible memory leaks (due to object islands), temporary young generation objects being as expensive as old generation objects (no bump pointer allocation in a nursery), excessive RC increments/decrements can trash performance (and if it's atomic it can IIRC force cache invalidation, which also makes the behavior less deterministic). So I don't think it's a silver bullet, it's just a different kind of GC with its own set of disadvantages. I think most of the time RC is chosen because it's simple to implement or because there's a legacy system where RC is the only choice, and all the other "benefits" are just afterthoughts to further justify the choice.
Decabytes 4y ago
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.
jollybean 4y ago
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.
- randyrand 4y ago
  A lot of programs have to deal with JNI or weak references.
- draw_down 4y ago
travisgriggs 4y ago
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.
- azinman2 4y ago
  Is it really that hard to deal with memory ownership? What’s situations are you in that it’s so stressful?
moonchild 4y ago
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-bacon.pdf https://courses.cs.washington.edu/courses/cse590p/05au/p50-b...
- saagarjha 4y ago
  > Are unlikely to ever get really huge (people balk at large downloads) Wait until you see how big apps are.
pjmlp 4y ago
And yet languages with tracing GC outperform Swift. https://github.com/ixy-languages/ixy-languages 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.
- astrange 4y ago
  This benchmark is not good enough to make a decision about how you should build an entire OS. They did make this decision when designing ARC and Swift, and they did have data for it, and first-order effects of how fast you can make a single task can't be the determining factor there. In particular you need to know how disruptive running the task will be to other more important stuff.
  - pjmlp 4y ago
    You can benchmark it against Android or Windows Phone devices then. Naturally with similar hardware across the board.
    - astrange 4y ago
      You can do that by looking up which one ships with less RAM installed. I believe the common wisdom is still that it's not Android.
      - pjmlp 4y ago
        To save you the trouble, any Windows Phone 7 device, using XNA or Silverlight as OS APIs, 512 MB.
      - 4y ago
benreesman 4y ago
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.
- saagarjha 4y ago
  None of the strategies you’re claiming is the “best” really wins in every situation. There’s inherent tradeoffs with all of them.
sharken 4y ago
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.
- ak39 4y ago
  Delphi has legendary ARC not just with its VCL and object hierarchies with TOwner model but also with its wrappers of COM's IUnknown and QueryInterfaces. Yes of course, developers can still make mistakes about sequences and memory management but a well constructed class hierarchy and discipline to manage the freeing of resources immediately after they're no longer needed is the cornerstone of basic Delphi applications. edit: The objects that are IUnknown linked don't even need to be explicitly freed! There are several clever use cases for this for example changing TCursor from hourglass back to normal when a procedure/function is complete. It just works.
ordu 4y ago
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.
- hayley-patton 4y ago
  There are moving collectors which use profiling information to try to improve locality. It appears they produce a 15-30% speedup or so. https://safari.ethz.ch/architecture/fall2017/lib/exe/fetch.php?media=p332-chen.pdf https://safari.ethz.ch/architecture/fall2017/lib/exe/fetch.p... https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/ismm_paper.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- verdagon 4y ago
  Take a look at Mesh [0] which brings compaction to a malloc-like system. I could see an RC-based or single-ownership-based language using it to avoid fragmentation. [0] https://tiba-jrchang.medium.com/mesh-compacting-memory-management-for-c-c-applications-bc2a2cecc8cc https://tiba-jrchang.medium.com/mesh-compacting-memory-manag...
- jandrewrogers 4y ago
  Database engine implementations sometimes work similar to this, being locality optimizing machines. Objects in memory can be moved and reorganized dynamically. Ensuring that references to those objects remain valid is not inexpensive because it requires indirection to dynamically resolve object locations and may require patching state referencing the object. The performance impact is only tolerable for database engines because the context and scope is sufficiently constrained such that clever software design elements can ensure that the cost is applied lazily and expensive effects are avoided except in rare cases. Even in database engines, thrashing your CPU cache is a common side effect of not getting the design right. I can't imagine trying to make this perform well for general purpose software.
jurschreuder 4y ago
"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.
- mirekrusin 4y ago
  Exactly, it's like athlete wanting to be a referee.
  - munchler 4y ago
    More like an athlete wanting to become a coach, which is very common.
torginus 4y ago
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.
- draw_down 4y ago
- jFriedensreich 4y ago
  Could you elaborate how this is connected to js and SPA frameworks? I totally get how reasoning and determinism is critical for sound processing, embedded low level, operating systems etc. But why would this be relevant for normal application or web development?
  - torginus 4y ago
    SPA frameworks manipulate the DOM through JS, which means they need to take a reference to DOM elements. In a static website, once you navigate away from a page, the browser can deallocate all the DOM resources related to the old page, which can be quite heavy (images etc.). In an SPA-driven website, the DOM is created by JS. Once you 'navigate' away (you tell the framework to render a different set of DOM components), the old ones still linger around in memory until the next GC cycle, meaning the browser has to wait for the GC to run before it can free them. Even worse, GC's tend to be tuned for GC memory pressure, and if you have a ton of GC objects holding onto native resources, the GC has no way of telling it needs to run, because from its perspective, the GC heap is small and it has no idea about the native objects.
    - 4y ago
losvedir 4y ago
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.
- mirekrusin 4y ago
  Sounds more like ownership annotation than generations. Generations basically takes advantage of the fact that recently allocated memory is much more likely to be deallocated sooner - ie. it's run time/age based. What you're describing with arena is more like ownership where siblings can't outlive ancestors - ie. deallocate when parent/root (arena container) is deallocated.
- verdagon 4y ago
  Some possibly relevant works: Pony has a separate GC for every actor. I suspect that in practice, these work a lot like arenas; since they're very short lived, I'd imagine that most actors just allocate a lot and then blast it away. [0] Odin (not GC'd) has an implicit "context" that has an allocator, [1] effectively decoupling the allocator from the code. One could use an arena allocator for any function they'd like. Vale (not GC'd) is taking this the context system bit further and makes it memory safe. [2] [0] https://tutorial.ponylang.io/appendices/garbage-collection.html https://tutorial.ponylang.io/appendices/garbage-collection.h... [1] https://odin-lang.org/docs/overview/#allocators https://odin-lang.org/docs/overview/#allocators [2] https://verdagon.dev/blog/zero-cost-refs-regions https://verdagon.dev/blog/zero-cost-refs-regions
ryneandal 4y ago
Had to do a double-take at the title, wondering what the former Duke basketball standout (https://www.youtube.com/watch?v=uH5ltiHSJqE https://www.youtube.com/watch?v=uH5ltiHSJqE) knew about garbage collection.
CyberDildonics 4y ago
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.
munificent 4y ago
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.
hayley-patton 4y ago
> 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.4603&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.... [2] https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/levanoni-on-the-fly-rc.pdf https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/levanon... page 5, figure 2 in particular
- deleted 4y ago
  [deleted]
rajnathani 4y ago
Off-topic: The discussion in the next section about Chris Lattner's woodworking is interesting.

326 points by Austin_Conlon 4y ago

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.

Someone 4y ago
Some programs spend over 50% of their time doing reference counting (http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf http://iacoma.cs.uiuc.edu/iacoma-papers/pact18.pdf), and that will show up I’m your throughput measurements. I expect you can find papers giving numbers in the same ballpark for malloc/free, too. A MVP of JavaScript, for example, that boxes everything, combined with a benchmark that creates a d destroys lots of objects.

twoodfin 4y ago

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.

melissalobos 4y ago
This sounds very nice, but just to make sure I understand your meaning: If you have a properly designed "systems" programming language(even if manually managed) you would release resources exactly(or nearly so) at the time when a proper ARC/RAII implementation would. Is that correct for your meaning? If so I fully agree.
- twoodfin 4y ago
  My point was that if by “systems” programming, you mean prioritizing efficient use of limited system resources (CPU cycles, bytes of memory, … ) then there’s no superior alternative to the precise control & reliability afforded by ARC/RAII.
- ncmncm 4y ago
  At this late date, a language inadequate to express ARC/RAII is better described as a toy. There is nothing wrong with toys, but they are not to be confused with professional tools. A systems language is, first and foremost, a professional tool.
- jandrewrogers 4y ago
  It is more subtle than this. Systems programming sometimes involves a resource life cycle that has semantics that map neither to a GC nor RAII/ARC. This is because systems programming often involves the direct management of hardware resources, like storage. For example, while resource acquisition and release may be deterministic, there is no implication that a released resource may be immediately reused or reacquired. This is not pattern most software engineers are used to. The reason for this is that hardware may hold a lingering reference to a software resource even if the software does not -- and hardware doesn't use reference counters or destructors. An arbitrary amount of time may pass between a resource being released in software and that same resource being available for reuse again in software. Many people new to systems engineering make the mistake of reusing a resource that was released but not reusable. Systems programming languages don't just ensure deterministic release of resources, they also need to provide a way to express that the hardware may hold references to objects the software has fully released such that it isn't really released. This is not something the average programmer has to deal with, but this is part of what makes systems engineering different.

cmrdporcupine 4y ago

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.

melissalobos 4y ago
> Reference counting is garbage collecting I am drawing a blank on google scholar at the moment, but I recall a very popular paper on exactly this topic of RC as the other side of Tracing GC.
- hayley-patton 4y ago
  "A unified theory of garbage collection"? https://dl.acm.org/doi/10.1145/1028976.1028982 https://dl.acm.org/doi/10.1145/1028976.1028982
  - melissalobos 4y ago
    Yes! Thank you, I couldn't think of the terms to search for to find this.

invalidname 4y ago

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.

jandrewrogers 4y ago
> For servers where overall performance matters more than 100% smooth consistency and RAM is cheaper... GCs have some advantages. I am having a difficult time parsing this in a way that makes sense. Generally speaking, overall performance on servers is a direct product of being able to take strict control of when things happen and minimizing RAM footprint. That "smooth consistency" is how performance happens because there are important classes of software optimization that don't work if this is not a property of your runtime. Similarly, high-performance server architectures are usually not heavily concurrent even on massively multicore systems for good reasons that a GC doesn't address. The only advantage a GC has in this context that I can think of is that it might reduce some types of bugs in some types of code.
- invalidname 4y ago
  I come from the world of JVM so here we do have multicore servers and you might see a peek where a particular request takes longer but overall the performance will be amazing. This isn't OK for GUI but is great if you have a HUGE server that can chug through tons of data with a huge amount of RAM/cache.
  - panick21_ 4y ago
    But this problem has technically mostly been fixed by Azul and is making its way into open as well, we have ZGC and so on now. Pauses are rather short even with large heaps.

GeekyBear 4y ago

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 https://twitter.com/Catfish_Man/status/1326238434235568128

astrange 4y ago
This has nothing to do with custom hardware, it's one of the few differences that's actually due to ARM vs x86. Though, part of it is from being a unified memory SoC.
- Tagbert 4y ago
  I heard in an interview with Craig Federighi, that in designing the Apple Silicon chips they had looked at specific operations that were frequently used by their OS and software and optimized those on their chips. Reference counting was one of those operations and that was why the speed of that operation was so much faster on Apple Silicon. Sure those other things about unified memory contribute speed to all kinds of operations, but they really focused on some of them to let their hardware and software work well together.
  - astrange 4y ago
    Choosing to use ARM and unified memory is part of designing the SoC, though. There is no magic in the refcount machinery; you can disassemble it and look at it.
pjmlp 4y ago
Now try Swift outside that hardware stack.
- aeldidi 4y ago
  I agree with the sentiment, but does Swift actually see any usage outside of Apple’s own hardware? I think Swift’s reliance on such an optimization is justified since the hardware this optimization is applied to is the main target. While Swift’s approach may be slower in theory, is it actually slower in practice? Just a thought.

pizlonator 4y ago

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.

vvanders 4y ago
I think his point about the amount of research done on ARC vs GC was interesting. Only recently have we see things like biased reference counting[1] that can significantly reduce the overhead of ARC. [1] http://iacoma.cs.uiuc.edu/iacoma-papers/PRES/present_pact18.pdf http://iacoma.cs.uiuc.edu/iacoma-papers/PRES/present_pact18....
- deleted 4y ago
  [deleted]
- pjmlp 4y ago
  Reference counting is the oldest garbage collection algorithm, it has seen plenty of research. What keeps being overseen is the amount of engineering to make reference counting perform in modern hardware, effectively overlaps with other garbage collection optimizations.

gary_0 4y ago

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.

12thwonder 4y ago
this is a really good benefit of RC codebase. Resource management becomes much more harmonious and easy to follow.
pjmlp 4y ago
There are Roslyn analysers for that.

nwatson 4y ago

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

vips7L 4y ago
ZGC also has sub millisecond pauses
panick21_ 4y ago
Yes. And if you read their papers, when they were able to add explicit hardware support they were able to do even better. I really think had vertical companies from the 90s not all died, seriously developing chips for personal computers (phones,laptops) with hardware support for the most important GC features would have been a huge winner. Apple could have done this but they were already bound to Object-C because of Next. Sun had the amazing Self VM in the early 90s already. And they made their own chips as well. But unfortunately they went with Java and instead of making a chip to support GC they tried to make a chip that implemented Java.
- pjmlp 4y ago
  The amazing Self VM is the genesis of Hotspot anyway. They didn't try, they actually did them, and ARM did that as well.
  - panick21_ 4y ago
    Yeah Sun of course later bought the tech they developed themselves. Totally dumb. What do you mean 'they did them' as far as I know they never did extensions to their main CPU specifically to improve garbage collection.
    - pjmlp 4y ago
      The story between Objective-C, Strongtalk, SELF, Tcl and Java is a bit more complicated than that. No they didn't, but the point was about Java specific CPUs, https://en.m.wikipedia.org/wiki/PicoJava https://en.m.wikipedia.org/wiki/PicoJava And then there was https://www.electronicdesign.com/technologies/digital-ics/article/21771934/hardware-speeds-up-java https://www.electronicdesign.com/technologies/digital-ics/ar...

armchairhacker 4y ago

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.

fauigerzigerk 4y ago
> Personally I find ARC really easy to reason about and worth it How do you reason about a closure that captures some stuff and gets passed to a library function? @escaping doesn’t give you enough information to reason about all lifetimes that could possibly matter.
- hmlongco 4y ago
  Uhh... because I can see what was captured? If I'm overly concerned that a given callback might be held somewhere for all time I'll simply capture a weak reference and be done with it.

nu11ptr 4y ago

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

verdagon 4y ago

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 https://verdagon.dev/blog/zero-cost-refs-regions [1] https://aardappel.github.io/lobster/memory_management.html https://aardappel.github.io/lobster/memory_management.html [2] https://github.com/Kindelia/HVM https://github.com/Kindelia/HVM [3] https://www.microsoft.com/en-us/research/publication/perceus-garbage-free-reference-counting-with-reuse/ https://www.microsoft.com/en-us/research/publication/perceus...

nu11ptr 4y ago
This. Said much better than my other posts, but this is exactly what I was trying to say. Naive ARC vs GC... a good GC will kill it, so don't make the ARC naive...cheat and find ways to skip most ref. counter bumps. It became amazingly clear when I started coding Rust: you only have to bump ref count when you get a new owner. Most RC objects die with just a few counter bumps. Most objects don't need RC at all (most objects can be single owner). Now imagine a lang (lobster given as an example above) that does this automatically. Sweet spot.
- nu11ptr 4y ago
  Two more interesting ways to speed it up: - Make threads a "special" tracked API call (for example, like Rust) so that you know when something will or won't be passed between threads. If it never "escapes" the thread, you can use non-atomic ref counts for the lifetime of that object (NOTE: I should add this is something I've been thinking on - I don't know how hard/feasible it is to do in practice) - Use biased RC - don't have link to paper handy, but idea is that most multithreaded objects spend most of their life on one thread and when they are on that thread, can use non-atomic ref counts by using a separate counter. When on any other thread they use an atomic counter. When both counts hit zero, object is destroyed.

ncmncm 4y ago

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.

klabb3 4y ago

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

verdagon 4y ago
I'm not sure most people use this technique, but when I was using RC-based systems, I would often assert that an object's refcount was 1 just before I let go of that last reference. Suddenly, we have RAII-like predictable destruction. I even built it into Vale as one of its memory management options called "constraint references" [0] though later switched to generational references which gave us RAII without the halts. I sometimes wonder how far I could have taken that RC + assert model. In my experience, the vast majority of objects even in an RC'd language do have strong refcount = 1. Perhaps we were in different domains though, I was mostly in game dev and app dev. [0] https://verdagon.dev/blog/raii-next-steps https://verdagon.dev/blog/raii-next-steps
kgeist 4y ago
I don't think it's quite deterministic because a simple variable going out of a scope can trigger deallocation of a random object tree (which can be large), which you cannot always predict locally (as a programmer) and which can affect performance on a critical path or introduce side effects at unpredictable times, plus the overall possibility of having uncollected cycles - so in the end for a programmer -- who's not willing to manually trace ownerships themselves to understand the behavior in every detail -- it has quite same disadvantages as a tracing GC (deallocation may kick in at "unpredictable" times) with the additional disadvantages such as: fragmentation and poorer memory locality in the long term (no compaction), possible memory leaks (due to object islands), temporary young generation objects being as expensive as old generation objects (no bump pointer allocation in a nursery), excessive RC increments/decrements can trash performance (and if it's atomic it can IIRC force cache invalidation, which also makes the behavior less deterministic). So I don't think it's a silver bullet, it's just a different kind of GC with its own set of disadvantages. I think most of the time RC is chosen because it's simple to implement or because there's a legacy system where RC is the only choice, and all the other "benefits" are just afterthoughts to further justify the choice.

Decabytes 4y ago

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.

jollybean 4y ago

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.

randyrand 4y ago
A lot of programs have to deal with JNI or weak references.
draw_down 4y ago

travisgriggs 4y ago

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.

azinman2 4y ago
Is it really that hard to deal with memory ownership? What’s situations are you in that it’s so stressful?

moonchild 4y ago

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-bacon.pdf https://courses.cs.washington.edu/courses/cse590p/05au/p50-b...

saagarjha 4y ago
> Are unlikely to ever get really huge (people balk at large downloads) Wait until you see how big apps are.

pjmlp 4y ago

And yet languages with tracing GC outperform Swift. https://github.com/ixy-languages/ixy-languages 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.

astrange 4y ago
This benchmark is not good enough to make a decision about how you should build an entire OS. They did make this decision when designing ARC and Swift, and they did have data for it, and first-order effects of how fast you can make a single task can't be the determining factor there. In particular you need to know how disruptive running the task will be to other more important stuff.
- pjmlp 4y ago
  You can benchmark it against Android or Windows Phone devices then. Naturally with similar hardware across the board.
  - astrange 4y ago
    You can do that by looking up which one ships with less RAM installed. I believe the common wisdom is still that it's not Android.
    - pjmlp 4y ago
      To save you the trouble, any Windows Phone 7 device, using XNA or Silverlight as OS APIs, 512 MB.
    - 4y ago

benreesman 4y ago

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.

saagarjha 4y ago
None of the strategies you’re claiming is the “best” really wins in every situation. There’s inherent tradeoffs with all of them.

sharken 4y ago

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.

ak39 4y ago
Delphi has legendary ARC not just with its VCL and object hierarchies with TOwner model but also with its wrappers of COM's IUnknown and QueryInterfaces. Yes of course, developers can still make mistakes about sequences and memory management but a well constructed class hierarchy and discipline to manage the freeing of resources immediately after they're no longer needed is the cornerstone of basic Delphi applications. edit: The objects that are IUnknown linked don't even need to be explicitly freed! There are several clever use cases for this for example changing TCursor from hourglass back to normal when a procedure/function is complete. It just works.

ordu 4y ago

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.

hayley-patton 4y ago
There are moving collectors which use profiling information to try to improve locality. It appears they produce a 15-30% speedup or so. https://safari.ethz.ch/architecture/fall2017/lib/exe/fetch.php?media=p332-chen.pdf https://safari.ethz.ch/architecture/fall2017/lib/exe/fetch.p... https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/ismm_paper.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
verdagon 4y ago
Take a look at Mesh [0] which brings compaction to a malloc-like system. I could see an RC-based or single-ownership-based language using it to avoid fragmentation. [0] https://tiba-jrchang.medium.com/mesh-compacting-memory-management-for-c-c-applications-bc2a2cecc8cc https://tiba-jrchang.medium.com/mesh-compacting-memory-manag...
jandrewrogers 4y ago
Database engine implementations sometimes work similar to this, being locality optimizing machines. Objects in memory can be moved and reorganized dynamically. Ensuring that references to those objects remain valid is not inexpensive because it requires indirection to dynamically resolve object locations and may require patching state referencing the object. The performance impact is only tolerable for database engines because the context and scope is sufficiently constrained such that clever software design elements can ensure that the cost is applied lazily and expensive effects are avoided except in rare cases. Even in database engines, thrashing your CPU cache is a common side effect of not getting the design right. I can't imagine trying to make this perform well for general purpose software.

jurschreuder 4y ago

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

mirekrusin 4y ago
Exactly, it's like athlete wanting to be a referee.
- munchler 4y ago
  More like an athlete wanting to become a coach, which is very common.

torginus 4y ago

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.

draw_down 4y ago
jFriedensreich 4y ago
Could you elaborate how this is connected to js and SPA frameworks? I totally get how reasoning and determinism is critical for sound processing, embedded low level, operating systems etc. But why would this be relevant for normal application or web development?
- torginus 4y ago
  SPA frameworks manipulate the DOM through JS, which means they need to take a reference to DOM elements. In a static website, once you navigate away from a page, the browser can deallocate all the DOM resources related to the old page, which can be quite heavy (images etc.). In an SPA-driven website, the DOM is created by JS. Once you 'navigate' away (you tell the framework to render a different set of DOM components), the old ones still linger around in memory until the next GC cycle, meaning the browser has to wait for the GC to run before it can free them. Even worse, GC's tend to be tuned for GC memory pressure, and if you have a ton of GC objects holding onto native resources, the GC has no way of telling it needs to run, because from its perspective, the GC heap is small and it has no idea about the native objects.
  - 4y ago

losvedir 4y ago

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.

mirekrusin 4y ago
Sounds more like ownership annotation than generations. Generations basically takes advantage of the fact that recently allocated memory is much more likely to be deallocated sooner - ie. it's run time/age based. What you're describing with arena is more like ownership where siblings can't outlive ancestors - ie. deallocate when parent/root (arena container) is deallocated.
verdagon 4y ago
Some possibly relevant works: Pony has a separate GC for every actor. I suspect that in practice, these work a lot like arenas; since they're very short lived, I'd imagine that most actors just allocate a lot and then blast it away. [0] Odin (not GC'd) has an implicit "context" that has an allocator, [1] effectively decoupling the allocator from the code. One could use an arena allocator for any function they'd like. Vale (not GC'd) is taking this the context system bit further and makes it memory safe. [2] [0] https://tutorial.ponylang.io/appendices/garbage-collection.html https://tutorial.ponylang.io/appendices/garbage-collection.h... [1] https://odin-lang.org/docs/overview/#allocators https://odin-lang.org/docs/overview/#allocators [2] https://verdagon.dev/blog/zero-cost-refs-regions https://verdagon.dev/blog/zero-cost-refs-regions

ryneandal 4y ago

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

CyberDildonics 4y ago

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.

munificent 4y ago

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.

hayley-patton 4y ago

> 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.4603&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.... [2] https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/levanoni-on-the-fly-rc.pdf https://sites.cs.ucsb.edu/~ckrintz/racelab/gc/papers/levanon... page 5, figure 2 in particular

deleted 4y ago
[deleted]

rajnathani 4y ago

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