www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - D2 Multithreading Architecture

reply Jason House <jason.james.house gmail.com> writes:
Bartosz's latest blog implies he's settled on a design. I'm curious if that
means dmd 2.031 will finally contain the critical changes for that.

If I understand the blog cirrectly, the design (in a nutshell) is as follows:
1. Data passing between threads reqires shared, unique, or invariant
2. Shared variables will include the proper monitor to lock in order to use them
3. Shared variabled ensure sequential consistency
4. Lockless programming will be supported

Did I miss anything or get anything wrong? I know there are specific details
yet to be shared, and I tried to not elaborate on specific points.
Apr 28 2009
next sibling parent BCS <ao pathlink.com> writes:
Reply to Jason,

 Bartosz's latest blog implies he's settled on a design. I'm curious if
 that means dmd 2.031 will finally contain the critical changes for
 that.
 
 If I understand the blog cirrectly, the design (in a nutshell) is as
 follows:
 1. Data passing between threads reqires shared, unique, or invariant
 2. Shared variables will include the proper monitor to lock in order
 to use them
 3. Shared variabled ensure sequential consistency
 4. Lockless programming will be supported
 Did I miss anything or get anything wrong? I know there are specific
 details yet to be shared, and I tried to not elaborate on specific
 points.
 

#2 & #4 had better mix without to much pain. Some sort of special wormhole?
Apr 28 2009
prev sibling next sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Tue, 28 Apr 2009 08:50:10 -0400, Jason House  
<jason.james.house gmail.com> wrote:

 Bartosz's latest blog implies he's settled on a design. I'm curious if  
 that means dmd 2.031 will finally contain the critical changes for that.

 If I understand the blog cirrectly, the design (in a nutshell) is as  
 follows:
 1. Data passing between threads reqires shared, unique, or invariant
 2. Shared variables will include the proper monitor to lock in order to  
 use them
 3. Shared variabled ensure sequential consistency
 4. Lockless programming will be supported

 Did I miss anything or get anything wrong? I know there are specific  
 details yet to be shared, and I tried to not elaborate on specific  
 points.

Pretty much, although by monitor Bartosz is probably referring less to an actual lock and more to general thread-safe objects (protected via locks, STM or lock-free programming, etc). I’ve actually been working on a concurrency type system for D proposal, which has been spurred on by some previous interest and Bartosz’s blog series. Now that finals are over, I’ve polished it up a bit. I’ve included a background section for those who want to get up to speed. For those familiar with shared-local-scope, etc. please feel free to jump down to the overview. ┌────────────┐ │ Highlights │ └────────────┘ •Fixes Bug 2095 •Scope delegates do not require heap allocation (i.e. may safely behave like D 1.0). •Permits thread-local garbage collection •Permits multiple threading models. •No costly escape analysis. •No complex function constraints. ┌────────────┐ │ Background │ └────────────┘ Why a type system for concurrency? Mostly, people talk about threading models, i.e. locks, actors, message passing, which concerns themselves with how one shares state. But, consider David Callahan’s Pillars of concurrency: Isolation, Scalability and Consistency. Isolation is provided by the type system. Essentially, its job is to separate shared state from un-shared state. In general, the former has to be designed in order to prevent deadlocks, races, etc. and has to use slower techniques, such as memory fences or locks. Un-shared state, on the other hand, doesn’t require this overhead and/or can use other algorithms and is therefore faster. The type system can also allow for the garbage collector to use thread-local heaps, which increases both its performance and scalability. The type system also helps the consistency of the language (although Callahan’s meaning was specific to shared state). What’s thread local heaps? A thread local heap is just like it sounds: a heap of memory that solely belongs to a single thread. This means that: 1) a lock isn’t needed during allocation, etc. 2) collection can be run by the parent thread so there’s no expensive kernel calls, context switches, etc. 3) each thread’s heap is relatively smaller and only visible by its own stack, reducing spurious pointers and collection time. 4) collection occurs in parallel with other running threads, i.e. a worker thread may collect without pausing an interactive GUI or rendering thread. Thus they increase performance and scalability. The caveat is, that shared state doesn’t get these benefits and must use a single, shared heap. Where’s D at? Currently, a ‘shared’ and ‘scope’ type have been implemented in D 2.0, though there are no rules (or even correct error messages) associated with them yet. Walter posted on his blog a while ago about escape analysis. Escape analysis determines how and in what ways a piece of state moves between scopes, i.e. a reference to a ‘local’ class is saved to a ‘shared’ class, and if it is valid, i.e. not in this case. While possible in dynamic languages, in static languages virtual functions and function pointers generally prohibit escape analysis. Therefore, Walter suggested using the type system to document a function’s properties and there was a decent discussion about it in the newsgroup about how to do this. Notably, there was a proposal by Michel Fortin about using constraints on the relative scopes of a function’s parameters, similar to template constraints. Bartosz is currently reading/research threading models their associated concurrency type systems. He has been posting very informative blogs about them for those interested. ┌──────────────┐ │ Overview │ ├──────────────┼─────────────────┬─────────────┬──────────────┐ │ Hierarchy │ Description │ Ownership │ Transitivity │ ├──────────────┼─────────────────┼─────────────┼──────────────┤ │ scope │ super-interface │ unknown │ deep† │ │ ││└─stack │ current scope │ stack │ implicit │ │ │└──local │ object default │ local-heap │ deep† │ │ ├───shared │ thread safe │ shared-heap │ deep† │ │ └───mobile │ unique objects │ shared-heap │ shallow │ └──────────────┴─────────────────┴─────────────┴──────────────┘ This proposal concerns using five distinct ownership types to provide the same protection and almost the same flexibility as complete escape analysis. It has the advantage of not requiring complex analysis or ownership inference/propagation. The programmer also need not decorate each function call with complex constraints. ‘Scope’ acts as a common super-like interface, allowing many functions to only be written once and not a combinatorial number of times for each possible type combination. As such, it fills the same role as const does for immutable-mutable type system. However, compared to previously proposed ‘no escape’ types, it’s less conservative and the rules providing its isolation properties are listed in the section on ‘scope’ below. ‘local’ objects are restricted to the current thread while ‘shared’ objects may be shared between threads. An object with a single owner is typically referred to as being unique or ‘mobile’ and allows an object to be shared, but retain the simplicity and performance of local objects. There is also an implicit ownership class for all data located on the stack (‘stack’). This plugs several well known holes in current stack classes and prevents pointers to variables on the stack from escaping, both to the heap and to shallower locations on the stack. ‘mobile’ is similar to other unique pointer wrappers, such as in std.typecons. The principal reason for making this a language level construct, instead of the current library solution is that one of the major benefits of ‘scope’ is the ability to pass a ‘mobile’ to a function as ‘scope’ without move semantics, in many situations, making writing code easier and more generic. Classes support qualifier polymorphism, like to Boyapati and Rinard’s GRFJ (and probably others). i.e. each ownership type is considered a template parameter to the class. However, unlike GRFJ, it is a single, implicit property, and the parameters of the classes’ methods may mix and match valid ownership types as needed. Class definers must also declare which ownership classes are supported. Thus, by default a class can not be shared. This creates a strong separation between the ownership types, which results in clean isolation. †Transitivity Technically, all ownership types are shallow, as they represent the physical location of an object’s memory. Thus, using transitivity is mostly about syntactic sugar. This doesn’t reduce expressiveness as scope visibility rules always moves the scope broader. i.e. an object on the local heap can not store a reference to the stack without casting. Issues •scope(T) in a function body conflicts with scope guard statements. This is a general problem with Walter’s choice of using the scope keyword for this concept. A clean solution is to mandate the use of {} in scope guard statements. Others include using an alternative keyword(auto, final, scope!(exit)), let the ambiguity stand, add a keyword, etc. •Clear, concise ddoc documentation is an issue (Multiple entries per class (one per ownership type) vs One large interleaved entry). This is a general problem with templated classes. ┌───────┬──────────────┬────────────────────┬─────────────┐ │ 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 3) Applies to references taken from scope types scope int* value = &(n.value); 4) Implicit conversion is always fully transitive. Foo[] y; scope Foo[] x = y; 5) Mixed implicit conversion is illegal. scope(Foo)[] z = y; // Error: cannot implicitly convert... 6) Functions with (scope U) ref, out, * or return parameters are said to be scope_ escape(T) where T is U, a member return of U or subtype of U. a) Implicit conversions of stack T to scope T are illegal if a function is scope_escape(T). This prevents deep stack objects escaping to shallower contexts. b) A mobile T may be passed to a non-scope_escape(T) function _without_ movement if it is not also passed to a another, mobile parameter. 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 Relaxation of Rule 6 Rule 6 may be partially relaxed using local analysis of the function for the escape of each particular variable. Practically, this might not help much since it would have to treat called functions or receiving functions in a conservative manner, i.e. if it could happen assume it does. This is a local escape analysis system; a whole-program escape analysis system, would eliminate the need for this rule. Interfaces to Scope Objects (or structs) The interface to scope objects is automatically generated from the intersection of the public shared and local interfaces of the class. Member variables that only differ by ownership and member functions that only differ by their return’s ownership are included and considered of scope ownership. ┌───────┬──────────────┬──────────────────┬──────────┐ │ stack │ Current Scope│ Stack Allocation │ Implicit │ └───────┴──────────────┴──────────────────┴──────────┘ This is the ownership type of all things located on a thread’s stack. As the keyword stack should not be reserved, I’m choosing to not have a keyword and just have new scope(Foo) or new auto(Foo) return a stack allocated object, with a type that’s internal to the compiler. Rules: 1) Refers to all variables located on the stack. scope Foo f = new Foo(); // Old syntax. Sugar for auto temp = new auto(Foo)(); // auto used to be used for RAII (DMD 0.043) auto temp2 = new scope(Foo)(); // other possible syntax scope Foo f2 = temp; int x = 3; // Including value types 2) Shallow, does no alter the tail type int* y = new int; *y = x; 3) Applies to references taken from stack types int* z = &x; // Error: can not convert type auto(int)* to int* 4) Objects and structs use the local interface f.push(5); // Error: push is not part of the scope interface temp.push(5); // Okay, push is part of the local interface Note that this catches all of Walter’s examples from the Escape Analysis blog via rule 3: int* foo() { int x = 3; return &x; // Error: can not convert type auto(int)* to int* } int* bar(int* p) { return p; } int* foo() { int x = 3; return bar(&x); // Error: ditto } void abc(int x, int** p) { *p = &x; } // Error: ditto ┌─┬┬─────────┬────────────────┬────────────────────────┬─────────────┐ │ │└─local │ Object Default │ Local-heap Allocation │ Transitive† │ │ ├───shared │ Thread Safe │ Shared-heap Allocation │ Transitive† │ │ └──mobile │ Unique Objects │ Shared-heap Allocation │ Shallow │ └────────────┴────────────────┴────────────────────────┴─────────────┘ There are three styles of heap allocated objects: default (a.k.a. local), shared and mobile. A class is implicitly templated on each style of heap allocation and only inherits from the super type of the same style. Thus each style may have very different interfaces, though all implicitly implement the automatically generated ‘scope’ interface. Mobile references implement move semantics, with the exception of scope rule 6b. Thus mobiles do not require garbage collection themselves (though they still need to be scanned), since they can be deterministically deleted on scope exit. Class Instantiation auto a = new T(); // object allocated using the class’ default auto b = new shared(T)(); // safe shared object auto c = new mobile(T)(); // unsafe shared object, protected by move semantics Class Definitions ┌───────────────────────────────┬──────────────────────────────┬─────────┐ │ Class Definitions │ Restricted to │ Default │ ├───────────────────────────────┼──────────────────────────────┼─────────┤ │ class │ local, deprecated stack │ local │ │ scope class │ stack │ stack │ │ shared(_model_) class │ shared │ shared │ │ shared( mobile) class │ mobile │ mobile │ │ shared(_model_, mobile) class │ shared, mobile │ shared │ │ shared class │ local, shared │ local │ │ mobile class │ local, mobile │ local │ │ shared mobile class │ local, shared, mobile │ local │ │ shared scope class │ stack, local, shared │ local │ │ mobile scope class │ stack, local, mobile │ local │ │ shared mobile scope class │ stack, local, shared, mobile │ local │ │ shared(_model_) mobile class │ shared, mobile │ shared │ └───────────────────────────────┴──────────────────────────────┴─────────┘ Rules: shared(_model_, ...) defines both allocation and protection methodology. It may apply to variable, function or class definitions. Each methodology provides a set of rules and optional syntactic sugar specific to that style of thread-safe programming. This also provides a way of simply adding new styles of thread programming as they are developed. Here are some initial suggestions: ‘unsafe’ : Local/stack members are invalid. Members default to shared. ‘volatile’ : ‘unsafe’ + sequential consistency guaranteed. ‘mobile’ : ‘volatile’ + represents the mobile ownership class. ‘manual’ : ‘volatile’ + no public mutable member variables. Default model. ‘atomic’ : ‘manual’ + all methods must be called from STM atomic blocks ‘synchronized’: ‘manual’ + all methods wrapped in synchronized blocks ‘actor’ : ‘manual’ + methods may only take shared or mobile parameters. Methods are automatically wrapped with the appropriate runtime backend. i.e. task creation and returning of a future/promise, etc. Conditional compilation Extensions to the is expression syntax, e.g. is(T==mobile), make scopeof(T) templates, etc possible. One possible piece of syntactic sugar, is for scope to mean scopeof(this) inside classes.
Apr 28 2009
next sibling parent reply BCS <ao pathlink.com> writes:
Reply to Robert,

 ??????????????
 ? Highlights ?
 ??????????????

