[mrkeen]

> Because of those "inaccessible" rules, we can never have a readwrite reference and a readonly reference to an object at the same time.

I can't not see this as a good thing. It's almost at the level of "the only thing an ownership system does".

If my thread is operating on a struct of 4 int64s, do I now have to think about another read-only thread seeing that struct in an invalid partially-written state?

[nmsmith]

The "Group Borrowing" concept that we're discussing still imposes aliasing restrictions to prevent unsynchronized concurrent access, and also to prevent "unplanned" aliasing. For example, for the duration of a function call, the default restriction is that a mut argument can only be mutated through the argument's identifier. The caller may be holding other aliases, but the callee doesn't need to be concerned about that, because the mut argument's group is "borrowed" for the duration of the function call.

I suppose you could describe the differences from Rust as follows:

- Borrowing happens for the duration of a function call, rather than the lifetime of a reference.

- We borrow entire groups, rather than individual references.

The latter trick is what allows a function to receive mutably aliasing references. Although it receives multiple such references, it only receives one group parameter, and that is what it borrows.

Hope that makes sense!

[codedokode]

> Borrowing happens for the duration of a function call

I don't understand this part. Cannot a function store a borrowed reference into a structure that outlives the function?

[nmsmith]

Yes, functions can return non-owning references. However, those references do not "borrow" their target, in the sense that they lock others out. That is the Rust model, and OP does a great job covering its limitations.

So, with the understanding that "borrowing" means "locking others out", a group parameter borrows the group for the duration of the function call. If it borrows the group as mutable, no other group parameters can borrow the group. If it borrows the group as immutable, other group parameters are limited to borrowing the group as immutable. This is reminiscent of the Rust model, but the XOR rule applies to group parameters rather than references, and borrowing lasts the duration of a function call, rather than the lifetime of a reference.

[codedokode]

The general rule to prevent any data races (as I guess) between threads is that at any point of time there can be either one writer or multiple readers to the same object. Rust guarantees this by not allowing to have any other references if you have a read-write (mutable) reference.

Note that Rust is more strict than necessary - theoretically you can have multiple writable and readable references, but not use them simultaneously and observe the rule. But it is difficult (or even impossible) to verify during compilation so Rust doesn't allow it. C allows it but leaves verification to the author which doesn't work well and doesn't scale.

This situation can happen if you have a graph of objects. For example, in an OS you might have a Process object having references to a list of opened Files, and have a File hold reference back to Process that opened it. In this case you cannot ever have a writable reference to the Process from anywhere because Files already have multiple reading references. And Files can have only read-only references to the Process that opened them.

So you have to use only read-only references and additional structures like Cell, Arc etc. that allow safe writing through them. They are cheap, but not free and ideally we as developers want to have memory safety for free. That's the problem yet to solve.

Note that there are other ways to achieve safety:

- use C and manually verify that your program never breaks this rule - requires god level coding skills

- immutable data - after the writer finished writing, data are "frozen" and can be safely shared without any checks and no rules are broken. Very good, but modification is expensive and requires you to clone the data or use clever and complicated design (for example, if you have 10-elements array but shared a reference only to first 7 elements, you can safely append to the last 3 elements because nobody else knows about them - that's how ring buffers work). See immer C++ library for example.

- atomic variables - allow safe reading and writing at the same time, but can hold at most 8 bytes. Note that using a same variable from different CPU cores causes L1 cache line migrations which, last time I measured it, takes about 2-3 ns or ~10-15 cycles.

- mutexes - ensure rule is observed but make everyone wait. Python's approach.

- using only a single thread. JavaScript's approach. You can have multiple references but you still need to ensure they are pointing to a live object (JS solves this by using an expensive garbage collector).

And by the way if you know more methods or ideas please share them!

[titzer]

> And by the way if you know more methods or ideas please share them!

Use a transaction manager (HTM or STM). The STM is going to boil down to lockfree synchronization, logging, and retry. Transactions can fail and retry.

But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write.

> at any point of time there can be either one writer or multiple readers

Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations. At the hardware level, you can basically think that a CPU receives asynchronous updates about cache lines from other processors (potentially out of order). While technically the cache coherence protocol pushes cache lines into processors, you can't ever guarantee that one "writer" can "push" updates into all other CPUs. Instead, you have to rely on those other CPUs executing either fences or being forced to execute fences through global OS means, such as IPIs. Those other CPUs executing fences (barriers) or other atomic operations induce happens-before relations.

[codedokode]

> Time is a slippery notion in concurrency. Most language-level memory models (e.g. Java) or even hardware-level concurrency models focus on happens-before relations, which are induced by executing certain operations

You are correct, but for simplicity we can assume that the CPU executes one operation at a time and still have a valid model for reasoning about data races.

> But ultimately, all inter-thread communication boils down to programs (or libraries) using barriers for acquire/release semantics and/or using compare/swap and atomic read-modify-write.

Interesting. I read about STM and it reminded me of "modification box" algorithm for modifying immutable trees, which also uses versions. So it is another clever but complicated trick. Also it seems that it requires locking? That's not very good given that locks often need syscalls.

[titzer]

> Also it seems that it requires locking? That's not very good given that locks often need syscalls.

AFAIU in most STMs all the fast paths are implemented using lock-free algorithms with just barriers.

[codedokode]

How do you implement "commit" part safely (writing changes to the object) without locking the object?

[titzer]

One way is that the writer thread prepares a completely new copy of the object in a private area and then either compare-and-swaps a pointer to it, or executes a store with a store-store barrier (depending on details of the STM system around it).

[mrkeen]

> Also it seems that it requires locking?

STM requires locking in the same way that GC requires malloc. It gets it right so that the programmer doesn't mess it up.

[astrange]

A non-compacting GC still needs a good malloc because it needs to avoid heap fragmentation.

[wavemode]

Ideally, the rules for single-threaded references and references that are allowed to be shared across threads would be different.

[zozbot234]

That's why Cell<T> and RefCell<T> are a thing. Both allow you to mutate shared references, but disable shared access across threads. The qcell crate even includes a version of Cell/RefCell that's "branded" by a region/lifetime, just like in this proposal.

[codedokode]

As I remember, Cell only allows moving/copying data from/to cell so if you have a 128-byte object inside do you have to copy it to modify? Or this can be optimized?

[kbolino]

Yes, that's how Cell works. If you want to work with the data in place, you need a RefCell instead.

[codedokode]

But it is expensive, because it does run-time checks? Or they are optimized out?

[Measter]

RefCell does do runtime checks, but the cost is checking the counter, a conditional branch, then incrementing/decrementing the counter twice.

Because the counter is non-atomic and non-volatile the optimiser can sometimes optimise out the actual modification of the counter. It's not free, but it's not also not a huge expense.

[codedokode]

Even with a single thread you need to ensure that the object you are accessing, still exists and was not freed.

[wavemode]

If you're talking about stack objects, that's what lifetimes are for.

If you're talking about heap, you can accomplish that by restricting that the references can't be used to free or invalidate the memory. But you could still allow them to be mutable.