7 ms·

Is reference counting slower than GC?

• oelang 10y ago
  All talk & no benchmarks. If reference counting with cycle detection was faster, the jvm & clr would use it.
  • mortoray 10y ago
    In my conclusion I mention why there are no benchmarks, it's nearly impossible to construct a realistic comparison between the two techniques. When I cosnider tracing GC my primary arguments against it have nothing to do with performance at all, yet it often comes up as an argument against my position. This article is attempting to address that critique, by saying I doubt you could compare the two directly.
    • tom_mellior 10y ago
      > In my conclusion I mention why there are no benchmarks, it's nearly impossible to construct a realistic comparison between the two techniques. You "mention" this as if it were fact, yes. Apparently you are not aware of realistic comparisons that do exist, such as http://www.cs.utexas.edu/users/mckinley/papers/mmtk-sigmetrics-2004.pdf http://www.cs.utexas.edu/users/mckinley/papers/mmtk-sigmetri... (Alternatively, the article needs a discussion of why you think this is not a "realistic comparison".)
    • oelang 10y ago
      The evidence is that all high performance garbage collected languages use some form of generational collectors. These implementations aren't made by idiots. for a deeper discussion see: https://www.infoq.com/presentations/java-vs-c-performance https://www.infoq.com/presentations/java-vs-c-performance
• vardump 10y ago
  Reference counting is fast with one CPU core. But it gets worse and worse as you add cores. Inter-CPU synchronization is slow and the buses can saturate. With enough cores, at some point that'll be all the system is doing. As far as I know, reference counting also requires you to have a heap with "alloc" and "free". Memory allocation is a slow operation, because it involves searching for the best matching free span to avoid heap fragmentation. On the other hand, GC can scale across any number of CPU cores.
  • sklogic 10y ago
    Reference counting is never fast. Even on a single core.
    • chipsy 10y ago
      Don't describe it as "fast". Use "latency" or "throughput". RC is a useful building block for making real-time latency guarantees, and for many apps that is more important than peak throughput.
      • sklogic 10y ago
        It is really hard to get real time guarantees with RC - given that time for cleaning up depends on a size of a structure. Just imagine it freeing a 10Gb linked list. Real time pure mark and sweep GCs are easier.
        • NickPollard 10y ago
          You don't have to clean up everything at once - it's possible to put items on a queue to be cleaned up when refcounts hit zero, and you can then control at what rate the queue is emptied.
          • sklogic 10y ago
            Which makes it already far too complicated, more complex than a real time mark&sweep. Especially if there are loop checks - you cannot just empty the queue gradually, it's all or nothing.
  • gpderetta 10y ago
    That's not how cpu synchronization work. Reference count updates by themselves are purely CPU local even when atomic. Cross CPU synchronization happens only if an object is actually shared. It is true that, if an object is actually shared, reference counting would 'upgrade' a read only sharing to writable which is expensive; there are ways around that though, look for differential reference counting. Re alloc and free, that's completely orthogonal with refcounting.
• sklogic 10y ago
  What? Of course reference counting is slower. Especially if you take loop handling into account. Imagine a degenerate scenario: using up all of your memory to allocate a single linked list, and then dropping it all at once. Another, much more common scenario: allocating huge numbers of very short living objects. A generational GC handles this with nearly zero overhead, while reference counting plus a heap allocation sucks on an epic scale. Also, do not forget about the compactification and cache locality implications.
  • jules 10y ago
    Tracing GC is not always faster. GC time is proportional to the size of the allocated memory, reference counting time is not.
    • sklogic 10y ago
      Why do you even care about the GC epoch length? It does not affect the mutator performance at all. EDIT: actually, it does a bit: the longer the epoch, the better, because at the end of the epoch a short stop-the-world is required to collect the global roots from registers and stacks.
      • jules 10y ago
        It doesn't affect mutator performance, until it does, and your program grinds to a halt for several seconds.
        • sklogic 10y ago
          > until it does How exactly? > grinds to a halt for several seconds What? Stop-the-world in the realtime collectors is always for a set duration, only to scan the registers and tops of the stacks (if there are any stacks at all, stackless implementations have even a better latency).
          • jules 10y ago
