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
> 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
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...
More information about the Digitalmars-d