• Andrei Alexandrescu (23/23) Dec 15 2013 Hello,
• Jacob Carlborg (6/28) Dec 15 2013 Is this supposed to be used by druntime? If that's the case then there
• Andrei Alexandrescu (4/8) Dec 16 2013 I'd say let's see where the design takes us.
• Joseph Rushton Wakeling (17/23) Dec 16 2013 GC- and allocator-related question, a bit tangential to the current disc...
• Benjamin Thaut (16/39) Dec 16 2013 Reading "The Handbook of Garbage Collection" I got the opinion that
• Andrei Alexandrescu (5/15) Dec 16 2013 That is correct. Such would come in the form of guarantees of when it's
• Benjamin Thaut (17/28) Dec 22 2013 Well they talk about all these issues in Chapter 11 where they give
• Andrei Alexandrescu (7/14) Dec 22 2013 Agreed. What worked for std.allocator was to set out to implement a
• Martin Nowak (2/6) Dec 19 2013 There are also the addRange/addRoot arrays.

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

Hello,


Seems like the low-level allocator is faring quite well. After quite a 
bit of thinking on the higher-level allocator, it seems to me I could 
attack the entire tracing/GC matter heads-on, possibly ultimately 
complementing or even providing an alternative (or more!) for the 
existing GC. The fresh modular approach focused on composition could 
make it much easier to design and implement high-performance collectors.

Anyhow, I've decided to investigate the issue closer. There is one part 
that is very low-level - collecting the roots. It would be awesome if 
that could be abstracted into a small, simple API.

There are several major roots - global memory, thread-local storage for 
all threads, and stack+registers. Currently all offer ranges of void*. 
Assuming we pull the work on precise GC, some of these root sources 
would offer ranges of void* + TypeInfo.

I was thinking it would be great to have a range-based API for walking 
these entities. With that in place, defining tracing algorithms can be 
done modularly and with relative ease. Each range-based API would come 
with specifications of how long the ranges are valid and when it's okay 
to interrupt and resume iteration etc. Some APIs might possibly switch 
to internal iteration, i.e. the user passes a lambda that gets called 
for each root.

What do you think?


Andrei

Jacob Carlborg <doob me.com> writes:

On 2013-12-16 05:15, Andrei Alexandrescu wrote:
 Hello,


 Seems like the low-level allocator is faring quite well. After quite a
 bit of thinking on the higher-level allocator, it seems to me I could
 attack the entire tracing/GC matter heads-on, possibly ultimately
 complementing or even providing an alternative (or more!) for the
 existing GC. The fresh modular approach focused on composition could
 make it much easier to design and implement high-performance collectors.

 Anyhow, I've decided to investigate the issue closer. There is one part
 that is very low-level - collecting the roots. It would be awesome if
 that could be abstracted into a small, simple API.

 There are several major roots - global memory, thread-local storage for
 all threads, and stack+registers. Currently all offer ranges of void*.
 Assuming we pull the work on precise GC, some of these root sources
 would offer ranges of void* + TypeInfo.

 I was thinking it would be great to have a range-based API for walking
 these entities. With that in place, defining tracing algorithms can be
 done modularly and with relative ease. Each range-based API would come
 with specifications of how long the ranges are valid and when it's okay
 to interrupt and resume iteration etc. Some APIs might possibly switch
 to internal iteration, i.e. the user passes a lambda that gets called
 for each root.

 What do you think?

Is this supposed to be used by druntime? If that's the case then there 
is potentially quite a lot of functionality from std.range and 
std.algorithm that is needed in druntime. How should that be handled?

-- 
/Jacob Carlborg

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/15/13 11:41 PM, Jacob Carlborg wrote:
 On 2013-12-16 05:15, Andrei Alexandrescu wrote:

[snip]
 Is this supposed to be used by druntime? If that's the case then there
 is potentially quite a lot of functionality from std.range and
 std.algorithm that is needed in druntime. How should that be handled?

I'd say let's see where the design takes us.

Andrei

Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:

On 16/12/13 05:15, Andrei Alexandrescu wrote:
 Seems like the low-level allocator is faring quite well. After quite a bit of
 thinking on the higher-level allocator, it seems to me I could attack the
entire
 tracing/GC matter heads-on, possibly ultimately complementing or even providing
 an alternative (or more!) for the existing GC. The fresh modular approach
 focused on composition could make it much easier to design and implement
 high-performance collectors.

GC- and allocator-related question, a bit tangential to the current discussion, 
but humour me please, it's related to some ongoing Phobos-related work which 
I'll be sharing shortly :-)

Suppose that I have a class -- which would normally be allocated on the heap.

Now consider a couple of scenarios:

     (i) I want to allocate it on the stack, not the heap, but have it otherwise
         behave like a normal class, and be garbage-collected.  Feasible, via
         this allocator framework or otherwise?

    (ii) I want to allocate it without invoking GC (either on stack or heap).
         How would this affect the use of methods like .save or .dup which
         involve allocating a new instance?

