A question about move() and a rant about shared

[Stanislav Blinov]

On Friday, 24 January 2014 at 19:54:31 UTC, Dmitry Olshansky 
wrote:

> 2 unrelated questions would be better as 2 nice smaller posts.
> Just saying.

I know. Sorry if it got you irritated. I have a feeling I'll be 
coming back with questions that are based on both move() and 
"shared" tied up together, hence I posted these together too.

> Consider that std.container is an incomplete piece of work...

Understood. Thanks.

> moveFront/moveBack/moveAt is a shameful and unknown thing about 
> ranges usually kept in a basement during public talks. Ask 
> Andrei of where these things go.

Now you've got me intrigued :)

> If I understand the current direction is to go with ref T and 
> make some language
> level/compiler level changes to the escaping reference.

Escaping... where? By "go with ref T" you mean return value of 
e.g. front()?

>> struct Packet {
>>     ulong ID;
>>     ubyte[32] header;
>>     ubyte[64] data;
>> }
>>
>> Note that I do have arrays in there, but they cannot possibly 
>> introduce any aliasing, since they're static.
>
> They can. To copy the thing out of somewhere you need to reach 
> into memory area  that is shared between threads and then all 
> bets are off.
> //Example:
> shared Packet[4] buffer;

Aha, I see you responded as you went through my post :) I've got 
this case covered further down. Of course they can this way. But 
instantiating them as "shared" doesn't make sense anyway, exactly 
because they are not "shared"-aware.

> High level invariants that deal with ownership are not 
> represented in D typesystem and hence exist only in the head of 
> people writing code/comments and better be encapsulated in 
> something manageable.

But they actually are. immutable === doesn't care: share or own, 
you only ever can read it. Value type === single owner. Because 
you can only ever give away the value entirely (move() it) or a 
copy of it (which is coincidentally both shallow and deep copy). 
References (any kind thereof) === sharing. Granted, this system 
is lacking (i.e. it'd be nice to have unique references). But 
that's at least a bare base.

>> It wouldn't work, because queue expects "shared" type.
>
> Depends on how you've defined push/pop.

I'm losing you here. Without any __gshared "tricks" we have this:

shared class Queue(T) {
     private Container!T q;

     void push(T);
     T pop();
}

Note that the class Queue is "shared"-qualified, meaning that "q" 
is also "shared", meaning that (due to transitive nature of 
"shared"), the container ultimately stores shared(T). In fact, 
the definition above would even fail to compile in this case, 
because push should take shared(T) and pop should return 
shared(T) (since Queue will be dealing with a container of shared 
Ts, right?)

> The thing is that both operation either accept local Packet or 
> produce local Packet.
> void push(ref Packet p);  //copy from local memory to the queue
> Packet pop(); //pop to the local memory

> But it is intrinsic to the way queue which is local (T1) --> 
> shared --> local (T2) bridge of sorts T1, T2 being some threads.

Umm... I did post an interface of Queue, did I not? Where'd that 
"ref Packet" come from? :) push() should take an rvalue, pop() 
should return an rvalue. The fact that pushing thread managed to 
create an rvalue to push means precisely that it no longer has 
any aliases to pushed data (remember, we're talking value types 
here). Same with popping thread: as soon as it gets the value, 
Queue no longer stores it.
If Packet weren't value type (e.g. contained references), it'd 
break the first invariant I imposed in my original post and would 
fall into "must be "shared"" category.

>> One solution would be to use a cast...
>> This is ugly...
>> Convention is not a reasonable justification for overlooking 
>> type system.
>
> To simplify you put shared qualifier on type and then suddenly 
> it doesn't do magic.

:D Was I that bad at explaining? Shared qualifier doesn't do any 
magic by itself anyway, it's our task as programmers to make it 
do what it means. I.e. put synchronization where it belongs.

> Sad but you have to think at what happens where with sharing.

I do. Lately, probably too much :) That's why I posted this.

