7 ms·

Yeah, further down in the article they track down the gap between cpp and Go/Java to the ref-counting deallocation work. I'm not a cpp expert, but it seems surp

Yeah, further down in the article they track down the gap between cpp and Go/Java to the ref-counting deallocation work. I'm not a cpp expert, but it seems surprising to me that GC would beat ref-counting in any scenario.

def-lkb 6y ago
That might seem counter-intuitive, but tracing GC is the fastest way to manage memory in general (arbitrary life time, graph shapes and allocation patterns). It permits really fast allocation, defragmentation and is sometime the only way to manage memory (cyclic datastructures for which reachability cannot be known directly from program text). Reference-counted GC on the other hand is notoriously slow, incomplete, and exhibit lots of bad performance patterns (that can be somehow managed by taking some elements of tracing GCs). The drawback is that tracing GCs are very hard to implement, to tune, and sometimes not all of the benefits are available at the same time. And because they are so counter intuitive, programmers in general have a hard time understanding their runtime behavior... Even GC experts struggle (the skills required range from low-level hardware to control theory, otherwise performance at scale is unpredictable).
- Rochus 6y ago
  In C/C++ we have the possibility to avoid dynamic allocation altogether and to use system features like memory mapping. If we use C++ the same way as Java (everything dynamically) it's not too surprising the result is not (much) faster than Java.
  - aidenn0 6y ago
    Their original implementation was in common lisp. Common Lisp also lets you use mmap (in fact it's not that uncommon to do so if you have a large amount of mostly static data) to manage your memory manually. They clearly wanted automatic memory management, so the C++ implementation is reasonable. A fairer comparison might have used MPS or boehm instead of refcounting, but I suspect the results would have been similar.
    - Rochus 6y ago
      > Common Lisp also lets you use mmap But not without allocating dynamic memory and copying data. > They clearly wanted automatic memory management Most likely because of some misconceptions. > so the C++ implementation is reasonable. How so? > but I suspect the results would have been similar Don't forget the data sets to be filtered, sorted an analyzed are up to 200 GB.
      - deleted 6y ago
        [deleted]
      - aidenn0 6y ago
        > > Common Lisp also lets you use mmap > But not without allocating dynamic memory and copying data. Sure it does. In SBCL you can force a stack allocation (though rarely does it improve performance), and very short-lived values do not leave registers in any case. > > They clearly wanted automatic memory management > Most likely because of some misconceptions. There are both good and bad reasons to want automatic memory management. At least one good reason it it would decrease the porting effort by keeping the code similar. > > so the C++ implementation is reasonable. > How so? Using reference counting is a reasonable way to get automatic memory management in C++ > > but I suspect the results would have been similar > Don't forget the data sets to be filtered, sorted an analyzed are up to 200 GB. Which is going to be rough on any automatic memory management system, which makes using a language with a better ecosystem of automatic memory management more performant.
        Rochus 6y ago
        Common Lisp: It is permissible for an implementation to simply ignore such declarations. And you still have to copy. Ref counting: only makes sense in a few special cases. Avoiding dynamic memory management: have a look at mmap.
        aidenn0 6y ago
        C++: It is permissible for an implementation to allocate every local variable on the heap. Going back to my original point, you are suggesting a complete rearchitecture of their allocation system. That does not require switching languages to C++. If we are talking about working with 100s of GB of data, that's probably even the correct approach! TFA does not, however, claim that they have a working set of 100s of GB of data. The data is 100s of GB at rest, but can be processed in chunks with a single pass. That, by itself, does not scream "mmap" to me. On top of that, the data is compressed at rest, so copying is inevitable.
antender 6y ago
Refcounting can mess with caches in multithreaded scenarios, so results aren't really surprising to me. It also generates unnecessary work to maintain counters on all writing threads, while concurrent tracing GC batches all its actions on separate thread.
mcguire 6y ago
"With reference counting, objects are recognized as obsolete due to their reference counts dropping to zero. Deallocation of these objects leads to transitive deallocations of other objects because of their reference counts transitively dropping to zero. Since this is an inherently sequential process, this leads to a similar significant pause as with a stop-the-world garbage collector." There are three primary performance penalties for reference counting: 1. This, where dropping one link causes a deallocation chain. 2. A typical heap implementation will leave live objects scattered throughout memory, leading to cache issues. 3. Maintaining the reference counts may cause writes to memory, leading to other cache issues, plus atomicity.
- Rochus 6y ago
  People often forget that memory allocation is very expensive; the C/C++ default allocator is very inefficient.
aidenn0 6y ago
I guess I was wrong with this comment: https://news.ycombinator.com/item?id=22959600 https://news.ycombinator.com/item?id=22959600 1. Reference counting is a form of GC; you could implement a JVM that used reference counting (though in order to be general a small amount of additional work is needed) 2. Reference counting causes extra work every time a reference appears or disappears. Tracing GCs amortize that cost across many allocations. 2.b. This is particularly hurtful to performance for short-lived objects, since most tracing GCs have zero GC overhead for short-lived objects (the cost of a nursery collection under most implementations scales with the amount of live data in the nursery, so objects that appear and disappear in the time-span of a single nursery GC are freed at zero extra cost). Furthermore a tracing GC 3. Malloc cannot move allocated data, so many implementations have a lot of complexity to avoid heap fragmentation, which comes at a cost to both allocating and freeing data. Many GC'd languages allocate small objects with a single instruction in the typical (just incrementing a pointer, the non-typical case would be when the nursery is full and a GC happens). 4. the JVM and Go both have a lot of effort put into their GC; the ref-counting implementation used by this test is probably a bit more naive. In particular they talk about large delays when a chain of links cause many allocations to die at the same time. A less naive refcounting implementation would queue deleted objects and spread that work out across a larger time period.
- nostrademons 6y ago
  They're duals. Seminal paper: https://www.researchgate.net/publication/221321424_A_unified_theory_of_garbage_collection https://www.researchgate.net/publication/221321424_A_unified... Performance characteristics depend where on that continuum your workload falls. For example, Erlang/BEAM uses a generational GC for most common heap objects, but refcounts large binary blobs. This is pretty much a perfect case for refcounting: new references are created infrequently, copying or moving is expensive, destruction is deterministic and happens immediately after the last reference disappears, and there're no pointers within the blob that would require tracing or cycle-detection. Similarly, UI components within a GUI is another good case for refcounting (and presumably why Apple continues to use this for Objective-C and Swift in Cocoa). New references happen only in non-performance-critical code, most data remains live across collections, and copying/moving existing data would a.) be slow and b.) would invalidate any C pointers into contained data. Sounds like the particular problem domain described in this article is one where heap allocations are frequent, which makes generational GCs more appropriate. That's probably the case with the vast majority of computational algorithms, but there are definitely problem domains where refcounting continues to beat GC.