• barrkel 10y ago
  This isn't an informed article. Reference counting is a type of garbage collection. It's not complete without collecting cycles, but it can form part of a GC mix. Assigning pointers in a scanning GC can have a cost; for example, generational GCs need to track writes to old generations that point to newer generation objects. There's no discussion of thread safety and how that affects reference counting. That's probably the biggest problem; you need to use memory barriers to make reference counting safe with multiple threads, and that can kill performance.
  • vardump 10y ago
    You don't necessarily need memory barriers (implementation detail). All you need is an atomic fetch-and-add (like x86 XADD opcode). Many architectures provide that as a primitive. On those that don't, you have to compose it out of other atomic primitives.
    • xxs 10y ago
      Atomic part has to notify the rest of caches to invalidate the cache line. Local latency in the best case.
      • gpderetta 10y ago
        FYI, any store has to invalidate remote cachelines, that's taken care by the coherence protocol even before the store is actually performed. Memory barrier (and atomic operations) don't have anything to do with it.
        • JoachimSchipper 10y ago
          Whether stores invalidate remote cachelines depends entirely on the architecture. But yes, Intel has fairly strong coherency.
          • gpderetta 10y ago
            It seems to me that any cache coherent system needs to do that. If multiple writers can be updating a cacheline a the same time [1] you can't talk of coherency at all. Intel is stronger as it guarantees a total ordering of modifications across all cachelines, but any coherent system will guarantee the ordering of modification of a single cacheline. [1] visibly at least. HTM complicates things a bit of course.
• nwalfield 10y ago
  The author unfortunately doesn't understand how GC works: > GC’s overhead relates to the total memory allocated, not just > the memory actively used in the code. Each new allocation > results in an increased time per scanning cycle. Certainly > there are many optimizations involved in a good GC to limit > this, but the fundamental relationship is still linear. As a > program uses more memory the overhead of it’s GC increases. A GC's overhead (at least a mark and sweep collector) is proportional to the number of live objects. This is because all of the dead objects are unreachable and thus aren't scanned.
  • dfox 10y ago
    Plain mark and sweep has to touch all currently allocated objects, it's obvious, it either has to mark the object or deallocate the object in the sweep phase. On the other hand two-space copying GC only touches live objects.
  • mortoray 10y ago
    I'm not sure how this disputes what I say about a scanning garbage collector. The number of live objects is proportional to the amount of total memory allocated. I don't consider dead objects, where the memory is not longer used and free to be allocated, to be part of the allocated memory.
    • lmm 10y ago
      That's a confusing choice of terminology. "allocated" reads like the past-tense of "allocate"; it's natural to think "allocated" means "was allocated at some point in the past". Maybe it is correct in some technical sense, but for the casual reader "live" would be a lot clearer.
    • titzer 10y ago
      > The number of live objects is proportional to the amount of total memory allocated. No, that's not right. The number (or ratio) of live objects depends on application behavior. According to the weak generational hypothesis, most objects die young, so a garbage collector that only touches live objects (e.g. tracing) does no work at all for the most objects. The actual survival rate is complex and depends on application behavior, but typical well-tuned GC systems often see survival rates from young generation collections around 10%--that means that only 10% of objects ever occur any GC overhead. Those 90% of quickly dying objects do, however, take up memory and cache space until they are reclaimed. IMO that is only remaining situation where manual memory management can outperform GC by wide margins: when a program can carefully reuse recently allocated memory to keep reusing the same cache lines.
• albeva 10y ago
  There are other differences to consider: such as deterministic destruction with reference counting.
