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

[Rodrigo Kumpera]

When doing major collections, sgen must know where a given object lives
(it's space), if it's on the nursery,
a major block, a large object and so on.

Right now, to identify a large object we calculate the object size and check
against a constant.
This is not very cache friendly and requires 5 memory loads for a regular
object.

The idea then is to have a faster way to identify this using an
address->space dictionary and this is
were the block map comes in.

The current design requires only 3 loads to identify the space of an object
of which 2 will probably
be very cache hot.

Since object spaces are very large memory regions we can get away with a
simple 2 level sparse
array with a granularity of 4096 bytes or more.

The current design is heavily inspired on boehm's implementation. It uses a
2 level sparse map
indexed on the pointer value, which is a fancy way of saying an array of
arrays.

pointer bits
31....22      21...12           11..0
first level    second level    ignored

To avoid a null check when resolving the second level, we use a single entry
filled with null.

Under 64 bits we replace the first level with a hashtable using bits 63..32
as hashes.

I'm glad you asked, because now that I've written a good explanation of it,
I just came to realize that it
can be improved by encoding the kind of space on the block pointer itself as
it will save a memory load.


On Tue, May 25, 2010 at 1:48 PM, Miguel de Icaza <miguel at novell.com> wrote:

> Hello,
>
>   For the sake of us that do not really speak the GC lingo, would you
> mind explaining what block map support for SGen is?
>
> >
> > 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
> > _______________________________________________
> > Mono-devel-list mailing list
> > Mono-devel-list at lists.ximian.com
> > http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20100525/639d5574/attachment.html