def-lkb 6y ago

That might seem counter-intuitive, but tracing GC is the fastest way to manage memory in general (arbitrary life time, graph shapes and allocation patterns). It permits really fast allocation, defragmentation and is sometime the only way to manage memory (cyclic datastructures for which reachability cannot be known directly from program text). Reference-counted GC on the other hand is notoriously slow, incomplete, and exhibit lots of bad performance patterns (that can be somehow managed by taking some elements of tracing GCs). The drawback is that tracing GCs are very hard to implement, to tune, and sometimes not all of the benefits are available at the same time. And because they are so counter intuitive, programmers in general have a hard time understanding their runtime behavior... Even GC experts struggle (the skills required range from low-level hardware to control theory, otherwise performance at scale is unpredictable).

Rochus 6y ago
In C/C++ we have the possibility to avoid dynamic allocation altogether and to use system features like memory mapping. If we use C++ the same way as Java (everything dynamically) it's not too surprising the result is not (much) faster than Java.
- aidenn0 6y ago
  Their original implementation was in common lisp. Common Lisp also lets you use mmap (in fact it's not that uncommon to do so if you have a large amount of mostly static data) to manage your memory manually. They clearly wanted automatic memory management, so the C++ implementation is reasonable. A fairer comparison might have used MPS or boehm instead of refcounting, but I suspect the results would have been similar.
  - Rochus 6y ago
    > Common Lisp also lets you use mmap But not without allocating dynamic memory and copying data. > They clearly wanted automatic memory management Most likely because of some misconceptions. > so the C++ implementation is reasonable. How so? > but I suspect the results would have been similar Don't forget the data sets to be filtered, sorted an analyzed are up to 200 GB.
    - deleted 6y ago
      [deleted]
    - aidenn0 6y ago
      > > Common Lisp also lets you use mmap > But not without allocating dynamic memory and copying data. Sure it does. In SBCL you can force a stack allocation (though rarely does it improve performance), and very short-lived values do not leave registers in any case. > > They clearly wanted automatic memory management > Most likely because of some misconceptions. There are both good and bad reasons to want automatic memory management. At least one good reason it it would decrease the porting effort by keeping the code similar. > > so the C++ implementation is reasonable. > How so? Using reference counting is a reasonable way to get automatic memory management in C++ > > but I suspect the results would have been similar > Don't forget the data sets to be filtered, sorted an analyzed are up to 200 GB. Which is going to be rough on any automatic memory management system, which makes using a language with a better ecosystem of automatic memory management more performant.
      - Rochus 6y ago
        Common Lisp: It is permissible for an implementation to simply ignore such declarations. And you still have to copy. Ref counting: only makes sense in a few special cases. Avoiding dynamic memory management: have a look at mmap.
        aidenn0 6y ago
        C++: It is permissible for an implementation to allocate every local variable on the heap. Going back to my original point, you are suggesting a complete rearchitecture of their allocation system. That does not require switching languages to C++. If we are talking about working with 100s of GB of data, that's probably even the correct approach! TFA does not, however, claim that they have a working set of 100s of GB of data. The data is 100s of GB at rest, but can be processed in chunks with a single pass. That, by itself, does not scream "mmap" to me. On top of that, the data is compressed at rest, so copying is inevitable.

antender 6y ago

Refcounting can mess with caches in multithreaded scenarios, so results aren't really surprising to me. It also generates unnecessary work to maintain counters on all writing threads, while concurrent tracing GC batches all its actions on separate thread.

mcguire 6y ago

"With reference counting, objects are recognized as obsolete due to their reference counts dropping to zero. Deallocation of these objects leads to transitive deallocations of other objects because of their reference counts transitively dropping to zero. Since this is an inherently sequential process, this leads to a similar significant pause as with a stop-the-world garbage collector." There are three primary performance penalties for reference counting: 1. This, where dropping one link causes a deallocation chain. 2. A typical heap implementation will leave live objects scattered throughout memory, leading to cache issues. 3. Maintaining the reference counts may cause writes to memory, leading to other cache issues, plus atomicity.

Rochus 6y ago
People often forget that memory allocation is very expensive; the C/C++ default allocator is very inefficient.

aidenn0 6y ago

I guess I was wrong with this comment: https://news.ycombinator.com/item?id=22959600 https://news.ycombinator.com/item?id=22959600 1. Reference counting is a form of GC; you could implement a JVM that used reference counting (though in order to be general a small amount of additional work is needed) 2. Reference counting causes extra work every time a reference appears or disappears. Tracing GCs amortize that cost across many allocations. 2.b. This is particularly hurtful to performance for short-lived objects, since most tracing GCs have zero GC overhead for short-lived objects (the cost of a nursery collection under most implementations scales with the amount of live data in the nursery, so objects that appear and disappear in the time-span of a single nursery GC are freed at zero extra cost). Furthermore a tracing GC 3. Malloc cannot move allocated data, so many implementations have a lot of complexity to avoid heap fragmentation, which comes at a cost to both allocating and freeing data. Many GC'd languages allocate small objects with a single instruction in the typical (just incrementing a pointer, the non-typical case would be when the nursery is full and a GC happens). 4. the JVM and Go both have a lot of effort put into their GC; the ref-counting implementation used by this test is probably a bit more naive. In particular they talk about large delays when a chain of links cause many allocations to die at the same time. A less naive refcounting implementation would queue deleted objects and spread that work out across a larger time period.

nostrademons 6y ago
They're duals. Seminal paper: https://www.researchgate.net/publication/221321424_A_unified_theory_of_garbage_collection https://www.researchgate.net/publication/221321424_A_unified... Performance characteristics depend where on that continuum your workload falls. For example, Erlang/BEAM uses a generational GC for most common heap objects, but refcounts large binary blobs. This is pretty much a perfect case for refcounting: new references are created infrequently, copying or moving is expensive, destruction is deterministic and happens immediately after the last reference disappears, and there're no pointers within the blob that would require tracing or cycle-detection. Similarly, UI components within a GUI is another good case for refcounting (and presumably why Apple continues to use this for Objective-C and Swift in Cocoa). New references happen only in non-performance-critical code, most data remains live across collections, and copying/moving existing data would a.) be slow and b.) would invalidate any C pointers into contained data. Sounds like the particular problem domain described in this article is one where heap allocations are frequent, which makes generational GCs more appropriate. That's probably the case with the vast majority of computational algorithms, but there are definitely problem domains where refcounting continues to beat GC.