A question about move() and a rant about shared

Dmitry Olshansky dmitry.olsh at gmail.com
Fri Jan 24 11:54:26 PST 2014


24-Jan-2014 21:07, Stanislav Blinov пишет:
> Ok, this is going to be a long one, so please bear with me.
>
> I'll start with a question.

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

> 1. std.algorithm.move() and std.container

[snip]

> But why is there no practical way of storing such uncopyable data in
> standard
> containers? I.e. both Array and DList do try perform a copy when
> insert() is called,
> and happily fail when this(this) is @disabled. Same with access: front()
> returns
> by value, so again no luck with @disabled this(this).

Consider that std.container is an incomplete piece of work that is going 
to get
an overhaul sometime "soon". Reasons are numerous but one is that sealed 
container concept couldn't be implemented well enough back then (hence 
need to copy or explicitly move on access). The second one is that the 
lack of allocators has pretty much blocked the development of std.container.

> What is interesting though is that range interfaces for containers
> do allow for moveFront() et al., and for some containers they're even
> defined.
> So it's safe to move contents *out* but not *in*?
> Is there some deeper technical reasoning behind this that I fail to see?

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.

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

> 2. "shared" is transitive. How transitive?
>
> Declaring something as "shared" means that all its representation is
> also "shared".
> This is a good thing, right?.

It is a necessary thing.

> But in case when there are no indirections (i.e. a primitive type, or,
> more practically,
> a struct with some primitive fields and a bunch of methods that reason
> about that data
> or maybe do something with it) it all comes down to usage.
> In case of
> that queue, no two threads
> could possibly access the same data simultaneously.
> Let me define it real quick (somewhat contrived but should state the
> intent):
>
> struct Packet {
>      ulong ID;
>      ubyte[32] header;
>      ubyte[64] data;
>
>      string type() inout @property { ... }
>      ulong checkSum() inout @property { ... }
>      Variant payload() inout @property { ... }
> }
>
> 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;

There are easily races on fields ID, header and data here. 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.

> As soon as a producer pushes such value, it releases ownership of it,
> and some consumer
> later gains ownership. Remember, there are no indirections, so no two
> threads could race
> against the same data. But I cannot just declare a plain struct and then
> start
> pushing it into that queue. It wouldn't work, because queue expects
> "shared" type.

Depends on how you've defined push/pop. 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.

>
> One solution would be to use a cast. On one hand, this is feasible: such
> data is
> really only logically shared when it's somewhere "in-between" threads,
> i.e. sits in a queue.
> The "shared" queue owns the data for a moment, and thus makes the data
> iself "shared".
> As soon as a consumer pops that value off a queue, it can be cast back
> to non-"shared".

> This is ugly: it imposes certain convention in handling one "shared"
> type (the queue) with another non-"shared" one (the struct): i.e.
> "always cast when push or pop".
> 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. Sad but you have to think at what happens where with 
sharing. Casts or no casts is an internal thing and sadly at the time 
pretty much required because compiler can't grasp ownership for you.

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


> In short: I don't need that container to be "shared" at all (provided
> it's a sane container
> that doesn't do anything else with the data except for storing it).

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

>
> Therefore, final iteration of Queue would look like this:
>
> shared class Queue(T) {
>      static if (hasUnsharedAliasing!T)
>          alias shared(T) Type;
>      else
>          alias T Type;
>
>      private __gshared Container!Type q;
>
>      // still synchronized :)
>      void push(Type) { ... }
>      Type pop() { ... }
> }

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

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

> There is, however, a nag with this: __gshared is not @safe. But getting
> rid of it
> would mean only one thing: the Queue could only ever store shared(T), which
> kind of kills initial message.

Forget __gshared it's nothing but a transitive kludge.

> So, is "shared" really not as transitive as D wants it to be?

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.

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.


-- 
Dmitry Olshansky


More information about the Digitalmars-d mailing list