[Mono-dev] Ephemeron support for sgen

[Rodrigo Kumpera]

Hi folks,

This is a summary of the initial design of Ephemeron support for sgen. The
idea is to tailor it specially for ConditionalWeakTable since
it's the only user for it on V4.

ConditionalWeakTable (CWT) will be implemented using open addressing instead
of chaining since both key and value must be reference types and
scanning it is more cache friendly since the whole thing is just an array.

Since ephemerons must prevent both key and value to be marked during regular
scan we'll use a valuetype for it and special case it's gc bitmap to be
empty. Something like "struct Ephemeron { object key,value;}". I'm don't
know if it's worth the trouble using a generics version of it since CWT is.

Ephemerons are handled using the traditional 3-phase GC, with
the additional phase happening before weak references. CWT icalls the
runtime to register
all relevant arrays, de-registering is done when they go unreachable.

The additional phase loops over all registered arrays looking for marked
keys without marked values and pushing those to the grey stack. Termination
happens when no new marked key/unmaked value pair is found.

Once this is properly working, two additional improvements should be done.
Split the registered arrays in two, for nursery and oldgen and use remset
information to know which old gen arrays needs to be scanned. The other is
to use a bitmap to encode which array slots must be scanned.

Using an array with references that are not scanned what chosen since the
alternative would be to use an array of IntPtr and lose support for write
barriers. It would have to be IntPtr otherwise since the GC must not scan
them. Moving both values to the runtime would make manipulating the array
much harder and possibly slower.

CWT won't be a nice, fast hashtable while I sort out all gc details, it will
do linear search and only then I'll look into using proper hashing with
linear/quadratic probing.

Finally, a note on boehm. Since it will be phased out after 2.8 the idea is
to implement it using a WeakReference for the key and live with leaks in
case the value references it. It sucks, but requires little effort and
should perform reasonably well.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20100426/95d98ae9/attachment.html