30 ms·

Reference count, don't garbage collect

• glouwbug 4y ago
  Isn’t garbage collection needed to solve circular reference counts?
  • arcticbull 4y ago
    Nope, you can just mark the back-reference as weak. GC is only required if you as a programmer (or programming language) do not provide sufficient information to the compiler or runtime to understand the object graph.
    • klodolph 4y ago
      It's not always obvious to know which reference to mark as weak, and there's not necessarily a clear indication of which reference is a back-reference. You can find various algorithms in journals or whatnot written with the assumption that there's GC. Algorithms designed with this assumption may not have clear ownership for objects, and those objects my have cyclic references. It's easy to say, "objects should have clear ownership relationships" but that kind of maxim, like most maxims, doesn't really survive if you try to apply it 100% of the time. Ownership is a tool that is very often useful for managing object lifetimes--it's not always the tool that you want.
      • eru 4y ago
        And if you have really clear ownership, you don't need reference counting either..
        • klodolph 4y ago
          That's definitely not true. "Clear ownership" may still be shared ownership.
          • eru 4y ago
            Hmm, ok. But how is that different from situations where tracing GC is useful? (And even languages with a tracing GC often offer weak pointers. Eg Haskell and Java do. Python does as well, but Python has both reference counting and tracing garbage collection.) Apart from performance (latency vs throughput) considerations, the only difference between RC and GC for your algorithms and datastructure design is whether you allow circles in your datastructures.
      • glouwbug 4y ago
        But, I mean, the whole purpose of using a reference counted GC language is for the productivity gain. If I'm going to be using a reference counted language and manually specifying weak pointers then I'd just C++
        • klodolph 4y ago
          It sounds like you're saying that the only productivity gain from ARC (automatic reference counting) is that you don't have to manually annotate what type of pointer you want. I don't agree with that. Yes, if you forget to mark a ref-counted pointer as weak, then you may get a memory leak. Memory leaks can be disastrous, but they can be benign, and they're always better than use-after-free. In C++ it is easy to create a raw pointer (with & or *). It's unsafe. Soon enough, you have some lambda inside another function, but the lambda is executed after the enclosing function returns, and you've captured a variable with &. Oops. You thought that the lambda would get executed during the enclosing function's execution, but you misread the API you were using. IMO the big productivity gain is being able to write code where I don't have to think too hard about whether the code is memory-safe. Modern C++ code makes this easier, but languages with ARC (like Objective-C or Swift) make this even easier. Code is mostly safe by default, and you can visually inspect code to look for unsafe behavior, more easily than you can with C++. There are also hybrid ref-counted + tracing GC options. CPython uses this approach.
        • eru 4y ago
          As a slight tangent, weak pointers are useful in languages with a tracing GC, too. Haskell offers weak pointers. For example they make certain kinds of caches easier.
• melony 4y ago
  You are in for a fun time when you need to make circular data structures with ARC.
• habibur 4y ago
  It's interesting how we have come full circle from "Reference counting is the worst of two worlds [manual and GC] and will always be slower" to now "Well, we all know it's actually faster." in like 10 years.
  • pclmulqdq 4y ago
    Its actually usually slower than both manual memory management and GC. It's only coming back now because people are finally learning how to make memory allocations large and rare. This blog post is an answer to: "Tell me you haven't learned about cache coherence without telling me you haven't learned about cache coherence."
    • rwmj 4y ago
      Hiring would certainly be a lot easier if more people were to make bold, completely wrong blog postings like these. I could immediately give my negative recommendation without the time and hassle of a phone interview.
      • deleted 4y ago
        [deleted]
      • pclmulqdq 4y ago
        I completely agree, but before we scare people away from blogging too much, I will say that my big problem with this post isn't the lack of knowledge, it's the willful ignorance and lack of humility. It's clear that the author doesn't really understand the position they are trying to argue against.
    • OskarS 4y ago
      > Its actually usually slower than both manual memory management and GC [citation needed] You and the blog post are arguing opposite things, and neither of you have shown any evidence. I get that you're arguing that reference counted objects are bigger (to store the reference count) and/or might use double indirection (depending on implementation), which are both bad for caches. It's not a bad argument. But the counter-argument that the blog posts makes is persuasive as well: it's expensive running a GC that scans the heap looking for loose objects, and reference counting does not need to do that. GC is also "stop-the-world" as well unpredictable and jittery in a way reference counting is not. My instinct is that reference counting is actually faster (which matches my personal experience), but really, this is not an argument you can solve by arguing in the abstract, you need actual data and benchmarks.
• carry_bit 4y ago
  You can optimize reference counting: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.231.4763&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23... With allocating as dead, you're basically turning it into a tracing collector for the young generation.
  • hayley-patton 4y ago
    https://users.cecs.anu.edu.au/~steveb/pubs/papers/lxr-pldi-2022.pdf https://users.cecs.anu.edu.au/~steveb/pubs/papers/lxr-pldi-2... is the most recent publication in this lineage of high-performance RC systems.
• jerf 4y ago
  From what I can see, the myth that needs to be debunked isn't that garbage collection is super fast and easy with no consequences, it's the myth that garbage collection always automatically means your program is going to be spending 80% of its time doing it and freezing for a second every five seconds the instant you use a language with garbage collection. I see far more "I'm writing a web server that's going to handle six requests every hour but I'm afraid the garbage collector is going to trash my performance" than people who believe it's magically free. It's just another engineering decision. On modern systems, and especially with any runtime that can do the majority of the GC threaded and on an otherwise-unused core, you need to have some pretty serious performance requirements for GC to ever get to being your biggest problem. You should almost always know when you're setting out to write such a system, and then, sure, think about the GC strategy and its costs. However for the vast bulk of programs the correct solution is to spend on the order of 10 seconds thinking about it and realizing that the performance costs of any memory management solution are trivial and irrelevant and the only issue in the conversation is what benefits you get from the various options and what the non-performance costs are. It is in some sense as big a mistake (proportional to the program size) to write every little program like it's a AAA game as it is to write a AAA game as if it's just some tiny little project, but by the sheer overwhelming preponderance of programming problems that are less complicated than AAA games, the former happens overwhelmingly more often than the latter. Edit: I can be specific. I just greased up one of my production systems with Go memstats. It periodically scans XML files via network requests and parses them with a parser that cross-links parents, siblings, and children using pointers and then runs a lot of XPath on them, so, it's kinda pessimal behavior for a GC. I tortured it far out of its normal CPU range by calling the "give me all your data" JSON dump a 100 times. I've clicked around on the website it serves to put load on it a good 10x what it would normally see in an hour, minimum. In 15 minutes of this way-above-normal use, it has so far paused my program for 14.6 milliseconds total. If you straight-up added 14.6 milliseconds of latency to every page it scanned, every processing operation, and every web page I loaded, I literally wouldn't be able to notice, and of course that's not what actually happened. Every second worrying about GC on this system would be wasted.
  • nickbauman 4y ago
    Yes; I have a friend who is part of a small team that wrote a very successful stock market trading gateway in Java. Turns out the JVM's GC can be tuned in very specific ways based on your needs. And there are ways to avoid having to do JVM GC in critical areas of the code as well.
