The GC comes up repeatedly in discussions around here. I've been thinking for a while about breaking it down into components, and now it seems the time is ripe.

The design at http://goo.gl/ZVCJeB seems to be a win. It works well, comprehends all major allocation tropes, someone implemented a subset of it in C++ and measured good results, and a coworker is considering adopting the design for a C++ project as well.

I've started with the next logical step - higher-level allocation that is aware of the type of the object being allocated, and realized that integrating a notion of tracing is appropriate at that level, and actually quite easy. So I'm thinking of just doing it.

A few highlights:

* The design will foster the small, composable components with required/optional primitives that worked for std.allocator.

* I plan to review and probably discard all of the pointers-to-functions nonsense in the current GC.

* At this point I won't worry about discovering roots; I assume druntime has the appropriate mechanisms in place. Instead I'll focus on primitives such as "given this root, mark all that transitively follows from it" (conservatively or not).

* I plan to rely on static introspection for the mark function, i.e:

void mark(T)(ref T obj);

would mark obj and everything transitively referred to by it. The function would probably take a second parameter that's the heap that obj is sitting in.

* I plan to segregate all objects that don't include references and pointers (e.g. int, int[], Tuple!(int, double) etc) into a completely different heap than the "interesting" objects. For the simpler objects there's no need to save detailed type information so they can be stored in a more compact, efficient manner.

* 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.)

* At this point I'm unclear on how generations can be componentized, but am cautiously optimistic. Will see once I get to it.

One thing that would be great now would be to make an effort to review and merge the current precise GC work. I'm sure it will be of great help with breaking into components.


Destroy.

Andrei

On 10/01/14 09:03, Andrei Alexandrescu wrote:
> The GC comes up repeatedly in discussions around here. I've been thinking for a
> while about breaking it down into components, and now it seems the time is ripe.
>
> The design at http://goo.gl/ZVCJeB seems to be a win. It works well, comprehends
> all major allocation tropes, someone implemented a subset of it in C++ and
> measured good results, and a coworker is considering adopting the design for a
> C++ project as well.
>
> I've started with the next logical step - higher-level allocation that is aware
> of the type of the object being allocated, and realized that integrating a
> notion of tracing is appropriate at that level, and actually quite easy. So I'm
> thinking of just doing it.

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?

On 2014-01-10 10:56, Joseph Rushton Wakeling 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?

There's the classic The Garbage Collection Handbook. Here in a later edition:

http://www.amazon.com/The-Garbage-Collection-Handbook-Management/dp/1420082795

-- 
/Jacob Carlborg

On Friday, 10 January 2014 at 09:57:18 UTC, Joseph Rushton Wakeling wrote:
> On 10/01/14 09:03, Andrei Alexandrescu wrote:
>> The GC comes up repeatedly in discussions around here. I've been thinking for a
>> while about breaking it down into components, and now it seems the time is ripe.
>>
>> The design at http://goo.gl/ZVCJeB seems to be a win. It works well, comprehends
>> all major allocation tropes, someone implemented a subset of it in C++ and
>> measured good results, and a coworker is considering adopting the design for a
>> C++ project as well.
>>
>> I've started with the next logical step - higher-level allocation that is aware
>> of the type of the object being allocated, and realized that integrating a
>> notion of tracing is appropriate at that level, and actually quite easy. So I'm
>> thinking of just doing it.
>
> 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?

Two good books

http://www.amazon.de/The-Garbage-Collection-Handbook-Management/dp/1420082795

http://www.amazon.de/Garbage-Collection-Algorithms-Automatic-Management/dp/0471941484

On Friday, 10 January 2014 at 09:57:18 UTC, Joseph Rushton Wakeling 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?

You mean about how GCs work? I have the book "Garbage Collection: Algorithms for Automatic Dynamic Memory Management" by Richard Jones, Rafael D Lins. I can recommend it. It is not too technical that it gets too hard. But it doesn't tell the reader how to write a GC. It's more an overview of various approaches in GC construction.

On Friday, 10 January 2014 at 10:05:45 UTC, Bienlein wrote:
> On Friday, 10 January 2014 at 09:57:18 UTC, Joseph Rushton Wakeling 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?
>
> You mean about how GCs work? I have the book "Garbage Collection: Algorithms for Automatic Dynamic Memory Management" by Richard Jones, Rafael D Lins. I can recommend it. It is not too technical that it gets too hard. But it doesn't tell the reader how to write a GC. It's more an overview of various approaches in GC construction.

Seems like we were all in parallel with our book recommendations; only some minutes apart ...

On 2014-01-10 11:30, Bienlein wrote:

> Seems like we were all in parallel with our book recommendations; only
> some minutes apart ...

That would hopefully indicate they're good recommendations :)

-- 
/Jacob Carlborg

10-Jan-2014 12:03, Andrei Alexandrescu пишет:
> The GC comes up repeatedly in discussions around here. I've been
> thinking for a while about breaking it down into components, and now it
> seems the time is ripe.
>
> The design at http://goo.gl/ZVCJeB seems to be a win.

O.T.: Please use full URLs, it's not that long.

Also how about actually starting formal process to include it as core.alllocator (package preferably).  This activity can go in parallel with with getting a through reveiw of currrent GC and taking steps towards precise GC into the mainstream.

> I've started with the next logical step - higher-level allocation that
> is aware of the type of the object being allocated, and realized that
> integrating a notion of tracing is appropriate at that level, and
> actually quite easy. So I'm thinking of just doing it.
>
> A few highlights:
>
> * The design will foster the small, composable components with
> required/optional primitives that worked for std.allocator.
>
> * I plan to review and probably discard all of the pointers-to-functions
> nonsense in the current GC.

Cool so far.

> * I plan to rely on static introspection for the mark function, i.e:
>
> void mark(T)(ref T obj);
>
> would mark obj and everything transitively referred to by it. The
> function would probably take a second parameter that's the heap that obj
> is sitting in.

This will not work AFAICT. Since nobody can tell what kind of type a
user-defined program may have and GC is certainly not templated on all types.
GC would have to rely on TypeInfos or rather RTInfo-s that describe the layout of Ts in a uniform way (bitmaps to indicate pointers, etc.).
I think Walter had some ideas on how to represent these to reduce space.

> * I plan to segregate all objects that don't include references and
> pointers (e.g. int, int[], Tuple!(int, double) etc) into a completely
> different heap than the "interesting" objects. For the simpler objects
> there's no need to save detailed type information so they can be stored
> in a more compact, efficient manner.
>

Yup. I though GC already did something like that, with BlkAttr.NO_SCAN.

> * 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.)

Would that mean 3 separate heaps, so that addresses given for immutable stuff would never be (sometime later) assigned to (thread-local) mutable? I might have got this point of yours wrong, but I think there is a merit in having separate heap at least for shared stuff.

-- 
Dmitry Olshansky

One big generic problem for GC that is to manage efficiently a huge tree.
More you program use memory for GC will go slower.
Maybe to have a GC profile for these applications could to be a good thing.

On Fri, 10 Jan 2014 09:56:45 -0000, Joseph Rushton Wakeling <joseph.wakeling@webdrake.net> 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?

IMO, the Microsoft documentation for the C# GC is a good place to start.
http://msdn.microsoft.com/en-us/library/ms973837.aspx

It's an overview of a specific collector so you get a concrete understand of one way to do it, which you can then use as a foundation to build understanding on etc.  It's the only thing I've read on GC and I understood (at least at the surface level) Andrei's post completely.  Plus it's not too long, and available online for free :)

R

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/