[concurrency-interest] Transformation of multiple volatile readswithout intervening writes

timo.kinnunen at gmail.com timo.kinnunen at gmail.com
Sun Sep 6 21:09:12 EDT 2015


Thanks, I’ve re-read about sequential consistency of volatile operations couple of times and I think I got it. First I’ll get rid of the redundant read because it makes the rest significantly more straightforward. So, reorder to get this:

	public static void thread1() {
		REG r1 = p;
		REG r2 = p;
		if(r1 == null) return;
		if(r2 == null) throw npe;
		// rest //
	}
Assign r1 to r2, inline r2, remove dead throw, rename r1 to r2 to remain consistent:

	public static void thread1a() {
		REG r2 = p;    if(r2 == null) return;
		REG r3 = r2.a; if(r3 == null) return;
		REG r4 = p;    if(r4 == null) throw npe;
		REG r5 = r4.a; if(r5 == null) throw npe;
		r5.x = 1; 
	}

If thread1a returns successfully, then for all such executions, a thread1b which follows the same synchronization order and performs the same actions as thread1a also returns successfully:

	public static void thread1b() {
		REG r2 = p;    if(r2 == null) throw npe;
		REG r3 = r2.a; if(r3 == null) throw npe;
		REG r4 = p;    if(r4 == null) return;
		REG r5 = r4.a; if(r5 == null) return;
		r5.x = 1; 
	}

Otherwise, if thread1a throws, then for all such executions thread1b performs identically except it returns normally instead. 

In both cases, a thread2 executing the same synchronization actions in the same order as thread1b starting from r4 executes identically to thread1b regardless of the synchronization actions prior to r4:

	public static void thread2() {
		REG r4 = p;    if(r4 == null) return;
		REG r5 = r4.a; if(r5 == null) return;
		r5.x = 1; 
	}

Otherwise thread1a must return early. For all such executions thread2 performs identically in thread1a’s place. 

To summarize, if the original version executes without throwing then the optimized version can perform the same actions in same order without the ruse being discovered. If there is a throw then either the original thread1a is executing or the transformed thread1b is executing. Only if the thread2 completes successfully in your example case does it prove that the optimization has been done, but thread2 could have also returned normally, and so could have the original thread too. 

I don’t know if this would disqualify the transformation as such. The threads still stop their reading when they see nulls, but whether the compiler should favor custom checks against nulls or the NPEs generated by some compiler seems like it wouldn’t fall under the JMM.




Sent from Mail for Windows 10



From: Hans Boehm
Sent: Friday, September 4, 2015 23:54
To: timo.kinnunen at gmail.com
Cc: concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] Transformation of multiple volatile readswithout intervening writes


Are you asking about transforming thread1() in isolation?  Or as part of a whole program transformation?

I think the answer to the former is no.  Assume p starts out not null, p.a starts out null, p changes to null, and then p.a changes to not null.  If the original code doesn't return prematurely, it must throw an npe, because p must be null the third time it's read.  The transformed code will return successfully in this case.

The first redundant read of p can safely be eliminated.  The second cannot.

I'm not sure the answer to the second question is interesting.

On Thu, Sep 3, 2015 at 9:27 PM, <timo.kinnunen at gmail.com> wrote:
Hi, 
 
Hopefully an easy question about permitted transformations. 
 
Initially, q.a == q, q.x == 0, p == q and npe == null. Variables p and q.a are volatile. Thread 1 is reading and threads 2 and 3 could interfere with this with their writes.
 
The code for thread 1 is:
                public static void thread1() {
                                REG r1 = p;
                                if(r1 == null) return;
                                REG r2 = p;
                                if(r2 == null) throw npe;
                                REG r3 = r2.a;
                                if(r3 == null) return;
                                REG r4 = p;
                                if(r4 == null) throw npe;
                                REG r5 = r4.a;
                                if(r5 == null) throw npe;
                                r5.x = 1;
                }
The code for threads 2 and 3 is:
                public static void thread2() {
                                REG r6 = q;
                                r6.a = null;
                                r6.a = r6;
                }
                public static void thread3() {
                                REG r7 = q;
                                p = null;
                                p = r7;
                }
 
Is a compiler permitted to transform thread 1’s code to this:
                public static void thread1b() {
                                REG r4 = p;
                                if(r4 == null) return;
                                REG r5 = r4.a;
                                if(r5 == null) return;
                                r5.x = 1;
                }
 
Because the volatile reads r1,r2,r4 do not synchronize-with reads r3,r5 or each other r2,r4 could be grouped next to r1. Reads r1 and r2 then become unnecessary synchronization that the compiler can optimize away, along with some now dead code. The compiler repeats this same optimization with r5, which gives the final transformed code. 
 
Would this be a valid compiler transformation according to the JMM?
 
 
 
Sent from Mail for Windows 10

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20150907/8d9c5cb8/attachment-0001.html>


More information about the Concurrency-interest mailing list