Re: Bitwise sweeping

I don't recall seeing precisely this scheme before, but I'm also not sure I=
 understand your context completely.  Nor am I sure that this is necessaril=
y a win, though it sounds like it is in your context.

Are you assuming that all objects in a region have fixed size?

An alternative to allocating directly based on the mark-bit array is to act=
ually build free-lists.  That takes more time, but means that you don't nee=
d to execute code to find and inspect mark bits on every allocation.  That =
may be much less of an issue if you are using this only to find lines in wh=
ich you then do bump-pointer allocation.  But allocating individual objects=
 by inspecting mark bits never seemed like a win to me in our setting.

Note that if you actually build free lists, there should be a reasonable ch=
ance of allocating memory that's already cached, whereas a pure bitmap allo=
cator may not touch the allocated memory, thus charging the ensuing cache m=
iss to the client.  Timing this is tricky.  You want to look at whole progr=
am execution, not a loop that just times allocation.

A down side of interspersing mark bits in the heap is that marking known po=
inter-free objects forces the mark-bits to be paged in if they're not alrea=
dy in physical memory.  Depending on the setting, this may greatly increase=
 the number of pages touched during a GC.  A possible down side of aligning=
 all mark bit arrays this way is that they can only be cached in a small su=
bset of the cache, namely those lines corresponding to region beginnings.  =
Depending on other details, both or neither of these may be serious.

Hans

> -----Original Message-----
> From: [email protected] [mailto:[email protected]]
> On Behalf Of Jon Harrop
> Sent: Sunday, January 09, 2011 4:30 PM
> To: [email protected]
> Subject: [gclist] Bitwise sweeping
>=20
> I just came up with an interesting idea that might be new...
>=20
> 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 (=3D 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.
>=20
> 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.
>=20
> 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).
>=20
> 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.
>=20
> Does anyone know if this is a new idea or what the closest prior art
> is?
>=20
> There are other obvious advantages in terms of parallelism and
> concurrency
> too...
>=20
> Cheers,
> Jon.
>=20