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<mar...@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@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
