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.
