On Wednesday, 12 November 2014 at 02:34:55 UTC, 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.
I think a combination of the C++'s standard library's approach
and Rust's approach would actually be the best possible. If we
were to follow C++'s strategy, I think it would be important to
make sure that it wouldn't require specifically adding template
parameters and constraints, and instead allow the use of a
concept-like system. I think that being able to default the
allocator parameter to the GC, provided the current method is not
@nogc, would also be a good idea. I think that if C++'s approach
were taken it would also be very beneficial to allow a syntax
such as `auto obj = new MyClass() with allocator`, and `delete
obj with allocator`. I do think that the definition of @nogc
would have to be slightly expanded though, so mean that any
values that are allocated with a given allocator are also freed
with the given allocator before returning. To connect back with
your proposal and allow even more to be @nogc, an owned(MyClass,
allocator) object would be allowable to be returned in an @nogc
function. This would allow transfer of the ownership of the data
and responsibility of deletion to the caller, provided that the
caller is @nogc. If the caller is @nogc and fails to free the
memory, DMD should produce an error. If the caller is not @nogc,
then DMD would say nothing, and assume that the allocator used to
allocate the object will do the cleanup.
This would allow far more situations to be accounted for by the
allocation system without needing a GC, while still allowing
programs that want to to use the GC. @nogc would simply mean that
no garbage is produced, it would not make a guarantee of what
allocator was used to perform the allocation. @nogc would also
mean that no allocators, other than the ones passed in by the
user, would be used to perform the allocations. This allows the
current definition of @nogc to still be present, while opening
the scope of @nogc up for use in a much larger variety of
situations.
