Immutability and reordering

The code below (Java Concurrency in Practice, Listing 16.3) is not thread-oriented for obvious reasons:

public class UnsafeLazyInitialization { private static Resource resource; public static Resource getInstance() { if (resource == null) resource = new Resource(); // unsafe publication return resource; } } 

However, a few pages later, in section 16.3, they state:

UnsafeLazyInitialization actually safe if the Resource unchanged.

I do not understand this statement:

  • If the Resource is immutable, any thread observing the resource variable will see it as null or fully constructed (thanks to the strict end-field guarantees provided by the Java memory model)
  • However, nothing prevents the reordering of commands: in particular, two readings of resource can be reordered (there is one read in if and one in return ). Thus, the stream could see a nonzero resource in if but return a null reference (*).

I think that UnsafeLazyInitialization.getInstance() can return UnsafeLazyInitialization.getInstance() even if Resource is immutable. Is that so and why (or why not)?




(*) To better understand my idea of ​​reordering, this blog post by Jeremy Manson, one of the authors of chapter 17 of the JLS on concurrency, explains how String hash code is published securely through a fair data race and how to remove the use of a local variable can lead to to the fact that the hash code will incorrectly return 0, due to a possible reordering, very similar to what I described above:

Here I added another read: a second read of the hash before returning. No matter how strange it sounds or how unlikely it may be, the first reading can return a correctly calculated hash value, and the second reading can return 0! This is permitted within the framework of the memory model because the model allows extensive reordering of operations. The second read can actually be moved in your code, so your processor will do it before the first!

+42
java multithreading concurrency order java-memory-model
Jan 31 '13 at 11:13
source share
10 answers

The confusion that I think you have is what the author meant by secure publishing. He meant the safe publication of a nonzero resource, but it seems you understand that.

Your question is interesting - is it possible to return a cached resource value of zero?

Yes.

The compiler can change the order of work, for example

 public static Resource getInstance(){ Resource reordered = resource; if(resource != null){ return reordered; } return (resource = new Resource()); } 

This does not violate the rules of consistent consistency, but may return a null value.

It will be the best implementation for discussion, but there are no rules to prevent this type of reordering.

+3
Jan 31 '13 at 16:25
source share

UPDATE Feb10

I make sure that we have to separate the two phases: compilation and execution .

I think that the deciding factor on whether it is allowed to return null or not is that bytecode . I made 3 examples:

Example 1:

Original source code literally converted to bytecode:

 if (resource == null) resource = new Resource(); // unsafe publication return resource; 

Bytecode:

