Comment by insanitybit | Hacker News Reader

Comment by insanitybit | Hacker News Reader

Parent Full thread

(This is all based on my recollection) Pony does this through reference capabilities, ownership, and garbage collection.

Basically in Pony you can describe memory as:

1. Single Ownership, Immutable

2. Single Ownership, Mutable

3. Shared Ownership, Immutable

4. Shared Ownership, Mutable

If you're moving (1) or (2) that's basically free.

If you're sharing (3) you just need an atomic reference count.

If you're sharing (4) you need an atomic reference count and some sort of synchronizing primitive, such as a mutex (or maybe the runtime can understand how to schedule things such that they don't race, don't know).

In Pony these reference capabilities all have names that I don't remember and there are also ways to "recover" a capability, basically translating one into another, which was one of the more complex features for me to get my head around.

That's basically how I recall it working, although the reference counting implementation is very interesting and they wrote a paper about it (Orca).

This isn't quite right. The key thing is that Pony uses the actor model, where an "actor" is an object, a green thread, and an MPSC queue, all bundled together into a single conceptual unit. These MPSC queues are the only synchronization primitive; there aren't mutexes (which means that Pony programs can't internally deadlock, though they can livelock). For this reason, for any given reference (pointer) to a piece of data, you can have any two of mutation, aliasing, and concurrency (i.e., sending the reference to another actor's queue, which doesn't count as mutating the actor). But you can't have all three, because that would allow data races.

Consequently, three "reference capabilities" fall out of this design:

- "iso": allows mutation and concurrency, but not aliasing.

- "val": allows aliasing and concurrency, but not mutation.

- "ref": allows mutation and aliasing, but not concurrency.

The other three are more for generic kinds of programming or to facilitate more complicated tricks:

- "box": only allows aliasing, without mutation or concurrency. Subtype of both val and ref.

- "trn": allows mutation and aliasing, but the aliases are box and so don't themselves allow mutation. Also, you can subsequently change it to either ref or val, to get either mutable aliasing or concurrency (but not both).

- "tag": allows aliasing and concurrency, but not mutation, and (unlike any of the others) also doesn't allow reading the data. The only things you can do are pointer comparisons, and sending something to the referent's queue if the referent is an actor (again, this doesn't count as mutating the actor). Subtype of all the other ones; they all allow tag aliases even if they don't otherwise allow aliasing.

Most of these would seem to be allowed under Rust semantics, except that Rust does not conflate references/pointers and MPSC channel ends; there's no notion of "identity" for the sending half of a MPSC channel like there seems to be for a Pony ref. But if you have one of these you can clone it and send it wherever.

The main thing you can't do on the Rust side is mutable aliasing. Most languages allow this, and Pony also allows it with ref and trn, so long as the aliasing is all within a single actor, precluding data races (though not other kinds of aliasing bugs). Rust does not allow this, in part because making it work in a memory-safe way in the presence of algebraic data types requires a runtime garbage collector, which Pony has and Rust doesn't. Some use cases for mutable aliasing are addressed by Rust's interior-mutability types like Cell and RefCell, but these have limitations compared to full unrestricted mutable aliasing.

Other than that, most of what Pony does could, in principle, be written as a library in Rust, though the lack of language-level tracing garbage collection would mean that the ergonomics would be a lot worse and you wouldn't necessarily have the same guarantees around things like deadlock prevention.

I've been working on a multithreaded interpreter language which uses a lockfree algorithm to communicate.

I also have a buggy incomplete implementation of runtime reference passing.

The idea is that you request access to some data and then receive a reference that you can read or write to then you pass the reference to the next requester.

In theory everyone can read at the same time and writers can run sequentially. And alternate between reading and writing. This should prevent data races.

I want to avoid contention and blocking and synchronization cost and complexity. I think the compiler can generate thread safe code with the right design but it is not trivially easy.

Correction: "subtype" should instead read "supertype".

Ah, ok, I had assumed there was a shared mutable version but couldn't remember. OK.

Thanks for that summary.

I'm working on a system where references can be passed around at runtime. Can references in Pony be passed around at runtime between threads?

I'm working on ideas such as:

- all threads reading or writing at the same time. This is how I think GPUs work.

- I am working how to parallelise the bank transfer problem. You have bank accounts of money and want to transfer money between them but never deduct below 0. So you need consistency on an accounts balance. I was looking at sharding the data. I want to get more than 1 million transfers a second.

This article is good. https://travisdowns.github.io/blog/2020/07/06/concurrency-co...

Worth noting that Rust also supports "Shared Ownership, Immutable" data - that's what Arc<T> gives you when T has no interior mutability, and thus implements Sync by default. (By contrast, a T with interior mutability needs explicit atomicity or synchronization, or else cannot have its access shared by multiple threads.)

This is powerful.

I'm not sure how to implement shared memory semantics in an interpreter since each interpreter has its own state.

Reply on news.ycombinator.com