On 12/11/2014 3:34 p.m., deadalnix wrote:
Hi all,
I want to get back on the subject of ownership, lifetime and propose
some solution, but before, propose to state the problem in a way that
haven't seen before (even if I have no doubt some have came to the same
conclusion in the past).
The problem at hand is double: memory management and thread safety.
Number one has been a hot topic for ages, and number 2 has become very
over the past years, to the widespreading of multicores CPU.
The problem at hand here is ownership of data. There are 3 roads you can
go about it:
- immutability and GC. Effectively, these 2 technique allow you to get
rid of ownership. There are advantages and drawbacks i'm going to
discuss later.
- Being unsafe and rely on convention. This is the C++ road (and a
possible road in D). It allow to implement almost any wanted scheme, but
come at great cost for the developer.
- Annotations. This is the Rust road. It also come a great cost for
the developer, as some schemes may be non trivial to express granted the
type system, but, contrary to the C++ road, is safe.
These approach all have some very nice things going on for them, but
also some killer scenarios.
Immutability+GC allow to have safety while keeping interfaces simple.
That is of great value. It also come with some nice goodies, in the
sense that is it easy and safe to shared data without bookkeeping,
allowing one to fit more in cache, and reduce the amount of garbage
created. Most text processing apps fall into this category and this is
why D is that good at them. Another big goodies is that many lock free
algorithm become possible. Once you remove the need for bookkeeping of
ownership many operations can be implemented in an atomic manner.
Additionally, it is possible to implement various GC optimization on
immutable heap, which make the GC generally more efficient. But the cost
is also real. For some use case, this mean having a large amount of
garbage generated (Carmack wrote a piece on haskell were he mention the
disastrous effect that having a framebuffer immutable would have: you'd
have to clone it everytime you draw in it, which is a no go). GC also
tend to cause unpredictable runtime characteristics, which programs with
real time constraint can have hard time to deal with.
Relying on convention has the advantage that any scheme can be
implemented without constraint, while keeping interface simple. The
obvious drawback is that it is time consuming and error prone. It also
make a lot of things unclear, and dev choose the better safe than sorry
road. That mean excessive copying to make sure one own the data, which
is wasteful (in term of work for the copy itself, garbage generation and
cache pressure). If this must be an option locally for system code, it
doesn't seems like this is the right option at program scale and we do
it in C++ simply because we have to.
Finally, annotations are a great way to combine safety and speed, but
generally come at a great cost when implenting uncommon ownership
strategies where you ends up having to express complex lifetime and
ownership relations.
Ideally, we want to map with what the hardware does. So what does the
hardware do ?
Multicore CPU have various cores, each of them having layers of cache.
Cache is organized in cache line and each cache line can be in various
modes. Actual system are quite complex and deal with problems we are not
very interesting here (like writeback) but the general idea is that
every cache line is owned with different modes.
Either the cache line is owned by a single core and can be written to,
or the cache line shared by several cores, each of them having a local
copy of the line, but none of them can write to. There is an internal
bus where cores can exchange cache line with each other and messages to
acquire cache line in read or read/write mode. That mean CPU are good at
thread local read/write, shared immutable and transfer of ownership from
one core to the other. They are bad at shared writable data (as
effectively, the cache line will have to bounce back and forth between
cores, and all memory access will need to be serialized instead of
performed out of order).
In that world, D has a bizaro position were it use a combination of
annotations (immutable, shared) and GC. Ultimately, this is a good
solution. Using annotation for common cases, fallback on GC/unsafe code
when these annotations fall short.
Before going into why it is fallign short, a digression on GC and the
benefits of segregating the heap. In D, the heap is almost segregated in
3 groups: thread local, shared and immutable. These group are very
interesting for the GC:
- Thread local heap can be collected while disturbing only one thread.
It should be possible to use different strategy in different threads.
- Immutable heap can be collected 100% concurrently without any
synchronization with the program.
- Shared heap is the only one that require disturbing the whole
program, but as a matter of good practice, this heap should be small
anyway.
Various ML family languages (like OCaml) have adopted segregated heap
strategy and get great benefice out of it. For instance, OCaml's GC is
known to outperform Java's in most scenarios.
We are sitting on a huge GC goldmine here, but 3 things prevent us to
exploit it:
- Exceptions. They can bubble from one thread to the other and create
implicit sharing.
- Uniqueness (as it is defined now) as it allow for unique object to
be merged with any heap.
- message passing. Ownership transfert is not possible and so unsafe
casting ensue.
* It has to be noted that delegate allow as well for this kind of
stunt, but this is recognized as a bug by now and hopefully it is gonna
be fixed.
D has a type qualifier system for which we pay a big price. Getting
everything const correct is difficult. We'd want to get the most bang
for the buck. One of the bang we are not far to be able to get is
segregating the heap. That mean shitty GC and unsafe code.
Let's present a concrete exemple using ownership:
pure Object foo() { ... }
immutable o = foo();
This is valid code. However, foo can do arbitrary manipulation to come
up with the object. These include various allocations. These allocation
are mutable into foo, which makes it impossible to allocate them on the
immutable heap (as a GC relying on this immutability could mess up
things pretty bad). They also cannot be allocated on the TL heap as once
promoted to immutable, the data become shared as well.
On the other hand, ownership means that the compiler can know when
things go out of scope and free them explicitly. Which is a plus as
generating less garbage is always a way to improve garbage collection.
The most efficient work there is is the one that do not need to be done.
I'd argue for the introduction of a basic ownership system. Something
much simpler than rust's, that do not cover all uses cases. But the good
thing is that we can fallback on GC or unsafe code when the system show
its limits. That mean we rely less on the GC, while being able to
provide a better GC.
We already pay a cost at interface with type qualifier, let's make the
best of it ! I'm proposing to introduce a new type qualifier for owned
data.
Now it means that throw statement expect a owned(Throwable), that pure
function that currently return an implicitly unique object will return
owned(Object) and that message passing will accept to pass around owned
stuff.
The GC heap can be segregated into island. We currently have 3 types of
islands : Thread local, shared and immutable. These are builtin island
with special characteristics in the language. The new qualifier
introduce a new type of island, the owned island.
owned island can only refers to other owned island and to immutable.
they can be merged in any other island at any time (that is why they
can't refers to TL or shared).
owned(T) can be passed around as function parameter or returned, or
stored as fields. When doing so they are consumed. When an owned is not
consumed and goes out of scope, the whole island is freed.
That means that owned(T) can implicitly decay into T, immutable(T),
shared(T) at any time. When doing so, a call to the runtime is done to
merge the owned island to the corresponding island. It is passed around
as owned, then the ownership is transferred and all local references to
the island are invalidated (using them is an error).
On an implementation level, a call to a pure function that return an
owned could look like this :
{
IslandID __saved = gc_switch_new_island();
scope(exit) gc_restore_island(__saved);
call_pure_function();
}
This allow us to rely much less on the GC and allow for a better GC
implementation.
@nogc . Remember ? It was in the title. What does a @nogc function look
like ? a no gc function o not produce any garbage or trigger the
collection cycle. there is no reason per se to prevent the @nogc code to
allocate on the GC as long as you know it won't produce garbage. That
mean the only operation you need to ban are the one that merge the owned
things into TL, shared or immutable heap.
This solves the problem of the @nogc + Exception. As Exception are
isolated, they can be allocated, throw and catched into @nogc code
without generating garbage. They can safely bubble out of the @nogc
section of the code and still be safe.
The same way, it open the door for a LOT of code that is not @nogc to
be. If the code allocate memory in an owned island and return it, then
it is now up to the caller to decide whether is want's it garbage
collected or keep it as owned (and/or make it reference counted for
instance).
The solution of passing a policy at compile for allocation is close to
what C++'s stdlib is doing, and even if the proposed approach by Andrei
is better, I don't think this is a good one. The proposed approach allow
for a lot of code to be marked as @nogc and allow for the caller to
decide. That is ultimately what we want libraries to look like.
Humm.
import std.stdio;
struct TypeOwnerShip(T) {
T value;
alias value this;
this(T)(T value) {
this.value = value;
}
// implict casts to immutable, shared?
// on cast to immutable, shared change islands
}
T owned(T)(T value) {
return TypeOwnerShip!T(value);
}
class Bar {
int x;
this(int x) pure {
this.x = x;
}
}
Bar foo() pure {
return owned(new Bar(5));
}
struct IslandAllocationStrategy {
this(ubyte v = 0) {
}
void opWithIn() {
writeln("opWithIn");
// thread local overriding
}
void opWithOut() {
import std.stdio;
writeln("opWithOut");
// reset thread local overriding
}
}
@property IslandAllocationStrategy island() {
return IslandAllocationStrategy();
}
void main() {
writeln("start");
with(island) {
opWithIn;
writeln("{");
Bar myValue = foo();
writeln(myValue.x);
writeln("}");
opWithOut;
}
writeln("end");
}
I feel like I've suggested this, just without the CS theory.
