7 ms·

Reference Counting: Harder Than It Sounds

53 points by sanjoy_das 10y ago

deleted 10y ago
[deleted]
akkartik 10y ago
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 reader will see a linked list with an identical topology. It will just be utterly disjoint with the original linked list. These design decisions allow me to provide safe pointer access and avoid all race conditions while teaching programming and concurrency, but they probably incur significant performance loss on certain programs. My hope is that the design constraints they impose on the programmer aren't insurmountable. We'll see. (More info on the project: https://github.com/akkartik/mu#readme https://github.com/akkartik/mu#readme. On its memory model: https://news.ycombinator.com/item?id=11855470 https://news.ycombinator.com/item?id=11855470. On the deep-copy implementation: https://github.com/akkartik/mu/blob/07ab3e3f35/073deep_copy.cc#L243 https://github.com/akkartik/mu/blob/07ab3e3f35/073deep_copy....)
- david-given 10y ago
  Yeah, CSP is awesome. The traditional thing to do here is to use immutable data structures; because they can never change, you don't need locks to access them, which means you can pass pointers between threads willy-nilly. And if you're sending a message to a process that doesn't share memory, you can fall back to serialisation. Bear in mind that you can still get race conditions and deadlocks with CSP --- consider a process which provides `get` and `set` messages, and then two other processes try to do `c.set(c.get() + 1)`.
  - rix0r 10y ago
    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.
    - Rexxar 10y ago
      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 10y ago
        [deleted]
    - david-given 10y ago
      Oh, yeah, I missed that bit of context. Oops. OP's comment makes much more sense now...
- sz4kerto 10y ago
  The tricky part with channels and deep copies that it does not solve the problem completely, just shifts it to a higher level. You will still have 'identity', and concurrent modification of the state of an identity has to be solved somehow.
  - sdegutis 10y ago
    The solution I like best, which someone in #proglangdesign mentioned the other day, is to only pass serializable data through. That's how I plan to do it.
  - akkartik 10y ago
    I'm not sure any problem needs a solution that requires concurrent modifications to the state of an identity, though. Can you think of any such? (Rust seems to be making the same bet.)
- rayiner 10y ago
  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 deferments in batches with threads paused, you can use a write barrier that has no synchronization operations. Though IIRC the Levonani-Petrank write barrier assumes stronger ordering of stores than is true on some architectures. EDIT: http://www.cs.technion.ac.il/~erez/Papers/refcount.pdf http://www.cs.technion.ac.il/~erez/Papers/refcount.pdf. The algorithm requires cores to see other cores" stores in program order, which is true on x86 (and ARMv8 with the correct instructions?)
  - Roboprog 10y ago
    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...
- mcguire 10y ago
  For an actor-based language that avoids deep-copying, check out Pony (http://www.ponylang.org/ http://www.ponylang.org/). It uses a small stack of reference capabilities to ensure safety even if you pass a mutable structure.
  - akkartik 10y ago
    Interesting! Could you point me at a talk or paper specifically about that aspect?
    - mcguire 10y ago
      Check out "Deny Capabilities for Safe, Fast Actors", "fast-cheap.pdf" at https://github.com/ponylang/ponylang.github.io/tree/master/media/papers https://github.com/ponylang/ponylang.github.io/tree/master/m...
nwalfield 10y ago
One way to reduce the cost of cross CPU synchronization is to use sloppy reference counters: "An Analysis of Linux Scalability to Many Cores" (https://pdos.csail.mit.edu/papers/linux:osdi10.pdf https://pdos.csail.mit.edu/papers/linux:osdi10.pdf)
zzzcpan 10y ago
I'm thinking, for shared refcounted pointers would it be better to just move synchronization off the critical path completely? I mean operate on local pointers in each thread, like it's a single threaded app, but every hundred decrements merge their counters. And release memory only if counters were zero and synchronized for some time, i.e. for at least a couple of synchronizations on every thread or something. It should be possible to get an order of magnitude better performance, than with any kind of synchronized refcounters.
- Qantourisc 10y ago
  Suppose you could make a queue for each thread, and stick the to-in/decrement list on there. But I'm no expert.
  - zzzcpan 10y ago
    Yeah, already glanced through a bunch of papers on refcounting. Seems like people have tried similar ideas and quite successfully.
- hendzen 10y ago
  It turns out that the whole notion of a 'reference count' that tracks the exact number of handles is unnecessarily powerful. If you weaken the guarantee to two states - 0 or greater than 0, you can do even better. See SNZI (scalable non-zero indicators): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.3091&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83....
radiospiel 10y ago
I don't see how in the example thread b's refcount could be zero, since there would exist a reference on thread a already (or else A could not create another reference) So how can that happen?
- Sharlin 10y ago
  if (--old_val->refcount == 0) It's pre-decrement; the refcount is decremented before comparison.
  - sanjoy_das 10y ago
    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 before it could increment the reference count and has been stalled since then? (I'll try to edit the post to make this clearer ^). I'd also like to stress that there are many ways around the problem, the only point of the post is that you'll have to solve some non-obvious problems if you try to generalize reference counting to a heap shared across threads.
    - gpderetta 10y ago
      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

53 points by sanjoy_das 10y ago

deleted 10y ago

[deleted]

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 reader will see a linked list with an identical topology. It will just be utterly disjoint with the original linked list. These design decisions allow me to provide safe pointer access and avoid all race conditions while teaching programming and concurrency, but they probably incur significant performance loss on certain programs. My hope is that the design constraints they impose on the programmer aren't insurmountable. We'll see. (More info on the project: https://github.com/akkartik/mu#readme https://github.com/akkartik/mu#readme. On its memory model: https://news.ycombinator.com/item?id=11855470 https://news.ycombinator.com/item?id=11855470. On the deep-copy implementation: https://github.com/akkartik/mu/blob/07ab3e3f35/073deep_copy.cc#L243 https://github.com/akkartik/mu/blob/07ab3e3f35/073deep_copy....)

david-given 10y ago
Yeah, CSP is awesome. The traditional thing to do here is to use immutable data structures; because they can never change, you don't need locks to access them, which means you can pass pointers between threads willy-nilly. And if you're sending a message to a process that doesn't share memory, you can fall back to serialisation. Bear in mind that you can still get race conditions and deadlocks with CSP --- consider a process which provides `get` and `set` messages, and then two other processes try to do `c.set(c.get() + 1)`.
- rix0r 10y ago
  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.
  - Rexxar 10y ago
    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 10y ago
      [deleted]
  - david-given 10y ago
    Oh, yeah, I missed that bit of context. Oops. OP's comment makes much more sense now...
sz4kerto 10y ago
The tricky part with channels and deep copies that it does not solve the problem completely, just shifts it to a higher level. You will still have 'identity', and concurrent modification of the state of an identity has to be solved somehow.
- sdegutis 10y ago
  The solution I like best, which someone in #proglangdesign mentioned the other day, is to only pass serializable data through. That's how I plan to do it.
- akkartik 10y ago
  I'm not sure any problem needs a solution that requires concurrent modifications to the state of an identity, though. Can you think of any such? (Rust seems to be making the same bet.)
rayiner 10y ago
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 deferments in batches with threads paused, you can use a write barrier that has no synchronization operations. Though IIRC the Levonani-Petrank write barrier assumes stronger ordering of stores than is true on some architectures. EDIT: http://www.cs.technion.ac.il/~erez/Papers/refcount.pdf http://www.cs.technion.ac.il/~erez/Papers/refcount.pdf. The algorithm requires cores to see other cores" stores in program order, which is true on x86 (and ARMv8 with the correct instructions?)
- Roboprog 10y ago
  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...
mcguire 10y ago
For an actor-based language that avoids deep-copying, check out Pony (http://www.ponylang.org/ http://www.ponylang.org/). It uses a small stack of reference capabilities to ensure safety even if you pass a mutable structure.
- akkartik 10y ago
  Interesting! Could you point me at a talk or paper specifically about that aspect?
  - mcguire 10y ago
    Check out "Deny Capabilities for Safe, Fast Actors", "fast-cheap.pdf" at https://github.com/ponylang/ponylang.github.io/tree/master/media/papers https://github.com/ponylang/ponylang.github.io/tree/master/m...

nwalfield 10y ago

One way to reduce the cost of cross CPU synchronization is to use sloppy reference counters: "An Analysis of Linux Scalability to Many Cores" (https://pdos.csail.mit.edu/papers/linux:osdi10.pdf https://pdos.csail.mit.edu/papers/linux:osdi10.pdf)

zzzcpan 10y ago

I'm thinking, for shared refcounted pointers would it be better to just move synchronization off the critical path completely? I mean operate on local pointers in each thread, like it's a single threaded app, but every hundred decrements merge their counters. And release memory only if counters were zero and synchronized for some time, i.e. for at least a couple of synchronizations on every thread or something. It should be possible to get an order of magnitude better performance, than with any kind of synchronized refcounters.

Qantourisc 10y ago
Suppose you could make a queue for each thread, and stick the to-in/decrement list on there. But I'm no expert.
- zzzcpan 10y ago
  Yeah, already glanced through a bunch of papers on refcounting. Seems like people have tried similar ideas and quite successfully.
hendzen 10y ago
It turns out that the whole notion of a 'reference count' that tracks the exact number of handles is unnecessarily powerful. If you weaken the guarantee to two states - 0 or greater than 0, you can do even better. See SNZI (scalable non-zero indicators): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.3091&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83....

radiospiel 10y ago

I don't see how in the example thread b's refcount could be zero, since there would exist a reference on thread a already (or else A could not create another reference) So how can that happen?

Sharlin 10y ago
if (--old_val->refcount == 0) It's pre-decrement; the refcount is decremented before comparison.
- sanjoy_das 10y ago
  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 before it could increment the reference count and has been stalled since then? (I'll try to edit the post to make this clearer ^). I'd also like to stress that there are many ways around the problem, the only point of the post is that you'll have to solve some non-obvious problems if you try to generalize reference counting to a heap shared across threads.
  - gpderetta 10y ago
    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