[bitc-dev] Comments on Concurrent GC

Jonathan S. Shapiro shap at eros-os.org
Fri Apr 13 15:11:45 PDT 2012


Since we've been discussing concurrent GC, STOPLESS, and C4, I want to put
forward an observation about STOPLESS, and another about David's "stop
stopping the world" meme.

The easy one: in the limit, "stop stopping the world" isn't the right goal.
If we can actually get the synchronous phase of the halt down to zero,
that's terrific. But if we can get a practical solution deployed that gets
the "halt the world" phase down to a few microseconds, that's good enough.
What David is really saying is that *if* we need a synchronously blocked
phase, it needs to be of such a short duration that it has negligible
impact on our ability to respond to real-time response requirements (both
hard and soft). So now I hope we're clear on the *technical* goal, and we
can go back to "stop stopping the world" as a sound bite - because it's a *
great* sound bite.


Now the observations about STOPLESS:

Having talked to Bjarne about it on various occasions, I think there is a
general misunderstanding here about the STOPLESS goals.

STOPLESS is a research collector designed to answer a research question.
The research question was: *Is it possible to build a concurrent collector
that does no synchronous locking?* The answer, clearly, is "For all
practical purposes, *yes*". STOPLESS did *not* attempt to answer the
question "How should we build a practical, production-grade, concurrent
GC". Bjarne is quite clear that the implementation complexity of STOPLESS
makes it surprisingly fragile, and probably too complicated to maintain in
a production VM.

Finally, STOPLESS does not ask whether complete lock freedom is actually
the right goal. Take note that the main mechanism used by STOPLESS is
hardware compare and exchange (CMPXCHG , a.k.a. compare and swap)
during certain phases, and that it further relies on a 64 bit compare and
swap. Now note that CMPXCHG is the same implementation mechanism used to
grab locks. The intrinsic issue here isn't the cost of lock acquisition;
it's avoidance of contention. *It isn't obvious that avoidance of
contention is the correct design goal.*
*
*
Avoidance of contention is clearly important when we copy a high-contention
object, but that's not a GC issue. It's a generic issue with shared mutable
access to highly concurrent objects. The GC is just one more accessor. It's
a viable design decision here for the GC to lock the object, copy it, and
then unlock it. The design rule is "high contention objects want to be
de-contended, and failing that, should be designed to be as small as
possible in order to minimize the lock duration required for copying".
That's a perfectly OK rule in real programs.

Avoidance of contention is also important when you get object sequences
that collect in the same order as they are accessed. In this case you can
get boxcar effects in the locking. But if the mutator uses a self-healing
barrier, there are ways to handle this. In particular, some of the Coyotos
locking tricks can be adapted to this purpose.

But the key point is that we are seeking to minimize *both* lock-related
delay and total GC overhead. It isn't obvious that "zero locks" is the
right way to do that.


Next: it isn't clear that copying is universally the right thing to do.
There are an awful lot of hybrid designs in which small object heaps are
partitioned by size, and copying is used only for the "odd men out". We
probably want to relocate small objects during major collections, but it
isn't obvious that we want to invoke the full power of concurrent copying
collection for these objects in all cases and at all times. Does anybody
know of solid experimental data on this point?


Concerning C4: I'm re-reading the paper, but I generally understand what
they have done. Does anybody here have a sense of the magnitude and nature
of the changes to OpenJDK? In particular: when OpenJDK n+1 is released, how
hard will it be to do the forward migration of C4 runtime variant?

Also, does anybody understand the patent implications? The C4 OpenJDK is
released under GPLv2, but no patent grant is in evidence. This actually
puts Azul in a moderately bad legal position: they haven't executed a
grant, but by virtue of releasing under GPLv2 they cannot enforce the
patent against GPLv2 licensees. In the limit, that could cost them the
patent...


shap
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.coyotos.org/pipermail/bitc-dev/attachments/20120413/51fa5e1a/attachment.html 


More information about the bitc-dev mailing list