[Mono-dev] [PATCH] Block map support for sgen

[Rodrigo Kumpera]

Hey folks,

The attached patch set implements block map support for sgen. It uses a
schema similar to boehm's, which is a 2 level sparse map.
Under 64 bits it uses hashing.

I benchmarked a modified binary-trees without valuetypes. Block maps gives a
very modest speedup under major-copying (about 2%) and
nothing under major-marksweep. I've only used the block map for
major_copy_or_mark_object thou. There are probably other places it
oould be used too.

The design is basically the same as boehm's except for a few things:

-It doesn't store list heads or address on each segment. This allows
segment's size to be a power of 2; and
-LOS is handled by filling all covering slots with its block instead of
using forwarding

Few notes:

Segments are not deallocated since this requires either scanning whole
segments on each deallocation or keeping block counts.
And it's probably not needed since Boehm doesn't do it. It's doable as long
as the block map is only read during GC and mutated
with the gc lock held.

64bits support has not been committed since it is a minor change to the code
in sgen-gc.c and I want to have the current change set
validated first.

A small config option that uses either a 3 level map or just hashing under
32bits can be done with ease.

The embedding of Block in MSBlockInfo wastes a word of memory. This could be
worked out by either factoring Block::role into a separate
struct or by using Block::next in place of MSBlockInfo::next.

Cheers,
Rodrigo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20100524/e4a8c486/attachment-0001.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: block_map_part1.patch
Type: text/x-patch
Size: 5665 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20100524/e4a8c486/attachment-0004.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: block_map_part2.patch
Type: text/x-patch
Size: 6769 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20100524/e4a8c486/attachment-0005.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: block_map_part3.patch
Type: text/x-patch
Size: 4954 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20100524/e4a8c486/attachment-0006.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: block_map_part4.patch
Type: text/x-patch
Size: 3018 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20100524/e4a8c486/attachment-0007.bin