I haven't seen ASCII box drawings for ages. Last time I remember seeing them was on an 8088!
Apr 28 2009
parent Georg Wrede <georg.wrede iki.fi> writes:
BCS wrote:
 Reply to Robert,
 
 ┌────────────┐
 │ Highlights │
 └────────────┘

I haven't seen ASCII box drawings for ages. Last time I remember seeing them was on an 8088!

You're behind your time: these are Unicode box drawings! :-D
Apr 29 2009
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Robert Jacques wrote:
 Repost in ascii, since utf-8 has been causing some issues.

You should know that posting a long, serious proposal here has less chances than the paper -> bottle -> ocean route. A month from now it will be forgotten. Please post in a wiki/blog/webpage. Andrei
Apr 28 2009
parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Andrei Alexandrescu wrote:
 Robert Jacques wrote:
 Repost in ascii, since utf-8 has been causing some issues.

You should know that posting a long, serious proposal here has less chances than the paper -> bottle -> ocean route. A month from now it will be forgotten. Please post in a wiki/blog/webpage. Andrei

Mostly because this teeny tiny window I read NG postings through doesn't work for long posts. Plus, Thunderbird doesn't support my Text-to-speech addon. Why not whack it up on the D wiki? -- Daniel
Apr 28 2009
parent reply Jason House <jason.james.house gmail.com> writes:
Robert Jacques Wrote:

 On Tue, 28 Apr 2009 22:12:41 -0400, Daniel Keep  
 <daniel.keep.lists gmail.com> wrote:
 
 Andrei Alexandrescu wrote:
 Robert Jacques wrote:
 Repost in ascii, since utf-8 has been causing some issues.

You should know that posting a long, serious proposal here has less chances than the paper -> bottle -> ocean route. A month from now it will be forgotten. Please post in a wiki/blog/webpage. Andrei

Mostly because this teeny tiny window I read NG postings through doesn't work for long posts. Plus, Thunderbird doesn't support my Text-to-speech addon. Why not whack it up on the D wiki? -- Daniel

I just did. :) http://www.prowiki.org/wiki4d/wiki.cgi?OwnershipTypesInD

A link to an overview of GRFJ would be helpful. The largest issue I see is using scope as any kind of output parameter. If I pass a variable in as a ref scope parameter, all type information I had must be erased. Any assignment to the head of the scope variable could be an incorrect type. For example, a local variable could be transformed into a shared variable. (both are scope inside the function call). This leads to a cascade of issues I have with the proposal, so I'll stop here and get your thoughts. Const scope isnot an issue, but I think you aim to handle more than that.
Apr 29 2009
parent Jason House <jason.james.house gmail.com> writes:
Robert Jacques Wrote:

 On Wed, 29 Apr 2009 08:53:16 -0400, Jason House  
 <jason.james.house gmail.com> wrote:
 
 Robert Jacques Wrote:

 On Tue, 28 Apr 2009 22:12:41 -0400, Daniel Keep
 <daniel.keep.lists gmail.com> wrote:

 Andrei Alexandrescu wrote:
 Robert Jacques wrote:
 Repost in ascii, since utf-8 has been causing some issues.

You should know that posting a long, serious proposal here has less chances than the paper -> bottle -> ocean route. A month from now it will be forgotten. Please post in a wiki/blog/webpage. Andrei

Mostly because this teeny tiny window I read NG postings through

 work for long posts.  Plus, Thunderbird doesn't support my
 Text-to-speech addon.

 Why not whack it up on the D wiki?

   -- Daniel

I just did. :) http://www.prowiki.org/wiki4d/wiki.cgi?OwnershipTypesInD

A link to an overview of GRFJ would be helpful. The largest issue I see is using scope as any kind of output parameter. If I pass a variable in as a ref scope parameter, all type information I had must be erased. Any assignment to the head of the scope variable could be an incorrect type. For example, a local variable could be transformed into a shared variable. (both are scope inside the function call). This leads to a cascade of issues I have with the proposal, so I'll stop here and get your thoughts. Const scope isnot an issue, but I think you aim to handle more than that.

I've adding a link to Bartosz's GRFJ summary: http://bartoszmilewski.wordpress.com/2009/03/30/generic-types-for-concurrency/ Indeed I intend to handle more than that. The simple answer is that you can not assign to a scope variable except at declaration. This is scope rule 2. But this basically prevents output parameters (for exactly the reasons you mentioned). However, I think you are referencing to the section on the relaxation of rule two, which allows limited use of output parameters. This relaxation works by recognizing that the head of scope variables _must_ exist on the stack. Thus it is safe (with a few exceptions, see scope rule 6) to swap them. However, assigning to anywhere off the stack could result in the escape you mentioned and hence is illegal: scope Node ln = myLocalNode; scope Node sn = mySharedNode; swap(sn,ln); // Okay, were are only swapping the local scope references that exist on the stack swap(sn, ln.next); // Error: Cannot take the reference of a scope tail

My gut reaction is that this is too restrictive of a limitation. If someone can't call swap(n.a, n.b) for an arbitrary non-const type n, they will complain.
Apr 29 2009
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Denis Koroskin wrote:
 The proposal sound reasonable, but it's hard to follow. I really can't 
 comment on it because I didn't fully understand it.

 I believe your proposal suffers from it, too. For example, when reading 
 an introduction, I see this:
 
 ┌──────────────┐
 │ Overview     │
 ├──────────────┼─────────────────┬─────────────┬──────────────┐
 │ Hierarchy    │ Description     │ Ownership   │ Transitivity │
 ├──────────────┼─────────────────┼─────────────┼──────────────┤
 │ scope        │ super-interface │ unknown     │ deep†        │
 │  ││└─stack   │ current scope   │ stack       │ implicit    
│
 │  │└──local   │ object default  │ local-heap  │ deep†      
 │
 │  ├───shared  │ thread safe     │ shared-heap │ deep†      
 │
 │  └───mobile  │ unique objects  │ shared-heap │ shallow     
│
 └──────────────┴─────────────────┴─────────────┴──────────────┘

You tell that you introduce 5 different qualifiers but you don't explain why are they needed. Why not 4, not 3? What problem each of them solve? All I can do is guess and be proven wrong, that's the most frustrating.

I agree. I also find the article hard to follow. I'm seeing some features discussed and all of a sudden "this solves that problem". I didn't have the time for a closer read, but I think I'll have a hard time understanding how this proposal works. Andrei
Apr 29 2009
prev sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2009-04-28 15:06:32 -0400, "Robert Jacques" <sandford 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. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Apr 29 2009
parent Michel Fortin <michel.fortin michelf.com> writes:
On 2009-04-29 22:54:20 -0400, "Robert Jacques" <sandford jhu.edu> said:

 On Wed, 29 Apr 2009 21:25:32 -0400, Michel Fortin  
 <michel.fortin michelf.com> wrote:
 
 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; }

You know, all functions could be made templates and it'd solve all our problems. Why aren't we doing that? Seriously, templates can't be the answer to everything. What if you wanted swap as a member function of a class, and want to override it in a derived class? We need a system that works with non-templates too.
 Object a;
 Object b;
 shared Object c;
 swap(a,b);   // Okay
 swap(b,c);   // Error, template instantiation swap(local object, shared 
  object)

