Message Passing and Shared Data

[dsimcha]

On 4/11/2011 12:45 AM, Andrew Wiley wrote:
> I'm working on an application that makes use of message passing to
> separate things that need to be responsive from tasks that may take
> some time, and I'm having trouble because my message passing
> discipline isn't meshing with D's type system. I'm pretty much
> following the contract that when I send a message from one thread to
> another, the original thread doesn't store any references to the
> message or what's in it, IE ownership is transferred. The receiving
> thread may then send some of the same objects back after some
> processing, but again, ownership is transferred.
> This has the benefit that I avoid a lot of memory allocations, but it
> means that right now, I'm constructing everything as shared, then
> casting it away to populate the object, then sending the object, then
> casting shared away again in the receiver, and so on.
> The messages are generally passed around for things like requesting a
> large chunk of data that takes a while to generate and receiving
> objects from an IO thread that's decoding objects from sockets.
>
> Any suggestions as to how I could avoid doing casts everywhere and/or
> restore some sort of safety while avoiding having to reallocate every
> object I mess with? I've tried fiddling with __gshared, but couldn't
> figure out any way to use it with message passing.

This is one of the biggest weaknesses of std.concurrency's model. 
Moving, as opposed to sharing, data between threads is perfectly safe 
but is difficult/impossible to statically check, especially when 
multiple levels of pointer indirection are involved.  I understand there 
are some D3-ish proposals to deal with this by extending the type 
system.  I haven't considered these both because I want to solve the 
problem in the context of D2 and because D2's type system is already way 
too complex and I think piling more on is a terrible idea.  I've been 
thinking about ways to make moving checkable at runtime, where checking 
is simpler and less conservative.  What type of objects are you working 
with, general classes or containers?

In the case of containers whose members don't have unshared aliasing 
(i.e. are either immutable, shared or don't have pointer indirection), I 
think the solution is sealed containers and reference counting.  (For 
newcomers, a sealed container is one that does not allow escaping 
pointers/references to its members.)  A sealed container whose members 
don't have unshared aliasing can be safely moved between threads if its 
reference count is 1.  We would define a primitive called moveSend  that 
takes a sealed container by reference, checks the reference count, puts 
it in the receiving thread's message queue, destroys the sending 
thread's view, then returns.  Before we do this, though, we need a full 
set of sealed containers.

In the case of general classes, I don't have a good answer.  I think 
some answers were proposed back in the initial discussion on D's 
concurrency model, but they involved making D's type system more complex 
(not recommended).  The problem is that virtual functions could be 
overridden to escape references to class members.  It may be possible to 
make moving class instances checkable without a more complicated type 
system under some restrictive circumstances:

1.  Create a RefCounted wrapper for classes and require that the 
reference count be 1.

2.  Introspect the class to verify it's sealed:

   a.  Require that the class have no public fields.

   b.  Require that all methods be weakly pure (can't write to globals), 
return types with no unshared aliasing and take only arguments that are 
const or don't have unshared aliasing.  The last requirement prevents 
escaping the address of a member variable to a field of an argument.

   c.  This still fails miserably in the case of multiple levels of 
indirection.  We could disallow them, make them also reference counted, 
or maybe come up with some other kludge.