[Haskell-cafe] Immix GC as a Soc proposal

[Simon Marlow]

On 01/04/10 22:19, Thomas Schilling wrote:
> In my opinion the project would be worthwhile even if it's not in the
> Top 8.  Mentors vote on the accepted projects based both on the
> priority of the project and the applying student, so it's probably not
> a bad idea to apply for other projects as well so you don't put all
> your stakes on just a single horse.
>
> Looking at your current proposal, however, I think that your timeline
> is, well, impossible.  You seem to suggest to build a new allocator
> and garbage collector from scratch.  GHC's allocator is already quite
> similar to Immix, so you don't really have to re-implement much.  The
> main differences (OTTOH) are the different region sizes, the marking
> accuracy (Immix marks 128 byte blocks, GHC is word-accurate), and
> eager compaction.

Immix actually marks twice: once for the object, and once for the line. 
  I propose that in GHC we just mark once in our bitmap.  Then the sweep 
phase looks for empty lines (we can experiment with different sizes), 
and constructs a free list from them.  We have to choose a 
representation for the free list, and the allocator in the GC will have 
to be taught how to allocate from the free list.  This is all pretty 
straighforward.  The tricky bit is how to deal with objects that are 
larger than a line: we'll have to use a different allocator for them, 
and we'll need to identify them quickly, perhaps with a different object 
type.

The other part is opportunistic defragmentation, which is a doddle in 
GHC.  We just identify blocks (in GHC's terminology) that are too 
fragmented, and flag them with the BF_COPY bit before GC, and any live 
objects in that block will be copied rather than marked.  The existing 
mark/sweep collector in GHC already does this.  We could experiment with 
different policies for deciding which blocks to defrag - one idea is 
just to defrag the oldest 10% of blocks during each GC, so you get to 
them all eventually.

So I think this is all quite doable for a keen SoC student.  Marco: I 
suggest reworking your timeline based on the above.  The mutator's 
allocator doesn't need to change, but the GC's allocator will.

In case it isn't clear, I propose we keep the existing generational 
framework and use Immix only for the old generation.

> Therefore I'd suggest to move in small steps:  Change some parameters
> (e.g., region size), fix the resulting bugs and benchmark each change.
>   Then, maybe, implement eager compaction on top of the existing
> system.  I believe this will keep you busy enough.  If in the end GC
> is 5% faster that would be a very good outcome!
>
> I also don't know how much complexity the parallel GC and other
> synchronisation stuff will introduce.  Maybe Simon (CC'd) can comment
> on that.

To do this in parallel you'd need to change the bitmap to be a byte map, 
and then it's pretty straightforward I think.  Objects are at least 2 
words, so the byte-map overhead is 12.5% on a 32-bit machine or 6.25% on 
a 64-bit machine.  There might be contention for the free list, so we 
might have to divise a scheme to avoid that.

Cheers,
	Simon



> / Thomas
>
> On 1 April 2010 22:00, Marco Túlio Gontijo e Silva<marcot at debian.org>  wrote:
>> Hi.
>>
>> I've written a Google Summer of Code proposal for implementing the Immix
>> Garbage Collector in GHC[0].  It's not on dons list of the 8 most important
>> projects[1], but I only saw that list after the proposal is done.  I'd like to
>> hear comments about it, specially about its relevance, since it's not on the
>> list of 8.
>>
>> 0: http://www2.dcc.ufmg.br/laboratorios/llp/wiki/doku.php?do=show&id=marco_soc
>> 1: http://donsbot.wordpress.com/2010/04/01/the-8-most-important-haskell-org-gsoc-projects/
>>
>> I'm planning to write another proposal, maybe about "LLVM Performance Study",
>> "LLVM Cross Compiler", "A Package Versioning Policy Checker" or "“cabal
>> test”", if mentors think they're more relevant than my current proposal.
>> Please let me know if this is the case.
>>
>> Greetings.
>> --
>> marcot
>> http://wiki.debian.org/MarcoSilva
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
>