Re: Doubling up pointers

Right, that's exactly what I was thinking. I'm guessing the transition could
occur as a gradual phase transition (aka ragged barrier) in order to avoid
gross synchronization. Perhaps the first phase would write to the left-hand
pointer, the second phase would have mutators write to both left- and
right-hand pointers while the GC threads copied every left-hand pointer over
its right-hand pointer and the third phase would have mutators write just to
right-hand pointers. Once the third phase is reached the left-hand pointers
in the heap contain a snapshot of its topology. Note that this write barrier
would only be expensive during the second phase: in the first and third
phases it is just a single pointer write. Moreover, my measurements indicate
that the .NET write barriers is ~5x slower than a single pointer write so
I'd expect this double-write barrier to be a relatively fast write barrier
even in the worst case. OCaml's write barrier is even slower than .NET's (it
is a functional language). The main disadvantage is doubling the space
consumed by pointers in the heap, of course.

As an aside, a VM with a JIT compiler might avoid the cost of testing the GC
phase in the write barrier by jumping between three different versions of
the compiled code, one specialized for each phase. Failing that, you could
use masks to avoid jumps.

Cheers,
Jon.

From: Andrew Chen [mailto:[email protected]] 
Sent: 14 September 2011 20:24
To: Jon Harrop
Cc: [email protected]
Subject: Re: [gclist] Doubling up pointers

I've never heard of it. I like the idea though, since it would seem like the
only point of synchronization would be when they swap between first/second
and second/first pointer within the pair.

But what I'm curious about, if this has been done, is, at the point of the
swap between first/second and second/first, how is the appropriate pointer
copied into the other one? It almost seems like you would need three, rather
than two: the mutator writes to p_{i} and p_{i+1) and reads from p_{i} only,
whereas the GC only traverses p_{i+2}, and at the end of the GC's work, i is
incremented (and all the indices are mod 3). This prevents the need to go
through the whole heap and copy from the one pointer into the other, at the
expense of having every pointer write actually be two writes.

But with this many pointers, this is almost the same overhead as various
other approaches, although it makes the memory overhead on a per-pointer
basis rather than on a per-object basis, so if you commonly had many objects
with no pointers, this could work quite well, I imagine.

Those are my thoughts. If someone has actually considered or tried this, I
do really want to learn more.

On Sep 14, 2011, at 01:09 PM, Jon Harrop <[email protected]> wrote:
In the context of taking a snapshot of the topology of the heap, I'm
wondering if anyone has considered or tried replacing each pointer with a
pair of pointers and having the mutators work on the first/second of each
pair while the GC traverses the second/first of each pair?

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com