I have read the paper that describes the proposed semantics of the
memory model for Java. I have found some side-effects of the definition
that I think should be paid some attention to.
Are these side effects a result of an explicit decision in favor of
easier implementation, or have they creeped there unintentionally? Have
they been considered?
The first one, in my opinion, can be fixed without incurring any
implementation overhead on a reasonable hardware. As for the second one,
it looks that it would be complicated to fix (and if I remember
correctly, there have been some discussion on similar issues on the
list), but it still must be made clear. We have seen disastrous results
of quiet assumptions that "Programmers will never do THIS".
Alex
------------------------------------------------------------------------
Consider the following executions:
Execution 1 Execution 2
1. x=1 1. x==1
//------------- no barriers //---------------- no barriers
2. x=2 2. x=2
3. x==1 3. x==1
Execution 1 is not permitted by the model. Execution 2 is permitted.
I have no problem understanding why Execution 1 should be forbidden. It
involves only the operations performed by a processor itlself, and
therefore, if it is permitted, it can be possible even in a
single-threaded environment. (Actually, aliasing - the situation that
can potentially lead to this result - is a hard optimization inhibitor.
In languages like C and C++, a new keyword, restrict, has been added to
help compiler find code without aliasing).
I have, however, a problem understanding why Execution 2 is permitted.
The first operation (x=1 in Ex1, x==1 in Ex2) can be placed
substantially far away from operations 2 and 3. In this case, from the
point of view of the compiler, second parts of Exs 1 and 2 are
indistinguishable. If Ex2 is permitted because compiler ignores some
aliasing, then Ex1 should also be permitted.
I have also failed to find any scenario where hardware would reorder
operations in Ex2 in such a way that it would become possible. After
all, the hardware does perform loads and stores to real addresses in the
memory, and the issue of aliasing doesn't exist there.
I have also the following "proof" that this cannot happen in hardware:
Every reasonable hardware has a "window of history", which is finite
since the processor resources are finite (reorder buffers, caches etc.).
The window can be quite short - the associativity of cache is seldom
more than 4, which means that cache can "remember" at most 4 events per
memory address. Reorder buffers are rapidly flushed, so their "memory"
is not long either.
Assume that Execution 2 had the "x=1" operation somewhere earlier in its
program order. Because of the "window of history" effect, if it is
sufficiently far away, at the point that Op.1 is executed, the fact that
the processor has written 1 to x is forgotten. In this case, according
to spec, Operation 3 cannot return 1. However, since this situation is
indistinguishable from the one where the processor did not write 1 to x,
Op 3 actually could return 1 --- a contradiction!
I think the spec should be fixed in a way that if a processor writes to
a variable, then it kills all the values it have read from that variable
previously. This does not however mean that "reads should kill".
------------------------------------------------------------------------
Consider the following program:
Thread 1 Thread 2
while (true) int k = -INF;
{ while (true) {
i++; if (k>i) OUCH;
} k = i;
}
The question is "Can this program get to execute the OUCH"?
The proposed spec permits it.
Original Java is Coherent, so it forbids that. As far as I understand,
it is also forbidden in CRF.
I understand that if it was not for the same variable, then it could
happen because of aliasing. In this case this is more a "syntactic"
issue where all the accesses to i are obviously accesses to the same
variable, both for the compiler, for JVM and for the programmer. If I
remember correctly, there
was a thread on more or less this issue on JMM mailing list, but it was
abandoned as not easily solvable (or not solvable at all?).
Still, I think that allowing this case can be quite confusing to
programmers. I can imagine situations in which code like this could be
useful, and I can imagine programmers ignoring the non-monotinicity of
i is possible. Then, if at some point in time someone invents
optimization (legal!) that actually makes this happen, OUCH!
In other words, the syntactic information from the program gives more
information than just the order of memory access operations. Your
definition (admittedly, like any other) chooses to ignore this
information.
So, I think this should be made clear. Either this execution is marked
as possible, even though it is non-intuitive and looks impossible on any
currently imaginable system, or the spec must be changed in such a way
so as to make it forbidden.
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:31 EDT