www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - isolated/owned would solve many problem we face right now.

reply "deadalnix" <deadalnix gmail.com> writes:
You know a idea is good when it can solve a large variety of 
problems and is by itself of limited complexity. I want to 
propose of of these idea today.

Everything start with this paper : 
http://research.microsoft.com/pubs/170528/msr-tr-2012-79.pdf

The paper state how microsoft is experimenting with immutable and 
isolated in C#. We already have immutable. However, we do not 
have isolated, and, strangely enough, adapted to D it can solve a 
unexpectedly large variety of issue, several of them which do not 
even exists in C#.

Let me start to sum up some of the advantages it can bring to Dn 
then I'll explains how this would work in D :
  - Transfer of ownership of data from one thread to another.
  - Convenient construction of immutable or shared objects.
  - Lock on a subtree of objects.
  - Reduce friction to use RefCounted safely.
  - Ensure safety of std.parallelism.
  - Opportunity for the compiler to insert explicit free and 
reduce GC pressure.
  - Avoid necessary array copy when slicing.
  - More optimization opportunities via alias analysis.

The whole thing at a moderate cost. We need to add an extra type 
qualifier. This isn't as bad as it seems because this type 
qualifier do NOT compose with other type qualifiers the regular, 
so we do not have a combinatorial explosion of cases to consider. 
The cost may still seems high, but considering it solves a large 
variety of recurring problem we have while adding more 
optimization opportunities, I do think it is worthwhile to pay.

This qualifier can probably be inferred in many situation by the 
compiler, but not always. For now I'll call it isolated, to mimic 
C#. I do think that owned is a nice alternative, but let's not 
make discussing that name the meat of the thread.

