[Mono-dev] [PATCH]Add ephemeron support for sgen

[Rodrigo Kumpera]

Hey guys,

Attached is a patch that has the initial implementation for ephemerons on
sgen.

It implements classic, by the book, ephemerons with the twist that only
arrays of them are supported. So it keeps
scanning all ephemeron arrays while new keys turn reachable.

The current algorithm should run in linear time requiring only a few rounds
per GC cycle with worst execution time of O(n^2)
where N is the number of ephemeron slots. This will only happen for some
very carefully crafted code, so in practice it should
not be a problem.

The minor/major split is there. Minor collections don't scan arrays in old
gen and the write-barrier takes care of cross-generation
pointers. The only issue of this design is that during a minor collection
all nursery ephemerons pointed by an old gen array
are treated as reachable. We could overcome this by having a custom wb but I
don't think there is much to gain here.

I didn't split the linked lists into minor/major sets since I don't expect
many ConditionalWeakTable (CWT) to be created - those tables will be just be
big instead.

One thing that might be worth looking at is to have a per-array bitmap of
slots that requires attention, this should speed up cases where
a lot of passes are requires. Otherwise it will probably just slow down
things.

I built up a suite of tests for the basics of ephemeron behavior and some
stress tests. The attached patch passes them all.

Once this patch is accepted I'll move into finishing the managed side of it.
Right now CWT is implemented doing linear search, but the idea is to switch
to
open addressing. To do that, the only change required to sgen is to store a
tombstone instead of NULL when clearing unreachable keys.


Thanks,
Rodrigo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20100504/b7d924fd/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ephemeron_take1.patch
Type: text/x-patch
Size: 12824 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20100504/b7d924fd/attachment-0001.bin