News for hackers. Stuff that matters.
Re:Is reference counting slower than GC? by barrkel on Tuesday May 24, 2016 @05:17AM (#11759978)
This isn't an informed article.

Reference counting is a type of garbage collection. It's not complete without collecting cycles, but it can form part of a GC mix.

Assigning pointers in a scanning GC can have a cost; for example, generational GCs need to track writes to old generations that point to newer generation objects.

There's no discussion of thread safety and how that affects reference counting. That's probably the biggest problem; you need to use memory barriers to make reference counting safe with multiple threads, and that can kill performance.

Re:Is reference counting slower than GC? by mortoray on Tuesday May 24, 2016 @05:42AM (#11760084)
I (author) actually agree that reference counting is a form of garbage collection. However, in most dicussions about memory management the generic term garbage collection tends to refer to scanning collectors. In particualr, people who often oppose my views on scanning GCs are the ones that actually use the term garbage collector to refer to those types of collectors.

Most places I see talking about reference counting just say reference counting, sometimes mentioning memory management. Automatic memory management is perhaps the most generic term.

How reference counting actually works is covered in my previous article, which I wrote as a lead-up to this one. It covers the particulars of how memroy coherency is the primary cost of reference counting.

Re:Is reference counting slower than GC? by michaelfeathers on Tuesday May 24, 2016 @05:48AM (#11760100)
There is a lot of data on this topic.

This is a good starting place: http://www.amazon.com/Garbage-Collection-Algorithms-Automati...

Re:Is reference counting slower than GC? by chrismonsanto on Tuesday May 24, 2016 @05:33AM (#11760046)
The reference counting != GC thing gets repeated all the time on HN, so I'm glad you called this out. For the record, what these people call "GC" is better called tracing garbage collection.
Re:Is reference counting slower than GC? by jasode on Tuesday May 24, 2016 @09:00AM (#11761167)
It's not just HN. It's also differentiated that way in the official Apple documentation. I previously commented on it:

https://news.ycombinator.com/item?id=7866732

The "rc != gc" ship has already sailed. I realize that it can be annoying to language purists but the way to make peace with it is to separate discussions into 2 types of contexts:

1) formal computer science discussion (such as Lambda The Ultimate) --> "rc == gc"

2) real-world discussions in Apple documentation and various other forums --> "rc != gc"

I'm not prescribing that you must like the situation but merely pointing out that's how it is these days. Repeatedly making corrections in the hopes that #1 overtakes #2 is not going to sway common usage. Even rigid and exacting computer scientists use words and concepts[1] that mathematicians frown on. In the end, the common usage (that often strays from original precision) prevails.

[1]e.g. "integer" as -32k to +32k instead of -inf to +inf, and "=" as "assignment" instead of "equality"

Re:Is reference counting slower than GC? by chrismonsanto on Tuesday May 24, 2016 @09:30AM (#11761340)
Alternatively, I'll continue to speak up for the established terminology in the GC literature, and continue to recommend that those interested in this subject read sources like Jones' GC Handbook rather than the "official" Apple documentation.

People who are actively hostile against using the established terminology are unlikely to have the expertise necessary to contribute productively to these kinds of discussions anyway.

Re:Is reference counting slower than GC? by jasode on Tuesday May 24, 2016 @03:44PM (#11764887)
>read sources like Jones' GC Handbook rather than the "official" Apple documentation.

I want to emphasize again that it's a language communication issue and not a technical issue and therefore, reading Jones' GC Handbook will not help nor solve the problem. One can thoroughly study that book, and 100% agree with the terminology that "rc is subset of gc", and in the end, still chooses to use the informal "rc != gc" -- because everyone else has been using it that way for a long time.

Also, by mentioning Apple, I may have given the impression that it's specifically "Apple" vs the "correct computer science" proponents. Or, I'm saying Apple is some sort of authority or blessing on loose terminology. No, the informal "rc vs gc" nomenclature has been used for over 30 years which is long before Apple did the GC/ARC flip flop in 2011. It is also before the Jones GC book published in 1996. Examples:

1989: https://groups.google.com/forum/#!search/reference$20countin...

1994: https://groups.google.com/forum/#!msg/comp.object/fqPmh_1wml...

2002: https://books.google.com/books?id=mGlI6kt6qzYC&pg=PA76&lpg=P...

In other words, the "rc != gc" ship sailed a long time before Apple's documentation and the cited links show how pervasive its usage was across several programming languages.

Ideally, "RC" would have been "RCGC" Ref Counting Garbage Collector, and "GC" would have been "TGC" Tracing Garbage Collector so all subsequent conversations were "RCGC vs TGC" but that's not how history played out. Studying Jones' GC Handbook does not reverse 30+ years of how people informally use terminology.

Re:Is reference counting slower than GC? by EdiX on Tuesday May 24, 2016 @06:23AM (#11760248)
I think the "reference counting != GC" meme originates in Apple's marketing, specifically they needed a simple way to market their reference counting (which they call ARC to distinguish it from manual reference counting previously used by ObjC) as different and superior to Android garbage collection.
Re:Is reference counting slower than GC? by pjmlp on Tuesday May 24, 2016 @01:11PM (#11763354)
And also to hide the fact that their Objective-C GC attempt was a failure.

It is true that their ARC semantics is a better solution to Objective-C's memory management semantics, but they needed to do the typical marketing stunt of selling a failure as something positive.

Re:Is reference counting slower than GC? by vardump on Tuesday May 24, 2016 @05:18AM (#11759983)
You don't necessarily need memory barriers (implementation detail).

All you need is an atomic fetch-and-add (like x86 XADD opcode). Many architectures provide that as a primitive. On those that don't, you have to compose it out of other atomic primitives.

Re:Is reference counting slower than GC? by gpderetta on Tuesday May 24, 2016 @05:27AM (#11760018)
if you have destructors or finalizers you do need memory barriers to make sure that any previous modification of the object happens-before the destructor is run.

Also many architectures with builtin fetch-and-add bundle it with an implicit memory barrier (that includes x86).

Re:Is reference counting slower than GC? by vardump on Tuesday May 24, 2016 @05:41AM (#11760078)
But then those barriers are not for the refcount itself, but for the data the object contains. Different things.

On x86, stores are always ordered anyways, so fetch-and-add doesn't need to do any implicit memory barrier.

Re:Is reference counting slower than GC? by gpderetta on Tuesday May 24, 2016 @07:07AM (#11760486)
Barriers are never needed for accesses to a single location as all practical systems guarantee total ordering, that a given. But on a refcounted system the only place to put the barrier for correct visibility, it is together with the refcount update.

It is true that on x86 all stores and loads have the correct implicit barriers, but you still get a store-load (including its cycle cost) with lock xadd whether you want it or not.

Re:Is reference counting slower than GC? by barrkel on Tuesday May 24, 2016 @05:50AM (#11760111)
I think you need more than just fetch-and-add.

Think about this:

    assign(value)
    {
        root.ref = value;
    }
needs to be expanded out into:

    assign(value)
    {
        if (value)
          inc_ref(value)
        tmp = value
        atomic_swap(&root.ref, &tmp)
        if (tmp && dec_ref(tmp) == 0)
            free(tmp)
    }    
If you don't use an atomic swap, you race with other threads trying to assign to the same location. You can't decrement the destination before incrementing the source because they could be equal. You can't make the logic conditional on equality because it races.

You have a harder time with this:

    a.b.c = value
You need to inc-ref each step in the chain, keeping them in temporaries, to ensure they don't get dec-refed out from underneath you on another thread.
Re:Is reference counting slower than GC? by vardump on Tuesday May 24, 2016 @05:54AM (#11760129)
But if you have both atomic primitives available, why would you ever do that?

Keyword is atomic. Fetch-and-add returns you the previous value atomically.

-------

Edit:

This (below) is obviously a buggy reference counting algorithm.

-------

In freeing (decrementing reference count) thread A, if it was 1 before (returned value) and A added -1, the object can be freed.

Because the operation is atomic, only one of two things can happen:

1) Another reference adding thread B increments it before A decreases it. So A doesn't see 1, thus won't free the object.

2) B increments it after A decremented it. So B gets zero and knows the object is invalid. (Edit: Oops, a bug: after B increments refcount, when thread C tries to do same, it would get 1 and conclude the object is valid!)

If B is allowed to allocate the object again (invalid state, refcount == 0), careful synchronization needs to be done remove any races with A's deallocation.

Re:Is reference counting slower than GC? by barrkel on Tuesday May 24, 2016 @08:06AM (#11760843)
I think you're hung up on multiple threads reference-counting a single instance. That's not where reference counting as a GC approach gets difficult. It's when you're updating references to values.
Re:Is reference counting slower than GC? by xxs on Tuesday May 24, 2016 @05:24AM (#11759999)
Atomic part has to notify the rest of caches to invalidate the cache line. Local latency in the best case.
Re:Is reference counting slower than GC? by gpderetta on Tuesday May 24, 2016 @05:30AM (#11760033)
FYI, any store has to invalidate remote cachelines, that's taken care by the coherence protocol even before the store is actually performed.

Memory barrier (and atomic operations) don't have anything to do with it.

Re:Is reference counting slower than GC? by JoachimSchipper on Tuesday May 24, 2016 @05:38AM (#11760060)
Whether stores invalidate remote cachelines depends entirely on the architecture. But yes, Intel has fairly strong coherency.
Re:Is reference counting slower than GC? by gpderetta on Tuesday May 24, 2016 @06:59AM (#11760431)
It seems to me that any cache coherent system needs to do that. If multiple writers can be updating a cacheline a the same time [1] you can't talk of coherency at all. Intel is stronger as it guarantees a total ordering of modifications across all cachelines, but any coherent system will guarantee the ordering of modification of a single cacheline.

[1] visibly at least. HTM complicates things a bit of course.

Re:Is reference counting slower than GC? by imtringued on Tuesday May 24, 2016 @05:31AM (#11760038)
So false sharing is the problem?
Re:Is reference counting slower than GC? by gpderetta on Tuesday May 24, 2016 @07:09AM (#11760505)
If the refcount is allocated in the same cacheline with the rest of the object, then false sharing is also a problem. But the violation of the single writer principle when updating refcounts is actually a form of true sharing.
Re:Is reference counting slower than GC? by pjmlp on Tuesday May 24, 2016 @05:51AM (#11760115)
Another thing is the usual issue that tends to get omitted, how GC enabled languages like Modula-3, Oberon(-2), D among others, do allow for a finer control of the GC.

In Modula-3, I can either fully rely on the GC, do safe global and stack allocations, or if really needed make use of manual memory management in unsafe modules.

So it is not as all allocations need to be on the GC heap, in GC enabled languages.

Re:Is reference counting slower than GC? by rubber_duck on Tuesday May 24, 2016 @06:17AM (#11760217)
I'm not sure about the others but the D model is probably the worst of both worlds - you can transparently store a GC allocated reference in to unmanaged heap and risk having dangling pointers after a random collection or you have to root everything you allocate increasing the scan.

Something like Rust has a type system powerful enough to track such things so if you added GC to Rust you could deal with it sanely.

Re:Is reference counting slower than GC? by pjmlp on Tuesday May 24, 2016 @06:40AM (#11760322)
D suffers from not having a good GC implementation in first place.

There is someone improving it with this year during a GSoC project.

Re:Is reference counting slower than GC? by rubber_duck on Tuesday May 24, 2016 @09:16AM (#11761254)
This is true as well but at least that part is fixable (although I'm not sure it's in the realm of a GSoC project considering the kind of work that went in to stuff like various JVM GC implementations)
Re:Is reference counting slower than GC? by pjmlp on Tuesday May 24, 2016 @09:30AM (#11761335)
They are mainly making it precise as stepping stone for further improvements.

https://summerofcode.withgoogle.com/projects/#62055978295623...

Re:Is reference counting slower than GC? by beefsack on Tuesday May 24, 2016 @07:20AM (#11760568)
What about RC boxes[1] in Rust? I believe they're correctly freed but not as part of explicit collecting cycles.

[1]: https://doc.rust-lang.org/std/rc/

Re:Is reference counting slower than GC? by barrkel on Tuesday May 24, 2016 @08:09AM (#11760857)
Rc boxes in Rust are not safe against cycles. That's not a memory safety error - i.e. it won't permit use-after-free - but it can be a potential memory leak.