Re: Bitwise mark-region collection

I need to see some code before discussing this topic. Without some actual
code to look at, I can't join the discussion ;).


On Tue, Jan 11, 2011 at 11:39 AM, Jon Harrop <[email protected]>wrote:

> Hans Boehm wrote:
> > We reconstruct free-lists at GC time, and they're built in address order.
>
> I see. There are some parallels between your mark bit array and my bitwise
> approach, advantages that my previous solution using free lists lacked.
>
> Incidentally, this gives me another idea: I should optimize the mark phase
> for marking sequences of blocks that reference their (unmarked) neighbours,
> setting all of the bits in the bitvector simultaneously. Then there wouldn't
> be any individual bitwise operations on the hot path...
>
> > Sweeping is relatively cheap for us...
>
> What does your performance profile look like when lots of small values are
> being recycled? What proportion of time is spent in marking and in sweeping?
>
> > > 2. There is no way to exploit the sparsity of deallocations, which
> > > often occur in contiguous runs when locality is preserved by using an
> > > allocator that hands out free blocks in order.
> >
> > If the GC is responsible for most deallocations, then we preserve
> locality,
> > and we sometimes do benefit from large empty blocks.
>
> What happens when you encounter a run of several consecutive unmarked
> allocated blocks? Presumably you append each one in turn to the end of the
> free list?
>
> > > 3. The size of the free list is considerable when your allocated blocks
> > > are as fine-grained as mine (e.g. 50% overhead when allocating 8-byte
> > > blocks).
> >
> > We link the blocks themselves through the first word, so there is no
> space
> > overhead.
>
> I was referring to your link pointers as overhead because they don't exist
> using this bitwise technique: the space requirements are a single bit per
> block rather than 1 word per block.
>
> Cheers,
> Jon.
>
>
> Trayport Limited
> Registered in England at 4th Floor Rose Court, 2 Southwark Bridge Road,
> London SE1 9HS
> Company registration no.2769279.
>



-- 
Schreppers I.T.
Phone: +32.486.11.88.36
Fax: +32.3.239.68.24
Mail: [email protected]