Making RCSlice and DIP74 work with const and immutable

Steven Schveighoffer via Digitalmars-d digitalmars-d at puremagic.com
Mon Mar 2 13:10:32 PST 2015


On 2/28/15 8:40 PM, Andrei Alexandrescu wrote:
> Tracing garbage collection can afford the luxury of e.g. mutating data
> that was immutable during its lifetime.
>
> Reference counting needs to make minute mutations to data while
> references to that data are created. In fact, it's not mutation of the
> "useful" data, the payload of a data structure; it's mutation of
> metadata, additional information about the data (i.e. a reference count
> integral).
>
> The RCOs described in DIP74 and also RCSlice discussed in this forum
> need to work properly with const and immutable. Therefore, they need a
> way to reliably define and access metadata for a data structure.
>
> One possible solution is to add a "@mutable" or "@metadata" attribute
> similar to C++'s keyword "mutable". Walter and I both dislike that
> solution because it's hamfisted and leaves too much opportunity for
> abuse - people can essentially create unbounded amounts of mutable
> payload for an object claimed to be immutable. That makes it impossible
> (or unsafe) to optimize code based on algebraic assumptions.
>
> We have a few candidates for solutions, but wanted to open with a good
> discussion first. So, how do you envision a way to define and access
> mutable metadata for objects (including immutable ones)?

So, the largest problem (already pointed out by many here), is that 
immutable is implicitly shared.

This means const must be treated as implicitly shared.

But I have an idea, not sure if it's viable or not, to try and mitigate 
this. What if, at the point of passing in a mutable or immutable item to 
a const function, opAddRef is called. Then when the function call 
returns, opRelease is called. Then during the function, you never have 
to worry about const ref counting, and you never have to worry about 
trying to atomically ref count mutable items.

This means opAddRef() const and opRelease() const would be illegal.

Of course, for shared and immutable items, you will need to deal with an 
atomic/shared count. I haven't figured out that problem yet, but I think 
Michel Fortin has some good ideas.

This leaves the only issue of creating "const" RC objects. We can just 
ban that (no sense in doing that, just create an immutable version). 
const then effectively becomes a borrowing type constructor.

Just as an aside, I know that immutable is implicitly shared because it 
does not need to be synchronized with a mutex. This makes it ideal for 
sharing. But the reality is, there are other reasons to make something 
immutable. And it poisons const in this way. Note that the array runtime 
still treats const items as thread local, not shared. This could 
potentially cause problems if you shared a tail-immutable array, and 
tried appending.

I would love to see immutable be by default thread local, and need to 
cast into shared(immutable) to be shareable. shared(immutable) is still 
pretty easy to use, since it would require no synchronization (except in 
these exceptional ways we are talking about).

One very important thing to consider here, is the optimization of pure 
functions. An immutable pointer passed into a pure function means the 
compiler can elide identical calls. This means opAddRef() immutable 
CANNOT be pure, or at least it cannot be strong pure. This really hints 
towards some sort of global hash.

But there may be a better way: What if the compiler marked a region of 
the data inside the object as "meta", and then when you called 
opAddRef() immutable, it's really calling opAddRef(Meta m) immutable. 
The way this works is:

1. The meta data is NOT EXTRACTABLE from the object any other way.
2. The meta data is ALWAYS mutable and (effectively) shared.

Essentially, this is how synchronized works too. And you can logically 
place the metadata somewhere outside the object if that makes more sense.

Just thinking out loud here...

-Steve


More information about the Digitalmars-d mailing list