In the case of my function with constrains you'd get something alike: swap(b,c); // Error, 'swap' wants c (shared Object c) // to be assignable to b (local Object b) which isn't allowed. Basically, you can't copy a scope variable to another scope variable inside a function (because they may not be of the same scope and/or ownership) unless the signature includes a constrain signaling the assignement, which is then evaluated at the call site.
 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.

Where am I assuming that? How? Perhaps I'm not understanding something of your proposal, but I don't see how adding scope constrains breaks shared objects. You say you want "scope" to be the super-type of all, which means that it should accept both local and shared variables, am I right? If that's the case I was right to write variable as being scope in my swap function, so it can accept everything.
 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.

That I certainly agree with. (And I never suggested escape analysis to determine the scope of function arguments, only local variables inside the function.) -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Apr 30 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
Repost in ascii, since utf-8 has been causing some issues.

Highlights
-Fixes Bug 2095
-Scope delegates do not require heap allocation (i.e. may safely behave  
like D 1.0).
-Permits thread-local garbage collection
-Permits multiple threading models.
-No costly escape analysis.
-No complex function constraints.

Background
Why a type system for concurrency?
Mostly, people talk about threading models, i.e. locks, actors, message  
passing, which concerns themselves with how one shares state. But,  
consider David Callahan?s Pillars of concurrency: Isolation, Scalability  
and Consistency. Isolation is provided by the type system. Essentially,  
its job is to separate shared state from un-shared state. In general, the  
former has to be designed in order to prevent deadlocks, races, etc. and  
has to use slower techniques, such as memory fences or locks. Un-shared  
state, on the other hand, doesn?t require this overhead and/or can use  
other algorithms and is therefore faster. The type system can also allow  
for the garbage collector to use thread-local heaps, which increases both  
its performance and scalability. The type system also helps the  
consistency of the language (although Callahan?s meaning was specific to  
shared state).

What?s thread local heaps?
A thread local heap is just like it sounds: a heap of memory that solely  
belongs to a single thread. This means that: 1) a lock isn?t needed during  
allocation, etc. 2) collection can be run by the parent thread so there?s  
no expensive kernel calls, context switches, etc. 3) each thread?s heap is  
relatively smaller and only visible by its own stack, reducing spurious  
pointers and collection time. 4) collection occurs in parallel with other  
running threads, i.e. a worker thread may collect without pausing an  
interactive GUI or rendering thread. Thus they increase performance and  
scalability. The caveat is, that shared state doesn?t get these benefits  
and must use a single, shared heap.

Where?s D at?
Currently, a ?shared? and ?scope? type have been implemented in D 2.0,  
though there are no rules (or even correct error messages) associated with  
them yet. Walter posted on his blog a while ago about escape analysis.  
Escape analysis determines how and in what ways a piece of state moves  
between scopes, i.e. a reference to a ?local? class is saved to a ?shared?  
class, and if it is valid, i.e. not in this case. While possible in  
dynamic languages, in static languages virtual functions and function  
pointers generally prohibit escape analysis. Therefore, Walter suggested  
using the type system to document a function?s properties and there was a  
decent discussion about it in the newsgroup about how to do this. Notably,  
there was a proposal by Michel Fortin about using constraints on the  
relative scopes of a function?s parameters, similar to template  
constraints. Bartosz is currently reading/research threading models their  
associated concurrency type systems. He has been posting very informative  
blogs about them for those interested.

Overview

Hierarchy	Description		Ownership	Transitivity
scope		super-interface		unknown		deep*
stack		current scope		stack		implicit
local		object default		local-heap	deep*
shared		thread safe		shared-heap	deep*
mobile		unique objects		shared-heap	shallow

This proposal concerns using five distinct ownership types to provide the  
same protection and almost the same flexibility as complete escape  
analysis. It has the advantage of not requiring complex analysis or  
ownership inference/propagation. The programmer also need not decorate  
each function call with complex constraints. ?Scope? acts as a common  
super-like interface, allowing many functions to only be written once and  
not a combinatorial number of times for each possible type combination. As  
such, it fills the same role as const does for immutable-mutable type  
system. However, compared to previously proposed ?no escape? types, it?s  
less conservative and the rules providing its isolation properties are  
listed in the section on ?scope? below. ?local? objects are restricted to  
the current thread while ?shared? objects may be shared between threads.  
An object with a single owner is typically referred to as being unique or  
?mobile? and allows an object to be shared, but retain the simplicity and  
performance of local objects. There is also an implicit ownership class  
for all data located on the stack (?stack?).
This plugs several well known holes in current stack classes and prevents  
pointers to variables on the stack from escaping, both to the heap and to  
shallower locations on the stack. ?mobile? is similar to other unique  
pointer wrappers, such as in std.typecons. The principal reason for making  
this a language level construct, instead of the current library solution  
is that one of the major benefits of ?scope? is the ability to pass a  
?mobile? to a function as ?scope? without move semantics, in many  
situations, making writing code easier and more generic.
Classes support qualifier polymorphism, like to Boyapati and Rinard?s GRFJ  
(and probably others). i.e. each ownership type is considered a template  
parameter to the class. However, unlike GRFJ, it is a single, implicit  
property, and the parameters of the classes? methods may mix and match  
valid ownership types as needed. Class definers must also declare which  
ownership classes are supported. Thus, by default a class can not be  
shared. This creates a strong separation between the ownership types,  
which results in clean isolation.

*Transitivity
Technically, all ownership types are shallow, as they represent the  
physical location of an object?s memory. Thus, using transitivity is  
mostly about syntactic sugar. This doesn?t reduce expressiveness as scope  
visibility rules always moves the scope broader. i.e. an object on the  
local heap can not store a reference to the stack without casting.

Issues
?scope(T) in a function body conflicts with scope guard statements. This  
is a general problem with Walter?s choice of using the scope keyword for  
this concept. A clean solution is to mandate the use of {} in scope guard  
statements. Others include using an alternative keyword(auto, final,  
scope!(exit)), let the ambiguity stand, add a keyword, etc.
?Clear, concise ddoc documentation is an issue (Multiple entries per class  
(one per ownership type) vs One large interleaved entry). This is a  
general problem with templated classes.

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
3) Applies to references taken from scope types
        scope int* value = &(n.value);
4) Implicit conversion is always fully transitive.
        Foo[] y;
        scope Foo[]  x = y;
5) Mixed implicit conversion is illegal.
        scope(Foo)[] z = y; // Error: cannot implicitly convert...
6) Functions with (scope U) ref, out, * or return parameters are said to  
be scope_ escape(T) where T is U, a member return of U or subtype of U.
    a) Implicit conversions of stack T to scope T are illegal if a function  
is scope_escape(T). This prevents deep stack objects escaping to shallower  
contexts.
    b) A mobile T may be passed to a non-scope_escape(T) function _without_  
movement if it is not also passed to a another, mobile parameter.

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

Relaxation of Rule 6
Rule 6 may be partially relaxed using local analysis of the function for  
the escape of each particular variable. Practically, this might not help  
much since it would have to treat called functions or receiving functions  
in a conservative manner, i.e. if it could happen assume it does. This is  
a local escape analysis system; a whole-program escape analysis system,  
would eliminate the need for this rule.

Interfaces to Scope Objects (or structs)
The interface to scope objects is automatically generated from the  
intersection of the public shared and local interfaces of the class.  
Member variables that only differ by ownership and member functions that  
only differ by their return?s ownership are included and considered of  
scope ownership.

stack 	 Current Scope	 Stack Allocation 	 Implicit
This is the ownership type of all things located on a thread?s stack. As  
the keyword stack should not be reserved, I?m choosing to not have a  
keyword and just have new scope(Foo) or new auto(Foo) return a stack  
allocated object, with a type that?s internal to the compiler.
Rules:
1) Refers to all variables located on the stack.
        scope Foo f  = new Foo();        // Old syntax. Sugar for
        auto  temp   = new auto(Foo)();  // auto used to be used for RAII  
(DMD 0.043)
        auto  temp2  = new scope(Foo)(); // other possible syntax
        scope Foo f2 = temp;
        int x        = 3;                // Including value types
2) Shallow, does no alter the tail type
        int* y = new int;
            *y = x;
3) Applies to references taken from stack types
        int* z = &x;                    // Error: can not convert type  
auto(int)* to int*
4) Objects and structs use the local interface
        f.push(5);                      // Error: push is not part of the  
scope interface
        temp.push(5);                   // Okay, push is part of the local  
interface

Note that this catches all of Walter?s examples from the Escape Analysis  
blog via rule 3:
        int* foo()
        {
            int x = 3;
            return &x;                  // Error: can not convert type  
auto(int)* to int*
        }

        int* bar(int* p) { return p; }
        int* foo()
        {
            int x = 3;
            return bar(&x);             // Error: ditto
        }

        void abc(int x, int** p) { *p = &x; } // Error: ditto

local	Object Default	Local-heap  Allocation	Transitive*
shared	Thread Safe	Shared-heap Allocation	Transitive*
mobile	Unique Objects	Shared-heap Allocation	Shallow
There are three styles of heap allocated objects: default (a.k.a. local),  
shared and mobile. A class is implicitly templated on each style of heap  
allocation and only inherits from the super type of the same style. Thus  
each style may have very different interfaces, though all implicitly  
implement the automatically generated ?scope? interface. Mobile references  
implement move semantics, with the exception of scope rule 6b. Thus  
mobiles do not require garbage collection themselves (though they still  
need to be scanned), since they can be deterministically deleted on scope  
exit.

Class Instantiation
    auto a = new T();         // object allocated using the class? default
    auto b = new shared(T)(); //   safe shared object
    auto c = new mobile(T)(); // unsafe shared object, protected by move  
semantics

Class Definitions
Class Definitions -> Restricted to [Default owner]
class, local -> deprecated stack [local]
scope class -> stack [stack]
shared(_model_) class -> shared [shared]
shared( mobile) class -> mobile [mobile]
shared(_model_, mobile) class -> shared, mobile [shared]
shared class -> local, shared [local]
mobile class -> local, mobile [local]
shared mobile class -> local, shared, mobile [local]
shared scope class -> stack, local, shared [local]
mobile scope class -> stack, local, mobile [local]
shared mobile scope class -> stack, local, shared, mobile [local]
shared(_model_) mobile  class -> shared, mobile [shared]

