A few thoughts on std.allocator

[Steven Schveighoffer via Digitalmars-d]

On 5/13/15 3:02 AM, Jakob Ovrum wrote:
> On Tuesday, 12 May 2015 at 17:21:04 UTC, Steven Schveighoffer wrote:
>> The one that always comes to my mind is array appending:
>>
>> immutable int[] x = new int[5];
>>
>> const int[] y = x;
>
> Do you mean:
>
> immutable(int)[] x = new int[5];
>
> const(int)[] y = x;
>
> ?
>
> Because you can't append to or reassign an immutable or const slice.

Yes, that is what I meant. Sorry.

>
>> x ~= 1; // should this lock;
>>
>> y ~= 1; // should this lock?
>
> Assuming x and y are head-mutable;
>
> Locking is needed because even though the elements themselves do not
> need locking for inspection[1], the metadata (capacity and whatever else
> is in there) is always mutable.

OK, then consider that this:

void main()
{
    string x;
    x ~= "hello";
    x ~= " world";
}

would require locking. That's unacceptable. Nobody would append with 
strings if this all required locking for no reason. The runtime 
currently does NOT lock for this case, it considers immutable and const 
to be thread-local.

> In other words, immutable(T)[] is
> implicitly convertible to immutable(T[]) which means it can be freely
> shared between threads, but when the slice refers to a druntime dynamic
> array, it *does* actually have mutable indirection.

Yeah, that's why this case is an odd duck. It's not generally allowed to 
access mutable metadata via an immutable pointer.

> Blergh, yet another
> reason why conflating slices with dynamic arrays in the type system was
> probably a bad idea. Or rather, a good reason why T[new] was a good idea
> for D2. Then again, the cost is only paid if the dynamic array features
> are actually used :)

You will never convince me of this :) T[new] was a terrible idea.

>> y = new int[5];
>>
>> y ~= 1; // should this too? If so, isn't it a waste of cycles?
>
> Yeah, it needs to lock and it is a waste... it could avoid it with some
> kind of virtual dispatch mechanism.

No, I think the answer is simpler. Introduce shared(immutable), and then 
we can distinguish between immutable data that is shared and data that 
is not shared. It also makes implementing local heaps easier. Shared 
really is orthogonal to mutability.

> Well, when the case is immutable(T)[], it's really not an odd case: in
> general you *can* grow a head-mutable container. In the case of an
> in-place append the existing elements are not touched, and in the case
> of reallocation the old elements are simply moved, which doesn't violate
> immutability either.

Right, I'm not saying it's violating immutability -- the data AFTER the 
array that's in the block is not referenced anywhere, so it's 
technically unique.

Here's something even weirder: If you append to y (const(int)[]) as a 
reference to x (immutable(int)[]), then part of the array is immutable 
and shareable, and the part that was appended is const and not shareable.

>>
>> But there are other cases. Consider a struct like this:
>>
>> struct S
>> {
>>    int a;
>>    immutable int b;
>> }
>>
>> I can create an S on the heap (or whatever allocator), and s.b could
>> be shared, but s.a could not be. How does that treat the block the
>> entire S is allocated in?
>
> As they are in the same structure, `a` and `b` will always have the same
> sharedness. In the case of immutable(S), both `a` and `b` are immutable
> and can be shared, while in the case of mutable S they are both
> unshared. I don't see it as an issue as long as S vs immutable(S) is
> provided at time of allocation.
>

This should work:

void main()
{
    auto s = new S;
    passToOtherThread(&s.b);
}

Which makes s.a unshared, and s.b shared. But the memory block needs to 
be shareable.

-Steve