Reference Counting: Harder Than It Sounds
playingwithpointers.com
Reference Counting: Harder Than It Sounds
1–10 of 27 posts
Re: Reference Counting: Harder Than It Sounds
#2[deleted]
Re: Reference Counting: Harder Than It Sounds
#3This 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. On its memory model: https://news.ycombinator.com/item?id=11855470. On the deep-copy implementation: https://github.com/akkartik/mu/blob/07ab3e3f35/073deep_copy....)
Re: Reference Counting: Harder Than It Sounds
#4One 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)
Re: Reference Counting: Harder Than It Sounds
#5This 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…
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)`.
Re: Reference Counting: Harder Than It Sounds
#6This 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…
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…
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.
Re: Reference Counting: Harder Than It Sounds
#7I'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.
Re: Reference Counting: Harder Than It Sounds
#8Earlier quoted context omitted.
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…
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.
Re: Reference Counting: Harder Than It Sounds
#9This 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.
Re: Reference Counting: Harder Than It Sounds
#10Earlier quoted context omitted.
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…
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.
Oh, yeah, I missed that bit of context. Oops. OP's comment makes much more sense now...