This was prompted by this exchange with Paul Backus that went like this:

Me: "We never got reference counting to work in safe pure nogc code. And we don't know how. If we did, we could write a slice-like type that does everything a slice does PLUS manages its own memory. This is the real problem with containers."

Paul: "I'm pretty sure at least some of us (including Atila) know how."

===

Eduard Staniloiu (at the time a student I was mentoring) tried really hard to define a built-in slice RCSlice(T) from the following spec:

- be as close in semantics to T[] as possible, i.e. most code should be able to simply replace T[] with RCSlice!T and work unchanged
- manage its own memory by using reference counting
- work in pure code just like T[] does
- work with qualifiers like T[] does, both RCSlice!(qual T) and qual(RCSlice!T)
- work in @nogc code just like T[] does
- work in @safe code just like T[] does

We were unable to define that within the limits of D. Here are the major issues we encountered:

1. We could not make reference counting work properly in pure functions (a pure function does not mutate data, which goes against manipulating the reference count).

2. Qualifiers compound problems with interlocking: mutable data is known to be single-threaded, so no need for interlocking. Immutable data may be multi-threaded, meaning reference counting needs atomic operations. Const data has unknown origin, which means the information of how data originated (mutable or not) must be saved at runtime.

3. Safety forced the use of trusted blocks all over. Not a showstopper, but a complicating factor.

So if there are any takers on getting RCSlice off the ground, it would be very interesting.

On Monday, 8 November 2021 at 21:42:12 UTC, Andrei Alexandrescu wrote:
> - work with qualifiers like T[] does, both RCSlice!(qual T) and qual(RCSlice!T)

I think this is an incorrect requirement. A const(T) is now allowed to increase a reference count by definition.

It in theory might still allow borrowing a reference, since there'd be no net change in reference count there and thus the data can remain immutable, but if isn't statically guaranteed to be balanced, you're directly in contradiction with the const rule.

On Monday, 8 November 2021 at 21:42:12 UTC, Andrei Alexandrescu wrote:
> 1. We could not make reference counting work properly in pure functions (a pure function does not mutate data, which goes against manipulating the reference count).
>

I don't think this one is a real problem, as one can cast a function call to pure and go through this. Dirty as hell, but done properly it should work even in the face of compiler optimization based on purity. GCC or LLVM would have no problem optimizing this scafolding away.

> 2. Qualifiers compound problems with interlocking: mutable data is known to be single-threaded, so no need for interlocking. Immutable data may be multi-threaded, meaning reference counting needs atomic operations. Const data has unknown origin, which means the information of how data originated (mutable or not) must be saved at runtime.
>

shared_ptr does atomic operation all the time. The reality is that on modern machines, atomic operation are cheap *granted there is no contention*. It will certainly limit what the optimizer can do, but all in all, it's almost certainly better than keeping the info around and doing a runtime check.

> 3. Safety forced the use of trusted blocks all over. Not a showstopper, but a complicating factor.
>
> So if there are any takers on getting RCSlice off the ground, it would be very interesting.

Yes, similar to pure, a bit anoying, but workable.

I think however, you missed several massive problems:
4. Type qualifier transitivity. const RCSlice!T -> const RCSlice!(const T) conversion needs to happen transparently.
5. Head mutability. const RCSlice!(const T) -> RCSlice!(const T) conversion needs to happen transparently.
6. Safety is impossible to ensure without a runtime check at every step, because it is not possible to enforce construction in D at the moment, so destrcutors and copy constructor/postblit always need to do a runtime check for .init .

I believe 4 and 5 to be impossible in D right now, 6 can be solved using a ton of runtime checks.

On Monday, 8 November 2021 at 22:07:46 UTC, Adam Ruppe wrote:
> On Monday, 8 November 2021 at 21:42:12 UTC, Andrei Alexandrescu wrote:
>> - work with qualifiers like T[] does, both RCSlice!(qual T) and qual(RCSlice!T)
>
> I think this is an incorrect requirement. A const(T) is now allowed to increase a reference count by definition.
>
> It in theory might still allow borrowing a reference, since there'd be no net change in reference count there and thus the data can remain immutable, but if isn't statically guaranteed to be balanced, you're directly in contradiction with the const rule.

To quote Herb Sutter, because it seems to be the fashion of the day, const actually means thread safe.

This is not a joke.

On 09/11/2021 10:42 AM, Andrei Alexandrescu wrote:
> 1. We could not make reference counting work properly in pure functions (a pure function does not mutate data, which goes against manipulating the reference count).

The concern with pure for me is a bit further down the road, deallocation (extending/shrinking too). An allocator has state dependent on an external global library (i.e. kernel), there is no way around this.

