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....)
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?)
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...
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)`.
If you didn't have garbage collection, when would you release the memory for these structures? That would bring you back to refcounting.
(Rust seems to be making the same bet.)
"An Analysis of Linux Scalability to Many Cores" (https://pdos.csail.mit.edu/papers/linux:osdi10.pdf)
if (--old_val->refcount == 0)
(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.
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.
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:
obj = x->field_a;
x->field_a = null;
x->field_b = null;
> 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:
int k = obj.field.hashCode()
obj.field = someOtherValue
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
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)