3 ms·

RAII does not mean a lot of reference counting. In the vast majority of cases in typical programs, objects have exactly one owner, and managing that ownership

by agwa 13y ago

RAII does not mean a lot of reference counting. In the vast majority of cases in typical programs, objects have exactly one owner, and managing that ownership is very easy if your language provides good facilities for move semantics (as C++11 and Rust do). You can't say reference counting is bad for multi-threaded programs without mentioning that GC is also bad for multi-threaded programs, since the garbage collector has to pause all other threads, either for the entirety of the GC run or (if you're lucky and using a good GC) for parts of it. The modularity argument is reasonable, and I've been annoyed by this aspect several times, though in the majority of cases it doesn't seem to be an issue.

pkolaczk 13y ago
Modern GCs use multiple threads to collect garbage. Also, it is possible to design a GC that does not pause mutator (e.g. C4) or does most of the things concurrently (CMS) or does incremental sweeps (G1 and other evacuating collectors), or uses separate isolated heaps for each thread (Erlang GC).
- bad_user 13y ago
  In Mozilla's Rust you can also have a thread-local garbage collector for each thread.
rbehrends 13y ago
If you mix up reference counting with manual memory management, you get the aforementioned modularity issue (as I mentioned as one of my points). You get rid of (some) of the overhead, at the cost of simplicity (you also may incur other overhead; manual memory management often introduces unnecessary copying in order to keep ownership simple). The problem with reference counting in concurrent programs is one of correctness, not one of speed [1] because every change of a reference count is a potential race condition. That's quite different from the challenges garbage collection faces in a multi-threaded environment. Whether a garbage collector has to pause all threads is an implementation issue. Modern garbage collectors can limit that pause effectively to the root scanning phase, then let the collector run concurrently with the mutator. You can also work around pausing threads entirely, though the tradeoffs are rarely worth it outside of hard realtime environments. Note also that this is an issue of pause time, not performance. While HN can get obsessed with pause times, not everyone programs video games, embedded systems, or kernel drivers where that matters. High-performance computing, for example, is a huge field where pause times are all but irrelevant and where amortized cost is what matters. (HPC is also where correctness can become easily more important than squeezing out a percent or more of performance through low-level hacks; if a job that takes several days to run crashes halfway through, that's an enormous loss.) [1] Technically, you can make reference count updates atomic, but the overhead is absurd, especially under contention. Hence why SNZIs [2] exist, which reduce the speed overhead at the expense of additional memory overhead. [2] http://dl.acm.org/citation.cfm?id=1281106 http://dl.acm.org/citation.cfm?id=1281106
- fauigerzigerk 13y ago
  >While HN can get obsessed with pause times, not everyone programs video games, embedded systems, or kernel drivers where that matters. The (my) problem is that it also matters whenever a program holds lots of data in memory (databases, data analysis, caching, etc). As the cost of RAM decreases, the importance of this problem increases, i.e. fast.
  - rbehrends 13y ago
    Large heaps and large pause times do not necessarily go hand in hand. That's a question of GC technology. For example, the Azul GC does <10 ms pauses for heaps that are hundreds of GB in size. Granted, Azul/Zing pricing doesn't exactly make it the most accessible technology (and it relies on kernel hackery for its compaction), but it demonstrates that multi-second pauses are hardly a necessity. Incremental garbage collection isn't a new technology [1] or one that's particularly difficult to implement by itself (a grad student could probably implement Baker's treadmill in a couple of days); what makes it hard is primarily compaction and multiple threads [1]. You can't effectively use (naive) RC with multiple threads and you don't get compaction with RC, either. Multi-threading is in practice a major driver for the need of GC, since (naive) RC isn't thread-safe and unpredictable object lifetimes don't go well with manual memory management. Also, deferred RC strategies can under certain circumstances contain the cost for cycle collection. Trial deletion is already limited to nodes reachable from other nodes whose reference count has been decremented; type information can be leveraged further to exclude nodes that cannot possibly be parts of cycles (this is particularly easy in ML-style languages, which make mutually recursive types explicit in the source code, but is not limited to those [2]). Finally, you can also use multiple disjoint heaps to simplify implementation and cap GC cost (one per thread and zero or more shared heaps). This can also bring naive RC back into play as a viable strategy, though you'd still lose compaction. Multiple heaps are particularly attractive for NUMA architectures. [1] I note that hard realtime guarantees are difficult to make with a basic incremental collector due to the potential of pathological behavior, but we are not talking about hard realtime guarantees here. [2] Obviously, JITs and dynamically or weakly typed languages have a harder time with this approach.

by agwa 13y ago

pkolaczk 13y ago

Modern GCs use multiple threads to collect garbage. Also, it is possible to design a GC that does not pause mutator (e.g. C4) or does most of the things concurrently (CMS) or does incremental sweeps (G1 and other evacuating collectors), or uses separate isolated heaps for each thread (Erlang GC).

bad_user 13y ago
In Mozilla's Rust you can also have a thread-local garbage collector for each thread.

rbehrends 13y ago

If you mix up reference counting with manual memory management, you get the aforementioned modularity issue (as I mentioned as one of my points). You get rid of (some) of the overhead, at the cost of simplicity (you also may incur other overhead; manual memory management often introduces unnecessary copying in order to keep ownership simple). The problem with reference counting in concurrent programs is one of correctness, not one of speed [1] because every change of a reference count is a potential race condition. That's quite different from the challenges garbage collection faces in a multi-threaded environment. Whether a garbage collector has to pause all threads is an implementation issue. Modern garbage collectors can limit that pause effectively to the root scanning phase, then let the collector run concurrently with the mutator. You can also work around pausing threads entirely, though the tradeoffs are rarely worth it outside of hard realtime environments. Note also that this is an issue of pause time, not performance. While HN can get obsessed with pause times, not everyone programs video games, embedded systems, or kernel drivers where that matters. High-performance computing, for example, is a huge field where pause times are all but irrelevant and where amortized cost is what matters. (HPC is also where correctness can become easily more important than squeezing out a percent or more of performance through low-level hacks; if a job that takes several days to run crashes halfway through, that's an enormous loss.) [1] Technically, you can make reference count updates atomic, but the overhead is absurd, especially under contention. Hence why SNZIs [2] exist, which reduce the speed overhead at the expense of additional memory overhead. [2] http://dl.acm.org/citation.cfm?id=1281106 http://dl.acm.org/citation.cfm?id=1281106

