On Tue, 28 Apr 2009 23:06:32 +0400, Robert Jacques <[email protected]> wrote:
On Tue, 28 Apr 2009 08:50:10 -0400, Jason House
<[email protected]> 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;
