5 ms·

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 wheth

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.
  - arc776 10y ago
    What's the difference been naive RC and non-naive? Would the above languages (Erlang, Dart and Nim) count as naive implementations? I was under the impression Nim, at least, had pretty efficient RC implementation that performed favourably compared with a Boehm GC when considering single threaded performance. Is this accurate?
    - rbehrends 10y ago
      By naive I refer to RC implementations that simply instrument pointer assignments with the necessary reference counting instructions. Non-naive RC implementations try to minimize the overhead associated with it; deferred reference counting or having the compiler optimize away unnecessary reference count updates are typical approaches. Erlang and Dart have tracing GCs; I was referring to their concurrency model (which uses thread-local heaps), not their method of garbage collection. Nim uses either deferred reference counting or a simple mark-and-sweep collector, depending on a compile time switch, but also uses thread-local heaps. The main attraction of Nim's deferred RC collector is that it can keep pause times very low; I haven't actually benchmarked its amortized performance, but I expect it should be competitive with or better than the Boehm GC, especially for large heaps.
      - arc776 10y ago
        Thanks for your answer. "Garbage collection" seems to cover a huge range of actual implementation approaches and sometimes it's hard to see the pros and cons of each approach when they're all lumped under the same thing. In my mind, 'stop the world' pauses are the biggest disadvantage of some GC approaches, so it's nice to hear that deferred RC ameliorates that to some extent.
