Re: Bitwise mark-region collection

> From: Jon Harrop
> Hi Hans,
>=20
> Apologies for the fresh post but I read your e-mail before I left and
> no longer have access to it.
>=20
> You mentioned free lists as an alternative. That is actually exactly
> what my last prototype was doing. My free lists were stacks pointed to
> by the first word in the region. Allocation popped a free reference off
> the top of the stack. Freeing pushed an unreachable reference onto the
> stack. With that technique, sweeping was the slowest GC phase and it
> took around 30% of the total running time. With the bitwise technique,
> sweeping is 700x faster according to my benchmarks.
>=20
> I identified several problems with my use of free lists:
I don't think any of these apply to the way we use them.  Sweeping is relat=
ively
cheap for us, and much of the overhead should be cache misses for blocks th=
e client is
likely to write soon anyway.  (At least that's the theory.  I haven't had a=
 chance
to measure.)  Things seem to depend on the context:

>=20
> 1. Disorder accumulates in the stack-based free list unless allocation-
> deallocation happens to be done in FIFO order so there is no locality
> of reference from one allocated block to the next, degrading mutator
> efficiency.
We reconstruct free-lists at GC time, and they're built in address order.
The trade-off is really between scanning the mark bits all at once (good)
and having to build an intermediate data structure (the free-lists, bad).
It's not clear to me that either alternative universally wins.

>=20
> 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.

>=20
> 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.

Hans

>=20
> I gave more precise statistics about sparsity in this blog post:
>=20
>   http://flyingfrogblog.blogspot.com/2011/01/importance-of-locality-
> and-sparsity-in.html
>=20
> Note that those results show a value being deallocated as part of a run
> of 23 consecutively-allocated values is 4x more likely that it being
> deallocated alone. I believe this is quite common in functional code
> and is one of the reasons why generational collectors have done so well
> there.
>=20
> My initial thought was, of course, to use a more sophisticated data
> structure to represent the free list in order to combat these
> deficiencies. For example, replacing the stack with an interval tree.
> Then I realised that the size of the free list is so small that a
> bitvector representation would fit into a cache line and allow the core
> operations to be performed on bytes or even whole words at a time
> (replacing 64 64-bit stack pops with a single bitwise int64 AND!)
> whilst simultaneously providing the optimal locality of subsequent
> allocation.
>=20
> So this bitwise approach is my evolution beyond the free list and,
> according to my results, it is a *lot* more efficient.
>=20
> Your point about cache associativity was a very good one that I had
> overlooked. However, most of the time most of the threads will be
> manipulating their own thread-local region's bitvectors so there will
> be no clash and, in a global collection of all regions, far more time
> will be spent marking that rewriting these bitvectors. Loading the two
> bitvectors from two cache lines in a region is sweeping 512 heap blocks
> whereas marking 512 heap blocks is likely to incur >>2 cache misses.
>=20
> If you made any other points that I forgot, please remind me.
>=20
> Cheers,
> Jon.
>=20
>=20
> Trayport Limited
> Registered in England at 4th Floor Rose Court, 2 Southwark Bridge Road,
> London SE1 9HS
> Company registration no.2769279.