Hacker News Reader

Comment by NkVczPkybiXICG | Hacker News Reader

ref-counting should be more than sufficient to deal with the standard multi-thread model of "read from concurrent queue, process, write to different concurrent queue". This covers a huge majority of cases where you'd want a GC. You only need a GC when you have unclear ownership semantics, and if that's the case you're usually fucked anyhow.

View on HN

Concurrent queues are important, but weren't the data structures I was talking about. I was referring to persistent data structures (like Clojure's) that rely on versioning (and used in MVCC, for example). The old version is collected when there are no more references. These immutable data structures don't require ownership anyway.

Circular references are a big problem, because even if you have a single circular reference, a significant portion of your object graph may leak. (Say A -> B -> C -> D -> E -> ..., and also B -> A. A tiny problem like this has just caused your entire object graph to leak).

A problem with persistent data structures is that they're memory-hungry. Combining that with the overhead of a garbage collector...

I think such structures are useful (and nice!) in some circumstances, but as a general solution for efficient system software they're just too hungry to be useful, at least for now. Having useful memory cut to 1/6th (if I'm being generous) or lower is painful, and god forbid the operating system decides it's time to start swapping out pages. The effective memory bandwidth will take a kick in the pants too.

No silver bullet, &c.

My main issue with persistent ds is that they don't have good (CPU) cache behavior on updates. They don't necessarily consume that much memory -- a 32-way trie is quite memory efficient -- as long as the refs to the old versions die soon.

But even mutable concurrent data structures need to keep the old version around, albeit momentarily (hopefully), as they CAS in a new node (depending on the nature of the data structure) in the presence of concurrent readers. Achieving even that with simple ref-counting is not trivial.

Except that basic reference counting is inherently unsafe in a multi-threaded environment. And thread-safe reference counting is not any simpler than garbage collection [1].

[1] E.g.: http://dl.acm.org/citation.cfm?id=1111597

"According to conventional wisdom, the update of reference slots and reference-counts requires atomic or synchronized operations. In this work we demonstrate this is not the case [...]"

Interesting. Rust currently has an atomically-reference-counted type (ARC, briefly mentioned in the OP's post) for sharing data between tasks. I wonder if the algorithm they describe would be useful for Rust as well.

Neither of those statements are true, and the cited article doesn't back up your claim. Check out this thread safe reference counting pointer, it's not complicated: http://www.boost.org/doc/libs/1_53_0/libs/smart_ptr/shared_p...

Not complicated but prohibitively expensive. Here's the source code: http://gcc.gnu.org/onlinedocs/gcc-4.6.0/libstdc++/api/a01034... It does a CAS on every copy!

Prohibitively? That really depends on your use case.

OpenSceneGraph [1] uses intrusive reference counting pointers yet has been found suitable for many real time applications.

[1] http://en.wikipedia.org/wiki/OpenSceneGraph

Prohibitive for the very data structures that make true many-core scaling possible and that necessitate a GC in the first place. A CAS on every pointer copy could obliterate your scaling. This kind of technique was fine in the good-old one- or two-core days. It won't cut it now - not if you want to scale.

Nothing about modern hardware is the same as it used to be. I strongly recommend watching this extremely enlightening talk by Doug Lea about designing multi-threaded algorithms (http://emergingtech.chariotsolutions.com/2013/04/phillyete-s...). For example, did you know that in order for a busy-wait (spin loop) to be effective on modern intel CPUs, it has to compute random numbers (otherwise, the CPU might think you're in the OS idle-loop and power-down the core)?

Thanks for Doug Lea's presentation, I'll try to produce presentation from the video using ffmpeg. The sound is... unpleasant.

Regarding CAS on every pointer copy, it's true that the current hardware has problem with it. Still I wonder if it would be worth and enough to optimize some future CPU to speed up the "interlocked increments" and "interlocked decrements" by introducing delays only to the cores that "interockedly" access the same addresses? I guess it can be tricky as one core has a lot of "in-flight" memory operations at the same tick, but I don't know the real limitations or if there's something more I'm missing, anybody reading this who knows more, what are the limitations?

A naive, thread-safe reference counter using atomic compare-swap is extremely expensive. On the best CPU's in the uncontended case it's 30-50 clock cycles. So modifying a single pointer field becomes a 100 clock cycle affair (decrement for the old value, increment for the new value).

Thread-safe deferred reference counting looks like GC.

Would auto pointers and weak references work better? I've always liked that paradigm...single transferable ownership just feels conceptually clean.

Reply on news.ycombinator.com