request for advice: safepoints in the JSR 292 spec

[Doug Lea]

On 12/09/10 19:09, John Rose wrote:
> I started a thread on Google Groups to get more advice on safepoint-based
> invalidation, which the EG is naming MutableCallSite#sync.
>
> http://groups.google.com/group/jvm-languages/browse_thread/thread/9c9d3e84fc745676#
>

TL;DR version: The scheme you laid out here seems sound.

(To avoid relays/forks of discussions, I tried joining and CCing the group)

My only concern about this is whether it precludes
further useful support for the general problem
of "phased computation", which is in turn either a
variant of or a generalization of fork/join computation,
depending on how you look at it. Since JDK7 includes
integrated support for both ForkJoinTask and Phaser,
that will both probably be used in JDK8 lambdas etc,
it seems almost a sure thing that people will further
explore underlying JVM support. Here's a synopsis of
issues. (Please bear with the background before
returning to questions at hand.)

Phased and fork/join computations impose enough structure
on parallel computations to allow cheaper low-level
memory-level accesses. Well, at least when they are used in
the intended ways; among the main difference between JDK7
support and explicitly parallel languages like X10
(supporting "clocks" (a form of Phasers) and async/finish
(a form of fork/join)) is that Java compilers cannot
enforce correct usage (although tools and IDE plugins
could be improved/developed that could do so in most cases).

As warmup, for fork/join, the main economies are due to the
static DAG structure of computation. Among other impacts,
accessing a variable modified by a joined task requires no
memory-level sync beyond what was required anyway
to determine the join. (We currently have no way to
designate such variables or usages; better support
probably awaits this.)

For phased computations, the main economies apply
to "phased" variables -- those that may take a
new value on each phase but are constant within phases.
(We also don't have a way of designating these.)
Conceptually, a phased variable is a holder of
two values/variables, call them "current" and "next",
where reads are from "current" and writes are
to "next". In existing JMM-ese, "current" is basically a
non-volatile variable, and "next" is volatile. And
conceptually, upon each phase advance, each party
does "current = next". There are a few ways to
implement this differently though. One common option
is to use only a single location per phased variable,
and to arrange an action taken upon phase advance
to do in-place updates (see for example Phaser.onAdvance,
http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/Phaser.html
which must by nature be performed in exclusion since
all other parties are blocked until advance. Another
option is to use a two-slot array per phased variable,
indexed by the lowest bit of phase number: reads are
from slot[phase & 1], writes are to slot[~phase & 1]
(assuming that phase numbers are explicit and sequential).
This avoids the need for copying.  Also, across
all of these, it is possible and sometimes desirable for
parties to use their own writes early, before advance.

Sadly enough, I don't know of a recipe determining which
of these options is best in a given situation. (Although
I do know one of the ingredients: whether you require
atomicity of updates across all parties upon advance.)
Maybe some further study and exploration could arrive at a
good recipe.

In the mean time, note that only one of these options
(explicit current+next) even has a reasonable interpretation
in existing JVM-ese. The others are mismatched in that
some of the operations have JMM-volatile semantics and some
don't, so it doesn't make sense to declare the variable
as either volatile or non-volatile.

John's proposal for MutableCallSite falls into this category,
hence the controversy about how to express it.
It is a specialization of the onAdvance (aka sync()) approach
with in-place updates, and safepoint generations serving
as phases. This seems reasonable given the likely need for
atomicity during safepoints anyway.

While ideally it would be nice to integrate this with
other phased computation even now (I can imagine defining
adjunct classes for use with j.u.c.Phaser), I'm not too
tempted to do so right now, because it is not always the
best available option.

However, someday, it would be great to be able
to allow use the same mechanics in each. As parallelism
becomes more widespread, we must make it easiest and
most attractive for people to use simpler constrained
execution control patterns like phasers and FJ rather than the
ad-hoc unstructured use of threads/volatiles/locks. One
way to help reach this goal is to improve JVM-level support
so that the most structured parallel code is also the fastest
parallel code.

-Doug