On Friday, 14 November 2014 at 21:59:47 UTC, deadalnix wrote:
> That is a well covered subject and told you what to google for as
> well as the basic approach. Your example here simply told me you
> haven't done your homework before posting.
>
> Please go look into scientific documentation about GC for ML
> languages.

It would help if you post links to articles.

ML is geared towards functional programming which have different behaviour from system level imperative programming, so I am not sure if ML is the best starting point.

From https://ocaml.org/learn/tutorials/garbage_collection.html :

«OCaml's garbage collector has two heaps, the minor heap and the major heap. This recognises a general principle: Most objects are small and allocated frequently and then immediately freed. These objects go into the minor heap first, which is GCed frequently. Only some objects are long lasting. These objects get promoted from the minor heap to the major heap after some time, and the major heap is only collected infrequently.

The OCaml GC is synchronous. It doesn't run in a separate thread, and it can only get called during an allocation request.»

Nothing about segregation here. The older MLkit which uses a regional allocator is interesting, but probably not what you are talking about.

On Friday, 14 November 2014 at 20:22:13 UTC, Marc Schütz wrote:
> It needs to be `owned(Exception)`, otherwise, how could the compiler know how to treat it correctly? But declaring foo() in that way would be unhelpful, because it would move the exception on calling the function, which is usually not desired. What you want here, instead, is borrowing:
>
>     void foo(T)(scope(T) arg) {
>         pragma(msg, T);
>     }

That is a very good question. I do think this should show the type of T, without owned qualifier.

ML is interesting because it emphasis immutability. For
performance reasons, a part of it is in effect mutable and thread
local. Some ML implementations are very interesting for us.

But let's get back to D. To make the example simpler, let's get
rid of shared (in effect, the same thing can be achieve with
write barrier on shared and do not fundamentally affect the way
it works).

So we have a TL GC that run on a regular basis.When doing so, it
also collect the pointers to the immutable heap and give the to
the immutable GC as roots.

Now the immutable GC works from these roots, but will consider
everything allocated after it get its root as alive.

This is working because the new root to the immutable heap that
can appear in the TL heap can come from:
  - new allocations.
  - from read in immutable heap.
  - other thread (and it will be a root from their scan).

Let's get rid of #3 by making std.concurency aware of the GC
system. An exchange from a non scanned thread to a scanned one
will register a root.

We get rid of #1 by choosing that all allocation done after
getting the roots are considered alive.

We get rid of #2 by recurrence. Reading from the immutable heap
require a reference to the immutable heap. Ultimately, you end up
with a root in #1 or #2 scenario, that will be considered alive.
As the chain of reference is immutable, the one you read will
ultimately be scanned.

The idea is based on Doligez-Leroy's GC, but using TL heap as the
small object and immutable heap as the shared. Note that this GC
is done for ML, where most things are immutable and this is why
it works well (only require write barriers). This strategy would
be a disaster in java for instance, or for us to use the small
object strategy for TL.
http://gallium.inria.fr/~xleroy/publi/concurrent-gc.pdf
http://www.cs.tau.ac.il/~msagiv/courses/mm/doligez.ppt

On Saturday, 15 November 2014 at 00:16:22 UTC, deadalnix wrote:
> The idea is based on Doligez-Leroy's GC, but using TL heap as the
> small object and immutable heap as the shared. Note that this GC
> is done for ML, where most things are immutable and this is why
> it works well (only require write barriers). This strategy would
> be a disaster in java for instance, or for us to use the small
> object strategy for TL.
> http://gallium.inria.fr/~xleroy/publi/concurrent-gc.pdf
> http://www.cs.tau.ac.il/~msagiv/courses/mm/doligez.ppt

Thanks for the link! I agree ML has some interesting work done for it, but they make some assumptions:

1. low portion of mutable objects

2. small heap fits in per-core-cache (<256KiB on Haswell).

So the small heap is basically a region allocator that caches allocations that are likely to die, cutting down on the more costly effort to update the big heap. But I am not sure if that fits system level programming, that is more typical for functional programming…

On Saturday, 15 November 2014 at 12:52:33 UTC, Ola Fosheim Grøstad wrote:
> Thanks for the link! I agree ML has some interesting work done for it, but they make some assumptions:
>
> 1. low portion of mutable objects
>
> 2. small heap fits in per-core-cache (<256KiB on Haswell).
>
> So the small heap is basically a region allocator that caches allocations that are likely to die, cutting down on the more costly effort to update the big heap. But I am not sure if that fits system level programming, that is more typical for functional programming…

The small heap do not apply for us. We can't reproduce that part of the GC in D. However, the big heap part of the strategy would fit D's immutable heap very nicely.