Rules:
shared(_model_, ...) defines both allocation and protection methodology.  
It may apply to variable, function or class definitions. Each methodology  
provides a set of rules and optional syntactic sugar specific to that  
style of thread-safe programming. This also provides a way of simply  
adding new styles of thread programming as they are developed. Here are  
some initial suggestions:
  ?unsafe?      : Local/stack members are invalid. Members default to  
shared.
  ?volatile?    : ?unsafe? + sequential consistency guaranteed.
  ?mobile?      : ?volatile? + represents the mobile ownership class.
  ?manual?      : ?volatile? + no public mutable member variables. Default  
model.
  ?atomic?      : ?manual? + all methods must be called from STM atomic  
blocks
  ?synchronized?: ?manual? + all methods wrapped in synchronized blocks
  ?actor?       : ?manual? + methods may only take shared or mobile  
parameters. Methods are automatically wrapped with the appropriate runtime  
backend. i.e. task creation and returning of a future/promise, etc.

Conditional compilation
Extensions to the is expression syntax, e.g. is(T==mobile), make  
scopeof(T) templates, etc possible. One possible piece of syntactic sugar,  
is for scope to mean scopeof(this) inside classes.
Apr 28 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
Repost without utf-8, attemp 2.

Highlights
-Fixes Bug 2095
-Scope delegates do not require heap allocation (i.e. may safely behave  
like D 1.0).
-Permits thread-local garbage collection
-Permits multiple threading models.
-No costly escape analysis.
-No complex function constraints.

Background
Why a type system for concurrency?
Mostly, people talk about threading models, i.e. locks, actors, message  
passing, which concerns themselves with how one shares state. But,  
consider David Callahan's Pillars of concurrency: Isolation, Scalability  
and Consistency. Isolation is provided by the type system. Essentially,  
its job is to separate shared state from un-shared state. In general, the  
former has to be designed in order to prevent deadlocks, races, etc. and  
has to use slower techniques, such as memory fences or locks. Un-shared  
state, on the other hand, doesn't require this overhead and/or can use  
other algorithms and is therefore faster. The type system can also allow  
for the garbage collector to use thread-local heaps, which increases both  
its performance and scalability. The type system also helps the  
consistency of the language (although Callahan's meaning was specific to  
shared state).

What's thread local heaps?
A thread local heap is just like it sounds: a heap of memory that solely  
belongs to a single thread. This means that: 1) a lock isn't needed during  
allocation, etc. 2) collection can be run by the parent thread so there's  
no expensive kernel calls, context switches, etc. 3) each thread's heap is  
relatively smaller and only visible by its own stack, reducing spurious  
pointers and collection time. 4) collection occurs in parallel with other  
running threads, i.e. a worker thread may collect without pausing an  
interactive GUI or rendering thread. Thus they increase performance and  
scalability. The caveat is, that shared state doesn't get these benefits  
and must use a single, shared heap.

Where's D at?
Currently, a 'shared' and 'scope' type have been implemented in D 2.0,  
though there are no rules (or even correct error messages) associated with  
them yet. Walter posted on his blog a while ago about escape analysis.  
Escape analysis determines how and in what ways a piece of state moves  
between scopes, i.e. a reference to a 'local' class is saved to a 'shared'  
class, and if it is valid, i.e. not in this case. While possible in  
dynamic languages, in static languages virtual functions and function  
pointers generally prohibit escape analysis. Therefore, Walter suggested  
using the type system to document a function's properties and there was a  
decent discussion about it in the newsgroup about how to do this. Notably,  
there was a proposal by Michel Fortin about using constraints on the  
relative scopes of a function's parameters, similar to template  
constraints. Bartosz is currently reading/research threading models their  
associated concurrency type systems. He has been posting very informative  
blogs about them for those interested.

Overview

Hierarchy	Description		Ownership	Transitivity
scope		super-interface		unknown		deep*
stack		current scope		stack		implicit
local		object default		local-heap	deep*
shared		thread safe		shared-heap	deep*
mobile		unique objects		shared-heap	shallow

This proposal concerns using five distinct ownership types to provide the  
same protection and almost the same flexibility as complete escape  
analysis. It has the advantage of not requiring complex analysis or  
ownership inference/propagation. The programmer also need not decorate  
each function call with complex constraints. 'Scope' acts as a common  
super-like interface, allowing many functions to only be written once and  
not a combinatorial number of times for each possible type combination. As  
such, it fills the same role as const does for immutable-mutable type  
system. However, compared to previously proposed 'no escape' types, it's  
less conservative and the rules providing its isolation properties are  
listed in the section on 'scope' below. 'local' objects are restricted to  
the current thread while 'shared' objects may be shared between threads.  
An object with a single owner is typically referred to as being unique or  
'mobile' and allows an object to be shared, but retain the simplicity and  
performance of local objects. There is also an implicit ownership class  
for all data located on the stack ('stack').
This plugs several well known holes in current stack classes and prevents  
pointers to variables on the stack from escaping, both to the heap and to  
shallower locations on the stack. 'mobile' is similar to other unique  
pointer wrappers, such as in std.typecons. The principal reason for making  
this a language level construct, instead of the current library solution  
is that one of the major benefits of 'scope' is the ability to pass a  
'mobile' to a function as 'scope' without move semantics, in many  
situations, making writing code easier and more generic.
Classes support qualifier polymorphism, like to Boyapati and Rinard's GRFJ  
(and probably others). i.e. each ownership type is considered a template  
parameter to the class. However, unlike GRFJ, it is a single, implicit  
property, and the parameters of the classes' methods may mix and match  
valid ownership types as needed. Class definers must also declare which  
ownership classes are supported. Thus, by default a class can not be  
shared. This creates a strong separation between the ownership types,  
which results in clean isolation.

*Transitivity
Technically, all ownership types are shallow, as they represent the  
physical location of an object's memory. Thus, using transitivity is  
mostly about syntactic sugar. This doesn't reduce expressiveness as scope  
visibility rules always moves the scope broader. i.e. an object on the  
local heap can not store a reference to the stack without casting.

Issues
.scope(T) in a function body conflicts with scope guard statements. This  
is a general problem with Walter's choice of using the scope keyword for  
this concept. A clean solution is to mandate the use of {} in scope guard  
statements. Others include using an alternative keyword(auto, final,  
scope!(exit)), let the ambiguity stand, add a keyword, etc.
.Clear, concise ddoc documentation is an issue (Multiple entries per class  
(one per ownership type) vs One large interleaved entry). This is a  
general problem with templated classes.

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
3) Applies to references taken from scope types
        scope int* value = &(n.value);
4) Implicit conversion is always fully transitive.
        Foo[] y;
        scope Foo[]  x = y;
5) Mixed implicit conversion is illegal.
        scope(Foo)[] z = y; // Error: cannot implicitly convert...
6) Functions with (scope U) ref, out, * or return parameters are said to  
be scope_ escape(T) where T is U, a member return of U or subtype of U.
    a) Implicit conversions of stack T to scope T are illegal if a function  
is scope_escape(T). This prevents deep stack objects escaping to shallower  
contexts.
    b) A mobile T may be passed to a non-scope_escape(T) function _without_  
movement if it is not also passed to a another, mobile parameter.

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

Relaxation of Rule 6
Rule 6 may be partially relaxed using local analysis of the function for  
the escape of each particular variable. Practically, this might not help  
much since it would have to treat called functions or receiving functions  
in a conservative manner, i.e. if it could happen assume it does. This is  
a local escape analysis system; a whole-program escape analysis system,  
would eliminate the need for this rule.

Interfaces to Scope Objects (or structs)
The interface to scope objects is automatically generated from the  
intersection of the public shared and local interfaces of the class.  
Member variables that only differ by ownership and member functions that  
only differ by their return's ownership are included and considered of  
scope ownership.

stack 	 Current Scope	 Stack Allocation 	 Implicit
This is the ownership type of all things located on a thread's stack. As  
the keyword stack should not be reserved, I'm choosing to not have a  
keyword and just have new scope(Foo) or new auto(Foo) return a stack  
allocated object, with a type that's internal to the compiler.
Rules:
1) Refers to all variables located on the stack.
        scope Foo f  = new Foo();        // Old syntax. Sugar for
        auto  temp   = new auto(Foo)();  // auto used to be used for RAII  
(DMD 0.043)
        auto  temp2  = new scope(Foo)(); // other possible syntax
        scope Foo f2 = temp;
        int x        = 3;                // Including value types
2) Shallow, does no alter the tail type
        int* y = new int;
            *y = x;
3) Applies to references taken from stack types
        int* z = &x;                    // Error: can not convert type  
auto(int)* to int*
4) Objects and structs use the local interface
        f.push(5);                      // Error: push is not part of the  
scope interface
        temp.push(5);                   // Okay, push is part of the local  
interface

Note that this catches all of Walter's examples from the Escape Analysis  
blog via rule 3:
        int* foo()
        {
            int x = 3;
            return &x;                  // Error: can not convert type  
auto(int)* to int*
        }

        int* bar(int* p) { return p; }
        int* foo()
        {
            int x = 3;
            return bar(&x);             // Error: ditto
        }

        void abc(int x, int** p) { *p = &x; } // Error: ditto

local	Object Default	Local-heap  Allocation	Transitive*
shared	Thread Safe	Shared-heap Allocation	Transitive*
mobile	Unique Objects	Shared-heap Allocation	Shallow
There are three styles of heap allocated objects: default (a.k.a. local),  
shared and mobile. A class is implicitly templated on each style of heap  
allocation and only inherits from the super type of the same style. Thus  
each style may have very different interfaces, though all implicitly  
implement the automatically generated 'scope' interface. Mobile references  
implement move semantics, with the exception of scope rule 6b. Thus  
mobiles do not require garbage collection themselves (though they still  
need to be scanned), since they can be deterministically deleted on scope  
exit.

Class Instantiation
    auto a = new T();         // object allocated using the class' default
    auto b = new shared(T)(); //   safe shared object
    auto c = new mobile(T)(); // unsafe shared object, protected by move  
semantics

Class Definitions
Class Definitions 		-> Restricted to 		[Default]
class 				-> local, deprecated stack 	[local]
scope class 			-> stack 			[stack]
shared(_model_) class 		-> shared 			[shared]
shared( mobile) class 		-> mobile 			[mobile]
shared(_model_, mobile) class 	-> shared, mobile 		[shared]
shared class 			-> local, shared 		[local]
mobile class 			-> local, mobile 		[local]
shared mobile class 		-> local, shared, mobile 	[local]
shared scope class 		-> stack, local, shared 	[local]
mobile scope class 		-> stack, local, mobile 	[local]
shared mobile scope class 	-> stack, local, shared, mobile	[local]
shared(_model_) mobile  class 	-> shared, mobile 		[shared]

