JVM option to optimize loop statements

Question

I've been told at school that it's a bad practice to modify the index variable of a for loop:

Example :

for(int i = 0 ; i < limit ; i++){
    if(something){
        i+=2;      //bad
    }
    if(something){
        limit+=2;      //bad
    }
}

The argument was that some compiler optimization can optimize the loop and not recalculate the index and bound at each loop.

I 've made some test in java and it seems that by default index and bound are recalculate each time.

I'm wondering if it's possible to activate this kind of feature in the JVM HotSpot?

For example to optimize this kind of loop :

for(int i = 0 ; i < foo.getLength() ; i++){   }

without having to write :

int length = foo.getLength()
for(int i = 0 ; i < length ; i++){   }

It's just an example I'm curious to try and see the improvments.

EDIT

According to Peter Lawrey answer why in this simple example the JVM don't inline getLength() method? :

public static void main(String[] args) {
   Too t = new Too();
   for(int j=0; j<t.getLength();j++){
   }
}


class Too {

    int l = 10;
    public Too() {
    }
    public int getLength(){
        //System.out.println("test");
        return l;
    }
}

In the output "test" is print 10 times.

I think it could be nice to optimize this kind of execution.

EDIT 2 : Seems I made a misunderstood...

I have remove the println and indeed the profiler tell me that the method getLength() is not even call once in this case.

Gold

You seem to misunderstand what inlining does. The 101 of every compiler optimization is that the produced code may be functionally equivalent to the behavior the JLS demands. This means we can inline a function call, but we CAN'T remove a println() call. Also you really shouldn't worry about such compiler optimizations - or if you do, you have to understand at least enough to know how to test this kind of code. – Rufena

Ok I didn't know that, I'm quite new and still learning a lot. This kind of "advance?" knowledges stay unteach at (my) school, so I'm trying to understand by myself and I often make mistakes :s – Gold

Was so free and actually looked at the code in detail - to answer your question shortly: The JIT will inline getLength() just fine, independent whether you have println() statement in there or not. If you want the details I posted a short summary below ;) – Rufena

Answer 1

I've made some test in java and it seems that by default index and bound are recalculate each time.

According to the Java Language Specification, this:

for(int i = 0 ; i < foo.getLength() ; i++){   }

means that getLength() is called on each loop iteration. Java compilers are only allowed to move the getLength() call out of the loop if they can effectively prove that it does not alter the observable behavior.

