On Sunday, 1 March 2015 at 16:45:04 UTC, Zach the Mystic wrote:
> On Sunday, 1 March 2015 at 01:40:40 UTC, Andrei Alexandrescu wrote:
>> 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.
>
> I need to get educated on this issue. First suggestion: Just break the type system by encouraging the idiom of using casts in opAddRef and opRelease. It's too easy, but I don't know why.

Well I guess it's about optimizing code. So the question is what the optimizer needs to know, and why.

On 2015-03-01 01:40:42 +0000, Andrei Alexandrescu said:

> 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)?

Store the metadata in a global hash table.

There's a problem with reference counting immutable objects: they are implicitly shared. Any metadata attached to them thus needs to be shared. Accessing the metadata through a global shared hash table isn't going to be that much of a performance hit compared to whatever mechanism is used to synchronize access to that data.

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On Sun, Mar 01, 2015 at 03:47:36PM +0000, via Digitalmars-d wrote:
> On Sunday, 1 March 2015 at 15:08:47 UTC, H. S. Teoh wrote:
> >On Sun, Mar 01, 2015 at 01:43:44PM +0000, via Digitalmars-d wrote:
> >>On Sunday, 1 March 2015 at 06:42:02 UTC, H. S. Teoh wrote:
> >[...]
> >>>So then Const!MyClass is a modified version of MyClass where >the data fields are const (similarly, we can define Immutable for the analogous purpose) but the fields marked as metadata will >remain mutable.
> >>>
> >>>Of course, this is just a crude first stab at the problem; >I'm sure there's plenty of room for refinement to make it more usable,
> >>>>and to address some obvious roadblocks, like how to make MyClass
> >>>>>implicitly convertible to Const!MyClass, etc.. But it seems likely that >D's template machinery can actually express this in a way that >does not violate the guarantee of physical const.
> >>
> >>You still cannot access it through a const reference, though.
> >
> >The whole point is to use Const!T instead of const(T).
> 
> But that's intrusive! You can only apply it code you control, or at least you have to convince everyone to use it.

I don't see any other way of supporting logical const without violating physical const in some way. As soon as const(T) means anything other than const(T), you open up a hole in the type system and the const guarantee becomes no longer a guarantee, but a mere advisory like C++ const.


T

-- 
Let's not fight disease by killing the patient. -- Sean 'Shaleh' Perry

On Sunday, 1 March 2015 at 15:53:07 UTC, Marc Schütz wrote:
> On Sunday, 1 March 2015 at 15:28:56 UTC, Jakob Ovrum wrote:
>> However, AFAICS, it comes with a serious problem. Immutable objects are freely passable between threads, so surely an immutable RC object would need atomic counting just like a shared RC object, but unlike shared, immutable does not necessarily express the intent of sharing between threads; the immutable RC object could easily be counting atomically for nothing.
>
> Argh! I didn't think about this. Any chance we can deprecate this behaviour? It's also an obstacle for the implementation of thread-local heaps.

No way! Neither for joke, please!

---
/P

On Sunday, 1 March 2015 at 20:39:54 UTC, Michel Fortin wrote:
> There's a problem with reference counting immutable objects: they are implicitly shared. Any metadata attached to them thus needs to be shared. Accessing the metadata through a global shared hash table isn't going to be that much of a performance hit compared to whatever mechanism is used to synchronize access to that data.

But there is no difference between having metadata as part of the object and using a hash table as long as the mutable and immutable data sits on separate cache lines. (The object address is basically a hash key, and memory is a big table).

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

On 3/2/15 4:10 PM, Steven Schveighoffer wrote:

> 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.

All this, except I meant the array runtime treats both const *and* immutable items as thread-local.

-Steve

On Sunday, 1 March 2015 at 15:49:12 UTC, Jakob Ovrum wrote:
> On Sunday, 1 March 2015 at 15:40:06 UTC, Atila Neves wrote:
>> I've lost count now of how many times I've had to downgrade to auto despite always wanting immutable or const. This doesn't work:
>>
>> auto reg = regex(`(foo)`);
>> const match = "foo".matchAll(reg);
>> writeln(match.captures); //oops, captures isn't const
>>
>> It should, but it doesn't. Maxime talked about it here as well:
>>
>> http://pointersgonewild.com/2014/07/11/the-constness-problem/
>>
>> Atila
>
> `match.captures` is a range; it's only natural for a range to have mutable state to be iterable.
>
> D's const is a bridge between immutable and mutable. const has to be transitive because immutable is transitive. Don't use it as if it was C++ const: there's no logical const in D, and if there ever will be, it can't use the same `const` type qualifier.

I know why it doesn't work. I know the reasons that go into the design decision. const has to be the way it is or else thread-safety goes out of the window. I'm not talking about logical const; I'm talking about making as many things const and immutable as I can to reduce the number of things I have to keep in my mind at any given time.

const foo = getFoo(); //no need to reason about foo anymore, it won't change
auto bar = getBar(); //oh-oh, now the next 50 lines can do whatever they want with this

I shouldn't have to make captures const if all I want to do is inspect the 3rd value. And yet I do. That was just one example, like I said I've lost count of how many times I've changed const to auto in my code because it wouldn't compile otherwise. I don't go as far as Manu as use mutable everywhere, just where I have to. And I'm always annoyed when it's the case.

Atila