• agentultra 4y ago
  A paper I quite enjoyed on automatic reference counting for pure, immutable functional programming: https://arxiv.org/abs/1908.05647 https://arxiv.org/abs/1908.05647 It can be quite "fast."
  • miloignis 4y ago
    Indeed, and this line of research has been continuing to improve in follow on work on Perceus in Koka: https://xnning.github.io/papers/perceus.pdf https://xnning.github.io/papers/perceus.pdf and https://www.microsoft.com/en-us/research/uploads/prod/2021/11/flreuse-tr-v1.pdf https://www.microsoft.com/en-us/research/uploads/prod/2021/1... Very cool stuff!
  • eru 4y ago
    If you have pure, immutable and strict, you can't create cycles. (That's what Erlang does for example.) That makes a lot of memory management techniques much simpler. Both tracing garbage collection and reference counting. If you have pure, immutable and lazy, you can get cycles. (That's Haskell.) This is almost as complicated for a GC as not having immutability.
• assbuttbuttass 4y ago
  In practice, I don't see any reference counting approaches that do cycle detection. I have an example from early in my career where I accidentally created a memory leak in Python from a cyclic reference between a closure and a function argument https://stackoverflow.com/questions/54726363/python-not-deleting-variable-when-it-goes-out-of-scope https://stackoverflow.com/questions/54726363/python-not-dele...
• byefruit 4y ago
  This article provides very little evidence for it's claims and seems to only have a superficial understanding of modern GCs. "Increments and decrements happen once and at a predictable time. The GC is running all the time and traversing the universe of GC objects. Probably with bad locality, polluting the cache, etc." This is only the case with a mark-sweep collector, usually most of your allocations die young in the nursery. With reference counting you pay the counting cost for everything. "In object-oriented languages, where you can literally have a pointer to something, you simply mark a reference as a weak reference if it might create a cycle." As someone who has tried to identify memory leaks in production where someone has forgotten to "simply" mark a reference in some deep object graph as weak, this is naive. "With an 8-byte counter you will never overflow. So...you know...just expand up to 8-bytes as needed? Usually you can get by with a few bits." So now my "about as minimal as you can get short of nothing at all" check as an unpredictable branch in it? "If you must overflow, e.g., you cannot afford an 8-byte counter and you need to overflow a 4-byte counter with billions of references, if you can copy it, you create a shallow copy." I don't even know where to begin with this. "If GC is so good, why wouldn't Python just garbage collect everything, which they already did once and could trivially do, instead of going through the hassle of implementing reference counting for everything but the one case I mentioned?" This probably has more to do with finalising resources and deterministic destruction than anything else. -- Anyone who is interested in actually studying this area would probably find https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf https://courses.cs.washington.edu/courses/cse590p/05au/p50-b... interesting. Also https://gchandbook.org/ https://gchandbook.org/
  • knome 4y ago
    >If GC is so good, why wouldn't Python just garbage collect everything, which they already did once and could trivially do I don't think python ever did pure mark-and-sweep ( cpython, at least, I'm sure jython and other alternate implementations have ). My understanding was that they did pure reference counting, and kludged on a sweep GC to do cycle breaking eventually, as manually breaking cycles in early versions of python was a pain point. A quick lookup seems to indicate python1 was pure reference counting, and they added the cycle breaking when they released python2.
• shwestrick 4y ago
  This debate has gone round and round for decades. There are no hard lines; this is about performance tradeoffs, and always will be. Perhaps the biggest misconception about reference counting is that people believe it avoids GC pauses. That's not true. Essentially, whereas tracing GC has pauses while tracing live data, reference counting has pauses while tracing garbage. Reference counting is really just another kind of GC. I'd highly recommend perusing this paper for more details: A Unifying Theory of Garbage Collection. https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-garbage.pdf https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-... One of the biggest issues with reference counting, from a performance perspective, is that it turns reads into writes: if you read a heap-object out of a data structure, you have to increment the object's reference count. Modern memory architectures have much higher read bandwidth than write bandwidth, so reference counting typically has much lower throughput than tracing GC does.
  • kaba0 4y ago
    One great example would be a C++ program that runs fast, and then just spends 10s of seconds doing “nothing” while it deallocates shared pointers’ huge object graphs at the end. They really are two sides of the same coin, with tracing GCs being actually correct (you need cycle detection for a correct RC implementation), and having much better throughput. It’s not an accident that runtimes with thousands dev hours are polishing their GC solutions instead of using a much more trivial RC.
    • hinkley 4y ago
      I don't know what the current state of the art is, but at one point the answer to GC in a realtime environment was to amortize free() across malloc(). Each allocation would clear up to 10 elements from queue of free-able memory locations. That gives a reasonably tight upper bound on worst case alloc time, and most workflows converge on a garbage-free heap. Big malloc after small free might still blow your deadlines, but big allocations after bootstrapping are generally frowned upon in realtime applications, so that's as much a social problem as a technical one.
      • 4y ago
• slavboj 4y ago
  People have been managing garbage collection schedules for decades now. It's quite possible for many systems to have completely deterministic performance, with the allocation/deallocation performance made extremely fast, gc restricted to certain times or a known constant overhead, etc. Ironically, from a programming perspective it's incredibly easy in a language like Java to see exactly what allocates and bound those cases. Conversely, it's also possible for reference counting to have perverse performance cases over a truly arbitrary reference graph with frequent increments and decrements. You're not just doing atomic inc/dec, you're traversing an arbitrary number of pointers on every reference update, and it can be remarkably difficult to avoid de/allocations in something like Python where there's not really a builtin notion of a primitive non-object type. Generally speaking, memory de/allocation patterns are the issue, not the specific choice of reference counting vs gc.
• mirekrusin 4y ago
  What about - garbage collect by reference counting, like Python?
  • eru 4y ago
    Python has reference counting for historical reasons, and added tracing garbage collection for dealing with cycles. If you wanted performance these days, you wouldn't want to go for that architecture. It's a historically accident that they can't really free themselves from because of backwards compatibility.
• exabrial 4y ago
  > I've already stated I'm not going to do benchmarks. Yikes
• jsnell 4y ago
  > Basically, you attach the reference to the object graph once, and then free it when you're done with it. So reference counting works by the programmer knowing the lifetime of each object allowing them to only increment / decrement the refcount once, and trusting that the raw uncounted pointers they use elsewhere are always valid? There's another word we have for this: manual memory management. It's unsafe and unergonomic, and it's pretty telling that the author needs to this pattern to make RC appear competitive. It's because actually doing reference counting safely is really expensive. > If GC is so good, why wouldn't Python just garbage collect everything, which they already did once and could trivially do, instead of going through the hassle of implementing reference counting for everything but the one case I mentioned? Because they've made reference counting a part of their C extension API and ABI. If they wanted to use a GC, they'd instead need a very different API, and then migrate all the modules to the new API. (I.e. a way for those native extension to register/unregister memory addresses containing pointers to Python objects for the GC to see.) Early on the deterministic deallocation given by reference counting would also have been treated by programmers as a language level feature, making it so that a migration would have broken working code. But I don't think that was ever actually guaranteed in the language spec, and anyway this was not carried over to various alternative Python implementations.
  • twic 4y ago
    Details aside, using Python to make an argument about performance is a pretty bold move.
    • cakoose 4y ago
      While Python is not high performance overall, people have spent a ton of time optimizing the memory management. So while it's not definitive proof of reference counting being slow, it seems like a fair initial question.
  • eru 4y ago
    Yes. In Python reference counting precedes tracing garbage collection. So they didn't 'go through the hassle of implementing reference counting' after they already had tracing garbage collection. Instead they went through the hassle of implementing tracing garbage collection after they already had reference counting. (And as you say for backwards compatibility reasons, they can't get rid of reference counting.)
• flohofwoe 4y ago
  Such a claim really needs hard data to back it up. Reference counting can be very expensive, especially if the refcount update is an atomic operation. It's hard to capture in profiling tools because the performance overhead is smeared all over the code base instead of centralized in a few hot spots, so most of the time you don't actually know how much performance you're losing because of refcounting overhead. The most performant approach is still manual memory management with specialized allocators tuned for specific situations, and then still only use memory allocation when actually needed.
  • okennedy 4y ago
    This. Exactly this. Garbage collection has a huge, and generally entirely unappreciated win when it comes to threaded code. As with most things, there are tradeoffs, but every reference counting implementation that I've used has turned any concurrent access to shared memory into a huge bottleneck.
  • arcticbull 4y ago
    > The most performant approach is still manual memory management with specialized allocators tuned for specific situations, and then still only use memory allocation when actually needed. RAII gets you a lot of the way there.
• bitwize 4y ago
  Boy, I can't wait for theangeryemacsshibe (posts here as hayley-patton) to tear into this one. But yeah, the correct way to handle resources (not just memory!) is with value semantics and RAII. Because then you know the object will be cleaned up as soon as it goes out of scope with zero additional effort on your part. In places where this is not appropriate, a simple reference counting scheme may be used, but the idea is to keep the number of rc'd objects small. Do not use cyclical data structures. Enforce a constraint: zero cycles. For data structures like arbitrary graphs, keep an array of vertices and an array of edges that reference vertices by index. If you use a language with GC, you're probably just contributing to global warming.
  • kaba0 4y ago
    Why not just write embedded programs with fixed size memory allocation then if we are that okay with restricting the programs we write?
    • bitwize 4y ago
      Because maybe we're not okay with restricting the programs we write that much.
      • kaba0 4y ago
        Nor am I okay with restricting my programs as much as a tree-like only allocation strategy would suffice and circular data structures are not evil.
  • eru 4y ago
    Doesn't RAII only work when your lifetimes are in a nested hierarchy? (Basically, your lifetimes have to be the same as your scopes, which are in a simple tree structure only.)
• knome 4y ago
  Reference counting can also have unpredictable hits if you release any large data structures. Whoever drops the last reference suddenly gets to sit through the entire deep set of items to release ( unless you can hand off the release cascade to a background thread ). I've never heard of a reference counting implementation that can handle memory compaction. Every time you update a reference count, which is every time you touch any object, you're going to have to write to that RAM, which means stealing it from any other threads using it on any other processors. If you share large trees of data between threads, traversing that tree in different threads will always end up with your threads constantly fighting with each other since there's no such thing as read only memory in reference counting. When releasing something like a huge list in reference counting, how does the release avoid blowing the stack with recursive releasing? My guess is this just a "don't use a large list whose release may blow the stack with recursive releasing" situation.
  • mamcx 4y ago
    > hits if you release any large data structures. Well, that depends in how is the RC done. This is key to understand because if you can control it, the RC become cheaper. You can see this way on http://sblom.github.io/openj-core/iojNoun.htm http://sblom.github.io/openj-core/iojNoun.htm ie: If instead of `[Rc(1), Rc(2)]` you do `Rc([1, 2])` that work great.
    • kaba0 4y ago
      How is that not the exact same for tracing GC?
      • mamcx 4y ago
        Well, you don't need the GC. That is the point of this: Rc could be piece-meal. That is something that could be exploited very well making a interpreter, for example (that is what Array langs do under the hood)
  • eru 4y ago
    > I've never heard of a reference counting implementation that can handle memory compaction. It's possible to add that in theory. But if you are tracing all your memory anyway so you can compact it, you typically might as well collect the garbage, while you are at it. But: you are in for a treat, someone implemented compaction for malloc/free. See https://github.com/plasma-umass/Mesh https://github.com/plasma-umass/Mesh They use virtual memory machinery as the necessary indirection to implement compaction, with neither changing any pointers nor reliably distinguishing pointers from integers.
• dpryden 4y ago
  This article is naive to the point of being flat-out wrong, since it makes extremely naive assumptions about how a garbage collector works. This is basically another C++-centric programmer saying that smart pointers work better than the Boehm GC -- which is completely true but also completely misleading. I'm not saying that GC is always the best choice, but this article gets the most important argument wrong: > 1. Updating reference counts is quite expensive. > > No, it isn't. It's an atomic increment, perhaps with overflow checks for small integer widths. This is about as minimal as you can get short of nothing at all. Yes, it is. Even an atomic increment is a write to memory. That is not "about as minimal as you can get short of nothing at all". Additionally, every modern GC does generational collection, so for the vast majority of objects, the GC literally does "nothing at all". No matter how little work it does, a RC solution has to do O(garbage) work, while a copying GC can do O(not garbage) work. Now, that's not to say that GC is automatically better. There are trade-offs here. It depends on the workload, the amount of garbage being created, and the ratio of read to write operations. The article says: > I've already stated I'm not going to do benchmarks. I am aware of two orgs who've already run extensive and far-reaching experiments on this: Apple, for use in their mobile phones, and the Python project. I can counterpoint that anecdata: Google extensively uses Java in high-performance systems, and invented a new GC-only language (Go) as a replacement for (their uses of) Python. The right answer is to do benchmarks. Or even better yet, don't worry about this and just write your code! Outside of a vanishingly small number of specialized use cases, by the time GC vs RC becomes relevant in any meaningful way to your performance, you've already succeeded, and now you're dealing with scaling effects.
  • eru 4y ago
    > [...] and invented a new GC-only language (Go) as a replacement for (their uses of) Python. That's not true. Go was invented with the intention of replacing C++ at Google. That didn't really work out, and in practice Go became more of a replacement of Python for some applications at Google. Also there are some indications that Go didn't gain traction necessarily on the merits of the language itself, but more on the starpower of its authors within Google. (I mostly agree with the rest of what you wrote.)
  • kgeist 4y ago
• dfox 4y ago
  One great advantage of garbage collection is that it removes need for thread synchronization in cases where is it only needed to make sure that object jou are going to call free/decref on is not in use in another thread. Corollaly to that GC is the thing that you need for many lock-free data structures to be practical and not of only theoretical interest. It might seem that it is simply about pushing your synchronizations problems onto the GC, but the synchronization issue that GC solves internally is different and usually more coarse-grained, so in the end you have significantly smaller synchronization overhead.
• titzer 4y ago
  I read most the article and it's just a lot of the same tired old arguments and an extremely simplified worldview of both GC and reference counting. I wish I had the author's address, because I'd like to mail them a copy of the Garbage Collection Handbook. They clearly have a very naive view of both garbage collection and reference counting. And there isn't a single dang measurement anywhere, so this can be completely dismissed IMHO.
  • cogman10 4y ago
    Agreed. What I particularly disliked is how absent of nuance it is. RC is a form of GC and all GC algorithms make tradeoffs. RC trades throughput for latency. Compacting mark and sweep trade latency (and usually memory) for throughput. The rant at the end can be boiled down to "I use confirmation bias [1] to make my engineering decisions". The OP has already decided that "GC" is slow, so I'm sure every time a runtime with it misbehaves it's "Well, that darn GC, I knew it was bad!" and every time RC misbehaves it's likely "Oh, well you should have nulled out your link here to break the cycle dummy!" I really don't like such absolutist thinking in software dev. All of software dev is about making tradeoffs. RC and GC aren't superior or inferior to each other, they are just different and either (or both) could be valid depending on the circumstance. [1] https://en.wikipedia.org/wiki/Confirmation_bias https://en.wikipedia.org/wiki/Confirmation_bias
    • titzer 4y ago
      > absent of nuance Yes, this is a good point. It makes overly general claims. E.g. a GC proponent could claim "well, tracing collectors do no work for dead objects, so they have no overhead!" Which is a good point, but not the whole story. Tracing collectors may need to repeatedly traverse live objects. Sure. But then generational collectors only traverse modified live objects that point to new objects. True. And concurrent collectors can trace using spare CPU resources, incremental collectors can break marking work up into small pauses, on and on. There are zillions of engineering tradeoffs and the GC Handbook covers most of them really well.
• cosmotic 4y ago
  > This is about as minimal as you can get short of nothing at all. With GC, you can do nothing at all. In a system with lots of garbage, you can do a GC by copying everything accessible from the GC root, then de-allocating all the garbage in a single free.
• deleted 4y ago
  [deleted]
• yyyk 4y ago
  Reference counting is garbage collection, just a different strategy - and all these strategies tend to blur to the same methods eventually, eventually offering a latency-optimized GC or a throughput-optimized GC. Swift is inferior here because it uses reference counting GC without much work towards mitigating its drawbacks like cycles (judging by some recent posts, some of its fans apparently aren't even aware RC has drawbacks), while more established GC languages had much more time to mitigate their GC drawbacks - e.g. Java's ZGC mitigates latency by being concurrent.
  • fingerlocks 4y ago
    What do you mean? Potential reference cycles are a compile time error in Swift. That’s the whole point of the @escaping annotation
    • yyyk 4y ago
      So this[0] wasn't current despite being edited half a year ago? I guess I'm guilty of the same mistake the post had: criticizing without understanding the state of the art on the other side (at least I didn't miss it by 20 years and on an entire subfield of Computer Science). [0] https://stackoverflow.com/questions/32262172/how-can-identify-strong-reference-cycles-in-swift https://stackoverflow.com/questions/32262172/how-can-identif...
      • jumhyn 4y ago
        No, the SO post is accurate—it’s trivially easy to create strong reference cycles in Swift and @escaping annotation is only of limited use in detecting strong reference cycles. Though Swift also broadly pushes towards the use of value types for which creating reference cycles of any kind is impossible since they’re values, not references!
  • musicale 4y ago
    Maybe Apple just hires mediocre developers (I certainly have lots of complaints about their software and UI issues, but I would probably suspect management/priorities/schedules rather than the technical staff) but they implemented GC and Automatic Reference Counting for ObjC and found that the latter resulted in better and more consistent responsiveness, which is probably what most users care about in apps. (Apps still get compressed or paged out which can lead to annoying pauses.) My anecdata indicate that Java apps are not as responsive as ObjC/Swift for the most part.
• spullara 4y ago
  This is a modern GC: https://kstefanj.github.io/2021/11/24/gc-progress-8-17.html https://kstefanj.github.io/2021/11/24/gc-progress-8-17.html Way better than RC.
  • viktorcode 4y ago
    See that last graph with memory overhead? Not everyone's definition of "better" allows for that.
• deleted 4y ago
  [deleted]
• jayd16 4y ago
  Is there such a thing as a compacting RC?
  • hayley-patton 4y ago
    Backup compaction can be useful, like backup tracing can be, but you can also use all the initial increments in a coalescing RC collector to determine which pointers need to be fixed up for copying, without tracing. See http://users.cecs.anu.edu.au/~steveb/pubs/papers/rcix-oopsla-2013.pdf http://users.cecs.anu.edu.au/~steveb/pubs/papers/rcix-oopsla... pages 8 and 9 on "Defragmentation with Opportunistic Copying" e.g.
  • rtfeldman 4y ago
    There was a great talk at Strange Loop about a drop-in malloc replacement which compacts. Apparently it actually led to memory usage improvements in industrial projects like Redis: https://youtu.be/c1UBJbfR-H0 https://youtu.be/c1UBJbfR-H0
    • eru 4y ago
      See https://github.com/plasma-umass/Mesh https://github.com/plasma-umass/Mesh for the code and a link to the paper.
• nemothekid 4y ago
  It's my theory that Java, unintentionally, did a lot of damage to P&L research. I write a lot of Rust, and while the borrow checker is great, I've come to really admire the work that was put in the Go GC even if it's not as fast Java. There is a whole generation of programmers that have come to equate GC with Java's 10 second pauses or generics/typed variables with Java's implementation of them. Even the return to typed systems (Sorbel, pythons' typing, typescript) could be seen as typed languages are great, what we really hated was Java's verbose semantics.
  • chrisseaton 4y ago
    > P&L research What’s P&L? > Java's verbose semantics Does Java have verbose semantics? I think Java’s semantics are pretty neat and concise. Where’s the verbosity?
    • mandevil 4y ago
      Not OP, but someone who has gotten paid to write Java for several years. I would say that isn't that Java's semantics are that verbose, it's that the way Java is traditionally written, with every line actually 3 lines on your screen of public function makeItalicTextBox(String actualTextIWantToBeItalic) { ItalicTextBox itb = italicTextBoxFactoryGenerator.GenerateFactory().buildItalicTextBox(actualTextIWantToBeItalic); return itb; } I think this is actually the pernicious work of Martin's _Clean Code_ which trained a whole generation of Java coders to write nonsense one line functions with a million interior function calls like this, not anything forced by the Java language itself, but it makes for really ugly code, in my exceptionally humble but undoubtedly correct opinion.
      • deleted 4y ago
        [deleted]
      • musicale 4y ago
        The builder pattern with method chaining is unfortunate and should usually be replaced by named/optional parameters, in any sensible/modern programming language at least. IDEs are an enabler for horriblyLongIdentifierNames because they enter them for you automatically without requiring you to type them on a keyboard.
• freecodyx 4y ago
  What if programming languages start offering both? In my opinion RC is GC in disguise. At least for example Golang GC has the merit to run in a separate thread(still has to stop the world when reclaiming memory back, and the memory allocator model is helping achieve great GC perfs).
  • eru 4y ago
    Python does both reference counting and garbage collection. Btw, GC is also often RC in disguise. What I mean is that generational garbage collectors are basically a hybrid of tracing GC and RC. See https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-garbage.pdf https://web.eecs.umich.edu/~weimerw/2012-4610/reading/bacon-... for the details.
• amiga1200 4y ago
  Just allocate then deallocate manually, use neither auto methods.
  • eru 4y ago
    What do you mean by 'manually'? Malloc and free still do lots of work. Or do you want to manually assign memory addresses to your objects?
• Jweb_Guru 4y ago
  I'm sorry, but this is a very poorly reasoned article that does not engage with any of the serious work that's been underway to get reference counting competitive with tracing GC. This is evident from the very first point: > 1. Updating reference counts is quite expensive. > No, it isn't. It's an atomic increment, perhaps with overflow checks for small integer widths. This is about as minimal as you can get short of nothing at all. The comparison is the ongoing garbage collection routine, which is going to be more expensive and occur unpredictably. First off, updating the reference count invalidates the entire cache line in which the reference count lives. For naive reference counting (which I'm assuming the author is talking about since they give no indication they're familiar with anything else), this generally means invalidating the object's cache line (and with an atomic RMW, to boot, meaning you need a bus lock or LL/SC on most systems). So right away, you have created a potentially significant cacheline contention problem between readers in multiple threads, even though you didn't intend to actually write anything. RC Immix, for example, tries to mitigate this in many creative ways, including deferring the actual reference count updates and falling back to tracing for reclamation when the count gets too high (to avoid using too many bits in the header or creating too many spurious updates). Secondly, you know what's cheaper than an atomic increment or decrement? Not doing anything at all. The vast majority of garbage in most production tracing garbage collectors (which are, with the exception of Go's, almost exclusively generational) dies young, and never needs to be updated, copied, or deallocated (so no calling destructors and no walking a tree of children, which usually involves slow pointer chasing). Even where the object itself doesn't die young, any temporary references to the object between collections don't have to do any work at all compared to just copying a raw pointer, C style. This and bump allocation (which the author also does not engage with) are the two biggest performance wins that tracing garbage collectors typically have over reference counting ones, and solutions like RC Immix must implement similar mechanisms to even become competitive. You don't even need to go into stuff like the potential benefits of compaction, or a reduction in garbage managing code on the hot path (which are more dubious and harder to show) to understand why tracing has some formidable theoretical advantages over reference counting! But what about in practice? Surely, the overhead of having to periodically run the tracing GC negates all these benefits? Well, bluntly--no, not even close. At least, not unless you care only about GC latency to the exclusion of everything else, or are using something fancier (like deferred RC). You can't reason backwards from "Rust and C++ are generally faster than languages with tracing GCs on optimized workloads" to conclude that reference counting is better than tracing GC--Rust and C++ both go out of their way to avoid using reference counting at all wherever possible. None of this is secret information, incidentally. It is very easy to find. The fact that the author is apparently so incurious that they never once bothered to find out why academics talk about tracing GC's performance being superior--and the fact that it was so dismissive about it!--makes me pretty doubtful that people are going to find useful insights in the rest of the article, either.
• smasher164 4y ago
  For how strongly worded this article is, you'd think the author would provide some substance in their reasoning. Reference counting, even atomic, is quite expensive. Not only because it can invalidate the cache line, but depending on the architecture (looking at you x86), the memory model will deter reordering of instructions. On top of this, reference counting has a cascading effect, where one destructor causes another destructor to run, and so on. This chain of destructor calls is more or less comparable to a GC pause.
  • cmroanirgo 4y ago
    One reason you'd choose ref counting is because it's deterministic behavior, whereas you lose that granularity with gc, even if you did a gc cleanup. I see great reasons for both systems being useful, but both systems also bring their own warts. Yes, ref counting affects cache and branch prediction, but gc is a whole complete subsystem running in parallel with your main code, constantly cleaning up after you. It will always depend upon the application which will determine what's best for that application. Some languages lean heavily one way than the other too. Scripting with ref counting would be a nightmare, as would running a garbage collector on an 8bit micro. Since the article's talking C & C++, then of course a pro ref counting stance makes sense.
    • eru 4y ago
      > Scripting with ref counting would be a nightmare, [...] Why? Old version of Python used ref counting only, and Python still largely relies on reference counting (but has a GC to detect cycles).
    • kgeist 4y ago
      >One reason you'd choose ref counting is because it's deterministic behavior Not sure if it's entirely deterministic. A variable going out of a scope can trigger deallocation of a large object graph and it's not always clear by just looking at a code what will happen (especially if objects have destructors with side effects, your object graph is highly mutable, and your code is on a hot path). A common trick is to delay deallocation to a later time, but then again you can't be sure when your destructors will be run. Another issue is cycles, if your RC system has cycle detection, your program will behave differently depending on whether a cycle formed at runtime or not.
• malkia 4y ago
  Clearly this person hasn't tried how this works on NUMA cpus. it's quite expensive to do these atomic inc/decs there, or even without NUMA... caches must be synced and flushed because of this.
  • brobinson 4y ago
    Yeah, surprised no one is mentioning this. (A)RC is awesome... for flushing caches. :-(
• nikolay 4y ago
  When I wrote a Lisp interpreter in the '90s, that's how I did it and I'm ashamed to admit that I have no idea how modern GC is done - I've always assumed (naively!) that it was like Lisp's!
  • eru 4y ago
    Modern Lisps likely have modern GCs. I mean there's no reason for them not to. Racket probably has a state-of-the-art garbage collector. (I don't actually know, but that's where I would start looking.) Clojure obviously has the same garbage collector as any other JVM language.
    • gus_massa 4y ago
      Racket has like 5 GC, perhaps more. In one extreme you can build Racket using the Senora GC that is conservative and not moving, that is used only for bootstraping. On the other extreme, both of the normal versions of Racket have custom moving incremental GC. The docs with some high level explanations are in https://docs.racket-lang.org/reference/garbagecollection.html https://docs.racket-lang.org/reference/garbagecollection.htm... The implementation details of the main "CS" version are in https://github.com/racket/racket/blob/master/racket/src/ChezScheme/c/gc.c#L25-L27 https://github.com/racket/racket/blob/master/racket/src/Chez... It's a replacement of the default GC of Chez Scheme that has better support for some features that are used in Racket, but I never have looked so deeply in the details.
      • eru 4y ago
        Thanks for doing the legwork! I didn't find anything definite in twenty seconds of Googling, so I left my comment vague.
• imtringued 4y ago
  Not only does the author ignore the huge progress in conventional garbage collected languages like Java, he also dismisses GC as inherently flawed despite the fact that the common strategy of only having one heap per application has nothing to do with garbage collection. In Pony each actor has its own isolated heap which means the garbage collector will only interrupt a tiny portion of the program for a much shorter period of time. Hence the concept of a stop the world pause is orthogonal to whether you have a GC or not. One could build a stop the world pause into an RC system through cycle detection if desired.
  • viktorcode 4y ago
    > he also dismisses GC as inherently flawed It's a compromise, on memory consumption and performance. Modern GCs are minimising the impact of those factors, but they still remain a part of the design. RC is a performance compromise.
  • Waterluvian 4y ago
    I’m out of my league so this may be dumb, but does any language or VM or whatnot have a combined system where each thread has its own heap, and you can talk by passing messages, but they also have a common heap for larger data that’s too expensive to pass around, but at the cost that you have to be much more careful with lifetimes or have to manage it manually or something?
    • jefftk 4y ago
      If you squint at it right you could say C works that way: you have many processes each with their own heap and they can pass messages, but if they want larger data that's too expensive to pass around you can use shared memory.
      • kaba0 4y ago
        That’s just IPC, nothing inherent to C.
        • 4y ago
• School-Cotton 4y ago
  Case 3.: You don’t “want” the constraints of Case 2, but are in practice forced into them due to a huge, poorly-educated developer base being incapable of writing correct refcounted code or even knowing what a weak pointer is. When I worked at Facebook, which is structurally and politically incapable of building high-quality client software, I was on a small team of people tasked with making heroic technical fixes to keep the iOS app running despite literally hundreds of engineers working on the same binary incentivized to dump shoddy code to launch their product features that nobody would use as fast as possible (did you know that at one point you could order food through the Facebook app, and that a whole two digit number of people per day used this feature? Etc.) Objective-C has ARC (automated reference counting) — every pointer is a refcounted strong reference by default unless special annotations are used. What makes it worse is that large, deep hierarchies are common, making reference cycles leaking huge amounts of memory easy to create. For example, the view controller for a large and complicated page (referencing decoded bitmap images and other large objects) is the root of a large tree of sub-objects, some of whom want to keep a reference to the root. Now imagine the user navigates away and the reference to the view controller goes away, but nothing in the tree is deallocated due to the backlink — congratulations, you just leaked 10 MB of RAM! It’s possible to do this correctly if you actually read the docs and understand what you’re doing, using tools like weak pointers, but when you have hundreds of developers, many of whom got their job either by transferring from an android team or by just memorizing pat answers to all the “Ninja” algorithms interview questions (practically all of which have leaked on Leetcode and various forums), you can be sure that enough of them will fail to do so to create major issues with OOMs. To mitigate this, we created a “retain cycle detector” — basically a rudimentary tracing GC — that periodically traced the heap to detect these issues at runtime and phone home with a stack trace, which we would then automatically (based on git blame) triage to the offending team. It was totally egregious undefined behavior, one thread tracing the heap with no synchronization with respect to the application threads that were mutating it, but the segfaults this UB caused were so much rarer than the crashes due to OOMs that it prevented that we decided to continue running it.
  • viktorcode 4y ago
    > It’s possible to do this correctly if you actually read the docs and understand what you’re doing, using tools like weak pointers, but when you have hundreds of developers, many of whom got their job either by transferring from an android team or by just memorizing pat answers to all the “Ninja” algorithms interview questions (practically all of which have leaked on Leetcode and various forums), you can be sure that enough of them will fail to do so to create major issues with OOMs. This pretty much nails down what I imagine is the main difference between GC and ARC: with the former you sacrifice performance for ease of use, and with the latter you improve performance by placing some additional work on the programmers.
• samsquire 4y ago
  My understanding of Python's Global Interpreter Lock is that reference counting cannot be done efficiently between threads, so we cannot remove the GIL with reference counting Java's GC is concurrent and runs at safe points and stops the world so it avoids this problem.
• omginternets 4y ago
  Whenever I read someting like this, I wonder what kind of programming the author is doing. I’m getting a strong whiff of embedded and/or real-time systems.
• _8j50 4y ago
  Pardon the ignorance but I thought refcount was a GC strategy?
  • viktorcode 4y ago
    The academia tends to call RC a form of GC. For programmers experienced in languages with manual memory management those are very different beasts.
• ridiculous_fish 4y ago
  There's a lot of discussion of comparative performance, but most software isn't performance sensitive so it just doesn't matter. But there's another major facet: FFIs. The choice of memory management has huge implications for how you structure your FFI. JavaScriptCore uses a conservative GC: the C stack is scanned, and any word which points at a heap object will act as a root. v8 is different, it uses a moving collector: references to heap objects are held behind a double-redirection so the GC may move them. Both collectors are highly tuned and extremely fast, but their FFIs look very different because of their choice of memory management. Read and write barriers also come into play. If your GC strategy requires that reads/writes go through a barrier, then this affects your FFI. This is part of what sunk Apple's ObjC GC effort: there was just a lot of C/C++ code which manipulated references which was subtly broken under GC; the "rules" for the FFI became overbearing. Java's JNI also illustrates this. See the restrictions around e.g. GetPrimitiveArrayCritical. It's hard to know if you're doing the right thing, especially bugs may only manifest if the GC runs which it might not in your test. One of the under-appreciated virtues of RC is the interoperability ease. I know std::sort only rearranges, doesn't add or remove references, so I can just call it. But if my host language has a GC then std::sort may mess up the card marking and cause a live object to be prematurely collected; but it's hard to know for sure!
  • chubot 4y ago
    I agree that the API and interop with C/C++ is a huge issue and something I haven't seen good articles on. But I was sort of put off from reference counting by working with Python extensions that leaked memory many years ago. It's so easy to forget a ref count operation. I don't have data, but I suspect it happens a lot in practice. With tracing, you have to annotate stack roots (and global roots if you have them). To me that seems less error prone. You can overapproximate them and it doesn't really change much. Moving is indeed a big pain, and I'm about to back out of it for Oil :-/ ---- edit: I don't have any experience with Objective C, but I also think this comment is unsurprising, and honestly I would probably get it wrong too: https://news.ycombinator.com/item?id=32283641 https://news.ycombinator.com/item?id=32283641 I feel like ref counting is more "littered all over your code" than GC is, which means there's more opportunity to get it wrong.
  • 4y ago
• deleted 4y ago
  [deleted]
• danybittel 4y ago
  He fails to mention that Apple added support for ref counting in silicon. And.. often GC will be able to use area allocators, before falling back to "proper" GC allocation. Which will be a lot faster than ref counting everything. And atomics can get very slow, I've had atmics show up regularly in the profiler. For my project, the combination that works great so far: unbox all types, use area allocators if the compiler can guarantee the value doesn't escape, use GC for data that changes often and ref counting for data that hardly ever changes. (luckily cycles are not possible)
• dgan 4y ago
  >> "The Python case is more inarguable. If GC is so good, why wouldn't Python just garbage collect everything,... ? It is because RC outperforms garbage collecting in all these standard cases" Pretty weird argument for one of the slowest languages out there ...
• pjmlp 4y ago
  Another RC advocate that misses the point about RC being a GC algorithm from CS point of view. https://gchandbook.org/ https://gchandbook.org/
• bjourne 4y ago
  Time to tout my own horn. I made a project comparing different types of garbage collectors (I still prefer the original terminology; both ref-counting and tracing garbage collection collects garbage, so they are both garbage collectors) a few years ago: https://github.com/bjourne/c-examples https://github.com/bjourne/c-examples Run ./waf configure build && ./build/tests/collectors/collectors and it will spit out benchmark results. On my machine (Phenom II X6 1090), they are as follows: Copying Collector 8.9 Reference Counting Collector 21.9 Cycle-collecting Reference Counting Collector 28.7 Mark & Sweep Collector 10.1 Mark & Sweep (separate mark bits) Collector 9.6 Optimized Copying Collector 9.0 I.e for total runtime it is not even close; tracing gc smokes ref-counting out of the water. Other metrics such as number of pauses and maximum pause times may still tip the balance in favor of ref-counting, but those are much harder to measure. Though note the abysmal runtime of the cycle-collecting ref-counter. It suggests that cycle collection could introduce the exact same pause times ref-counting was supposed to eliminate. This is because in practice cycles are very difficult to track and collect efficiently. In any case, it clearly is about trade-offs; claiming tracing gc always beats ref-counting gc or vice versa is naive.
  • staticassertion 4y ago
    This is cool, thank you. Note that my comments are those of a layman, I don't consider myself an expert on these topics, but this gave me some thoughts. Happy to learn more, would love links to blogs/ papers where I can read more. I would not be surprised to find that even a naive mark and sweep collector is faster than naive refcounting on some workloads. One obvious thing to consider is that the work is delayed, you can perform the sweeping 'as needed'. Even the marking doesn't have to run on any deterministic schedule. The thing is that, from my naive perspective, run of the mill tracing collector algorithms are just way more advanced than your typical refcount. Most refcounting is just that - either an integer, atomic integer, or both, that gets incremented and decremented based on a number of operations applied to the underlying type. The naive approach has no delays. Tracing GCs on the other hand, although perhaps not naive ones (could you link me info on the quickfit algorithm? I can not find anything online), might contain epochs that bump allocate in the majority of cases. That'll be particularly nice for benchmarks where allocations are likely very short lived and may actually never need to get to the mark/sweep phase. Your algorithm isn't really documented and I just really don't feel like looking at C right now. Although naive refcounting is very common it's not the only game in town. Depending on the language you can group refcounts together - for example, imagine you have: (assuming all fields are automatically refcounted) struct Foo { bar: Bar, baz: Baz, } In theory, a "copy" of this type would involve 3 increments, possibly atomic increments. Each increment would also require a heap pointer dereference, and there would be no locality of those integers behind the pointers. That would be the trivial implementation. But depending on the language you could actually flatten all of those down to 1 RC. This is language dependent, and it requires understanding how these values can be moved, referenced, etc, at compile time. You could also store all reference counts in tables associated with structures, such that you have locality when you want to read/write to multiple counters. The pointer dereference is going to be brutal so having locality there will be a nice win. I'd be curious to run your benchmarks through valgrind to see how much the refcount is just spending time on memory fetches that get invalidated in the cache immediately. Anyway, an example of a pretty slick refcounting GC is what Pony built: https://tutorial.ponylang.io/appendices/garbage-collection.html https://tutorial.ponylang.io/appendices/garbage-collection.h... https://www.ponylang.io/media/papers/OGC.pdf https://www.ponylang.io/media/papers/OGC.pdf Pony has different types for: 1. Local, Immutable 2. Local, Mutable 3. Shared, Immutable 4. Shared, Mutable You can read the paper where they discuss how they track local variables vs shared variables, the implementation of counter tables, etc. So I guess to summarize: 1. The results make sense, or as much sense as anything. I'd be interested in more details on the algorithms involved and your benchmark methodology. 2. "Naive" tracing GCs are actually pretty advanced, and advanced refcount implementations are pretty scarce.
• samatman 4y ago
  Definitely use reference counting, it's better! Now you're avoiding cyclic data structures and it sucks, so maybe just for a few objects we'll put them on a linked list, maybe mark them, definitely sweep from time to time to see if anything is unreachable. I'm told there's an algorithm by Boehm. Well, ok, let's go whole hog, we're collecting garbage again, and it sucks, we get all these baby objects, let's try and optimize the GC: we can keep, I dunno, a count of references to new objects, do some allocation sinking to see if we can avoid making them, put the babies in an orphanage, hey look, RC is GC, QED.
• benibela 4y ago
  An advantage of RC is that you can also use it to verify ownership. When the counter is 1, you can do anything with the object without affecting any other references. Like the object could be mutable for a counter=1, and copy-on-write otherwise. Then you can make a (lazy) deep copy by just increasing the counter.
• pizlonator 4y ago
  Atomic inc/dec is hella expensive relative to not doing it. It’s true that CPUs optimize it, but not enough to make it free. RC as a replacement for GC means doing a lot more of this expensive operation - which the GC will do basically zero of in steady state - so this means RC just costs more. Like 2x slowdown more. The atomic inc/dec also have some nasty effects on parallel code. The cpu ends up thinking you mutated lines you didn’t mean to mutate. So, GC is usually faster. RC has other benefits (more predictable behavior and timing, uses less memory, plays nicer with OS APIs).
  • manuelabeledo 4y ago
    > So, GC is usually faster. GC is way faster if there is little collection. In memory or cache intensive applications, garbage collection as a whole can be significantly slower.
    • pizlonator 4y ago
      GC is faster even if you collect a lot. GCs create better cache locality especially for recently allocated objects, and their cache behavior is not generally worse than malloc (but there are many GCs and many mallocs and some try harder than others to make caches happy). The total time spent in GC across a program’s execution time is usually around 30% or so. Maybe more in some cases (some crazy Java workloads can go higher) or less in others (JavaScript since the mutator is slow), but 30% is a good rule of thumb. That includes the barriers, and total cost of all allocations, including the cost of running the GC itself. Reference counting applied as a solution to memory safety, as a replacement for GC, is going to cost you 2x overhead just for the ref counting operations and then some more on top of that for the actual malloc/free. When you throw in the fact that GCs always beats malloc/free in object churn workloads, it’s likely that the total overhead of counting refs, calling free(), and using a malloc() that isn’t a GC malloc is higher than 2x, I.e. more than 50% of time spent in memory management operations (inc, dec, malloc, free). It’s a trade off, though. The GC achieves that 30% because it uses more memory. All of the work of understanding the object graph is amortized into a graph search that happens infrequently, leading to many algorithmic benefits (like no atomic inc/dec, faster allocation fast path, freeing is freeish, etc), but also causing free memory to be reused with a delay, leading to 2x or more memory overhead. That also implies that if you ask the GC to run with lower memory overhead, it’ll use more than 30% of your execution time. It’s true that if you want the memory usage properties of RC, and you try to tune your GC to get you there, you gonna have a slow GC. But that’s not how most GC users run their GCs.
• UltraViolence 4y ago
  Reference counting forces the developer to think about memory management. Apple has a nice talk on ARC [1] but it got me thinking: if I have to think about reference counting this much I might just as well manage memory all by myself. The true joy of Garbage Collection is that you can just create objects left and right and let the computer figure out when to clean them up. It's a much more natural way of doing things and lets computers do what they're best at: taking tedious tasks out of the hands of humans. [1]: https://developer.apple.com/videos/play/wwdc2021/10216/ https://developer.apple.com/videos/play/wwdc2021/10216/