On heap segregation, GC optimization and @nogc relaxing

[Orvid King via Digitalmars-d]

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.