Re: Bitwise sweeping

Hi Jon,

For previous work on bitwise sweep, see, for example,

Robert T. Dimpsey,=A0Rajiv Arora, Kean Kuiper: Java server performance:=
 A
case study of building efficient, scalable Jvms.=A0IBM Systems Journal =
39(1):
151- (2000).

Regards,
Hillel



From:	"Jon Harrop" <[email protected]>
To:	<[email protected]>
Date:	01/10/2011 02:31 AM
Subject:	[gclist] Bitwise sweeping
Sent by:	[email protected]



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

A region based collector. Regions are aligned on region-sized boundarie=
s 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 reg=
ion
stores 512 allocated bits (=3D 1 cache line) that indicate which of the=
 512
blocks in the remainder of the region have been allocated. The second c=
ache
line contains a similar bitvector for mark bits that are zero if the va=
lue
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 th=
e
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 tha=
n
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 byt=
e in
the allocated bitvector and using a 255-element lookup table to find th=
e
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 f=
ast
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 b=
ut 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 a=
nd
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 concurre=
ncy
too...

Cheers,
Jon.


=