pure should be @nogc effectively. We are faking it right now and that is not ok if you care about pure.

> 2. Qualifiers compound problems with interlocking: mutable data is known to be single-threaded, so no need for interlocking. Immutable data may be multi-threaded, meaning reference counting needs atomic operations. Const data has unknown origin, which means the information of how data originated (mutable or not) must be saved at runtime.

This is not true.

All pointers have an unknown origin and transitivity of thread ownership unless proven otherwise by the compiler during compilation.

Lastly, as far as I'm concerned a reference counted struct should never be const (I've gone to great lengths to make it VERY undesirable to end up with a const reference counted struct in my stuff). Deadalnix covered this with his point 5.

On 2021-11-08 17:07, Adam Ruppe wrote:
> On Monday, 8 November 2021 at 21:42:12 UTC, Andrei Alexandrescu wrote:
>> - work with qualifiers like T[] does, both RCSlice!(qual T) and qual(RCSlice!T)
> 
> I think this is an incorrect requirement. A const(T) is now allowed to increase a reference count by definition.

How do you mean "now"?

On 2021-11-08 17:15, deadalnix wrote:
> On Monday, 8 November 2021 at 21:42:12 UTC, Andrei Alexandrescu wrote:
>> 1. We could not make reference counting work properly in pure functions (a pure function does not mutate data, which goes against manipulating the reference count).
>>
> 
> I don't think this one is a real problem, as one can cast a function call to pure and go through this. Dirty as hell, but done properly it should work even in the face of compiler optimization based on purity. GCC or LLVM would have no problem optimizing this scafolding away.

If you cast to pure then same compilers will be within their rights to optimize away calls - because they're pure.

>> 2. Qualifiers compound problems with interlocking: mutable data is known to be single-threaded, so no need for interlocking. Immutable data may be multi-threaded, meaning reference counting needs atomic operations. Const data has unknown origin, which means the information of how data originated (mutable or not) must be saved at runtime.
>>
> 
> shared_ptr does atomic operation all the time. The reality is that on modern machines, atomic operation are cheap *granted there is no contention*. It will certainly limit what the optimizer can do, but all in all, it's almost certainly better than keeping the info around and doing a runtime check.

In my measurements uncontested atomic increment are 2.5x or more slower than the equivalent increment.

>> 3. Safety forced the use of trusted blocks all over. Not a showstopper, but a complicating factor.
>>
>> So if there are any takers on getting RCSlice off the ground, it would be very interesting.
> 
> Yes, similar to pure, a bit anoying, but workable.
> 
> I think however, you missed several massive problems:
> 4. Type qualifier transitivity. const RCSlice!T -> const RCSlice!(const T) conversion needs to happen transparently.
> 5. Head mutability. const RCSlice!(const T) -> RCSlice!(const T) conversion needs to happen transparently.
> 6. Safety is impossible to ensure without a runtime check at every step, because it is not possible to enforce construction in D at the moment, so destrcutors and copy constructor/postblit always need to do a runtime check for .init .
> 
> I believe 4 and 5 to be impossible in D right now, 6 can be solved using a ton of runtime checks.

To which I say, stop posting, start coding.

On 2021-11-08 17:26, rikki cattermole wrote:
> a reference counted struct should never be const

So then we're toast. If that's the case we're looking at the most important challenge to the D language right now.

On Monday, 8 November 2021 at 22:35:59 UTC, Andrei Alexandrescu wrote:
> How do you mean "now"?

errr I meant "not". since it is const, you aren't allowed to modify it or *anything* through it. that would include the ref count.

(now i know you can look it up in a global AA, using the pointer as a key into it, and fake it, so this prohibition isn't really that meaningful. but of course pure prohibits even that, so there's no winning - if modifying that refcont, either you're const and not pure, or you're pure and not const. perhaps the definition of const should change though.)

On 09/11/2021 11:40 AM, Andrei Alexandrescu wrote:
> On 2021-11-08 17:26, rikki cattermole wrote:
>> a reference counted struct should never be const
> 
> So then we're toast. If that's the case we're looking at the most important challenge to the D language right now.

I disagree with it as being the most important (empowering scope, value no runtime exceptions are at the top).

However I have thought about this quite a bit due to signatures.

In a large number of cases of alias this, its due to wanting a wrapper struct around another type that is being managed using i.e. reference counting.

So, I think what we are missing is some form of custom reference type.

A type that the compiler understands has some mutable state controlling lifetimes (that is optional) and to treat it as another type whose state is being stored on the heap some place external.

That is an observation of mine, although it would fit in well with const. Throw in ARC, that may solve our problems here.