Rules:
shared(_model_, ...) defines both allocation and protection methodology.  
It may apply to variable, function or class definitions. Each methodology  
provides a set of rules and optional syntactic sugar specific to that  
style of thread-safe programming. This also provides a way of simply  
adding new styles of thread programming as they are developed. Here are  
some initial suggestions:
  'unsafe'      : Local/stack members are invalid. Members default to  
shared.
  'volatile'    : 'unsafe' + sequential consistency guaranteed.
  'mobile'      : 'volatile' + represents the mobile ownership class.
  'manual'      : 'volatile' + no public mutable member variables. Default  
model.
  'atomic'      : 'manual' + all methods must be called from STM atomic  
blocks
  'synchronized': 'manual' + all methods wrapped in synchronized blocks
  'actor'       : 'manual' + methods may only take shared or mobile  
parameters. Methods are automatically wrapped with the appropriate runtime  
backend. i.e. task creation and returning of a future/promise, etc.

Conditional compilation
Extensions to the is expression syntax, e.g. is(T==mobile), make  
scopeof(T) templates, etc possible. One possible piece of syntactic sugar,  
is for scope to mean scopeof(this) inside classes.
Apr 28 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Tue, 28 Apr 2009 22:12:41 -0400, Daniel Keep  
<daniel.keep.lists gmail.com> wrote:

 Andrei Alexandrescu wrote:
 Robert Jacques wrote:
 Repost in ascii, since utf-8 has been causing some issues.

You should know that posting a long, serious proposal here has less chances than the paper -> bottle -> ocean route. A month from now it will be forgotten. Please post in a wiki/blog/webpage. Andrei

Mostly because this teeny tiny window I read NG postings through doesn't work for long posts. Plus, Thunderbird doesn't support my Text-to-speech addon. Why not whack it up on the D wiki? -- Daniel

I just did. :) http://www.prowiki.org/wiki4d/wiki.cgi?OwnershipTypesInD
Apr 28 2009
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Tue, 28 Apr 2009 23:06:32 +0400, Robert Jacques <sandford jhu.edu> wrote:

 On Tue, 28 Apr 2009 08:50:10 -0400, Jason House  
 <jason.james.house gmail.com> wrote:

 Bartosz's latest blog implies he's settled on a design. I'm curious if  
 that means dmd 2.031 will finally contain the critical changes for that.

 If I understand the blog cirrectly, the design (in a nutshell) is as  
 follows:
 1. Data passing between threads reqires shared, unique, or invariant
 2. Shared variables will include the proper monitor to lock in order to  
 use them
 3. Shared variabled ensure sequential consistency
 4. Lockless programming will be supported

 Did I miss anything or get anything wrong? I know there are specific  
 details yet to be shared, and I tried to not elaborate on specific  
 points.

Pretty much, although by monitor Bartosz is probably referring less to an actual lock and more to general thread-safe objects (protected via locks, STM or lock-free programming, etc). I’ve actually been working on a concurrency type system for D proposal, which has been spurred on by some previous interest and Bartosz’s blog series. Now that finals are over, I’ve polished it up a bit. I’ve included a background section for those who want to get up to speed. For those familiar with shared-local-scope, etc. please feel free to jump down to the overview. ┌────────────┐ │ Highlights │ └────────────┘ •Fixes Bug 2095 •Scope delegates do not require heap allocation (i.e. may safely behave like D 1.0). •Permits thread-local garbage collection •Permits multiple threading models. •No costly escape analysis. •No complex function constraints. ┌────────────┐ │ Background │ └────────────┘ Why a type system for concurrency? Mostly, people talk about threading models, i.e. locks, actors, message passing, which concerns themselves with how one shares state. But, consider David Callahan’s Pillars of concurrency: Isolation, Scalability and Consistency. Isolation is provided by the type system. Essentially, its job is to separate shared state from un-shared state. In general, the former has to be designed in order to prevent deadlocks, races, etc. and has to use slower techniques, such as memory fences or locks. Un-shared state, on the other hand, doesn’t require this overhead and/or can use other algorithms and is therefore faster. The type system can also allow for the garbage collector to use thread-local heaps, which increases both its performance and scalability. The type system also helps the consistency of the language (although Callahan’s meaning was specific to shared state). What’s thread local heaps? A thread local heap is just like it sounds: a heap of memory that solely belongs to a single thread. This means that: 1) a lock isn’t needed during allocation, etc. 2) collection can be run by the parent thread so there’s no expensive kernel calls, context switches, etc. 3) each thread’s heap is relatively smaller and only visible by its own stack, reducing spurious pointers and collection time. 4) collection occurs in parallel with other running threads, i.e. a worker thread may collect without pausing an interactive GUI or rendering thread. Thus they increase performance and scalability. The caveat is, that shared state doesn’t get these benefits and must use a single, shared heap. Where’s D at? Currently, a ‘shared’ and ‘scope’ type have been implemented in D 2.0, though there are no rules (or even correct error messages) associated with them yet. Walter posted on his blog a while ago about escape analysis. Escape analysis determines how and in what ways a piece of state moves between scopes, i.e. a reference to a ‘local’ class is saved to a ‘shared’ class, and if it is valid, i.e. not in this case. While possible in dynamic languages, in static languages virtual functions and function pointers generally prohibit escape analysis. Therefore, Walter suggested using the type system to document a function’s properties and there was a decent discussion about it in the newsgroup about how to do this. Notably, there was a proposal by Michel Fortin about using constraints on the relative scopes of a function’s parameters, similar to template constraints. Bartosz is currently reading/research threading models their associated concurrency type systems. He has been posting very informative blogs about them for those interested. ┌──────────────┐ │ Overview │ ├──────────────┼─────────────────┬─────────────┬──────────────┐ │ Hierarchy │ Description │ Ownership │ Transitivity │ ├──────────────┼─────────────────┼─────────────┼──────────────┤ │ scope │ super-interface │ unknown │ deep† │ │ ││└─stack │ current scope │ stack │ implicit │ │ │└──local │ object default │ local-heap │ deep† │ │ ├───shared │ thread safe │ shared-heap │ deep† │ │ └───mobile │ unique objects │ shared-heap │ shallow │ └──────────────┴─────────────────┴─────────────┴──────────────┘ This proposal concerns using five distinct ownership types to provide the same protection and almost the same flexibility as complete escape analysis. It has the advantage of not requiring complex analysis or ownership inference/propagation. The programmer also need not decorate each function call with complex constraints. ‘Scope’ acts as a common super-like interface, allowing many functions to only be written once and not a combinatorial number of times for each possible type combination. As such, it fills the same role as const does for immutable-mutable type system. However, compared to previously proposed ‘no escape’ types, it’s less conservative and the rules providing its isolation properties are listed in the section on ‘scope’ below. ‘local’ objects are restricted to the current thread while ‘shared’ objects may be shared between threads. An object with a single owner is typically referred to as being unique or ‘mobile’ and allows an object to be shared, but retain the simplicity and performance of local objects. There is also an implicit ownership class for all data located on the stack (‘stack’). This plugs several well known holes in current stack classes and prevents pointers to variables on the stack from escaping, both to the heap and to shallower locations on the stack. ‘mobile’ is similar to other unique pointer wrappers, such as in std.typecons. The principal reason for making this a language level construct, instead of the current library solution is that one of the major benefits of ‘scope’ is the ability to pass a ‘mobile’ to a function as ‘scope’ without move semantics, in many situations, making writing code easier and more generic. Classes support qualifier polymorphism, like to Boyapati and Rinard’s GRFJ (and probably others). i.e. each ownership type is considered a template parameter to the class. However, unlike GRFJ, it is a single, implicit property, and the parameters of the classes’ methods may mix and match valid ownership types as needed. Class definers must also declare which ownership classes are supported. Thus, by default a class can not be shared. This creates a strong separation between the ownership types, which results in clean isolation. †Transitivity Technically, all ownership types are shallow, as they represent the physical location of an object’s memory. Thus, using transitivity is mostly about syntactic sugar. This doesn’t reduce expressiveness as scope visibility rules always moves the scope broader. i.e. an object on the local heap can not store a reference to the stack without casting. Issues •scope(T) in a function body conflicts with scope guard statements. This is a general problem with Walter’s choice of using the scope keyword for this concept. A clean solution is to mandate the use of {} in scope guard statements. Others include using an alternative keyword(auto, final, scope!(exit)), let the ambiguity stand, add a keyword, etc. •Clear, concise ddoc documentation is an issue (Multiple entries per class (one per ownership type) vs One large interleaved entry). This is a general problem with templated classes. ┌───────┬──────────────┬────────────────────┬─────────────┐ │ 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

What's Node? Is it a class or a struct? It looks like it's a reference type (n = n.next), but then, you didn't construct n. Is it automatically constructed without calling "new Node!(int);"? If not, you get an acess violation (n.next = new Node!(int)();), so I assume it is. I believe you should have put Node's definition, first, and explained and implicit ctor call, if one takes place.
 3) Applies to references taken from scope types
         scope int* value = &(n.value);

So, scope T and scope T* have different meaning? scope T means that T is constructed on stack, but scope T* is essentially "a pointer to scope variable". If that's the case, it is *very* confusing, because one could expect scope T to be the same no matter T is a class, a struct or a primitive type like int or ptr. It would be better to write scope(int)* value = &(n.value); Now it's more clear that value is a pointer to a data of type int which is stored on stack. I believe that's what intended in your example.
 4) Implicit conversion is always fully transitive.
         Foo[] y;
         scope Foo[]  x = y;

