Bitwise mark-region collection

Hi Hans,

Apologies for the fresh post but I read your e-mail before I left and no lo=
nger have access to it.

You mentioned free lists as an alternative. That is actually exactly what m=
y last prototype was doing. My free lists were stacks pointed to by the fir=
st word in the region. Allocation popped a free reference off the top of th=
e 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 acc=
ording to my benchmarks.

I identified several problems with my use of free lists:

1. Disorder accumulates in the stack-based free list unless allocation-deal=
location happens to be done in FIFO order so there is no locality of refere=
nce from one allocated block to the next, degrading mutator efficiency.

2. There is no way to exploit the sparsity of deallocations, which often oc=
cur in contiguous runs when locality is preserved by using an allocator tha=
t hands out free blocks in order.

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).

I gave more precise statistics about sparsity in this blog post:

  http://flyingfrogblog.blogspot.com/2011/01/importance-of-locality-and-spa=
rsity-in.html

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 deallocat=
ed alone. I believe this is quite common in functional code and is one of t=
he reasons why generational collectors have done so well there.

My initial thought was, of course, to use a more sophisticated data structu=
re to represent the free list in order to combat these deficiencies. For ex=
ample, 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 o=
r 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.

So this bitwise approach is my evolution beyond the free list and, accordin=
g to my results, it is a *lot* more efficient.

Your point about cache associativity was a very good one that I had overloo=
ked. However, most of the time most of the threads will be manipulating the=
ir 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 line=
s in a region is sweeping 512 heap blocks whereas marking 512 heap blocks i=
s likely to incur >>2 cache misses.

If you made any other points that I forgot, please remind me.

Cheers,
Jon.


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