On Friday, 14 November 2014 at 21:59:47 UTC, deadalnix wrote:
> On Friday, 14 November 2014 at 11:46:51 UTC, Marc Schütz wrote:
> That is a well covered subject and told you what to google for as
> well as the basic approach. Your example here simply told me you
> haven't done your homework before posting.

Ok, you caught me there :-P

To my excuse, I did do some (too) superficial research, but even found statements like some ML languages not supporting multithreading, but no details about GC techniques used.

But your explanation makes it clear, and this indeed a very clever idea.

Nice article.

Some observations:

1. I don't understand the difference between 'unique', 'owned' and 'isolated'. (Some other systems use 'isolated'.) Is there a difference?

2. I suspect that 'owned' does not need to be a type qualifier - it can be a storage class much like 'ref' is. This makes for a much simpler implementation.

3. Taking it a step further, I suspect that 'owned' can be implemented as a library type, ala owned!T, with only a smidgen of compiler help.

On Sunday, 16 November 2014 at 10:21:53 UTC, Marc Schütz wrote:
> On Friday, 14 November 2014 at 21:59:47 UTC, deadalnix wrote:
>> On Friday, 14 November 2014 at 11:46:51 UTC, Marc Schütz wrote:
>> That is a well covered subject and told you what to google for as
>> well as the basic approach. Your example here simply told me you
>> haven't done your homework before posting.
>
> Ok, you caught me there :-P
>
> To my excuse, I did do some (too) superficial research, but even found statements like some ML languages not supporting multithreading, but no details about GC techniques used.
>
> But your explanation makes it clear, and this indeed a very clever idea.

If you mean OCaml, the runtime is being made multi-thread.

http://www.ocamlpro.com/blog/2013/07/01/monthly-06.html

On Monday, 17 November 2014 at 08:04:44 UTC, Walter Bright wrote:
> Nice article.
>
> Some observations:
>
> 1. I don't understand the difference between 'unique', 'owned' and 'isolated'. (Some other systems use 'isolated'.) Is there a difference?
>
> 2. I suspect that 'owned' does not need to be a type qualifier - it can be a storage class much like 'ref' is. This makes for a much simpler implementation.
>
> 3. Taking it a step further, I suspect that 'owned' can be implemented as a library type, ala owned!T, with only a smidgen of compiler help.

Ok, I'm gonna respond in reverse order, so I can use one answer
as a starting point for the next one.

3. This is not doable as a library type. The proposal interact
with @nogc, pure function and exception handling. There is no way
to make it @safe as a librayr type as well, consider:
static A statica;
class A {
     void foo() {
         statica = this;
     }
}

owned!A owneda = ...
owneda.foo();

We want the compiler to be able to determine what is owned as
much as possible and insert the right runtime magic calls to make
that work.

2. I'm not sure if that is enough to make it work. It is worth
investigating. It is gonna be much more limited than what I have
in mind.

How do you see this working with fields in struct/classes for
instance ?

1. owned is simply a refined version of isolated. The reserach
team comming up with isolated did it for concurrency reasons, and
it is useful for this, but my proposal include a memory
management aspect, that isolated lacks. So I figured out I'd come
up with a better name.

It is different from unique in the sense that there can be
multiple references to the owned object. For instance:

class A {
     A next;
}

pure auto foo() {
     auto a1 = new A();
     auto a2 = new A();
     a1.next = a2;
     a2.next = a1;

     return a1;
}

Here the returned reference is owned. But it is not unique (a2
also have a reference to that object). Owned indicate that you
enter into a new island. Everything reached transitively from
there is assumed to be in the same island unless you cross a new
owned or immutable reference.

That means code like:

owned(A) bar() {
     auto a = foo();
     auto next = a.next;
     // At this point, we have 2 local reference to the island.

     // Returning is an operation that consume. It would
invalidate all local reference to that island. That is ok here as
we are returning and not using them anyway.
     return a.next;
}

is valid. The type system here is not checking that a reference
to an object is unique, but that who owns the island is know (and
the island only has one owner at a time). It is a more generic
and more powerful construct, and I don't think it come at extra
complexity for the user compared to unique. However, it
definitively means more work on our side.

On 11/17/2014 1:57 PM, deadalnix wrote:
> 2. I'm not sure if that is enough to make it work. It is worth
> investigating. It is gonna be much more limited than what I have
> in mind.

There was a lot of skepticism initially when I proposed that ref be a storage class rather than a type constructor, but it turned out that the problems were resolvable and the end design was an unqualified win. So I think we can do this - at a minimum we need to exhaust the possibility.