Why HotSpot will optimize the following using hoisting?

Question

In the "Effective Java", the author mentioned that

while (!done) i++;

can be optimized by HotSpot into

if (!done) {
    while (true) i++;
}

I am very confused about it. The variable done is usually not a const, why can compiler optimize that way?

Palingenesis

Answer 1

The author assumes there that the variable done is a local variable, which does not have any requirements in the Java Memory Model to expose its value to other threads without synchronization primitives. Or said another way: the value of done won't be changed or viewed by any code other than what's shown here.

In that case, since the loop doesn't change the value of done, its value can be effectively ignored, and the compiler can hoist the evaluation of that variable outside the loop, preventing it from being evaluated in the "hot" part of the loop. This makes the loop run faster because it has to do less work.

This works in more complicated expressions too, such as the length of an array:

int[] array = new int[10000];
for (int i = 0; i < array.length; ++i) {
    array[i] = Random.nextInt();
}

In this case, the naive implementation would evaluate the length of the array 10,000 times, but since the variable array is never assigned and the length of the array will never change, the evaluation can change to:

int[] array = new int[10000];
for (int i = 0, $l = array.length; i < $l; ++i) {
    array[i] = Random.nextInt();
}

Other optimizations also apply here unrelated to hoisting.

Hope that helps.

Gas

I don't get it, how will the loop be terminated, if condition is always true? – Reincarnation

I believe the author of EJ's point is that because the JIT compiler can optimize this way, a programmer should not depend on the value of 'done' changing from a different thread. It's possible that the JIT compiler could optimize the code to this construct and then the loop really never would terminate. – Gas

This optimisation can happen even if done is an instance or class variable, as long as it is not volatile. – Caesar

Answer 2

Joshua Bloch's "Effective Java" explains why you must be careful when sharing variables between threads. If there doesn't exist any explicit happens before relation between threads, the HotSpot compiler is allowed to optimize the code for speed reasons as shown by dmide.

Most nowadays microprocessors offer different kinds of out-of-order strategies. This leads to a weak consistency model which is also the base for Java's Platform Memory Model. The idea behind is, as long as the programmer does not explicitly express the need for an inter-thread coordination, the processor and the compiler can do different optimizations.

The two keywords volatile (atomicity & visibility) and synchronized (atomicity & visibility & mutual exclusion) are used for expressing the visibility of changes (for other threads). However, in addition you must know the happens before rules (see Goetz et al “Java Concurrency in Practice” p. 341f (JCP) and Java Language Specification §17).

So, what happens when System.out.println() is called? See above. First of all, you need two System.out.println() calls. One in the main method (after changing done) and one in the started thread (in the while loop). Now, we must consider the program order rule and the monitor lock rule from JLS §17. Here the short version: You have a common lock object M. Everything that happens in a thread A before A unlocks M is visible to another thread B in that moment when B locks M (see JCP).

In our case the two threads share a common PrintStream object in System.out. When we take a look inside println() you see a call of synchronized(this).

Conclusion: Both threads share a common lock M which is locked and unlocked. System.out.println() “flushes” the state change of variable done.

Indra

Good answer. Note: there is no flushing of variables. Caches are always coherent and the source of truth. Also there is no operation to 'flush caches' to main memory. – Inappetence

You are right, the verb flush is misleading. I used the double-quoted "flush" to emphasize what the programmer sees, not what happens inside JMM. JSR133 FAQ (cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#volatile) mentions, that writing to a volatile variable initiates a real flush operation. However, The JLS is silent on this. The reason is simple. The JMM can implement a suitable solution for the visibility guarantees on each supported platform. – Indra

Answer 3

If you add System.out.println("i = " + i); in the while loop. The hoisting won't work, meaning the program stops as expected. The println method is thread safe so that the jvm can not optimize the code segment?

Crankshaft

Answer 4

public class StopThread {
private static boolean stopRequested;

private static synchronized void requestStop() {
    stopRequested = true;
}

private static synchronized boolean stopRequested() {
    return stopRequested;
}

public static void main(String[] args)
                throws InterruptedException {
    Thread backgroundThread = new Thread(new Runnable() {
        public void run() {
            int i = 0;
            while (!stopRequested())
                i++;
        }
    });
    backgroundThread.start();
    TimeUnit.SECONDS.sleep(1);
    requestStop();
}
}

the above code is right in effective code,it is equivalent that use volatile to decorate the stopRequested.

private static boolean stopRequested() {
  return stopRequested;
}

If this method omit the synchronized keyword, this program isn't working well.
I think that this change cause the hoisting when the method omit the synchronized keyword.

Proposal