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

11–20 of 27 posts

Re: Reference Counting: Harder Than It Sounds

#11

Post by sdegutis »

sz4kerto wrote: post #9
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 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.

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.

Re: Reference Counting: Harder Than It Sounds

#13

Post by Qantourisc »

zzzcpan wrote: post #7

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 sh…

Suppose you could make a queue for each thread, and stick the to-in/decrement list on there. But I'm no expert.

Re: Reference Counting: Harder Than It Sounds

#14

Post by Sharlin »

radiospiel wrote: post #12

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?

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

Re: Reference Counting: Harder Than It Sounds

#15

Post by rayiner »

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 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. The algorithm requires cores to see other cores" stores in program order, which is true on x86 (and ARMv8 with the correct instructions?)

Re: Reference Counting: Harder Than It Sounds

#16

Post by zzzcpan »

Qantourisc wrote: post #13
zzzcpan wrote: post #7

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 sh…

Suppose you could make a queue for each thread, and stick the to-in/decrement list on there. But I'm no expert.

Yeah, already glanced through a bunch of papers on refcounting. Seems like people have tried similar ideas and quite successfully.

Re: Reference Counting: Harder Than It Sounds

#17

Post by hendzen »

zzzcpan wrote: post #7

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 sh…

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....

Re: Reference Counting: Harder Than It Sounds

#18

Post by akkartik »

sz4kerto wrote: post #9
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 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.

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.)

Re: Reference Counting: Harder Than It Sounds

#19

Post by sanjoy_das »

Sharlin wrote: post #14
radiospiel wrote: post #12

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?

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 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.

Re: Reference Counting: Harder Than It Sounds

#20

Post by mcguire »

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.
Post reply on HN