I don't understand what this example does.
 5) Mixed implicit conversion is illegal.
         scope(Foo)[] z = y; // Error: cannot implicitly convert...
 6) Functions with (scope U) ref, out, * or return parameters are said to  
 be scope_ escape(T) where T is U, a member return of U or subtype of U.
     a) Implicit conversions of stack T to scope T are illegal if a  
 function is scope_escape(T). This prevents deep stack objects escaping  
 to shallower contexts.
     b) A mobile T may be passed to a non-scope_escape(T) function  
 _without_ movement if it is not also passed to a another, mobile  
 parameter.

 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

 Relaxation of Rule 6
 Rule 6 may be partially relaxed using local analysis of the function for  
 the escape of each particular variable. Practically, this might not help  
 much since it would have to treat called functions or receiving  
 functions in a conservative manner, i.e. if it could happen assume it  
 does. This is a local escape analysis system; a whole-program escape  
 analysis system, would eliminate the need for this rule.

 Interfaces to Scope Objects (or structs)
 The interface to scope objects is automatically generated from the  
 intersection of the public shared and local interfaces of the class.  
 Member variables that only differ by ownership and member functions that  
 only differ by their return’s ownership are included and considered of  
 scope ownership.

 ┌───────┬──────────────┬──────────────────┬──────────┐
 │ stack │ Current Scope│ Stack Allocation │ Implicit │
 └───────┴──────────────┴──────────────────┴──────────┘
 This is the ownership type of all things located on a thread’s stack. As  
 the keyword stack should not be reserved, I’m choosing to not have a  
 keyword and just have new scope(Foo) or new auto(Foo) return a stack  
 allocated object, with a type that’s internal to the compiler.
 Rules:
 1) Refers to all variables located on the stack.
         scope Foo f  = new Foo();        // Old syntax. Sugar for
         auto  temp   = new auto(Foo)();  // auto used to be used for  
 RAII (DMD 0.043)
         auto  temp2  = new scope(Foo)(); // other possible syntax
         scope Foo f2 = temp;
         int x        = 3;                // Including value types
 2) Shallow, does no alter the tail type
         int* y = new int;
             *y = x;
 3) Applies to references taken from stack types
         int* z = &x;                    // Error: can not convert type  
 auto(int)* to int*
 4) Objects and structs use the local interface
         f.push(5);                      // Error: push is not part of  
 the scope interface
         temp.push(5);                   // Okay, push is part of the  
 local interface

I don't understand this example. What's the difference between temp and f? They all said to be the same (see example 1). What's a difinition of push, anyway? *Please*, provide class difinition, first.
 Note that this catches all of Walter’s examples from the Escape Analysis  
 blog via rule 3:
         int* foo()
         {
             int x = 3;
             return &x;                  // Error: can not convert type  
 auto(int)* to int*
         }

         int* bar(int* p) { return p; }
         int* foo()
         {
             int x = 3;
             return bar(&x);             // Error: ditto
         }

         void abc(int x, int** p) { *p = &x; } // Error: ditto

I don't see *any* difference between scope and stack variables. Besides, both using the same keyword, scope, and essentially are the same. It's very confusing because I got no idea about the difference between them, aside from scope object being created automagically and stack object need to be constructed explicitly: scope Node!(int) n; // scope scope Foo foo = new Foo(); // stack All I can say, wtf?
 ┌─┬┬─────────┬────────────────┬────────────────────────┬─────────────┐
 │ │└─local   │ Object Default │ Local-heap  Allocation │
Transitive† │
 │ ├───shared │ Thread Safe    │ Shared-heap Allocation │
Transitive† │
 │ └──mobile  │ Unique Objects │ Shared-heap Allocation │ Shallow
    │
 └────────────┴────────────────┴────────────────────────┴─────────────┘
 There are three styles of heap allocated objects: default (a.k.a.  
 local), shared and mobile. A class is implicitly templated on each style  
 of heap allocation and only inherits from the super type of the same  
 style. Thus each style may have very different interfaces, though all  
 implicitly implement the automatically generated ‘scope’ interface.  
 Mobile references implement move semantics, with the exception of scope  
 rule 6b. Thus mobiles do not require garbage collection themselves  
 (though they still need to be scanned), since they can be  
 deterministically deleted on scope exit.

 Class Instantiation
     auto a = new T();         // object allocated using the class’  
 default
     auto b = new shared(T)(); //   safe shared object
     auto c = new mobile(T)(); // unsafe shared object, protected by move  
 semantics

 Class Definitions
 ┌───────────────────────────────┬──────────────────────────────┬─────────┐
 │       Class Definitions       │ Restricted to                │ Default
 
 │
 ├───────────────────────────────┼──────────────────────────────┼─────────┤
 │                         class │ local, deprecated stack      │ local  
 
 │
 │                   scope class │ stack                        │ stack  
 
 │
 │         shared(_model_) class │ shared                       │ shared 
 
 │
 │         shared( mobile) class │ mobile                       │ mobile 
 
 │
 │ shared(_model_, mobile) class │ shared, mobile               │ shared 
 
 │
 │                  shared class │ local, shared                │ local  
 
 │
 │                  mobile class │ local, mobile                │ local  
 
 │
 │           shared mobile class │ local, shared, mobile        │ local  
 
 │
 │            shared scope class │ stack, local, shared         │ local  
 
 │
 │            mobile scope class │ stack, local, mobile         │ local  
 
 │
 │     shared mobile scope class │ stack, local, shared, mobile │ local  
 
 │
 │ shared(_model_) mobile  class │ shared, mobile               │ shared 
 
 │
 └───────────────────────────────┴──────────────────────────────┴─────────┘

 Rules:
 shared(_model_, ...) defines both allocation and protection methodology.  
 It may apply to variable, function or class definitions. Each  
 methodology provides a set of rules and optional syntactic sugar  
 specific to that style of thread-safe programming. This also provides a  
 way of simply adding new styles of thread programming as they are  
 developed. Here are some initial suggestions:
   ‘unsafe’      : Local/stack members are invalid. Members default to  
 shared.
   ‘volatile’    : ‘unsafe’ + sequential consistency guaranteed.
   ‘mobile’      : ‘volatile’ + represents the mobile ownership class.
   ‘manual’      : ‘volatile’ + no public mutable member variables.  
 Default model.
   ‘atomic’      : ‘manual’ + all methods must be called from STM
atomic  
 blocks
   ‘synchronized’: ‘manual’ + all methods wrapped in synchronized blocks
   ‘actor’       : ‘manual’ + methods may only take shared or mobile  
 parameters. Methods are automatically wrapped with the appropriate  
 runtime backend. i.e. task creation and returning of a future/promise,  
 etc.

 Conditional compilation
 Extensions to the is expression syntax, e.g. is(T==mobile), make  
 scopeof(T) templates, etc possible. One possible piece of syntactic  
 sugar, is for scope to mean scopeof(this) inside classes.

The proposal sound reasonable, but it's hard to follow. I really can't comment on it because I didn't fully understand it. Many of my coworkers are preparing for an upcoming Game Developers Conference (КРИ, Russia) and we listen to the their talks everyday, spot errors, make some suggestions etc. And almost everyone does the same mistake: they explain solution without explaining a problem. It is very important but *really* hard to understand *why* you do something when you don't know what's a problem is. I believe your proposal suffers from it, too. For example, when reading an introduction, I see this:
 ┌──────────────┐
 │ Overview     │
 ├──────────────┼─────────────────┬─────────────┬──────────────┐
 │ Hierarchy    │ Description     │ Ownership   │ Transitivity │
 ├──────────────┼─────────────────┼─────────────┼──────────────┤
 │ scope        │ super-interface │ unknown     │ deep†        │
 │  ││└─stack   │ current scope   │ stack       │ implicit    
│
 │  │└──local   │ object default  │ local-heap  │ deep†      
 │
 │  ├───shared  │ thread safe     │ shared-heap │ deep†      
 │
 │  └───mobile  │ unique objects  │ shared-heap │ shallow     
│
 └──────────────┴─────────────────┴─────────────┴──────────────┘

You tell that you introduce 5 different qualifiers but you don't explain why are they needed. Why not 4, not 3? What problem each of them solve? All I can do is guess and be proven wrong, that's the most frustrating. Next, you tell about issues:
 •scope(T) in a function body conflicts with scope guard statements. This  
 is a general problem with Walter’s choice of using the scope keyword for  
 this concept. A clean solution is to mandate the use of {} in scope  
 guard statements. Others include using an alternative keyword(auto,  
 final, scope!(exit)), let the ambiguity stand, add a keyword, etc.

Great! You never told that "scope" keyword is used by your proposal. Without showing any line of code, it's absolutely worthless to mention keyword conflict. Issues belongs to "pros and cons" section at the end of your proposal, just before a conclusion. I also didn't understand a difference between scope and stack - that's pretty much all you explained! You gave no example of shared or mobile object, how they are used, how ownership passing occurs etc. I expected to see a rationale of these qualifiers, but there is no one. cents += 2;
Apr 29 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 29 Apr 2009 08:53:16 -0400, Jason House  
<jason.james.house gmail.com> wrote:

 Robert Jacques Wrote:

 On Tue, 28 Apr 2009 22:12:41 -0400, Daniel Keep
 <daniel.keep.lists gmail.com> wrote:

 Andrei Alexandrescu wrote:
 Robert Jacques wrote:
 Repost in ascii, since utf-8 has been causing some issues.

You should know that posting a long, serious proposal here has less chances than the paper -> bottle -> ocean route. A month from now it will be forgotten. Please post in a wiki/blog/webpage. Andrei

Mostly because this teeny tiny window I read NG postings through

 work for long posts.  Plus, Thunderbird doesn't support my
 Text-to-speech addon.

 Why not whack it up on the D wiki?

   -- Daniel

I just did. :) http://www.prowiki.org/wiki4d/wiki.cgi?OwnershipTypesInD

A link to an overview of GRFJ would be helpful. The largest issue I see is using scope as any kind of output parameter. If I pass a variable in as a ref scope parameter, all type information I had must be erased. Any assignment to the head of the scope variable could be an incorrect type. For example, a local variable could be transformed into a shared variable. (both are scope inside the function call). This leads to a cascade of issues I have with the proposal, so I'll stop here and get your thoughts. Const scope isnot an issue, but I think you aim to handle more than that.

