Re: Bitwise mark-region collection

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 localit=
y,
> and we sometimes do benefit from large empty blocks.

What happens when you encounter a run of several consecutive unmarked alloc=
ated 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 spac=
e
> 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 b=
lock rather than 1 word per block.

Cheers,
Jon.


Trayport Limited
Registered in England at 4th Floor Rose Court, 2 Southwark Bridge Road, Lon=
don SE1 9HS
Company registration no.2769279.