time complexity or hidden cost of <Array Name>.length in java
I was looking at a project in java and found a for
loop which was written like below:
for(int i=1; i<a.length; i++)
{
...........
...........
...........
}
My question is: is it costly to calculate the a.length
(here a is array name)? if no then how a.length
is getting calculated internally (means how JVM make sure O(1) access to this)? Is is similar to:
int length = a.length;
for(int i=1; i<length; i++)
{
...........
...........
...........
}
i.e. like accessing a local variable's value inside the function. Thanks.
My question is: is it costly to calculate the a.length
No. It's just a field on the array (see JLS section 10.7). It's not costly, and the JVM knows it will never change and can optimize loops appropriately. (Indeed, I would expect a good JIT to notice the normal pattern of initializing a variable with a non-negative number, check that it's less than length
and then access the array - if it notices that, it can remove the array boundary check.)
a.length
is not a calculation but merely an access to a field held within the array. That type of read operation is super fast.
If the code is part of a method which is called often enough, it is almost certain that the JIT compiler will do the optimisation you propose to make it even faster.
The potential speed difference is in nanoseconds here (probably without an "s").
For your convenience, I've microbenchmarked it. The code:
public class ArrayLength
{
static final boolean[] ary = new boolean[10_000_000];
static final Random rnd = new Random();
@GenerateMicroBenchmark public void everyTime() {
int sum = rnd.nextInt();
for (int i = 0; i < ary.length; i++) sum += sum;
}
@GenerateMicroBenchmark public void justOnce() {
int sum = rnd.nextInt();
final int length = ary.length;
for (int i = 0; i < length; i++) sum += sum;
}
}
The results:
Benchmark Mode Thr Cnt Sec Mean Mean error Units
o.s.ArrayLength.everyTime thrpt 1 3 5 40215.790 1490.800 ops/msec
o.s.ArrayLength.justOnce thrpt 1 3 5 40231.192 966.007 ops/msec
Summary: no detectable change.