I've adding a link to Bartosz's GRFJ summary: http://bartoszmilewski.wordpress.com/2009/03/30/generic-types-for-concurrency/ Indeed I intend to handle more than that. The simple answer is that you can not assign to a scope variable except at declaration. This is scope rule 2. But this basically prevents output parameters (for exactly the reasons you mentioned). However, I think you are referencing to the section on the relaxation of rule two, which allows limited use of output parameters. This relaxation works by recognizing that the head of scope variables _must_ exist on the stack. Thus it is safe (with a few exceptions, see scope rule 6) to swap them. However, assigning to anywhere off the stack could result in the escape you mentioned and hence is illegal: scope Node ln = myLocalNode; scope Node sn = mySharedNode; swap(sn,ln); // Okay, were are only swapping the local scope references that exist on the stack swap(sn, ln.next); // Error: Cannot take the reference of a scope tail
Apr 29 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 29 Apr 2009 09:12:52 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:
 Denis Koroskin wrote:
 The proposal sound reasonable, but it's hard to follow. I really can't  
 comment on it because I didn't fully understand it.

 I believe your proposal suffers from it, too. For example, when reading  
 an introduction, I see this:

 ┌──────────────┐
 │ Overview     │
 ├──────────────┼─────────────────┬─────────────┬──────────────┐
 │ Hierarchy    │ Description     │ Ownership   │ Transitivity │
 ├──────────────┼─────────────────┼─────────────┼──────────────┤
 │ scope        │ super-interface │ unknown     │ deep†        │
 │  ││└─stack   │ current scope   │ stack       │ implicit    
│
 │  │└──local   │ object default  │ local-heap  │ deep†      
 │
 │  ├───shared  │ thread safe     │ shared-heap │ deep†      
 │
 │  └───mobile  │ unique objects  │ shared-heap │ shallow     
│
 └──────────────┴─────────────────┴─────────────┴──────────────┘

explain why are they needed. Why not 4, not 3? What problem each of them solve? All I can do is guess and be proven wrong, that's the most frustrating.

I agree. I also find the article hard to follow. I'm seeing some features discussed and all of a sudden "this solves that problem". I didn't have the time for a closer read, but I think I'll have a hard time understanding how this proposal works.

The paragraph immediately underneath the summary table explains each type and its rational. Although in retrospect it might have been better to put the text before the table. Here’s an alternative explanation. For each memory location there’s one type 1) stack, for things allocated on the stack 2) local, for things allocated on the thread local heap 3) shared, for things allocated on the shared heap (i.e. multi-threaded objects) Then you have one common type, like const to simplify writing functions and reduce code bloat: 4) scope, the thing everything ownership type can implicitly cast to And lastly, I included a unique / mobile type for three reasons. 1) There’s a need for objects private to a shared object. These are protected by the parent shared object and don’t need or want (slow) protection of their own. Mobiles are perfect for this, but they should handle the majority of cases. 2) There is a need to cheaply pass data between threads, which mobiles are perfect for, and doing so in a library type would require relying on using unsafe types with usage conventions for safety, which is a recipe for disaster. 3) There are advantages to have the type system be aware of mobiles, with regard to generic scope functions (see scope rule 6b)
Apr 29 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 29 Apr 2009 04:26:55 -0400, Denis Koroskin <2korden gmail.com>  
wrote:
 On Tue, 28 Apr 2009 23:06:32 +0400, Robert Jacques <sandford jhu.edu>
 ┌───────┬──────────────┬────────────────────┬─────────────┐
 │ 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

What's Node? Is it a class or a struct?

Opps. Class. I've updated the wiki4D page with scope Node!(int) n = mySharedNode;
 I believe you should have put Node's definition, first, and explained  
 and implicit ctor call, if one takes place.

Okay.
 3) Applies to references taken from scope types
         scope int* value = &(n.value);

So, scope T and scope T* have different meaning? scope T means that T is constructed on stack, but scope T* is essentially "a pointer to scope variable". If that's the case, it is *very* confusing, because one could expect scope T to be the same no matter T is a class, a struct or a primitive type like int or ptr.

No, your confusion stems from Walter's choice to reuse the scope keyword, yet again. Logically, scope T -> scope(T) scope T* -> scope(T*) As scope is transitive.
 It would be better to write

 scope(int)* value = &(n.value);

 Now it's more clear that value is a pointer to a data of type int which  
 is stored on stack. I believe that's what intended in your example.

Though this is also correct. (Wiki code example updated)
 4) Implicit conversion is always fully transitive.
         Foo[] y;
         scope Foo[]  x = y;

I don't understand what this example does.
 5) Mixed implicit conversion is illegal.
         scope(Foo)[] z = y; // Error: cannot implicitly convert...


Rule 4 and 5 have to do with the ways arrays can create loopholes in the type system (Bug 2095, http://d.puremagic.com/issues/show_bug.cgi?id=2095) Adding a link in the wiki.
 4) Objects and structs use the local interface
         f.push(5);                      // Error: push is not part of  
 the scope interface
         temp.push(5);                   // Okay, push is part of the  
 local interface

I don't understand this example. What's the difference between temp and f? They all said to be the same (see example 1). What's a difinition of push, anyway? *Please*, provide class difinition, first.

Opps. My example is completly wrong. *Sigh* How's this. auto sf = new auto(Stack!(Foo))(); // declared as class Stack(T) {}, stack interface defaults auto f1 = new Foo(); auto f2 = new auto(Foo)(); sf.push(f1); // Okay, push(local Foo) is defined sf.push(f2); // Error: push(stack Foo) is is not defined, use a scope class declaration instead And I need to work on clearer examples...
 Note that this catches all of Walter’s examples from the Escape  
 Analysis blog via rule 3:
         int* foo()
         {
             int x = 3;
             return &x;                  // Error: can not convert type  
 auto(int)* to int*
         }

         int* bar(int* p) { return p; }
         int* foo()
         {
             int x = 3;
             return bar(&x);             // Error: ditto
         }

         void abc(int x, int** p) { *p = &x; } // Error: ditto

I don't see *any* difference between scope and stack variables. Besides, both using the same keyword, scope, and essentially are the same. It's very confusing because I got no idea about the difference between them, aside from scope object being created automagically and stack object need to be constructed explicitly: scope Node!(int) n; // scope scope Foo foo = new Foo(); // stack All I can say, wtf?

Honestly, I seriously though of using final instead of scope to avoid just this confusion. But I decided to follow Walter's choice. (Besides it's more intuitive). scope Foo foo = new Foo(); // Foo is a of type scope and has been allocated on the stack. (see rule 1) auto Foo f2 = new scope(Foo)(); // Foo is a of type stack and has been allocated on the stack. (see rule 1) I think scope Foo foo = new Foo(); should be probably be deprecated. (which I hinted at in the class definition section)
 The proposal sound reasonable, but it's hard to follow. I really can't  
 comment on it because I didn't fully understand it.

 Many of my coworkers are preparing for an upcoming Game Developers  
 Conference (КРИ, Russia) and we listen to the their talks everyday, spot  
 errors, make some suggestions etc. And almost everyone does the same  
 mistake: they explain solution without explaining a problem. It is very  
 important but *really* hard to understand *why* you do something when  
 you don't know what's a problem is.

 I believe your proposal suffers from it, too. For example, when reading  
 an introduction, I see this:

 ┌──────────────┐
 │ Overview     │
 ├──────────────┼─────────────────┬─────────────┬──────────────┐
 │ Hierarchy    │ Description     │ Ownership   │ Transitivity │
 ├──────────────┼─────────────────┼─────────────┼──────────────┤
 │ scope        │ super-interface │ unknown     │ deep†        │
 │  ││└─stack   │ current scope   │ stack       │ implicit    
│
 │  │└──local   │ object default  │ local-heap  │ deep†      
 │
 │  ├───shared  │ thread safe     │ shared-heap │ deep†      
 │
 │  └───mobile  │ unique objects  │ shared-heap │ shallow     
│
 └──────────────┴─────────────────┴─────────────┴──────────────┘

You tell that you introduce 5 different qualifiers but you don't explain why are they needed. Why not 4, not 3? What problem each of them solve? All I can do is guess and be proven wrong, that's the most frustrating. Next, you tell about issues:
 •scope(T) in a function body conflicts with scope guard statements.  
 This is a general problem with Walter’s choice of using the scope  
 keyword for this concept. A clean solution is to mandate the use of {}  
 in scope guard statements. Others include using an alternative  
 keyword(auto, final, scope!(exit)), let the ambiguity stand, add a  
 keyword, etc.

Great! You never told that "scope" keyword is used by your proposal. Without showing any line of code, it's absolutely worthless to mention keyword conflict. Issues belongs to "pros and cons" section at the end of your proposal, just before a conclusion. I also didn't understand a difference between scope and stack - that's pretty much all you explained! You gave no example of shared or mobile object, how they are used, how ownership passing occurs etc. I expected to see a rationale of these qualifiers, but there is no one. cents += 2;

Thanks a lot for the comments. They a really appreciated. I see I need to go back and do some rewriting.
Apr 29 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 29 Apr 2009 11:49:11 -0400, Jason House  
<jason.james.house gmail.com> wrote:
 Robert Jacques Wrote:
 Indeed I intend to handle more than that. The simple answer is that you
 can not assign to a scope variable except at declaration. This is scope
 rule 2. But this basically prevents output parameters (for exactly the
 reasons you mentioned). However, I think you are referencing to the
 section on the relaxation of rule two, which allows limited use of  
 output
 parameters. This relaxation works by recognizing that the head of scope
 variables _must_ exist on the stack. Thus it is safe (with a few
 exceptions, see scope rule 6) to swap them. However, assigning to  
 anywhere
 off the stack could result in the escape you mentioned and hence is
 illegal:
 scope Node ln = myLocalNode;
 scope Node sn = mySharedNode;
 swap(sn,ln);       // Okay, were are only swapping the local scope
 references that exist on the stack
 swap(sn, ln.next); // Error: Cannot take the reference of a scope tail

My gut reaction is that this is too restrictive of a limitation. If someone can't call swap(n.a, n.b) for an arbitrary non-const type n, they will complain.

I understand where you're coming from, but the whole point of having a scope type is to be a 'const' for ownership types. Just like const represents n may be immutable or mutable, scope represents n may be stack, local, shared or mobile. So I was trying to swap two objects of an arbitrary non-const type, I was trying to swap two objects of unknown and possibly different types (in this case a local and shared object, which is logically invalid). Swap is the canonical function that causes an object to escape its scope and supporting it at all is an achievement. By the way, you can call swap(n.a, n.b) for scope n, if n.a and n.b are defined as having the same non-scope ownership type in the scope interface. for example: class Node(T) { T value; Node(T) next; } has a scope interface of { T value; Node(T) next; } and shared class SL_Node(T) { T value; Node(T) next; } has a scope interface of { T value; scope Node(T) next; } so scope a = new Node!int(); scope b = new Node!int(); swap(a.next,b.next); // Okay, a.next and b.next are both of type local Node(int) swap(a,b.next); // Error, a is of type scope Node(int) auto c = new shared Node!int(); // error, writter of Node didn't declare it multi-thread aware scope c = new shared SL_Node!int(); // Okay scope d = new shared SL_Node!int(); // Okay swap(c.next,d.next); // Error, c.next and d.next are scope tails. Hmm, need to clarify this on the wiki. Another example shared class E_Node(T) { atatic if(is(this==shared)) { T* value; } else { T value; } Node(T) next; } has a scope interface of { // notice that value is missing scope Node(T) next; }
Apr 29 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Wed, 29 Apr 2009 21:25:32 -0400, Michel Fortin  
<michel.fortin michelf.com> wrote:

 On 2009-04-28 15:06:32 -0400, "Robert Jacques" <sandford 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.
