A few thoughts on std.allocator

[Jakob Ovrum via Digitalmars-d]

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.

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

[1] Immutable guarantees that the elements cannot be mutated from 
*any* thread, while const guarantees that the data is either 
immutable or thread-local, unless combined with shared. Remember 
that there is such a thing as shared(const(T)), but no such thing 
as shared(immutable(T)).

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

> Of course, array appending is an odd duck here, as generally 
> you are not generally able to add data to an immutable piece of 
> data.

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.

The issue is the invisible, mutable metadata that is inherent in 
D's arrays, not an issue for head-mutable containers of 
immutable/const elements in general.

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