Compiler trick

java-programmer, Compiler trick Joona I Palaste wrote:

> If we have two
> threads, one of which does A and B, the other does C and D, then the
> actual physical sequence may be A-B-C-D, A-C-B-D, A-C-D-B, C-A-B-D,
> C-A-D-B or C-D-A-B. It is always guaranteed that all four operations
> are done, A is done before B, and C is done before D. Nothing else
> about the ordering is guaranteed. (This is assuming a strictly
> sequential intra-thread execution with no control structures.)

I may be missing your point here, but I think that without synchronisation,
there is no such guarantee. As it happens I've just written a passage in
another post which fits just as well here. Apologies to anyone who sees it
twice ;-)

This is discussed in the Java Memory Model JSR, see:

http://www.cs.umd.edu/~pugh/java/memoryModel/PublicReview.pdf

Two threads, two shared variables A and B, two passages of code that access
them without synchronisation:

Initially A == B == 0

Thread 1:
r2 = A;
B = 1;

Thread 2:
r1 = B;
A = 2;

A legal result of this is that r2 == 2 and r1 == 1. The JSR describes this as
"surprising behavoir". Which is a classic bit of understatement...

-- chris

java-programmer >> Compiler trick Joona I Palaste wrote:

> If we have two
> threads, one of which does A and B, the other does C and D, then the
> actual physical sequence may be A-B-C-D, A-C-B-D, A-C-D-B, C-A-B-D,
> C-A-D-B or C-D-A-B. It is always guaranteed that all four operations
> are done, A is done before B, and C is done before D. Nothing else
> about the ordering is guaranteed. (This is assuming a strictly
> sequential intra-thread execution with no control structures.)

I may be missing your point here, but I think that without synchronisation,
there is no such guarantee. As it happens I've just written a passage in
another post which fits just as well here. Apologies to anyone who sees it
twice ;-)

This is discussed in the Java Memory Model JSR, see:

http://www.cs.umd.edu/~pugh/java/memoryModel/PublicReview.pdf

Two threads, two shared variables A and B, two passages of code that access
them without synchronisation:

Initially A == B == 0

Thread 1:
r2 = A;
B = 1;

Thread 2:
r1 = B;
A = 2;

A legal result of this is that r2 == 2 and r1 == 1. The JSR describes this as
"surprising behavoir". Which is a classic bit of understatement...

-- chris

java-programmer >> Compiler trick Chris Uppal <email***@***.com> scribbled the following:
> Joona I Palaste wrote:

>> If we have two
>> threads, one of which does A and B, the other does C and D, then the
>> actual physical sequence may be A-B-C-D, A-C-B-D, A-C-D-B, C-A-B-D,
>> C-A-D-B or C-D-A-B. It is always guaranteed that all four operations
>> are done, A is done before B, and C is done before D. Nothing else
>> about the ordering is guaranteed. (This is assuming a strictly
>> sequential intra-thread execution with no control structures.)

> I may be missing your point here, but I think that without synchronisation,
> there is no such guarantee. As it happens I've just written a passage in
> another post which fits just as well here. Apologies to anyone who sees it
> twice ;-)

> This is discussed in the Java Memory Model JSR, see:

> http://www.cs.umd.edu/~pugh/java/memoryModel/PublicReview.pdf

> Two threads, two shared variables A and B, two passages of code that access
> them without synchronisation:

> Initially A == B == 0

> Thread 1:
> r2 = A;
> B = 1;

> Thread 2:
> r1 = B;
> A = 2;

> A legal result of this is that r2 == 2 and r1 == 1. The JSR describes this as
> "surprising behavoir". Which is a classic bit of understatement...

Ah, I have not been clear enough. When I mentioned the actions A, B, C
and D, I was only talking about the actual operations (in this case "A"
is "r2=A", "B" is "B=1", "C" is "r1=B", D is "A=2"), not about overall
effects in the program state. In other words, I left the outcome of the
actions as undefined.
If this sounds too confusing, another way to put it is that what I wrote
applies only when A, B, C and D are independent actions whose effects do
not affect each other.

--
/-- Joona Palaste (email***@***.com) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"C++ looks like line noise."
- Fred L. Baube III

java-programmer >> Compiler trick Chris Smith <email***@***.com> wrote in message news:<email***@***.com>...
> FISH wrote:
> > In a multi-threaded environment this is even more of a headache, as
> > even two consecutive 'if' statements that have inverse logic can be
> > either both or neither run. Okay - this is less of a problem for
> > variables of local scope - but even if the OP does comes up with such
> > a deterministic algorithm, multi-threading would mean it could only
> > be applied to data members which the compiler could prove would be
> > unique only to that thread of execution. Surely?
>
> None of that is wrong, but you make it sound harder than it is. A local
> variable is *always* unique to a thread of execution, so the "proof" on
> the part of the compiler is trivial. This isn't like C where you could
> pass around pointers to your local variables; a local variable is only
> accessed by one thread, within the context of a single method
> invocation. No exceptions.