 public static Resource getInstance(); Code: 0: getstatic #20; //Field resource:LResource; 3: ifnonnull 16 6: new #22; //class Resource 9: dup 10: invokespecial #24; //Method Resource."<init>":()V 13: putstatic #20; //Field resource:LResource; 16: getstatic #20; //Field resource:LResource; 19: areturn 

This is the most interesting case, because there are 2 read (line # 0 and line # 16), and between them is 1 write (line No. 13). I affirm that it is impossible to change the order , but consider it below.

Example 2 :

"Optimized for the compiler" code that can be literally converted to java as follows:

 Resource read = resource; if (resource==null) read = resource = new Resource(); return read; 

Bytecode for this (I actually created this by compiling the above code snippet):

 public static Resource getInstance(); Code: 0: getstatic #20; //Field resource:LResource; 3: astore_0 4: getstatic #20; //Field resource:LResource; 7: ifnonnull 22 10: new #22; //class Resource 13: dup 14: invokespecial #24; //Method Resource."<init>":()V 17: dup 18: putstatic #20; //Field resource:LResource; 21: astore_0 22: aload_0 23: areturn 

Obviously, if the compiler "optimizes" and the bytecode is obtained as indicated above, zero reading may occur (for example, I refer to Jeremy Manson's Blog )

It is also interesting to see how a = b = c works: the link to the new instance (line No. 14) is duplicated (line No. 17), and the same link is saved, and then first b (resource, (Line # 18)), then a (read, (line # 21)).

Example 3 :

Make an even smaller modification: read resource only once! If the compiler starts to optimize (and using the registers, as others have indicated), this is better optimization than the above, because line number 4 here represents "register access" rather than the more expensive "static access" in example 2.

 Resource read = resource; if (read == null) // reading the local variable, not the static field read = resource = new Resource(); return read; 

Bytecode for example 3 (also created with literal compilation above):

 public static Resource getInstance(); Code: 0: getstatic #20; //Field resource:LResource; 3: astore_0 4: aload_0 5: ifnonnull 20 8: new #22; //class Resource 11: dup 12: invokespecial #24; //Method Resource."<init>":()V 15: dup 16: putstatic #20; //Field resource:LResource; 19: astore_0 20: aload_0 21: areturn 

It is also easy to see that it is not possible to get null from this bytecode, since it is built in the same way as String.hashcode() , having only 1 reading of the static variable resource .

Now consider Example 1 :

 0: getstatic #20; //Field resource:LResource; 3: ifnonnull 16 6: new #22; //class Resource 9: dup 10: invokespecial #24; //Method Resource."<init>":()V 13: putstatic #20; //Field resource:LResource; 16: getstatic #20; //Field resource:LResource; 19: areturn 

You can see that line No. 16 (reading variable#20 to return) is most noticeable for writing from line # 13 (assigning variable#20 from the constructor), so it cannot be placed forward in any execution order where line # 13 is executed . Thus, reordering is not possible .

For the JVM, you can build (and use) a branch that (using certain additional conditions) bypasses line No. 13 write: the condition is that reading from variable#20 should not be zero .

Thus, in no case can null be returned for example 1.

Output:

Seeing the above examples, the bytecode shown in Example 1 DOES NOT null . Optimized bytecode, as in example 2 CHECK null , but there is an even more optimized optimization Example 3, which DOES NOT produce null .

Since we cannot be ready for all possible optimization of all compilers, we can say that in some cases this is possible, some other cases are impossible for return null , and it all depends on the byte code. In addition, we showed that there is at least one example for both cases .




Previous reasoning . We draw attention to the Assylias example: the main question is: is it (with respect to all JMM, JLS specifications) that the VM will change the reading order of 11 and 14 so that 14 happens before 11?

If this can happen, then independent Thread2 can write the resource with 23, so 14 can read null . I declare that it is impossible .

In fact, since there is a possible entry 13, it will not be a valid order of execution . The VM can optimize the execution order so that it excludes idle branches (the remaining 2 reads, without writing), but to make this decision, it must perform the first read (11), and it must read non-null , so reading 14 cannot precede 11 read . Thus, it is impossible to return null .




Invariance

Regarding immutability, I think this statement is wrong:

UnsafeLazyInitialization is really safe if the resource is immutable.

However, if the constructor is unpredictable, interesting results may appear. Imagine a constructor like this:

 public class Resource { public final double foo; public Resource() { this.foo = Math.random(); } } 

If we have Thread s, this could lead to 2 threads receiving an object with a different behavior. So, the full statement should read like this:

UnsafeLazyInitialization is really safe if the resource is unchanged and its initialization is consistent.

By convention, I mean that by calling the resource constructor twice we get two objects that behave exactly the same (calling the same methods in the same order on both will give the same results).

+3
Jan 31 '13 at 15:36
source share

After applying the JLS rules to this example, I came to the conclusion that getInstance can definitely return null . In particular, JLS 17.4 :

The memory model determines which values ​​can be read at each point in the program. The actions of each thread in isolation should behave as controlled by the semantics of that thread, except that the values ​​observed by each read are determined by the memory model .

Then it is clear that in the absence of synchronization, null is a legitimate result of the method , since each of the two readings can observe anything.




Evidence

Decomposition of records and records

The program can be decomposed as follows (to clearly see recordings and recordings):

  Some Thread --------------------------------------------------------------------- 10: resource = null; //default value //write ===================================================================== Thread 1 | Thread 2 ----------------------------------+---------------------------------- 11: a = resource; | 21: x = resource; //read 12: if (a == null) | 22: if (x == null) 13: resource = new Resource(); | 23: resource = new Resource(); //write 14: b = resource; | 24: y = resource; //read 15: return b; | 25: return y; 

What JLS Says

JLS 17.4.5 gives read rules to read records:

We say that reading r of a variable v is allowed to observe a record of w in v, if in partial execution order:

  • r is not ordered to w (i.e., this is not the case when hb (r, w)) and
  • there is no intermediate notation w 'in v (i.e. do not write w' in v such that hb (w, w ') and hb (w', r)).

Rule application

In our example, suppose that thread 1 sees zero and correctly initializes the resource . In thread 2, an invalid execution would be for 21 to observe 23 (due to the order of the program), but any other record (10 and 13) can be observed either with:

  • 10 occurs - before all actions, so reading is not performed until 10
  • 21 and 24 have no hb relationship with 13
  • 13 does not happen - until 23 (there is no hb relationship between them)

Thus, both 21 and 24 (our 2 readings) have the ability to observe either 10 (zero) or 13 (non-zero).

Execution path that returns null

In particular, assuming Thread 1 sees zero on line 11 and initializes resource on line 13, Thread 2 can legitimately do the following:

  • 24: y = null (reads record 10)
  • 21: x = non null (read record 13)
  • 22: false
  • 25: return y

Note. To clarify, this does not mean that T2 sees not null, and then sees null (which violates the requirements of causality) - this means that from the point of view of execution, these two reads were reordered, and the second to the first, but it seems that later the record was noticed prior to the earlier, based on the original order of the program.

UPDATE Feb 10

Returning to the code, the actual reordering will be:

 Resource tmp = resource; // null here if (resource != null) { // resource not null here resource = tmp = new Resource(); } return tmp; // returns null 

And since this code is consistently consistent (if it is executed by a single thread, it will always have the same behavior as the source code), it shows that the causality requirements are satisfied (there is a valid execution that leads to the result).




After posting to the concurrency interest list, I received several messages regarding the legality of this reordering, which confirm that null is a legal result:

  • Transformation is definitely legal, as single-threaded execution will not tell the difference. [Note that] the conversion does not seem reasonable - there is no good reason for the compiler to do this. However, given the larger amount of surrounding code, or possibly the optimization of the compiler "error", this may happen.
  • The statement about ordering the internal thread and the order of the program is what made me question the validity of things, but ultimately JMM refers to the bytecode that is being executed. The conversion can be performed by the javac compiler, in which case the null value will be completely correct. And there are no rules for how javac should convert bytecode from a Java source to Java, so ...
+3
Feb 01 '13 at 18:25
source share

There are two questions you ask:

1. Can the getInstance() method return null due to reordering?

(which I think you really are after this, so I will try to answer it first)

Although I believe that creating Java for this is absolutely insane, it seems like you actually right that getInstance() can return null.

Code example:

 if (resource == null) resource = new Resource(); // unsafe publication return resource; 

logically 100% identical to the blog example you linked to:

 if (hash == 0) { // calculate local variable h to be non-zero hash = h; } return hash; 

Jeremy Manson then describes that his code may return 0 due to reordering. Firstly, I did not believe in this, because I thought the following “happen-to” -logical should be done:

  "if (resource == null)" happens before "resource = new Resource();" and "resource = new Resource();" happens before "return resource;" therefore "if (resource == null)" happens before "return resource;", preventing null 

But Jeremy cites the following example in a comment on his blog post, how this code can be correctly rewritten by the compiler:

 read = resource; if (resource==null) read = resource = new Resource(); return read; 

This in a single-threaded environment behaves exactly the same as the source code, but in a multi-threaded environment it can lead to the following execution order:

 Thread 1 Thread 2 ------------------------------- ------------------------------------------------- read = resource; // null read = resource; // null if (resource==null) // true read = resource = new Resource(); // non-null return read; // non-null if (resource==null) // FALSE!!! return read; // NULL!!! 

Now, from an optimization point of view, it makes no sense to me, since the whole point of these things would be to reduce several readings in one place, and in this case there is no point in the fact that the compiler does not generate if (read==null) , preventing the problem. So, as Jeremy points out on his blog, this is unlikely to happen. But it seems that, purely from the point of view of the rules of the language, in fact, this is allowed.

This example is really covered in JLS:

http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4

The effect observed between r2 , r4 and r5 in Table 17.4. Surprising results caused by forward substitution Table 17.4. Surprising results caused by forward substitution is equivalent to what can happen with read = resource , if (resource==null) and return resource in the example above.

Also: why am I referring to a blog post as the ultimate source of response? Because the guy who wrote this is also the guy who wrote JLS chapter 17 on concurrency! So it’s better to be right! :)

2. Would make the Resource immutable to make the getInstance() method thread safe?

Given the potential null result that can occur regardless of whether the Resource volatile or not, the immediate simple answer to this question is: No (not strictly)

If we ignore this extremely unlikely, but possible scenario, the answer is: Depends .

The obvious problem with the code stream is that it can lead to the following execution order (without any reordering):

 Thread 1 Thread 2 ---------------------------------------- ---------------------------------------- if (resource==null) // true; if (resource==null) // true resource=new Resource(); // object 1 return resource; // object 1 resource=new Resource(); // object 2 return resource; // object 2 

Thus, non-thread safety comes from the fact that you can return two different objects from a function (although without reordering, none of them will ever be null ).

Now what the book was probably trying to say is this:

Immutable Java objects, such as strings and integers, try not to create multiple objects for the same content. So, if you have "hello" in one place and "hello" in another place, Java will provide you with the exact same description of the object. Similarly, if you have new Integer(5) in one place and new Integer(5) in another. If this were the case with new Resource() , you would get the same link back, and object 1 and object 2 in the above example would be the same object. This would indeed lead to an efficient thread-safe function (ignoring the reordering problem).

But if you implement Resource yourself, I do not believe that there is even a way for the constructor to return a link to a previously created object, rather than creating a new one. Thus, you cannot make object 1 and object 2 the same object. But, given that you are calling the constructor with the same arguments (neither in both cases), it is likely that although your created objects are not the same exact object, they will, in effect, behave as if they were also effectively make code safe for threads.

This does not have to be so. Imagine an immutable version of Date , for example. The default constructor, Date() uses the current system time as the date value. Thus, although the object is immutable and the constructor is called with the same argument, calling it twice probably will not result in an equivalent object. Therefore, the getInstance() method is not thread safe.

So, as a general statement, I believe that the line you quoted from the book is simply incorrect (at least as inferred from the context here).

ADD Re: reordering

I find the resource==new Resource() example too simplistic to help understand why WHY allows such Java reordering to ever make sense. So let me see if I can come up with something that could help in the optimization:

 System.out.println("Found contact:"); System.out.println(firstname + " " + lastname); if (firstname==null) firstname = ""; if (lastname ==null) lastname = ""; return firstname + " " + lastname; 

, , ifs false , String firstname + " " + lastname , , . , , :

 System.out.println("Found contact:"); String contact = firstname + " " + lastname; System.out.println(contact); if ((firstname==null) || (lastname==null)) { if (firstname==null) firstname = ""; if (lastname ==null) lastname = ""; contact = firstname + " " + lastname; } return contact; 

, , , / , , , . , , - , , , , , , / , , . , , , , , , ( , ).

, , , .

+2
10 . '13 4:30
source share

null , null . , null , -t20, , .

, , . if , .

0
31 . '13 11:19
source share

, ( ), , :

UnsafeLazyInitialization , .

. :

...

,

0
31 . '13 11:47
source share

, , , , , (, ) null. , , :

 public class UnsafeLazyInitialization { private static Resource resource; public static Resource getInstance() { Resource tmp = resource; if (resource == null) tmp = resource = new Resource(); // unsafe publication return tmp; } } 

, null, ( tmp , if , tmp null).

"" ( , ), resource ( , :

 public class UnsafeLazyInitialization { private static Resource resource; public static Resource getInstance() { Resource cur = resource; if (cur == null) { cur = new Resource(); resource = cur; } return cur; } } 
0
31 . '13 15:51
source share

, , concurrency, , .

, concurrency, .
" JVM - ". . , , , .
: , , , . . , . No. (, ). , (.. ). ( singleton, )

0
01 . '16 13:18
source share

UnsafeLazyInitialization.resource , :

 private static final Resource resource = new Resource(); 

, Resource , . Resource , , , getInstance() ).

, , ,

UnsafeLazyInitialization , * r * esource .

-one
31 . '13 11:25
source share

UnsafeLazyInitialization.getInstance() null .

@assylias.

  Some Thread --------------------------------------------------------------------- 10: resource = null; //default value //write ===================================================================== Thread 1 | Thread 2 ----------------------------------+---------------------------------- 11: a = resource; | 21: x = resource; //read 12: if (a == null) | 22: if (x == null) 13: resource = new Resource(); | 23: resource = new Resource(); //write 14: b = resource; | 24: y = resource; //read 15: return b; | 25: return y; 

Thread 1. Thread 1 10 11 11 14. 2. 14, 14, , JMM. , 13, , Thread 2. - 11. , 23. 10 , 11 - -thread ordering.

, Resource . , , , null, -thread. JLS 17.4.7 .

t , t A, , , w V (w), , r V (W (r)). , , . , P.

, , , , , , .

null ( 10). , , null .

null . " JCIP" :

JVM ; - JVM , [JLS 12.4.2] .

, , UnsafeLazyInitialization.getInstance() , null, null. , .

EDIT

, . , .

 public static Object object = new Integer(0); 

1 :

 object = new Integer(1); object = new Integer(2); object = new Integer(3); 

2 :

 System.out.println(object); System.out.println(object); System.out.println(object); 

- , , Thread 2 .

 1, 2, 3 0, 0, 0 3, 3, 3 1, 1, 3 etc. 

, ​​ 3, 2, 1. , 17.4.7, . object , , , .

-one
05 . '13 17:05
source share



All Articles