CODEWITHSUNDEEP
javaarrayscomplexity-theory
Trying
Trying

Reputation: 14278

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.

Upvotes: 13

Views: 8831

Answers (5)

zidsal
zidsal

Reputation: 587

in java arrays are fixed. Once you declare it you can not change that array's size in memory (if you tried to change the array size it will make a new array in memory).

Because of this we get O(1) length lookup. As we know the total size in memory of the array. If we also look up the size in memory of the first index we can do a quick calculation to get length at O(1) speed. As no matter how big our array is, its going take the same amount of time to lookup the size in memory and lookup the first index's size

Upvotes: 4

Marko Topolnik
Marko Topolnik

Reputation: 200148

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.

Upvotes: 5

Pablo Lozano
Pablo Lozano

Reputation: 10342

In an array, length is not a function as in List.size(). When you create an array in java, its length is a constant. So the cost is minimal

Upvotes: 3

assylias
assylias

Reputation: 328598

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").

Upvotes: 10

Jon Skeet
Jon Skeet

Reputation: 1500095

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.)

Upvotes: 15

Related Questions