(For instance, if getLength() just returns the value of some variable, then there is a chance that the JIT compiler can inline the call. If after inlining it can deduce that the variable won't change (under certain assumptions) it can apply a hoisting optimization. On the other hand, if getLength() involves getting the length of a concurrent or synchronized collection, the chances are slim to none that the hoisting optimization will be permitted ... because of potential actions of other threads.)

So that's what a compiler is allowed to do.

I'm wondering if it's possible to activate this kind of feature in the JVM HotSpot?

The simple answer is No.

You seem to be suggesting a compiler switch that tells / allows the compiler to ignore the JLS rules. There is no such switch. Such a switch would be a BAD IDEA. It would be liable to cause correct/valid/working programs to break. Consider this:

class Test {
   int count;

   int test(String[] arg) {
       for (int i = 0; i < getLength(arg); i++) {
           // ...
       }
       return count;
   }

   int getLength(String[] arg) {
       count++;
       return arg.length;
   }
}

If the compiler was permitted to move the getLength(arg) call out of the loop, it would change the number of times that the method was called, and therefore change the value returned by the test method.

^{Java optimizations that change the behaviour of a properly written Java program are not valid optimizations. (Note that multi-threading tends to muddy the waters. The JLS, and specifically the memory model rules, permit a compiler to perform optimizations that could result in different threads seeing inconsistent versions of the application's state ... if they don't synchronize properly, resulting in behaviour that is incorrect from the developer's perspective. But the real problem is with the application, not the compiler.)}

---

By the way, a more convincing reason that you shouldn't change the loop variable in the loop body is that it makes your code harder to understand.

Pandarus

Thanks for informations. For the second part of your answer, I agree that it's probably a bad idea to enable (if it's possible) this feature with working programm. But if you start a project knowing this rules I think it could improve performance. – Gold

The only way to actually tell whether one piece of Java will run faster than another is to use a benchmarking tool specifically designed for Java, that warms up the JVM and everything. – Invariant

@LouisWasserman I used the netbeans profiler. You were rigtht about println, see my edit. – Gold

@Gold - It is totally against Java's "write once, run everywhere" goal to have JVM switches altering the behavior of programs. This isn't C ... where you typically have to play guessing games to figure out which optimization flags help, and which ones break the application. – Pandarus

Answer 2

It depends on what foo.getLength() does. If it can be inlined, it can be effectively the same thing. If it cannot be inlined, the JVM cannot determine whether the result is the same.

BTW you can write for a one liner.

for(int i = 0, length = foo.getLength(); i < length; i++){   }

EDIT: It is worth nothing that;

• methods and loops are usually not optimised until they have been called 10,000 times.
• profilers sub-sample invocations to reduce overhead. They might count every 10 or 100 or more so a trivial example may not show up.

Predikant

Answer 3

The main reason not to do that is that it makes it much harder to understand and maintain the code.

Whatever the JVM optimizes, it won't compromise the correctness of the program. If it can't do an optimization because the index is modified inside the loop, then it won't optimize it. I fail to see how a Java test could show if there is or not such an optimization.

Anyway, Hotspot will optimize a whole lot of things for you. And your second example is a kind of explicit optimization that Hotspot will happily do for you.

Ingrained

HotSpot is a mysterious black box to me, but would it really make that optimization? What about multiple threads modifying the foo such that getLength() was changing, assuming foo is not String, where getLength is immutable? I.e. assume a mutable collection and use getSize() instead. – Talion

For the second example I'm not sure JVM Hotspot make any optimisation. Let's say foo.getLength() return 10, then the method getLength() will be executed 10 times. – Gold

You will never see any actual difference in the program's behavior due to optimizations. If you removed the line System.out.println("test"), it's entirely possible that the JVM would make the optimization. – Invariant

@alain The JLS specifies the behavior of a program in terms of a single thread. That means: Behavior changes that occur only if several threads work together are ignored by the JLS (obviously ignoring the additional semantics of the threading/synchronization constructs!). Also the println() call makes absolutely no problem wrt to inlining - that is as long as we stay within the inlining budget. – Rufena

Answer 4

Before we go into more reasoning why the field access isn't inlined. Maybe we should show that yes, if you know what you're looking for (which really is non-trivial in Java) the field access is inlined just fine.

First we need a basic understanding of how the JIT works - and I really can't do that in one answer. Suffice to say that the JIT only works after a function has been called often enough (>10k usually)

So we use the following code for actual testing stuff:

public class Test {
    private int length;

    public Test() {
        length = 10000;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 14000; i++) {
            foo();
        }
    }

    public static void foo() {
        Test bar = new Test();
        int sum = 0;
        for (int i = 0; i < bar.getLength(); i++) {
            sum += i;
        }
        System.out.println(sum);
    }

    public int getLength() {
        System.out.print("_");
        return length;
    }    
}

Now we compile this code and run it with java.exe -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,*Test.foo Test >Test.txt Which results in a unholy long output, but the interesting part is:

  0x023de0e7: mov    %esi,0x24(%esp)
  0x023de0eb: mov    %edi,0x28(%esp)
  0x023de0ef: mov    $0x38fba220,%edx   ;   {oop(a 'java/lang/Class' = 'java/lang/System')}
  0x023de0f4: mov    0x6c(%edx),%ecx    ;*getstatic out
                                        ; - Test::getLength@0 (line 24)
                                        ; - Test::foo@14 (line 17)
  0x023de0f7: cmp    (%ecx),%eax        ;*invokevirtual print
                                        ; - Test::getLength@5 (line 24)
                                        ; - Test::foo@14 (line 17)
                                        ; implicit exception: dispatches to 0x023de29b
  0x023de0f9: mov    $0x3900e9d0,%edx   ;*invokespecial write
                                        ; - java.io.PrintStream::print@9
                                        ; - Test::getLength@5 (line 24)
                                        ; - Test::foo@14 (line 17)
                                        ;   {oop("_")}
  0x023de0fe: nop    
  0x023de0ff: call   0x0238d1c0         ; OopMap{[32]=Oop off=132}
                                        ;*invokespecial write
                                        ; - java.io.PrintStream::print@9
                                        ; - Test::getLength@5 (line 24)
                                        ; - Test::foo@14 (line 17)
                                        ;   {optimized virtual_call}
  0x023de104: mov    0x20(%esp),%eax
  0x023de108: mov    0x8(%eax),%ecx     ;*getfield length
                                        ; - Test::getLength@9 (line 25)
                                        ; - Test::foo@14 (line 17)
  0x023de10b: mov    0x24(%esp),%esi
  0x023de10f: cmp    %ecx,%esi
  0x023de111: jl     0x023de0d8         ;*if_icmpge
                                        ; - Test::foo@17 (line 17)

which is the inner loop we're actually executing. Note that the following 0x023de108: mov 0x8(%eax),%ecx loads the length value in a register - the stuff above it is for the System.out call (I'd have removed it since it makes it more complicated, but since more than one person thought this would hinder inlining I left it in there). Even if you aren't that fit in x86 assembly you can clearly see: No call instruction anywhere except for the native write call.

Rufena

Unfortunnaletely on ubuntu I get a file full of "_". I don't see any mov lines... – Gold

@alain Make sure you have the necessary plugin installed - and better remove the print statements for testing to make sure you don't just miss it (or install a null stream in system.out) – Rufena

The solution has been found here if someone interested! How to use -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print option with JVM HotSpot – Gold