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