[concurrency-interest] reordering

Joe Bowbeer joe.bowbeer at gmail.com
Fri May 19 16:27:21 EDT 2006

On 5/19/06, Pete Soper <Pete.Soper at sun.com> wrote:
> But it's important to realize that "program order" is a certified Java
> tricky term

To reiterate and hopefully illuminate Jeremy's response:

Program Order *is* an easy concept, and the JMM is designed to
maintain its usefulness as a tool for reasoning about the behavior of
a concurrent program -- while at the same time not preventing many
optimizations that would be prohibited by an even more
programmer-friendly sequential model (such as sequential consistency).

The following description is from


1.1 Sequential Consistency

Sequential consistency specifies that memory actions will appear to
execute one at a time in a single total order; actions of a given
thread must appear in this total order in the same order in which they
appear in the program prior to any optimizations – this is an informal
definition of what we shall refer to as the "program order".

Later in section 2.1:

It is difficult for programmers to reason about specific hardware and
compiler transformations. For ease of use, we therefore specify the
model so that programmers do not have to reason about hardware or
compiler transformations or even our formal semantics for correctly
synchronized code.

Aside: In the JMM literature, I find the term "compiler" more
confusing than "program order".  In these discussions, "compiler"
often refers to the actions of HotSpot (in converting bytecode to
native code) more than it refers to javac.

On 5/19/06, Pete Soper <Pete.Soper at sun.com> wrote:
> I think it's interesting that Java Concurrency in Practice gives extremely
> brief mention of compiler/hardware optimizations. Until I find out otherwise
> I'm going to conclude this detail is distraction from the more important
> points.

Good idea :-)  I agree that a Visible VM would be illuminating.  I
think many programmers would find it satisfying.  After all, some
programmers *like* to reason about specific compiler and hardware
transformations rather than abstract models.  That's why they're
programmers!  But optimization is a fast-moving target today, and only
the formal model describes the full, as yet unrealized, potential of
future VM's.

On 5/19/06, Pete Soper <Pete.Soper at sun.com> wrote:
> Bart Jacobs wrote:
> > There are multiple ways to explain the Java memory model. One uses the
> > notion of "reorderings".
> >
> > There is also a different explanation, which is not in terms of
> > "reorderings", and which may be clarifying for you. In this other
> > explanation, in each program execution, all actions performed by a given
> > thread occur in the order specified by the program (known as the program
> > order). The only difference with the single-threaded semantics is that,
> > for fields accessed concurrently by multiple threads, field reads do not
> > necessarily yield the value written by the most recent preceding write.
> >
> > In short, the memory model has no effect on single-threaded programs,
> > and it affects only fields accessed concurrently by multiple threads.
> But it's important to realize that "program order" is a certified Java
> tricky term, because modern compilers and modern hardware frequently
> make this order VERY different from the lexical order of the source code
> statements. I believe this is a major point Hans has been stressing.
> A bit of history. Since the 80s compilers have been doing things that
> the average developer would flatly declare impossible, illegal, or at
> least cruel with respect to true understanding of what's happening at
> runtime. The situation gets worse with concurrency added to the picture.
> In the 80s there were two supercompiler camps developing concurrency
> detection to do automatic parallelization and to get the most out of
> programs making use of extended "parallel" version of languages like
> Fortran (before these features were standardized). But in both of those
> cases it fell on the compiler to avoid races and the worst that would
> happen to a developer was that his loops didn't run faster because he
> had a dependency that inhibited optimization and they ran partially or
> entirely as sequential code. By contrast, Java with the j.u.c. APIs is
> absolute freedom and absolute responsibility for the developer.
> When David Holmes mentioned "program order" recently I found myself
> struggling to come up with a simple explanation for what this means in
> the context of the JMM with concurrent apps, to amplify this part of
> David's remarks. It needs to communicate the two dimensions of data
> dependencies on the one hand while not requiring a degree in
> supercompiler writing to be comprehensible on the other. The JLS
> definition of "program order" in chapter 17 says what needs to be said,
> but for a very limited readership!! But in my opinion the sooner folks
> get this "program order" term straight in their heads, the sooner they
> can climb higher up the JMM mountain.
> David's key point recently was:
>   "To create cross-thread happens-before relationships you have
> to use synchronization tools, like Locks, sync regions, or volatiles."
> But back to your statement. I don't agree. The memory model *does* have
> relevance to single threaded programs, as the "constructor completion
> happens-before finalizer runs" rule shows us. At least I hope it does!
> It would be terrible if the finalizer thread can say "well, we're tired
> of waiting: lets just run this thing anyway."  Put a different way, even
> if the developer thinks they have a 100% single-threaded application,
> it's not running in a single-threaded environment.
> -Pete

More information about the Concurrency-interest mailing list