Yes I know. I did write a long paragraph about how having one rule for
method-scoped variables and one rule for everything else would only lead
to confusion, and started to quote an example or two before realising I
was just rambling, so I cut it. I guess that without that second part
of my argument the first part lacked clarity.

An interesting point that I was mulling over in the back of my mind as
I wrote the original posting was whether it would be possible for a
compiler to study the synchronisation of code blocks and thereby prove
the thread-safe-ness (for want of a better term) of non-local variables.
Perhaps that's why I made it sound so enigmatic? :-) Either way, it is
a very bad idea - you still end up with two different sets of rules
being applied depending upon how, and where, a variable is used.

-FISH- ><>

java-programmer >> Compiler trick Joona I Palaste" <email***@***.com> wrote in message
news:ci4vca$agc$email***@***.com...
> Your explanation is correct, however I think that Chris already knew
> that.

I just can't resist the urge to pontificate....

regards,
Dar7yl

Posted: 2004-10-15 19:50:00

java-programmer >> Compiler trick Hi Chris and others,

I am not sure whether I can (and should ;-)) revive this thread, but I'd
like
to follow up on this statement of Chris'
> A local variable is *always* unique to a thread of execution, so the
> "proof" on
> the part of the compiler is trivial. This isn't like C where you could
> pass around pointers to your local variables; a local variable is only
> accessed by one thread, within the context of a single method
> invocation. No exceptions.

This is true if you look strictly at the value of the variable in question.
It, indeed, is unique and private to the local thread. And, btw, C is not
different from Java in this respect: the value of a pointer variable can't
be
changed in another thread either. Nor is the value of a pointer to pointer
to
pointer.

What may under certain conditions be accessible and in danger is
*what is pointed at*.
And we must keep in mind that object variables in Java actually
*are pointers* to objects!

So, the quoted statement above is fine with regard to variables of the
simple types,
like int, char, byte and the like.
With objects and their states, however, it looks quite different:

Any object may in its constructor call static methods, of its own class or
of other classes. So it may import data, and hence change its state
accordingly,
dependent on the world extraneous to its own thread and accessible to other
threads.
An object may even pass itself to a static method of some arbitrary class.
If this other class is accessible to other threads, our object may change
its state in
a way totally beyond its control and unforeseeable.

Accordingly, if my code looks like this
1: MyClass myObj = new MyClass(0);
2: if (myObj.getNumber() != 0)
3: myObj.doThis();
4: else
5: myObj.doThat();

by the time line 5 is executed, some fiend in another thread may well have
changed the hidden number inside of myObj to 0,
provided the locally allocated myObj has exposed its inner workings to
the outer world somehow during its construction.

Regards,
Tillmann

--
T. Wegst / Software++
E-Mail email***@***.com
Home www.tillmann-wegst.de

Posted: 2004-10-15 20:58:00

java-programmer >> Compiler trick Sorry, I made a mistake here
> changed the hidden number inside of myObj to 0,
it should read something like

> changed the hidden number inside of myObj to 1,

Apologies,
Tillmann

Posted: 2004-10-15 22:54:00

java-programmer >> Compiler trick Tillmann Wegst wrote:
> Hi Chris and others,
>
> I am not sure whether I can (and should ;-)) revive this thread, but I'd
> like
> to follow up on this statement of Chris'
> > A local variable is *always* unique to a thread of execution, so the
> > "proof" on
> > the part of the compiler is trivial. This isn't like C where you could
> > pass around pointers to your local variables; a local variable is only
> > accessed by one thread, within the context of a single method
> > invocation. No exceptions.
>
> This is true if you look strictly at the value of the variable in question.
> It, indeed, is unique and private to the local thread. And, btw, C is not
> different from Java in this respect: the value of a pointer variable can't
> be changed in another thread either. Nor is the value of a pointer to pointer
> to pointer.

C code:

pthread_cond_t cv;
pthread_mutex_t mx;
int done = 0;

void *fn2(void *arg)
{
int *p = (int *) arg;
pthread_mutex_lock(&mx);
*p = 12;
done = 1;
pthread_cond_signal(&cv);
pthread_mutex_unlock(&mx);

return NULL;
}

int main(int argc, int *argv[])
{
int a = 0;
pthread_t thread;

pthread_mutex_init(&mx, NULL);
pthread_cond_init(&cv, NULL);

pthread_create(&thread, NULL, fn2, (void *) &a);

pthread_mutex_lock(&mx);
while (!done) pthread_cond_wait(&cv, &mx);
pthread_mutex_lock(&mx);

printf("%i\n", a);

return 0;
}

That's what I mean when I say that unlike in C, Java's threads can never
change the value of a local variable. Languages that do the sort of
thing above can do escape analysis to identify those local variables
that might be changed from elsewhere, but in Java the "escape analysis"
is trivial for local variables, because a local variable can never
escape.

> So, the quoted statement above is fine with regard to variables of the
> simple types, like int, char, byte and the like.
> With objects and their states, however, it looks quite different:

Sure, I only said that about local variables. Shared state obviously
must be protected, and that's never been in dispute.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation