While updating for loops to for-each loops in our application, I came across a lot of these "patterns":
for (int i = 0, n = a.length; i < n; i++) {
...
}
instead of
for (int i = 0; i < a.length; i++) {
...
}
I can see that you gain performance for collections because you don't need to call the size() method with each loop. But with arrays??
So the question arose: is array.length more expensive than a regular variable?
No, a call to array.length is O(1) or constant time operation.
Since the .length is(acts like) a public final member of array, it is no slower to access than a local variable. (It is very different from a call to a method like size())
A modern JIT compiler is likely to optimize the call to .length right out anyway.
You can confirm this by either looking at the source code of the JIT compiler in OpenJDK, or by getting the JVM to dump out the JIT compiled native code and examining the code.
Note that there may be cases where the JIT compiler can't do this; e.g.
array.length be O(1) and still take longer than int len = array.length; i < len;, which would also be O(1)? –
Shakespeare .length right out anyway." [citation needed] –
Donnelldonnelly javac didn't optimize anything. I don't know much about JIT compilers. –
Donnelldonnelly I had a bit of time over lunch:
public static void main(String[] args) {
final int[] a = new int[250000000];
long t;
for (int j = 0; j < 10; j++) {
t = System.currentTimeMillis();
for (int i = 0, n = a.length; i < n; i++) { int x = a[i]; }
System.out.println("n = a.length: " + (System.currentTimeMillis() - t));
t = System.currentTimeMillis();
for (int i = 0; i < a.length; i++) { int x = a[i]; }
System.out.println("i < a.length: " + (System.currentTimeMillis() - t));
}
}
The results:
n = a.length: 672
i < a.length: 516
n = a.length: 640
i < a.length: 516
n = a.length: 656
i < a.length: 516
n = a.length: 656
i < a.length: 516
n = a.length: 640
i < a.length: 532
n = a.length: 640
i < a.length: 531
n = a.length: 641
i < a.length: 516
n = a.length: 656
i < a.length: 531
n = a.length: 656
i < a.length: 516
n = a.length: 656
i < a.length: 516
Notes:
n = a.length shows as being faster than i < a.length by about half, probably due to garbage collection(?).250000000 much larger because I got OutOfMemoryError at 270000000.The point is, and it is the one everyone else has been making, you have to run Java out of memory and you still don't see a significant difference in speed between the two alternatives. Spend your development time on things that actually matter.
I doubt there is any significant difference whatsoever, and even if there was, I would bet it's probably optimized away during compilation. You're wasting your time when you try to micro-optimize things like that. Make the code readable and correct first, then if you have a performance problem, use a profiler, then worry about choosing better data structures/algorithms if appropriate, then worry about optimizing the parts your profiler highlights.
.length by orders of magnitude. –
Shakespeare The length of an array is stored as a member variable of the array (not the same as an element) in Java, so fetching that length is a constant time operation, the same as reading a member variable from a regular class. Many older languages like C and C++ don't store the length as part of the array, so you'd want to store the length before the loop starts. You don't have to do that in Java.
It might be ever-so-slightly faster to store it in a variable. But I would be extremely surprised if a profiler pointed to it as being a problem.
At the bytecode level, getting the length of an array is done with the arraylength bytecode. I don't know if it is slower than an iload bytecode, but there shouldn't be enough difference to notice.
In that case, why don't you make an inverse loop:
for (int i = a.length - 1; i >= 0; --i) {
...
}
There are 2 micro optimizations here:
This answer is from a C# point of view, but I would think the same applies to Java.
In C#, the idiom
for (int i = 0; i < a.length; i++) { ...}
is recognized as iterating over the array, so the bounds check is avoided when accessing the array in the loop instead of with each array access.
This may or may not be recognized with code such as:
for (int i = 0, n = a.length; i < n; i++) { ...}
or
n = a.length;
for (int i = 0; i < n; i++) { ...}
How much of this optimization is performed by the compiler vs. the JITter I don't know, and in particular if it's performed by the JITter I'd expect all 3 to generate the same native code.
However, the first form is also arguably more readable by people, so I'd say go with that.
Array.length is a constant and the JIT compiler should see through that in both instances. I would expect the resulting machine code to be the same in both cases. At least for the server compiler.
© 2022 - 2024 — McMap. All rights reserved.