• rbehrends 10y ago
  It is well-known that the amortized cost of naive reference counting is considerably higher than that of a modern tracing garbage collector (regardless of whether you also support cycle collection). It is also well-known that non-naive RC-based approaches generally make it easier to achieve lower pause times (though cycle collection may throw a spanner in the works). Attempts to bring amortized RC performance up to par with tracing GCs [1] generally require an underlying machinery that is just as complicated as that of a tracing GC; you will typically rely on stack scanning to implement deferred reference counting or non-trivial compiler optimizations with the goal to eliminate or reduce the overhead of local pointer assignments and you may still be left with a more expensive write barrier, so you may also have to gun for a hybrid approach. Advantages of naive RC are that it is easier to add to an existing language without extensive compiler/runtime support (assuming you don't need cycle detection) and that it can more easily coexist with other approaches to memory management; amortized cost is not one of them. [1] Such as https://www.cs.purdue.edu/homes/hosking/690M/urc-oopsla-2003.pdf https://www.cs.purdue.edu/homes/hosking/690M/urc-oopsla-2003...
  • mortoray 10y ago
    In my quest for a memory management scheme on Leaf it's your final point which is primarily forcing my decision: the compatibility with other memory managers. In this article I just wish to provide counterpoint to those people trying to convince me that tracing GC is a better approach. In the end, it's the need to right libraries and be compatible that prevents me from using a complex GC.
    • rbehrends 10y ago
      Just keep in mind the trade-offs that you are making. For starters, you are adding a considerable performance overhead to local pointer assignments; you're replacing a register-register move (and one that can be optimized away in many situations by a modern compiler through register renaming, turning it into a no-op) with a register-register move plus two memory updates plus a branch. Even where you have cache hits and the branch can be predicted correctly almost always, you're dealing with cache and BTB pollution; these effects may not fully show up in micro-benchmarks, but only completely manifest in large programs. Second, adding concurrency to the mix can complicate matters a lot (depending on your concurrency model [1]). You may need additional atomicity guarantees for the reference count updates – which, while cheaper than a full-blown lock, is generally still more expensive than the purely sequential case; you preclude compiler optimizations that can eliminate the overhead of pointer updates; and you're still lift with the potential for race conditions (e.g. when one thread writes to a global variable or heap location while another thread is retrieving a pointer from the same location, and that pointer is the only remaining reference to an object). Third, typical approaches to cycle detection and collection (such as trial deletion) reintroduce most of the challenges of tracing GC. While you may think that you can avoid cycles or handle them manually, they often crop up in unexpected places. A common case is when a closure is stored in an object that is also captured in the closure's environment [2]. I don't mean to discourage you from your decision – I don't know what your ultimate goals are and naive RC may very well be the best set of trade-offs you can make – I just want to alert you to possible trade-offs that you are making. [1] Some popular concurrency models (such as Erlang's, Dart's, or Nim's) avoid shared references, so these issues would not even crop up for such languages, of course. [2] I have a hypothesis that naive RC as an approach to memory management is particularly common in languages that do not (or historically, did not) support closures, but that's a different story.
• majke 10y ago
  Years pass but I still prefer languages with reference counting over languages with proper GC. Main reasons for me: - Reference counting is deterministic (barring refcnt loops, which can usually be avoided by a careful programmer). Each run of the program will allocate/free memory in _exactly_ the same way. - No latency spikes. "When GC kicks in, the latency must raise" - This means it's way easier to understand the performance characteristics of code. Having that in mind, there are couple of problems with refcnt: - Cache spill. Increasing/decreasing a counter values in random places in memory kills cache. I remember one time I separated the "string object" data structure in python away from the immutable (!) string value (python has usually C struct object followed in memory by value blob). The python program suddenly went _way_ faster - immutable (readonly) string values in memory were close to each other, mutated refcnts were close to another. Everyone was happier - When dealing with large data (binary blobs), refcnt programming languages have a tendency to copy over needed data. Copying over is in many cases slower. In general I'd say it's the last point that is critical. The big question is less of "refcnt" vs "gc", but how to deal with binary blobs. "Copy over" pattern (C style) and newer version: "slices" (golang style) VS "proper GC" style of trying to guess how may pointers point to a blob.
  • mortoray 10y ago
    Those are some of the points I'm considering as well when doing the memory management for Leaf. My desire to have predictable destructors is tough to reconcile in a tracing GC. I'm uncertain of what you mean with "copying the data over" in reference to large data. Surely it's still just the pointer being copied? Or are you speaking of things like `std::vector` in C++ that are value-copied by default?
  • norswap 10y ago
    I tend to agree but don't overlook the downside of rfcnt loops. It's quite easy to introduce them (for instance, when creating closures in Objective-C), hence negating the big selling point of gc in the first place.
  • david-given 10y ago
    Regarding latency spikes: that's not entirely true. If you drop the last reference to an object, then freeing that object can cause the last reference to other objects to be dropped, etc. So it's possible that dropping a reference can cause a large amount of work, which if it happens during a critical path can cause a latency spike. Particularly if finalisers are involved. If your object ownership graph is straightforward this isn't a problem, but if you have large objects with shared ownership it's very easy to be surprised here. (Used to work on a object-oriented operating system which used reference counting everywhere, and I discovered this the hard way.) I don't follow your comment about binary blobs?
• vardump 10y ago
  I wish people would realize they're just some of the different tools in the memory/resource management toolbox. Neither is the best option in every case. We should just use whatever fits better for the purpose.