[Mono-dev] [PATCH] Block map support for sgen
kumpera at gmail.com
Tue May 25 14:14:14 EDT 2010
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
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
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
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:
> 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...
More information about the Mono-devel-list