Compiler/JIT optimisation of bounds check of for loop in Java and C++

Question

I have learned from this answer on for and while loops in C# that: "The compiler/JIT has optimisations for this scenario as long as you use arr.Length in the condition:"

for(int i = 0 ; i < arr.Length ; i++) {
    Console.WriteLine(arr[i]); // skips bounds check
}

This tempted me to wonder if java compiler has such optimizations.

for(int i=0; i<arr.length; i++) {
    System.out.println(arr[i]); // is bounds check skipped here?
}

I think it does, well, does it? Does the same happen when using Collection like ArrayList?

But what if I have to use the value of myList.size() inside the body of the for loop, considering now myList to be an ArrayList? So in that case will not hoisting myList.size() help, since size() is a method call? For example may be something like this:

int len = myList.size(); // hoisting for using inside the loop
for(int i = 0; i < myList.size(); i++) { // not using hoisted value for optimization
    System.out.println(myList.get(i));

    if(someOtherVariable == len) {
        doSomethingElse();
    }
}

Edit: Though I haven't obtained an answer for java, I am still adding a second part to this question.

Q: Does C++ (C++98/C++11) have such optimisations, e.g. for vector.size() and string.size()? For instance, which is better performance-wise?

for (int i = 0; i < myvector.size(); ++i)
    cout << myvector[i] << " "; // is bounds checking skipped here, like in C#?

or

// does this manual optimisation help improve performance, or does it make?
int size = myvector.size();
for (int i = 0; i < size; ++i)
    cout << myvector[i] << " ";

That said, does such optimisation exist for std::string as well?

Don't worry about it; the method call will usually be inlined anyway. — SLaks, Feb 14 '16 at 02:43
For Arrays and Collection Java already has optimized loop i.e. enhanced for-loop. `for(int n : arr){ System.out.println(n); }` — , Feb 14 '16 at 02:48
Comments so far say only about inlining, but what about the optimisation by not checking bounds when `arr.length` in used in condition, in java? — Sнаđошƒаӽ, Feb 16 '16 at 09:37
I cannot address the first question, but for your second question (about C++), that is really compiler dependent. For example, if you were to test it out, you may find that using GNU's GCC compiler with certain optimization settings gives you better results than using Microsoft's C++ compiler. C++ is native/unmanaged, so all optimizations are applied when the code is compiled. Because of that, it is difficult to judge the efficiency of an approach without knowing which compiler and optimization settings will be used. — Spencer D, Feb 17 '16 at 16:45
C++ `std::vector` does not check bounds in `operator[]` at all so there is nothing to optimize. — StenSoft, Feb 17 '16 at 17:13
For collections, bounds checking cannot be removed in bytecode because it is done by the called method, not at the place of the call. For primitive arrays, compiler can since Java 7 eliminate bounds checking in bytecode if it can prove that out-of-bound access is not possible (JIT and AOT compilers could do that even before Java 7). — StenSoft, Feb 17 '16 at 17:24
@StenSoft why don't you write a little more *in detail*, and as an answer? Thanks! — Sнаđошƒаӽ, Feb 17 '16 at 17:26
`std::string` has the same rules for `operator[]` and `at` as `std::vector` or any other STL container. — StenSoft, Feb 17 '16 at 18:47

StenSoft · Accepted Answer · 2016-02-17T18:01:54.240

Java

Since Java 7, the compiler eliminates bounds checking for primitive arrays if it can prove that out-of-bound access is not possible. Before Java 7, JIT or AOT compilers can do that. For JIT and AOT compilers, it is not limited to for (int i = 0; i < arr.length; i++), it can move bounds checks outside the loop for loops such as for (int i = 0; i < 10000000; i++), reducing it to a single check. If that check fails, it will run a version of the code with full bounds checking to throw the exception at the correct place.

For collections it's much more complicated because the bounds are checked by the called method, not at the place of the call. Generally, it cannot be eliminated from the bytecode but JIT and AOT compilers can eliminate it if they can inline the methods (which depends on how the object is instantiated and where it is stored, among other things, because all non-private methods in Java are virtual so the compiler needs to make sure it won't need virtual call) but I don't know if they actually do.

C++

C++ does not check bounds in operator []. It does check bounds when you use at. at is inlined so it depends on the specific compiler and its flags but generally, the compiler can remove bounds checking if it can prove that out-of-bound access is not possible. It could also move the bounds check outside the loop but it still needs to guarantee that the exception will be thrown at the correct place so I don't know if any does.

Both examples for C++ will be equivalent in a compiler that does Dead Code Elimination, assuming you don't use int size after the for loop. The latter may be faster if you would use some methods that are not inlined. (You can also put the definition of size inside the initialization: for (int i = 0, size = myvector.size(); i < size; ++i))

Compiler/JIT optimisation of bounds check of for loop in Java and C++

1 Answers1

Java

C++