| |
 | Posted by deadalnix |  Permalink Reply |
|
deadalnix 
| 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.
|