Apr 29 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Thu, 30 Apr 2009 07:04:59 -0400, Michel Fortin  
<michel.fortin michelf.com> wrote:
 On 2009-04-29 22:54:20 -0400, "Robert Jacques" <sandford jhu.edu> said:

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

 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.

using a template works fine: void swap(T)(ref T x, ref T y) { T t t = y; y = x; x = t; }

You know, all functions could be made templates and it'd solve all our problems. Why aren't we doing that? Seriously, templates can't be the answer to everything. What if you wanted swap as a member function of a class, and want to override it in a derived class? We need a system that works with non-templates too.

I agree, which is why using a function where people immediately think 'shouldn't that be a template' is a bad example. By the way, using scope(x = t && t = y) int* t; implies to me that the function is templated.
 Object a;
 Object b;
 shared Object c;
 swap(a,b);   // Okay
 swap(b,c);   // Error, template instantiation swap(local object, shared  
  object)

In the case of my function with constrains you'd get something alike: swap(b,c); // Error, 'swap' wants c (shared Object c) // to be assignable to b (local Object b) which isn't allowed. Basically, you can't copy a scope variable to another scope variable inside a function (because they may not be of the same scope and/or ownership) unless the signature includes a constrain signaling the assignement, which is then evaluated at the call site.

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

Where am I assuming that? How?

Sorry. I was making assumptions based on your previous proposal of scope constraints: void swap(scope ref int* a, scope ref int* b) if ((*a).scope <= b.scope && (*b).scope <= a.scope) The <= operator implies that it is possible that an object of one ownership might get assigned to an object of a different ownership. I was also making the assumption that the scope function parameter implied templating on that ownership type, as implied by. scope(x = t && t = y) int* t; Speaking of limiting constraints to equality, how about: void swap(scope[0] ref int* x, scope[0] ref int* y) { scope[0] t; t = x; x = y; y = t; } with scope meaning any owner and scope[id] meaning the same ownertype as all the other scope[id]'s. (id is a number or identifier) Hmm... scope[>id] and scope[<id] also seem intuitive. An advantage I see with this approach is that swap composes much more easily: void bar(scope ref int* x, scope ref int* y) scope(x = y && y = x) // Possible information loss, compiler knows satisfaction, not what generated satisfaction { swap(x,y); // Does the compiler know enough to allow this call? } void bar(scope[0] ref int* x, scope[0] ref int* y) { swap(x,y); // Yes, the compiler knows x and y have the same scope }
 Perhaps I'm not understanding something of your proposal, but I don't  
 see how adding scope constrains breaks shared objects.

Adding any scope restraints other than equality, can be shared objects. See above. Perhaps this will explain my thinking better: shared class Foo {} becomes Interface __scope_Foo {} class __local_foo: __scope_Foo {} class __shared_foo: __scope_Foo {} under the hood. Even if scope is a super-type and not an interface, you can see how these two ownerships might produce incompatible classes. Of importance is that member variables are sequentially consistent on shared types vs non-shared types and that they may have different vtables, etc.
 You say you want "scope" to be the super-type of all, which means that  
 it should accept both local and shared variables, am I right? If that's  
 the case I was right to write variable as being scope in my swap  
 function, so it can accept everything.

No, I said that scope is the super-interface of all. Which would have made a difference if you were using objects instead of int*s.
 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.

That I certainly agree with. (And I never suggested escape analysis to determine the scope of function arguments, only local variables inside the function.)

Opps, I misread that.
Apr 30 2009
prev sibling parent reply Nick B <nick.barbalich gmail.com> writes:
Jason House wrote:
 Bartosz's latest blog implies he's settled on a design. I'm curious if that
means dmd 2.031 will finally contain the critical changes for that.
 
 If I understand the blog cirrectly, the design (in a nutshell) is as follows:
 1. Data passing between threads reqires shared, unique, or invariant
 2. Shared variables will include the proper monitor to lock in order to use
them
 3. Shared variabled ensure sequential consistency
 4. Lockless programming will be supported
 
 Did I miss anything or get anything wrong? I know there are specific details
yet to be shared, and I tried to not elaborate on specific points.

Back on April 29th, Jason posted this summary, above, of Bartosz's proposal. Bartosz, since then, has posted more details. This one on May 26th : http://bartoszmilewski.wordpress.com/2009/05/26/race-free-multithreading/ and this one on June 2nd http://bartoszmilewski.wordpress.com/2009/06/02/race-free-multithreading-ownership/ Now there seems to be some difference of opinion as to if Bartosz's proposal should be included in D2. So if you have been reading these posts with interest, AND you think this should be included with D2 then place your vote. Hopefully Walter, balancing all the demands on his time, will notice what the community has said it would like, and commit to include bartosz's proposal into D2 before it is finalized. Here is my vote. +1. please vote. cheers Nick B
Jun 08 2009
parent reply Jason House <jason.james.house gmail.com> writes:
Nick B Wrote:

 Jason House wrote:
 Bartosz's latest blog implies he's settled on a design. I'm curious if that
means dmd 2.031 will finally contain the critical changes for that.
 
 If I understand the blog cirrectly, the design (in a nutshell) is as follows:
 1. Data passing between threads reqires shared, unique, or invariant
 2. Shared variables will include the proper monitor to lock in order to use
them
 3. Shared variabled ensure sequential consistency
 4. Lockless programming will be supported
 
 Did I miss anything or get anything wrong? I know there are specific details
yet to be shared, and I tried to not elaborate on specific points.

Back on April 29th, Jason posted this summary, above, of Bartosz's proposal. Bartosz, since then, has posted more details. This one on May 26th : http://bartoszmilewski.wordpress.com/2009/05/26/race-free-multithreading/ and this one on June 2nd http://bartoszmilewski.wordpress.com/2009/06/02/race-free-multithreading-ownership/ Now there seems to be some difference of opinion as to if Bartosz's proposal should be included in D2. So if you have been reading these posts with interest, AND you think this should be included with D2 then place your vote.

That sounds like a biased survey...
 Hopefully Walter, balancing all the demands on his time, will notice 
 what the community has said it would like, and commit to include 
 bartosz's proposal into D2 before it is finalized.

Will a community poll be enough to convince Walter to ignore Andrei's reservations? I doubt it. As best as I can tell, Andrei has the following concerns: 1. unique types and lent will require extensive changes to code similar to the const system 2. ownership tracking will require excessive templating 3. Shared memory won't be used much and all we need is message passing The last one is used as justification to reconsider multi-threaded design. To truly get something rolling, one or more of the following need to be proven: 1. Upcoming hardware and software systems will use shared memory over message passing. 2. Message passing requires more than just unique value types or arrays to value types. (under such restrictions, library-based solutions become trivial) I have to hold my vote until a D-based design incorporating Bartosz's ideas is made. I like unique, move semantics, and lent. I worry that ownership specification will feel unnatural and that reasonable defaults for ownership and lent won't be found.
 Here is my vote. +1.
 
 
 please vote.
 
 cheers
 Nick B

Jun 08 2009
next sibling parent reply Bartosz Milewski <bartosz-nospam relisoft.com> writes:
Why don't you wait for part 3 (coming this week) which talks about templates.
You'll find it simpler than you'd expect. Let's not fight the strawman. I'm
also working on the tutorial.
Jun 08 2009
next sibling parent Jason House <jason.james.house gmail.com> writes:
Bartosz Milewski Wrote:

 Why don't you wait for part 3 (coming this week) which talks about templates.
You'll find it simpler than you'd expect. Let's not fight the strawman. I'm
also working on the tutorial.

Are you replying to me or the original poster? I thought I said I wanted to wait before casting a vote...
Jun 08 2009
prev sibling parent reply Nick B <nick.barbalich gmail.com> writes:
Bartosz Milewski wrote:
 Why don't you wait for part 3 (coming this week) which talks about templates.
You'll find it simpler than you'd expect. Let's not fight the strawman. I'm
also working on the tutorial.

Bartosz How is part 3 coming along ? Nick B.
Jun 13 2009
parent reply Nick B <nick.barbalich gmail.com> writes:
Nick B wrote:
 Bartosz Milewski wrote:
 Why don't you wait for part 3 (coming this week) which talks about 
 templates. You'll find it simpler than you'd expect. Let's not fight 
 the strawman. I'm also working on the tutorial.

Bartosz How is part 3 coming along ? Nick B.

http://bartoszmilewski.wordpress.com/ thanks Bartosz
Jun 16 2009
parent Nick B <nick.barbalich gmail.com> writes:
see below for the latest post on this subject from Bartosz.
 
 http://bartoszmilewski.wordpress.com/
 

Jun 26 2009
prev sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2009-06-08 08:43:04 -0400, Jason House <jason.james.house gmail.com> said:

 Will a community poll be enough to convince Walter to ignore Andrei's 
 reservations? I doubt it. As best as I can tell, Andrei has the 
 following concerns:
 1. unique types and lent will require extensive changes to code similar 
 to the const system
 2. ownership tracking will require excessive templating
 3. Shared memory won't be used much and all we need is message passing
 
 The last one is used as justification to reconsider multi-threaded design.
 
 To truly get something rolling, one or more of the following need to be proven:
 1. Upcoming hardware and software systems will use shared memory over 
 message passing.
 2. Message passing requires more than just unique value types or arrays 
 to value types. (under such restrictions, library-based solutions 
 become trivial)
 
 I have to hold my vote until a D-based design incorporating Bartosz's 
 ideas is made. I like unique, move semantics, and lent. I worry that 
 ownership specification will feel unnatural and that reasonable 
 defaults for ownership and lent won't be found.

Same for me, but with a little less worries. I'd sure like D to to be race-free when working with shared memory, and I expect Bartosz to come up with something good for expressing ownership. But I can't say for sure that I will like his proposal before I see it whole. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Jun 08 2009