fauigerzigerk 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 True, but I think these comparisons are often done under the assumption that memory utilisation remains fairly low. Tracing GCs react very badly to growing memory utilisation in my experience. This is of course ultimately an economic question and maybe it should be modelled that way.
IshKebab 10y ago
What about how reference counting is done in languages like C++ and Rust? I.e. you explicitly make a value reference-counted, usually for large values (an entire class for example). Small values like ints are copied. That seems like the best approach to me. Plus you can use RAII which is a far bigger advantage than any minor speed differences.
- pjmlp 10y ago
  RAII is also possible in GC languages, just done differently. If the language supports macros or trailing closures, you can somehow have similar approaches to RAII handle classes. with-database { // connection is only accessible here } // connection is now closed and gone with-file { // file is only accessible here } // file is now closed with-mutex { // mutex guarded resource is now visible here } // mutex is now released, regardless of possible errors with-native-memory { // able to use an OS memory block } // OS got the memory back
iofj 10y ago
I submit this is only true for equivalent number of things to keep track of. In practice this is not the case. Languages with GC go completely overboard with GC, using it completely everywhere, even when not strictly necessary and certainly java does. In C++, if you have a map with items, you use move semantics and you have have either 0 or 1 refcounts to keep track of, the one for the map itself. The rest is still "refcounted" but without ever touching any integer, by the normal scoping rules. Same goes for Rust code. That's ignoring the fact that a Java object is, at minimum, 11 bytes larger than a C++ object. Given java's boxing rules and string encoding, the difference in object sizes becomes bigger with bigger objects. Because out-of-stackframe RTTI is a basic necessity of tracing garbage collectors this is unavoidable, and cannot be fixed in another language. Bigger object sizes also mean more memory needed, more memory bandwidth needed, ... And Java's constant safety checks also mean In Java, the same map will give the GC 3 items to keep track of (minimum) per entry in the map, plus half a dozen for the map itself. One for the object that keeps the key and the value, one of the key and one for the value. That's assuming both key and value are boxed primitives, not actual java objects. In that case, it'll be more. Now you might argue that it'll therefore depend on a case by case basis. And while that is technically correct, any real program will in fact have a number of maps, and vectors, and ... and C++ smart pointers will wipe the floor with their java tracing equivalent (but will be significantly less correct, or perhaps expressed better it will take a far better programmer to get the C++ code right memory-use wise than for Java). An additional comment should be made that the Java JVM's garbage collector is the result of 21 years of development by very, very good programmers. It is not able to beat C++'s smart pointers in most cases, mostly due to it's VM overhead. If you are not able to beat a department of senior Sun/Oracle programmers you cannot beat their GC's performance without doctoring benchmarks. Therefore the chances of any new GC'ed language beating the performance of C++ smart pointers any time soon (by which I mean decades) seems negligible. In practice it is considered very good performance for any non-C++ language to be about half as fast as C++ when it comes to memory allocation and deallocation.
- vardump 10y ago
  Sounds like you're conflating GC with Java's limited type/value system. > That's ignoring the fact that a Java object is, at minimum, 11 bytes larger than a C++ object. In C++ minimum object size is 0 bytes. No virtual methods and no member variables. > In Java, the same map will give the GC 3 items to keep track of (minimum) per entry in the map, plus half a dozen for the map itself. One for the object that keeps the key and the value, one of the key and one for the value. This is because of lack of value types in Java, nothing to do with GC. Think of how horrible C/C++ would be if you had only primitive types (char, int, double, etc.), and pointers to objects or primitive arrays. > That's assuming both key and value are boxed primitives, not actual java objects. In that case, it'll be more. Boxed primitives are actual Java objects. > "and C++ smart pointers will wipe the floor with their java tracing equivalent" No, C++ "smart pointers" (are you talking about std::shared_ptr?) will definitely be slower in amortized runtime costs. High cost of std::shared_ptr is one reason why std::unique_ptr exists. Disclaimer: C++, not a Java programmer.

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.
- arc776 10y ago
  What's the difference been naive RC and non-naive? Would the above languages (Erlang, Dart and Nim) count as naive implementations? I was under the impression Nim, at least, had pretty efficient RC implementation that performed favourably compared with a Boehm GC when considering single threaded performance. Is this accurate?
  - rbehrends 10y ago
    By naive I refer to RC implementations that simply instrument pointer assignments with the necessary reference counting instructions. Non-naive RC implementations try to minimize the overhead associated with it; deferred reference counting or having the compiler optimize away unnecessary reference count updates are typical approaches. Erlang and Dart have tracing GCs; I was referring to their concurrency model (which uses thread-local heaps), not their method of garbage collection. Nim uses either deferred reference counting or a simple mark-and-sweep collector, depending on a compile time switch, but also uses thread-local heaps. The main attraction of Nim's deferred RC collector is that it can keep pause times very low; I haven't actually benchmarked its amortized performance, but I expect it should be competitive with or better than the Boehm GC, especially for large heaps.
    - arc776 10y ago
      Thanks for your answer. "Garbage collection" seems to cover a huge range of actual implementation approaches and sometimes it's hard to see the pros and cons of each approach when they're all lumped under the same thing. In my mind, 'stop the world' pauses are the biggest disadvantage of some GC approaches, so it's nice to hear that deferred RC ameliorates that to some extent.

fauigerzigerk 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 True, but I think these comparisons are often done under the assumption that memory utilisation remains fairly low. Tracing GCs react very badly to growing memory utilisation in my experience. This is of course ultimately an economic question and maybe it should be modelled that way.

IshKebab 10y ago

What about how reference counting is done in languages like C++ and Rust? I.e. you explicitly make a value reference-counted, usually for large values (an entire class for example). Small values like ints are copied. That seems like the best approach to me. Plus you can use RAII which is a far bigger advantage than any minor speed differences.

pjmlp 10y ago
RAII is also possible in GC languages, just done differently. If the language supports macros or trailing closures, you can somehow have similar approaches to RAII handle classes. with-database { // connection is only accessible here } // connection is now closed and gone with-file { // file is only accessible here } // file is now closed with-mutex { // mutex guarded resource is now visible here } // mutex is now released, regardless of possible errors with-native-memory { // able to use an OS memory block } // OS got the memory back

iofj 10y ago

I submit this is only true for equivalent number of things to keep track of. In practice this is not the case. Languages with GC go completely overboard with GC, using it completely everywhere, even when not strictly necessary and certainly java does. In C++, if you have a map with items, you use move semantics and you have have either 0 or 1 refcounts to keep track of, the one for the map itself. The rest is still "refcounted" but without ever touching any integer, by the normal scoping rules. Same goes for Rust code. That's ignoring the fact that a Java object is, at minimum, 11 bytes larger than a C++ object. Given java's boxing rules and string encoding, the difference in object sizes becomes bigger with bigger objects. Because out-of-stackframe RTTI is a basic necessity of tracing garbage collectors this is unavoidable, and cannot be fixed in another language. Bigger object sizes also mean more memory needed, more memory bandwidth needed, ... And Java's constant safety checks also mean In Java, the same map will give the GC 3 items to keep track of (minimum) per entry in the map, plus half a dozen for the map itself. One for the object that keeps the key and the value, one of the key and one for the value. That's assuming both key and value are boxed primitives, not actual java objects. In that case, it'll be more. Now you might argue that it'll therefore depend on a case by case basis. And while that is technically correct, any real program will in fact have a number of maps, and vectors, and ... and C++ smart pointers will wipe the floor with their java tracing equivalent (but will be significantly less correct, or perhaps expressed better it will take a far better programmer to get the C++ code right memory-use wise than for Java). An additional comment should be made that the Java JVM's garbage collector is the result of 21 years of development by very, very good programmers. It is not able to beat C++'s smart pointers in most cases, mostly due to it's VM overhead. If you are not able to beat a department of senior Sun/Oracle programmers you cannot beat their GC's performance without doctoring benchmarks. Therefore the chances of any new GC'ed language beating the performance of C++ smart pointers any time soon (by which I mean decades) seems negligible. In practice it is considered very good performance for any non-C++ language to be about half as fast as C++ when it comes to memory allocation and deallocation.

vardump 10y ago
Sounds like you're conflating GC with Java's limited type/value system. > That's ignoring the fact that a Java object is, at minimum, 11 bytes larger than a C++ object. In C++ minimum object size is 0 bytes. No virtual methods and no member variables. > In Java, the same map will give the GC 3 items to keep track of (minimum) per entry in the map, plus half a dozen for the map itself. One for the object that keeps the key and the value, one of the key and one for the value. This is because of lack of value types in Java, nothing to do with GC. Think of how horrible C/C++ would be if you had only primitive types (char, int, double, etc.), and pointers to objects or primitive arrays. > That's assuming both key and value are boxed primitives, not actual java objects. In that case, it'll be more. Boxed primitives are actual Java objects. > "and C++ smart pointers will wipe the floor with their java tracing equivalent" No, C++ "smart pointers" (are you talking about std::shared_ptr?) will definitely be slower in amortized runtime costs. High cost of std::shared_ptr is one reason why std::unique_ptr exists. Disclaimer: C++, not a Java programmer.