A question about move() and a rant about shared

[Dmitry Olshansky]

25-Jan-2014 02:13, 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();
> }

Which is the same as:

 > class Queue(T) {
 >      shared private Container!T q;
 >
 >      void push(T) shared;
 >      T pop() shared;
 > }
>
> 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).

For functions only this pointer becomes shared. For data - yes, 
transitivity, turtles all the way down.

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

No Queue in your definition of Queue it may take local T no problem at 
all. It all depends on the contents of pop/push to understand if it 
compiles.

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

Well seeing that Packet is such a fat type, I instinctively went for 
'ref' :)

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

If the queue ultimately copies the data to its store it doesn't matter 
if there are aliases to the original thread's local packet.

 From the type system point of view there already can't be aliases in 
the queue as it's shared an the argument/return type is not :)

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

Given the interface alone it doesn't break anything. The whole "as soon 
as it gets value" is the only interesting part. There are different 
hack/tricks that could be used to make the queue go
shared --copy-> local by hand.

What I can deduce is that shared containers in general that return a 
copy may do a shallow unqual, i.e. mark one "level" of a indirections as 
not shared since it is a copy.

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

Okay.

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

Mmm as I've seen above there is no problem modeling it - that is taking 
local/mutable argument and put it into shared container.

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

You don't need shared interface for Packets to store them in a shared 
container. In this case only because of no indirections property of Packets.

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

Yes, by locking wrapper I meant exactly this. I just have no idea how 
you'd generally wrap unknown beforehand container otherwise (well there 
are spinlocks and whatnot, but still locks).

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

No, for many wrapper is enough or even all the boundary of what we could 
do. What's needed is more containers that are (by their nature) shared 
(thread-safe). See Java's ConcurrentHashMap.

> Following that logic, how would you
> build some shared conatiner on top of D arrays which are by their nature
> not synchronized?

New type with a shared interface, lock and hacks with casts inside.

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

There was a lot of confusion, partly because the problem statement was 
defined as "rant" ;) I've meant here the need for shared containers 
and/or wrappers around non-shared ones.

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

For _data_ it must else you allow low-level races.
"Everything" is bit too general a word.

-- 
Dmitry Olshansky