> Casts or no casts is an internal thing and sadly at the time 
> pretty much required because compiler can't grasp ownership for 
> you.

It can't, and therefore it's my task to solve. I mean, in all of 
my example the only rock-solid shared thing is the queue. The 
queue would be the object all threads access simultaneously, the 
queue would be declared somewhere as "shared(Queue) theQueue;", 
the queue would be pushed and popped and fed and milked dry of 
its contents. But the contents, each individual packet, would 
*never* be accessed by more than one thread at a time, this is by 
design in this particular case. Generalizing that design to 
"always support shared" just doesn't make sense: why would I need 
to implement shared interface (and thus, shared access and all 
that comes with it) for those Packets if they're never used 
concurrently?

>> Another solution would be to instantiate those structs as 
>> "shared" in
>> the first place.
>
> And it doesn't work nicely because they are in fact not, only 
> inside of the queue they are shared.

Eggz-actly. And even this "sharing" is purely incidental, due to 
the very nature of both such queues and this particular type 
Packet. Consider an already existing example of all that jazz 
with producer-consumer queue: std.concurrency. Only in that case 
that would be multi producer single consumer. It is perfectly 
safe to send() value types all day. You don't have to design your 
structs (or your ints :) ) as shared in order to pass them from 
one thread to another in a message. That is as long as your types 
don't have any references or pointers, which would *have* to be 
"shared".

> There you are horribly wrong. All containers need to be aware 
> of the fact that they are shared between threads else some ugly 
> things are going to happen. (Simultaneous insert and removal 
> from an shared array?)

Umm... I don't follow the logic. As you suggest further below, 
all I'm doing is designing a container type instances of which 
can be safely shared between threads. I can't build that 
container using only other "shared"-enabled types, and why should 
I? The underlying "storage" container is forever encapsulated in 
my shared one, the shared one deals with synchronization.

> In essence all you need is a locking wrapper container that 
> gives you shared interface around a mutable container or a 
> container that is shared-aware by its nature (lock-free or 
> whatever it may be inside).

Not exactly. In essence what I need is a "shared" wrapper that 
deals with all synchronization issues (not necessarily locking). 
Why does whatever it uses for *storage* have to know anything 
about sharing? Classical implementations of such queues on top of 
dlists, ring buffers, other queues...

I know that there are shared structures that can be implemented 
more efficiently entirely from scratch (Andrei proposes a couple 
as examples in TDPL, the latter being, in his own words, somewhat 
barbaric), i.e. that maintain their own storage. But that's not 
always required nor needed. If I'd reduce my Queue to single 
producer single consumer (a pipe) it can be happily built on top 
of a plain array plus a couple of pointers.

Do I understand you correctly that *everything* down to the 
lowest level should be shared-enabled, i.e. thread-safe, i.e. 
synchronized? Should Phobos just have e.g. two versions each of 
Array, DList, RBTree, you-name-it, one shared, one - not? 
Following that logic, how would you build some shared conatiner 
on top of D arrays which are by their nature not synchronized?

> The need is well recognized and you are not alone in this.

That's good to hear. That is, if I didn't lose your meaning 
completely :)

> It is. The problem with shared and immutable is that we humans 
> by our very nature expect:
>
> immutable(SomeContainer!T)
>
> to mean the same as
> ImmutableSomeContainer!T
>
> Where ImmutableSomeContainer is almost the same thing but in 
> fact is a different type that has immutable interface and 
> handles immutable data well.

I'd say that's more of a way of thinking imposed by some other 
language(s) rather than our human nature. Then again, the 
boundaries do blur sometimes :)

> Example - ImmutableVector vs Vector.
> ImmutableVector need not to known about things such as 
> capacity, has different kind of range and is a different type 
> in general not just Vector with some auto-magic restrictions 
> bolted on top of it.
>
> The same could be said about shared.

ImmutableVector is a strange concept altogether, but I understand 
what you mean here. What I still don't completely understand is 
the general message of "with "shared" everything should be 
"shared"". How can it be?