A question about move() and a rant about shared

[Stanislav Blinov]

On Saturday, 25 January 2014 at 10:03:55 UTC, Dmitry Olshansky 
wrote:

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

It can already be inferred from the interface. The Queue uses 
some Container as storage. Obviously push()/pop() would actually 
access that storage to store/remove elements. If Container does 
not support "shared", we're in trouble.

Let's get a little more concrete:

http://dpaste.dzfl.pl/5bd15697

A dastardly simple implementation of Queue. Note that Queue is 
being designed as shared type, what it uses for storage is its 
business. However, due to transitivity of "shared", it cannot 
really use anything *but* other "shared" containers. Therefore, 
we either need casts or __gshared :(
Note that "T" for Queue is "Packet", bur for Container it's 
"shared(Packet)".

Well, ok. Let's take a step back and forget about existing 
containers. I could implement the storage myself, inside the 
Queue type, right? Something like that:

class Queue(T) {
    struct Node {
        T value;
        Node* prev, next;
    }

    private Node* head, tail;
    // Implementation follows...
}

I'd implement the whole business with doubly-linked list, maybe 
even employ some interesting algorithm to make the whole thing 
lock-free... But again, transitivity of "shared" now dictates 
that Queue can only store shared(T).

Now about this Queue type, it has a very interesting property: 
it's a shared data structure that never allows more than one 
thread access to any single stored item at a time. It allows to 
push() and pop() concurrently (well, ok, this one is blocking). 
But it does not have random access, in fact, in its public 
interface it doesn't have anything *but* push() and pop()! 
Therefore, even though the Queue is a shared type (and instances 
of it will always be shared), it can *safely* store non-shared 
data. This does not mean that it *shouldn't* store shared data, 
it just means that the transitivity of "shared" can be lifted in 
one particular case: iff !hasUnsharedAliasing!(T). That's the 
same basis upon which std.concurrency is built. And that's why I 
went through that whole business with __gshared in my original 
post :)

>> Where'd that "ref Packet" come from? :)
>
> Well seeing that Packet is such a fat type, I instinctively 
> went for 'ref' :)

Aww, 'tis not fat, just a little overweight :D

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

Eggz-actly. But this is only true for data types such as that 
Packet. If it contained pointers or references... no go.

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

You don't know that beforehand. Unlike its guts, which dictate 
that what it stores is in fact shared(T), it's interface does not 
say anything about T. T is T. Queue could be instantiated as 
Queue!(shared(FancyType)) too :)

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

Almost my thinking. In fact, there's no sense in *copying* shared 
data anyway. Moving - yes. OTOH, copying *references* to shared 
data is perfectly fine.

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

Yes, but either by using casts, or __gshared :)

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

That would depend on a container. As you've demostrated earlier, 
if a container did allow concurrent access to its items, the 
Packets could provide a world of hurt. The Queue does not allow 
such things, therefore it's indeed safe.

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

Of course it's not unknown beforehand. I've already mentioned 
that such queues could be built on top of dlists, other queues, 
ring buffers, you-name-it. But if those are not "shared", we 
again come back to all these shennanigans with casts or __gshared.

>> Do I understand you correctly that *everything* down to the 
>> lowest level
>> should be shared-enabled?..
>
> 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.

Whew :)

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

Just like the Queue from my original post :D

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

Hmm... I'll take that into my reply to your next message ;)