Bitwise sweeping

I just came up with an interesting idea that might be new...

A region based collector. Regions are aligned on region-sized boundaries so
a pointer to any block within a region can be used to obtain a pointer to
the region by zeroing out the low bits. The first cache line in the region
stores 512 allocated bits (= 1 cache line) that indicate which of the 512
blocks in the remainder of the region have been allocated. The second cache
line contains a similar bitvector for mark bits that are zero if the value
in the block is unreachable and marked as one by the mark phase of the GC if
the value is found to be reachable. Sweeping a region is then simply a case
of reading the two bitvectors, computing the bitwise AND and storing the
result back to the first bitvector.

I have implemented a prototype using this technique and it is sweeping at a
rate of 40GB of heap objects per second, which is 700x faster than the sweep
phase of my previous mark-sweep collector. The performance of the whole
program has improved so much that it has gone from being 20x slower than
OCaml (which uses a two-generation GC) to just 2-10% slower than OCaml.
Moreover, the implementation is remarkably simple.

I also allocate using bit-tricks by searching for the first non-255 byte in
the allocated bitvector and using a 255-element lookup table to find the
first zero bit in it. I also remember the last byte in order to restart the
search from there rather than the beginning of the bitvector. This is fast
enough to perform an allocation every 53ns in my benchmark (a purely
functional list-based n-queens solver).

I have read many research papers on garbage collectors over the years but I
cannot recall any that use bit-tricks like this to accelerate GC phases like
sweeping. The Immix paper is the obvious precursor but they allow more
ad-hoc allocations that span lines and so forth, burdening allocation and
sweeping with significantly more work.

Does anyone know if this is a new idea or what the closest prior art is?

There are other obvious advantages in terms of parallelism and concurrency
too...

Cheers,
Jon.