On 10/01/14 17:22, Andrei Alexandrescu wrote:
> You know I wouldn't write that unless I had an ace up my sleeve. Watch me :o).

Ahh, we're getting an allocation-based Dance of the Seven Veils here? :-)

On Friday, 10 January 2014 at 09:57:18 UTC, Joseph Rushton Wakeling wrote:
> On 10/01/14 09:03, Andrei Alexandrescu wrote:
>
> Can you recommend some good background reading for those of us who would love to have some input (or at least insight) to this, but don't yet have the theoretical understanding?

I like the thesis "Scheduling Garbage Collection in Embedded Systems" by Roger Henriksson. It shows how GC can work with various types of systems, including real-time embedded control systems. It includes a comparison of GC styles. And disects an actual algorithm.

Joseph

On 10/01/14 23:25, Joseph Cassman wrote:
> I like the thesis "Scheduling Garbage Collection in Embedded Systems" by Roger
> Henriksson. It shows how GC can work with various types of systems, including
> real-time embedded control systems. It includes a comparison of GC styles. And
> disects an actual algorithm.

Interesting -- I'll have to look that up.

Thanks to everyone for your suggestions -- some good new books to add to the reading list! :-)

On 1/10/2014 12:37 PM, Rainer Schuetze wrote:
> As written in the other thread ("how to contribute to GC"), I have just made an
> attempt to make it more reviewable:
> https://github.com/rainers/druntime/commits/gcx_precise2
>
> The necessary compiler fixes are here:
> https://github.com/D-Programming-Language/dmd/pull/2480

Rainer, I want to apologize to you for not getting your efforts the attention they deserve. I hope we can make progress on this shortly.

On 10/01/14 23:25, Joseph Cassman wrote:
> I like the thesis "Scheduling Garbage Collection in Embedded Systems" by Roger
> Henriksson. It shows how GC can work with various types of systems, including
> real-time embedded control systems. It includes a comparison of GC styles. And
> disects an actual algorithm.

The link, for anyone who's interested:
http://www.cs.lth.se/home/Roger_Henriksson/thesis.pdf

On Friday, 10 January 2014 at 20:37:53 UTC, Rainer Schuetze wrote:
> I think this might help in having different heaps (especially thread local heaps if you include "shared"), but I'm not sure this works in unsafe D where casting is allowed.
>

One of the key to a fast GC is segregating the heap in smaller
parts. This is why generational collectors are so popular in java
for instance.

Segregating the heap imply so complications. For instance, it is
necessary to track reference from one heap to another, typically
from young to older objects.

In D, the type system provide a natural segregation. It would be
a great missed opportunity to not take advantage of it. This
segregation is really nice as pointers go from one to another in
a single direction, avoiding the need to track references
changes, and all element of the heap part share some common
characteristics. These characteristics allow for specialized GC
algorithms (for instance, a GC can run on the immutable heap
without the program even knowing about it).

Casting is by essence bypassing the type system. In this case,
you must be help responsible for what happen. The language cannot
provide guarantees.

On 01/10/2014 09:03 AM, Andrei Alexandrescu wrote:
>
> * There will be no possibility to change the type of certain objects
> once allocated. An allocation for an immutable object cannot e.g. make
> it later a mutable one. (This is an essential issue with the current
> allocator, I think.)

I assume you are aware that there is implicit casting to immutable upon return from a strongly pure function. What about it?

On Saturday, 11 January 2014 at 04:26:51 UTC, Timon Gehr wrote:
> On 01/10/2014 09:03 AM, Andrei Alexandrescu wrote:
>>
>> * There will be no possibility to change the type of certain objects
>> once allocated. An allocation for an immutable object cannot e.g. make
>> it later a mutable one. (This is an essential issue with the current
>> allocator, I think.)
>
> I assume you are aware that there is implicit casting to immutable upon return from a strongly pure function. What about it?

Is it a bird ? Is it a plane ? No it is *ISOLATED* !

On Fri, Jan 10, 2014 at 11:58:21PM +0000, deadalnix wrote:
> On Friday, 10 January 2014 at 20:37:53 UTC, Rainer Schuetze wrote:
> >I think this might help in having different heaps (especially thread local heaps if you include "shared"), but I'm not sure this works in unsafe D where casting is allowed.
> >
> 
> One of the key to a fast GC is segregating the heap in smaller parts. This is why generational collectors are so popular in java for instance.
> 
> Segregating the heap imply so complications. For instance, it is necessary to track reference from one heap to another, typically from young to older objects.

Which unfortunately is not an option in D if write barriers are required.


> In D, the type system provide a natural segregation. It would be a great missed opportunity to not take advantage of it. This segregation is really nice as pointers go from one to another in a single direction, avoiding the need to track references changes, and all element of the heap part share some common characteristics. These characteristics allow for specialized GC algorithms (for instance, a GC can run on the immutable heap without the program even knowing about it).

Yeah, the transitivity of immutable really makes this a big opportunity. You know immutable can never point to mutable, and also that immutable never ever changes, so that makes for a perfect partitioning of GC memory. You never have to scan the immutable heap when collecting the mutable heap, and there's never a problem with mutating references in the immutable heap. So you don't need write barriers, and probably(?) don't need locks when collecting the immutable heap, too.

Const is an interesting grey area here, though. It's also transitive, and doesn't allow mutation through it, but something else may mutate the data via another reference. So I'm not sure how exactly const will come into play here, though it does seem like another promising area for GC optimization.


> Casting is by essence bypassing the type system. In this case, you must be help responsible for what happen. The language cannot provide guarantees.

Agreed.


T

-- 
Don't drink and derive. Alcohol and algebra don't mix.

On 1/10/14 8:26 PM, Timon Gehr wrote:
> On 01/10/2014 09:03 AM, Andrei Alexandrescu wrote:
>>
>> * There will be no possibility to change the type of certain objects
>> once allocated. An allocation for an immutable object cannot e.g. make
>> it later a mutable one. (This is an essential issue with the current
>> allocator, I think.)
>
> I assume you are aware that there is implicit casting to immutable upon
> return from a strongly pure function. What about it?

I don't know. Need to think about it. Maybe it's a wrong design decision (or maybe separate heaps are wrong).

Andrei