fauigerzigerk 13y ago
>While HN can get obsessed with pause times, not everyone programs video games, embedded systems, or kernel drivers where that matters. The (my) problem is that it also matters whenever a program holds lots of data in memory (databases, data analysis, caching, etc). As the cost of RAM decreases, the importance of this problem increases, i.e. fast.
- rbehrends 13y ago
  Large heaps and large pause times do not necessarily go hand in hand. That's a question of GC technology. For example, the Azul GC does <10 ms pauses for heaps that are hundreds of GB in size. Granted, Azul/Zing pricing doesn't exactly make it the most accessible technology (and it relies on kernel hackery for its compaction), but it demonstrates that multi-second pauses are hardly a necessity. Incremental garbage collection isn't a new technology [1] or one that's particularly difficult to implement by itself (a grad student could probably implement Baker's treadmill in a couple of days); what makes it hard is primarily compaction and multiple threads [1]. You can't effectively use (naive) RC with multiple threads and you don't get compaction with RC, either. Multi-threading is in practice a major driver for the need of GC, since (naive) RC isn't thread-safe and unpredictable object lifetimes don't go well with manual memory management. Also, deferred RC strategies can under certain circumstances contain the cost for cycle collection. Trial deletion is already limited to nodes reachable from other nodes whose reference count has been decremented; type information can be leveraged further to exclude nodes that cannot possibly be parts of cycles (this is particularly easy in ML-style languages, which make mutually recursive types explicit in the source code, but is not limited to those [2]). Finally, you can also use multiple disjoint heaps to simplify implementation and cap GC cost (one per thread and zero or more shared heaps). This can also bring naive RC back into play as a viable strategy, though you'd still lose compaction. Multiple heaps are particularly attractive for NUMA architectures. [1] I note that hard realtime guarantees are difficult to make with a basic incremental collector due to the potential of pathological behavior, but we are not talking about hard realtime guarantees here. [2] Obviously, JITs and dynamically or weakly typed languages have a harder time with this approach.