Want reasonable reference counting? Disable automatic sharing of immutable

[Andrei Alexandrescu]

On 2021-11-12 14:22, Steven Schveighoffer wrote:
> On 11/12/21 1:12 PM, Andrei Alexandrescu wrote:
>> On 2021-11-12 8:03, Timon Gehr wrote:
>>> On 12.11.21 13:31, Steven Schveighoffer wrote:
>>>>
>>>> I've come to the conclusion, in order to fix this situation, so 
>>>> `__mutable` really means mutable and `shared` is an orthogonal 
>>>> piece, you need to remove the implicit sharing of `immutable`.
>>>
>>> I agree, that would be much better.
>>
>> We discussed this a couple of times. It's interesting. Sadly at this 
>> point implicit thread sharing of immutable is so baked into the 
>> language, it would take a lot of care to extricate. It would be very 
>> difficult even for Timon or Paul.
> 
> I'm not going to fight for this, I just wanted to bring it up. But I 
> think it's pointless to try for reference counting of immutable data 
> (the long RCSlice thread), when it's obviously not immutable data.

I'm not so sure. I mean no laws of physics or even of typing are broken.

Consider as a baseline the following: there is a global synchronized 
hashtable mapping pointers to objects to pointers to reference counters. 
The table is obviously mutable. Whenever a reference to some piece of 
data is copied around, a function gets called that looks up the pointer 
to the reference count and increments it. Depending on type, the 
increment is interlocked or not.

This is correct code that typechecks and everything. The challenge is to 
make it faster. One common solution is to group together the memory for 
the counter (metadata) together with the memory for the object (data). 
For example, metadata can be placed before the data (negative offsets) 
or just after the data. Then the lookup becomes as cheap as a integral 
to pointer addition. Sure, that all does take some gnarly code that is 
not automatically verifiable, but the result is safe. All languages, no 
matter how safe, have such manipulation in their implementation.

The real challenge is figuring out exactly the minimum amount of change 
to the language specification to allow defining such a scheme.

> The only solution is to make it not mean the same as immutable does now 
> (i.e. possibly shared). The fact that `shared(immutable)` would mean the 
> same thing as `immutable` does now is a path forward, but I can 
> understand if nobody wants to do that. I happen to think most cases 
> people are not sharing their immutable data, just like they mostly 
> aren't sharing thread-local data.

Though that may be a solution, I'm not sure it's the only solution. I 
can tell it's an expensive enough solution (in terms of changes to the 
language and/or broken code) that it warrants looking for another.