If this is too vague, no worries -- I'll revisit the questions in the context
of 
the particular code I'm working on -- but I thought I might as well ask, since 
allocation strategies are being discussed :-)

Thanks & best wishes,

     -- Joe

Benjamin Thaut <code benjamin-thaut.de> writes:

Am 16.12.2013 05:15, schrieb Andrei Alexandrescu:
 Hello,


 Seems like the low-level allocator is faring quite well. After quite a
 bit of thinking on the higher-level allocator, it seems to me I could
 attack the entire tracing/GC matter heads-on, possibly ultimately
 complementing or even providing an alternative (or more!) for the
 existing GC. The fresh modular approach focused on composition could
 make it much easier to design and implement high-performance collectors.

 Anyhow, I've decided to investigate the issue closer. There is one part
 that is very low-level - collecting the roots. It would be awesome if
 that could be abstracted into a small, simple API.

 There are several major roots - global memory, thread-local storage for
 all threads, and stack+registers. Currently all offer ranges of void*.
 Assuming we pull the work on precise GC, some of these root sources
 would offer ranges of void* + TypeInfo.

 I was thinking it would be great to have a range-based API for walking
 these entities. With that in place, defining tracing algorithms can be
 done modularly and with relative ease. Each range-based API would come
 with specifications of how long the ranges are valid and when it's okay
 to interrupt and resume iteration etc. Some APIs might possibly switch
 to internal iteration, i.e. the user passes a lambda that gets called
 for each root.

 What do you think?


 Andrei

Reading "The Handbook of Garbage Collection" I got the opinion that 
doing a generalized tracing API would be a bad idea. In the book they 
usually describe tracing as a specialized task depending on what type of 
collector is chosen.

Generally I think it is a good idea to think about tracing and identify 
all problems the language still has with propper tracing. Because it 
seems that this has not been done in the past.

Tracing alone is also not enough. There would also be a need for a 
gc-stop point kind of api that inserts points where the GC can stop the 
program without corrupting it.

Kind Regards
Benjamin Thaut

-- 
Kind Regards
Benjamin Thaut

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/16/13 10:18 AM, Benjamin Thaut wrote:
 Reading "The Handbook of Garbage Collection" I got the opinion that
 doing a generalized tracing API would be a bad idea. In the book they
 usually describe tracing as a specialized task depending on what type of
 collector is chosen.

What parts of the book support that opinion?

 Generally I think it is a good idea to think about tracing and identify
 all problems the language still has with propper tracing. Because it
 seems that this has not been done in the past.

 Tracing alone is also not enough. There would also be a need for a
 gc-stop point kind of api that inserts points where the GC can stop the
 program without corrupting it.

That is correct. Such would come in the form of guarantees of when it's 
safe to initiate, pause, and resume iteration.


Andrei

Benjamin Thaut <code benjamin-thaut.de> writes:

Am 16.12.2013 19:21, schrieb Andrei Alexandrescu:
 What parts of the book support that opinion?

 Generally I think it is a good idea to think about tracing and identify
 all problems the language still has with propper tracing. Because it
 seems that this has not been done in the past.

 Tracing alone is also not enough. There would also be a need for a
 gc-stop point kind of api that inserts points where the GC can stop the
 program without corrupting it.

 That is correct. Such would come in the form of guarantees of when it's
 safe to initiate, pause, and resume iteration.


 Andrei

Well they talk about all these issues in Chapter 11 where they give 
different ways to implement finding pointers, read / write barriers etc.
They mention several times, that the implementation highly depends on 
the type of Collector choosen and on the architecture (e.g. can you 
afford to waste a CPU register?) In all other parts of the book they 
constantly talk about "balancing the cost between the mutator and the 
collector" also depending on the type of collector choosen.

In my opinion we should first decide on the type of collector to be 
implemented and then implement the subsystems needed by that collector, 
in a way that optimally serves that collector. If someone wants to 
implement another type of collector, they will have to work with whats 
there. In my opinion doing a to generalized solution will lead to bad 
performance and unneccessary issues when implementing the reference 
collector.

Kind Regards
Benjamin Thaut

Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:

On 12/22/13 5:50 AM, Benjamin Thaut wrote:
 In my opinion we should first decide on the type of collector to be
 implemented and then implement the subsystems needed by that collector,
 in a way that optimally serves that collector. If someone wants to
 implement another type of collector, they will have to work with whats
 there. In my opinion doing a to generalized solution will lead to bad
 performance and unneccessary issues when implementing the reference
 collector.

Agreed. What worked for std.allocator was to set out to implement a 
number of classic allocation tropes and seek out the smallest API that 
would do. Of course that means figuring what tropes are important and 
how to best implement them. As they say, there's no substitute for 
expertise :o).

Andrei

Martin Nowak <code dawg.eu> writes:

On 12/16/2013 05:15 AM, Andrei Alexandrescu wrote:
 There are several major roots - global memory, thread-local storage for
 all threads, and stack+registers. Currently all offer ranges of void*.
 Assuming we pull the work on precise GC, some of these root sources
 would offer ranges of void* + TypeInfo.

There are also the addRange/addRoot arrays.