3 ms·

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

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.
  - fauigerzigerk 13y ago
    >Large heaps and large pause times do not necessarily go hand in hand Not necessarily, but in practice they do go hand in hand. I didn't say the problem was impossible to solve, just that it is an important problem that needs solving. Azul solved the technology issues (or so they claim) but not the economics of it, and they solved it for a language that isn't a good fit for in-memory computing in the first place (to put it politely). If I have to write software today that keeps a lot of data in-memory and requires reasonable latency (and I do) my only realistic option is C++. I know all the drawbacks of naive reference counting. C++ shared pointers are a horrible kludge. Fortunately they are only needed in very few places, thanks to RAII and unique_ptr. The problem is that C++ has tons of other issues that will never be solved (antiquated modularity, header files, crazy compile times, excessive complexity and generally lots of baggage from the past).

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.
- fauigerzigerk 13y ago
  >Large heaps and large pause times do not necessarily go hand in hand Not necessarily, but in practice they do go hand in hand. I didn't say the problem was impossible to solve, just that it is an important problem that needs solving. Azul solved the technology issues (or so they claim) but not the economics of it, and they solved it for a language that isn't a good fit for in-memory computing in the first place (to put it politely). If I have to write software today that keeps a lot of data in-memory and requires reasonable latency (and I do) my only realistic option is C++. I know all the drawbacks of naive reference counting. C++ shared pointers are a horrible kludge. Fortunately they are only needed in very few places, thanks to RAII and unique_ptr. The problem is that C++ has tons of other issues that will never be solved (antiquated modularity, header files, crazy compile times, excessive complexity and generally lots of baggage from the past).