Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

Immix garbage collection

Moderators: kris

Posted: 04/23/09 21:41:17

Immix (as per the link below) seems to be a very good performing garbage collector. From what I can tell, it would fit quite neatly into D.

http://www.cs.utexas.edu/users/speedway/DaCapo/papers/immix-pldi-2008.pdf

Is there any interest in an Immix-style collector? To be more specific, if I were to spend some time writing a gcx.d that implemented Immix, where there be any interest in incorporating it into Tango?

Basically, Immix has good space and time efficiencies (you get the best of copying and mark-sweep in one collector).

1. fast bump-allocation that can happen concurrently between threads w/o mutex locking (each to a separate block)

2. "opportunistic" compaction

3. can be "generational"

4. support for "pinned" objects

Author Message

Posted: 04/23/09 22:17:17

I guess I can't say much more than that it sounds very interesting, and that we would love to test such an implementation.

Note that the GC is the most important part in having a stable D, and so testing will have to be rigorous in all possible manners. I think Fawzi may have some stresstests that can come in handy.

Posted: 04/23/09 22:24:24

Yeah, that sounds very interesting. We'd love to see that happen :)

Posted: 04/24/09 13:06:27

Great. Well, I'll work on it and let you guys know when/if I come up with anything working. I definitely understand the need for the garbage collection code to be _very_ stable.

Posted: 04/24/09 15:50:33

Yes it would be definitely intersting to have something like that in tango. Indeed it has to be coded defensively and carfully, making a first version that has as first objective to have something working, and working correctly, performance optimization has to come later.

You don't need to have everything working perfectly before giving it to us, especially if you want some help in testing it, probably it can be added as optional gc as soon as it works, even if it is not fully tested yet.

The gc should be kind of pluggable, and if you need to change something in the interface then we will need to see how to restore/redefine the interface so that it remains pluggable. Actually this will be the first real test for the interface of the gc, so probably you will need to change some things.

I gave just a quick read to the paper, it seems really nice, but it needs some precise heap, maybe even stack (would be nice) information. This because it is partially moving. It can cope with pinned objects, with is needed in D, so it is a real possibility for D.

Leandro Lucarella was also working on a moving GC, and he does also need those pieces of information, he wanted to make an exact heap to begin. There was a discussion about it in the NG, and maybe you can contact him, because on the part "make the heap exact" you can probably collaborate, I am willing to add the changes needed to make the heap exact to tango, as soon as they are available in a reasonable form, I would also like to participate to eventual discussions about the design.

The other part (integrating with gcx, is dependent on immix). As it is also the first kind of generational gc, you might need to change some things. I would like to know if you need to do massive changes, what you paln to do, so that we find the best way to integrate this.

Fawzi

Posted: 04/24/09 23:46:04

I will probably start with a non-generational version to get my fingers wet and to get a good handle on the interface, etc (leave remembered sets and all that jaz for a second iteration).

I looked over the "digitalmars.D" newsgroup and found a lot of posts by Leandro Lucarella. I'm not sure exactly which posts you were referring to as far as the more precise heap info goes. But I'll write him an email re moving objects.

Actually, the basic algorithm can be implemented without any moving/compaction, so I may just get the "blocks" and "lines" and the whole Immix heap organization implemented first, and then worry about moving objects.

All this to say, in its simplest (barely usable) form, I don't think Immix will require any interface changes.

I guess I should also mention that this is a spare time project, so I unfortunately won't have volumes of code on a daily basis :(.

Posted: 04/25/09 01:59:20

Sounds great!

Posted: 04/25/09 17:32:54

fawzi wrote:

Leandro Lucarella was also working on a moving GC, and he does also need those pieces of information, he wanted to make an exact heap to begin. There was a discussion about it in the NG, and maybe you can contact him, because on the part "make the heap exact" you can probably collaborate, I am willing to add the changes needed to make the heap exact to tango, as soon as they are available in a reasonable form, I would also like to participate to eventual discussions about the design.

As I told Keith in a private mail, unfortunately I won't be working on a precise collector for my thesis, I finally agreed with my thesis tutor to concentrate in improving the current GC, making it concurrent to minimize pauses. So I guess I won't be playing with precise GC, not at least until my thesis is done.

That said, I will also be very interested in participating in design discussion to allow implementing a wider range of collectors using the same GC interface.

And here is a link to the thread where different approaches were made to allow a more precise GC: http://www.digitalmars.com/d/archives/digitalmars/D/Std_Phobos_2_and_logging_library_87794.html#N87831

Leandro Lucarella (luca)