Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reference Counting: Harder Than It Sounds

playingwithpointers.com

Post reply on HN
Print view View original

21–27 of 27 posts

Re: Reference Counting: Harder Than It Sounds

#21

Post by akkartik »

mcguire wrote: post #20
akkartik wrote: post #3

This is probably simplistic, but in my safe, toy assembly language for teaching programming I simply avoid ever sharing (always refcounted) pointers between threads. Instead it pervasively uses channels for communication, and while channels are generic anything you put in them gets deep-copied on write. The deep copy is smart enough to preserve cycles, so say if you send in a linked list that contains a cycle the rea…

For an actor-based language that avoids deep-copying, check out Pony ( http://www.ponylang.org/ ). It uses a small stack of reference capabilities to ensure safety even if you pass a mutable structure.

Interesting! Could you point me at a talk or paper specifically about that aspect?

Re: Reference Counting: Harder Than It Sounds

#22

Post by Roboprog »

rayiner wrote: post #15
akkartik wrote: post #3

This is probably simplistic, but in my safe, toy assembly language for teaching programming I simply avoid ever sharing (always refcounted) pointers between threads. Instead it pervasively uses channels for communication, and while channels are generic anything you put in them gets deep-copied on write. The deep copy is smart enough to preserve cycles, so say if you send in a linked list that contains a cycle the rea…

The article is about making ref-counting thread safe in an uncooperative environment (c++ shared_ptrs). If you're willing to relax one of those conditions, there are solutions that don't require giving up shared data. See Yossi Levanoni and Erez Petrank, An on-the-fly reference counting garbage collector for Java . If you buffer all reference count updates in thread local buffers, then process increments and defermen…

I remember the horror I felt when first reading about threads in Novell and OS2 back around 1990 or so.

Threads provide a lot of research opportunities. Should they really be exposed at the application programming level? Java was a nice try, but I think any language that is going to tightly integrate threads should emulate processes and interprocess communication, isolating casual variable references between threads.

Cue: somebody more knowledgable than me discuss Erlang here...

Re: Reference Counting: Harder Than It Sounds

#23

Post by gpderetta »

sanjoy_das wrote: post #19
Sharlin wrote: post #14

Earlier quoted context omitted.

if (--old_val->refcount == 0) It's pre-decrement; the refcount is decremented before comparison.

In (other) words, the situation is that you've just decremented the reference count of an object, because you've nulled out the only location in the heap that reached it. The reference count becomes zero after decrementing, so you know that _now_ there are no slots in the heap that point to it; but how do you know that there isn't a thread that fetched the object out of the heap before you started, and got stalled be…

How did the other thread get the reference to the object? The only possible existing reference is the one we are using to decrement the shared counter.

Decrementing is done when the reference itself is being dropped (set to null or to point to a different object), which is a logically mutating operation (remember that only the reference count updates are atomic, the operations on the references themselves are not), thus no other acquire operation can be happening concurrently or it would be a data race.

Any concurrent operations on the reference itself must be synchronized via external means, usually a mutex. Of course concurrently mutating distinct references which refer to the same object/ref count is fine.

edit: rewording

Re: Reference Counting: Harder Than It Sounds

#24

Post by sanjoy_das »

gpderetta wrote: post #23
sanjoy_das wrote: post #19

Earlier quoted context omitted.

In (other) words, the situation is that you've just decremented the reference count of an object, because you've nulled out the only location in the heap that reached it. The reference count becomes zero after decrementing, so you know that _now_ there are no slots in the heap that point to it; but how do you know that there isn't a thread that fetched the object out of the heap before you started, and got stalled be…

How did the other thread get the reference to the object? The only possible existing reference is the one we are using to decrement the shared counter. Decrementing is done when the reference itself is being dropped (set to null or to point to a different object), which is a logically mutating operation (remember that only the reference count updates are atomic, the operations on the references themselves are not), t…

> How did the other thread get the reference to the object? The only possible existing reference is the one we are using to decrement the shared counter.

I don't think this affects the point you're trying to make, but I suppose you could have three threads, where the logical operations are:

    ThreadA:
      obj = x->field_a;
    
    ThreadB:
      x->field_a = null;
    
    ThreadC:
      x->field_b = null;
with both field_a and field_b pointing to the same object initially. It does not affect your point, since ThreadA and ThreadB are now racing.

> Decrementing is done when the reference itself is being dropped (set to null or to point to a different object), which is a logically mutating operation (remember that only the reference count updates are atomic, the operations on the references themselves are not), thus no other acquire operation can be happening concurrently or it would be a data race.

It depends on your programming language. In Java racing on field updates (at the Java level) is well defined (but is allowed to return counter-intuitive results to some degree). That is:

    ThreadA
      int k = obj.field.hashCode()

    ThreadB
      obj.field = someOtherValue
is defined and is not allowed to have arbitrarily bad effects like crashing the VM. This is different from C++ (where these kind of accesses are UB, as you seem to imply). Generally, I think for high level languages it is better to have Java-like semantics where even racy accesses have some guarantees.

For C++, I can get the same Java-like guarantees by using `memory_order_relaxed` loads, but I suppose it is defensible for an atomic `shared_ptr` to have a complex refcounting protocol even for `memory_order_relaxed` loads and stores.

> Any concurrent operations on the reference itself must be synchronized via external means, usually a mutex.

Not sure how you're using a reference here, but if by "reference" you mean "a location in the heap" then that does not apply for Java. I personally tend to use "reference" in the same way as "pointer".

> Of course concurrently mutating distinct references which refer to the same object/ref count is fine. edit: rewording

edit: formatting

Re: Reference Counting: Harder Than It Sounds

#25

Post by [deleted] »

Rexxar wrote: post #8
rix0r wrote: post #6

Earlier quoted context omitted.

Saying "use immutable data structures" here assumes garbage collection though. If you didn't have garbage collection, when would you release the memory for these structures? That would bring you back to refcounting.

Is it a problem in practice to use reference counting for an "immutable data structures" ? Obviously it's not 100% immutable as the counters are updated. But if it's done with a thread safe reference counter the data structures is usable like a pure immutable data structure and doesn't need an additional garbage collector.

[deleted]

Re: Reference Counting: Harder Than It Sounds

#26

Post by mcguire »

akkartik wrote: post #21
mcguire wrote: post #20

Earlier quoted context omitted.

For an actor-based language that avoids deep-copying, check out Pony ( http://www.ponylang.org/ ). It uses a small stack of reference capabilities to ensure safety even if you pass a mutable structure.

Interesting! Could you point me at a talk or paper specifically about that aspect?

Check out "Deny Capabilities for Safe, Fast Actors", "fast-cheap.pdf" at

https://github.com/ponylang/ponylang.github.io/tree/master/m...

Re: Reference Counting: Harder Than It Sounds

#27

Post by gpderetta »

sanjoy_das wrote: post #24
gpderetta wrote: post #23

Earlier quoted context omitted.

How did the other thread get the reference to the object? The only possible existing reference is the one we are using to decrement the shared counter. Decrementing is done when the reference itself is being dropped (set to null or to point to a different object), which is a logically mutating operation (remember that only the reference count updates are atomic, the operations on the references themselves are not), t…

> How did the other thread get the reference to the object? The only possible existing reference is the one we are using to decrement the shared counter. I don't think this affects the point you're trying to make, but I suppose you could have three threads, where the logical operations are: ThreadA: obj = x->field_a; ThreadB: x->field_a = null; ThreadC: x->field_b = null; with both field_a and field_b pointing to the…

I was of course discussing the semantics of a C-like language, especially in light of the C++11 memory model.

Being memory safe at all cost, java (and any other shared-memory memory safe language) must guarantee minimum of safety to concurrent reference updates. A JVM which uses reference counting instead of a proper GC would be interesting to implement...

You can't currently put a shared_ptr in an atomic variable as it does not meet the concept requirements (Trivially constructible and copyable), but, IIRC, you will in C++17 and, yes, even relaxed loads will be expensive (in practice implementations are expected to lock a spinlock around every operation)

Post reply on HN