Before going further, I now need to introduce the concept of 
island. An island is a group of objects that can refers each 
other as well as immutable objects, they also can refers other 
island, as long as the island graph is acyclic (which is ensure 
as long as the type system isn't broken). User can have only one 
reference to one object in the island.

The compiler need to keep track of islands, but they do not need 
to be expressed explicitly. At some point in the program, a 
island can be merge with the shared, TL or immutable heap. Then 
the island cease to exist.

Each explicit use of isolated mean a new island. Each assignation 
of an isolated to something else means that the island is merged :
isolated Foo a = ...;
immutable b = a; // The island referred by a is promoted to 
immutable.

isolated Foo a = ...;
auto b = a; //  The island referred by a is promoted to Thread 
local.

isolated Foo a = ...;
struct Bar {
     Foo field;
}
isolated Bar b = ...;
b.field = a; // a's island is merged in b's island.

When an island is merged, all references to that island are 
invalidated. It means that a is not usable anymore after each 
assignations in the samples presented. It must be noted that 
passing a as a function argument will have the exact same effect.

As a result, when you manipulate an isolated, you know you are 
the only one to get a reference to it (or the type system has 
been broken).

isolated is transitive, but you'll find some subtleties compared 
to other qualifiers. Let's see how it goes :
class A {
     B mfield;
     isolated B ifield;
}

A a;
a.field; // This is isolated.

immutable A a;
a.ifield; // This is immutable.

shared A a;
a.ifield; // This is isolated.

isolated A a;
a.mfield; // This is isolated. Same island as a.
a.ifield; // This is isolated. Different island than a.

Now we have isolated object and can assign to them. But we need 
to do the operation the other around. The only way to do that is 
to swap.

A a;
B b = a.ifield; // Error, as a.ifield is not a local.
A a;
B b;
swap(b, a.ifield);  // OK, you can swap isolated.

That imply to add some unsafe black magic into swap, but it is 
100% safe to use from outside.

To be complete we need to discuss how isloated and postblit 
interact. When an isolated is passed to another isolated, 
previous references are invalidated. This means that the postblit 
do not run on isolated structs.

As the mechanism has been explain, I can explicit how it solves 
the problems mentioned above :
  - Transfer of ownership of data from one thread to another.
std.concurency can now propose function taking isolated in the 
interface. As passing a isolated as argument invalidate other 
isolated from the same island, the thread sending data 
effectively loose its ownership and can't use the data anymore.

  - Convenient construction of immutable or shared objects.
Objects can be constructed as isolated and then merged to 
immutable or shared heap.

  - Lock on a subtree of objects.
If an object own some of its subdata, it should mark them as 
isolated. Now we do not need to recursively lock on a shared 
object to use its owned internal.

  - Reduce friction to use RefCounted safely.
RefCounted can take an isolated reference when constructed. It 
can blast the whole island (and all island referred by that 
island) when the RefCount goes to 0. That make RefCounted safer 
to construct and more powerfull on what memory it can control.

  - Ensure safety of std.parallelism.
isolated(Stuff)[] can be used to run a processing on each item of 
the slice in parallel, 100% safe.

  - Opportunity for the compiler to insert explicit free and 
reduce GC pressure.
When an island is not invalidated when it goes out of scope, the 
compiler can blast the whole island and referred island.

  - Avoid necessary array copy when slicing.
It is always safe to append to an isolated slice. No need to 
allocate and copy new arrays.

  - More optimization opportunities via alias analysis.
Items from different island cannot alias each other.
Oct 11 2013
parent reply =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
Also see:
http://forum.dlang.org/thread/k7j1ta$2kv8$1 digitalmars.com
http://forum.dlang.org/thread/k831b6$1368$1 digitalmars.com

http://vibed.org/api/vibe.core.concurrency/makeIsolated
http://vibed.org/api/vibe.core.concurrency/lock

The last two links point to a working library based implementation that 
I have been experimenting with in the vibe.d. It already provides a lot 
of the possible advantages, but with additional language support it 
could be made really seamless and safe.
Oct 11 2013
parent reply "deadalnix" <deadalnix gmail.com> writes:
On Friday, 11 October 2013 at 20:55:00 UTC, Sönke Ludwig wrote:
 Also see:
 http://forum.dlang.org/thread/k7j1ta$2kv8$1 digitalmars.com
 http://forum.dlang.org/thread/k831b6$1368$1 digitalmars.com

 http://vibed.org/api/vibe.core.concurrency/makeIsolated
 http://vibed.org/api/vibe.core.concurrency/lock

 The last two links point to a working library based 
 implementation that I have been experimenting with in the 
 vibe.d. It already provides a lot of the possible advantages, 
 but with additional language support it could be made really 
 seamless and safe.
Ha, I remembered that someone did a lib implementation, but couldn't remember who. The lib implementation has some serious flaw when it come to safety, but this is already better than nothing !
Oct 11 2013
parent =?UTF-8?B?U8O2bmtlIEx1ZHdpZw==?= <sludwig outerproduct.org> writes:
Am 11.10.2013 23:06, schrieb deadalnix:
 On Friday, 11 October 2013 at 20:55:00 UTC, Sönke Ludwig wrote:
 Also see:
 http://forum.dlang.org/thread/k7j1ta$2kv8$1 digitalmars.com
 http://forum.dlang.org/thread/k831b6$1368$1 digitalmars.com

 http://vibed.org/api/vibe.core.concurrency/makeIsolated
 http://vibed.org/api/vibe.core.concurrency/lock

 The last two links point to a working library based implementation
 that I have been experimenting with in the vibe.d. It already provides
 a lot of the possible advantages, but with additional language support
 it could be made really seamless and safe.
Ha, I remembered that someone did a lib implementation, but couldn't remember who. The lib implementation has some serious flaw when it come to safety, but this is already better than nothing !
I agree, it's a lot better than nothing, but it's main purpose should be to gather experience for an integrated solution (I could live with a partially integrated library solution if safety can be guaranteed, i.e. no 'cast' or 'assumeX' overrides are necessary). Another related ^point is that we need a better implementation of 'scope', currently it doesn't really guarantee anything (although it's still good to have).
Oct 11 2013