D2 Multithreading Architecture

[Robert Jacques]

On Wed, 29 Apr 2009 21:25:32 -0400, Michel Fortin  
<michel.fortin at michelf.com> wrote:

> On 2009-04-28 15:06:32 -0400, "Robert Jacques" <sandford at jhu.edu> said:
>
>> ┌───────┬──────────────┬────────────────────┬─────────────┐
>> │ scope │ Common Super │ Unknown Allocation │ Transitive† │
>> └───────┴──────────────┴────────────────────┴─────────────┘
>> Use of the scope keyword for the common ownership-type is based upon   
>> Walter’s original escape analysis blog. However, this design is based  
>> upon  using the type system restrictions as opposed to full escape  
>> analysis to  prevent object escape. Full escape analysis would  
>> alleviate the  restrictions in rule 6.
>> Basic Rules:
>> 1) Refers to scope definitions inside a function body.
>> 2) May only be assigned at declaration
>>         scope Node!(int) n;
>>         n.next = new Node!(int)(); // Error: Possible escape
>>         n = n.next;                // Error: see relaxation of this  
>> rule  below
>
> [...]
>
>> Relaxation of Rule 2
>> Technically, only the tail of a scope type must obey rule 2).  
>> Therefore,  assigning to the head of a scope type is valid. This allows  
>> for more  imperative style programming and for things like swap to be  
>> valid,  however, I don’t know how difficult this is to implement.
>>         n = n.next;
>>         auto n2 = n;
>>         swap(n, n2);
>>         swap(n, n.next); // Error: Cannot take the reference of a scope  
>> tail
>>         Node!(int) m = new Node!(int)();
>>         swap(n, m); // Error: m is local, not scope
>
> That's basically why I suggested adding scope constrains back then. To  
> implement swap safely, you need to know that the scope of the pointer  
> you are assigning to is always smaller or equal to the scope of the  
> memory block you're feeding them with.
>
> Here's a new syntax for expressing contrains I've been thinking about:
>
> 	void swap(scope int* x, scope int* y)
> 	  scope(x = y && y = x)  // caller enforces that y is assignable to x  
> and x to y
> 	{
> 		scope(x = t && t = y) int* t;
> 		// y assignable to t and t to x; also imply that
> 		// x is assignable to y, which holds against previous constrains
>
> 		t = y;  // valid since scope(t = y)
> 		y = x;  // valid since scope(y = x)
> 		x = t;  // valid since scope(x = t)
> 	}
>
> Perhaps with simple escape analysis, the compiler could infer the scope  
> constrains of local variable t so you don't have to write it everywhere.

You know, the implementation of swap is really a bad example, since using  
a template works fine:
void swap(T)(ref T x, ref T y) {
     T t
     t = y;
     y = x;
     x = t;
}

Object a;
Object b;
shared Object c;
swap(a,b);   // Okay
swap(b,c);   // Error, template instantiation swap(local object, shared  
object)

Actually, speaking of templates, using the template system for the  
constraints might work:
void swap(scope S)(S int* x, S int* y) {
     S int* t
     t = y;
     y = x;
     x = t;
}

e.g.
void foo(scope S:U, scope U)(S Bar a, U Bar b)
v.s.
void foo(scope Bar a, scope Bar b) scope( b <= u )

Although it does lead to a code bloat issue.

The real test of the system is in its composability. What does code using  
swap look like? And how does it scale to large code bases?

Here are some specific issues:
1) You seem to assume that different ownerships are interchangable. They  
are not. Even if the data layout and member signatures are the made to be  
the same, shared objects must maintain sequential consistency (i.e. memory  
fences).
1a) Limiting object signatures to being identical makes it hard for  
library writers to make a class that can be both allocated on both the  
shared and local heaps.
2) You shouldn't rely on escape analysis to determine your function  
signature. It essentially forces you to do whole program static escape  
analysis, if you want to do it right, which is implausible. Consider  
recursive and member functions. What's the proper signature? And this  
isn't even considering the composability and forward referencing issues.