time complexity or hidden cost of .length in java

Question

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.

The time is a constant but its probably a tiny bit slower than storing the length in a stack variable. I suspect this because the JVM has to go to the array and then get the length. But it doesn't scan the array elements and count them. — Lee Meador, Aug 01 '13 at 15:34
see http://stackoverflow.com/questions/5950155/how-is-length-implemented-in-java-arrays — jamesSampica, Aug 01 '13 at 15:34

score 15 · Accepted Answer · answered Aug 01 '13 at 15:34

15

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

answered Aug 01 '13 at 15:34

Jon Skeet

1,421,763
867
9,128
9,194

`It's just a field on the array`. what does this mean? array is not a container which will have a field. can you please explain? thanks for your effort. – Trying Aug 01 '13 at 15:46
@assylias ya. and have doubt in the line `The array's length is available as a final instance variable length.` How come this is handled is my doubt. thanks. – Trying Aug 01 '13 at 15:48
@Trying arrays are Objects, which happen to have one additional field called `length`. – assylias Aug 01 '13 at 15:51
1

@Trying: What do you mean by "how come this is handled"? When you say "array is not a container" - um, it's an object which has a final field called `length`. What do you mean by "array is not a container"? – Jon Skeet Aug 01 '13 at 15:52
@JonSkeet i mean to say that when we declare `int[] a = new int[10]` and i am doing `a.length`. Here `a` is not a class so that it will contain a field called `length` so i am asking how the filed `length` is getting stored, so that it gives `o(1)` access. Thanks. – Trying Aug 01 '13 at 15:55
1

@Trying: `a` is a reference to an object, which is an instance of the `int[]` class. I think you've got some fundamental misconceptions about arrays. I suggest you read http://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html – Jon Skeet Aug 01 '13 at 15:57
@JonSkeet Thanks. I have read the link several times but never read the first line carefully i got clarified by reading the first line itself: `An array is a container object that holds a fixed number of values of a single type.`. Hence array is an `object` so it can have field. That's why it contains a final field naming length and accessing of which is `O(1)`. Thanks. – Trying Aug 01 '13 at 16:01

score 10 · Answer 2 · answered Aug 01 '13 at 15:34

10

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

answered Aug 01 '13 at 15:34

assylias

321,522
82
660
783

2

Run it through `jmh` :) – Marko Topolnik Aug 01 '13 at 15:45
3

I've run it, and your estimate was almost correct: it's *with* "s", namely *zero nanoseconds* :) – Marko Topolnik Aug 01 '13 at 16:07
@MarkoTopolnik my comment was on performance before JIT! I think there is an option somewhere to prevent compilation if you feel bored! – assylias Aug 01 '13 at 16:32
You're guessing right, I do feel bored :) With `-Xint`, the story is quite different: 6.75 ops/msec (cache in local variable) vs. 4.94 ops/msec (fetch .length every time). – Marko Topolnik Aug 01 '13 at 18:20
Wow! I would not have expected it to take so long to be honest... 150,000 nanoseconds to read from a local variable?! I realise I'm not very familiar with the performance of interpreted code. – assylias Aug 01 '13 at 18:22
No, I just quote method invocations per second. You know, the standard `jmh` metric. In one invocation I actually do 10,000 iterations, and do more than just read the .lenght field (the usual stuff). – Marko Topolnik Aug 01 '13 at 18:32
Next I measured the c1 compiler (the one used in the client mode), which only has basic optimizations. There the difference is already negligible: 63.5 vs. 62.7. – Marko Topolnik Aug 01 '13 at 18:34
@MarkoTopolnik I had missed the 10k iterations! That makes more sense! – assylias Aug 01 '13 at 18:37
Thanks for your time! (I try to avoid jmh as it had become even worse than SO w.r.t. my severe procrastination issue!) – assylias Aug 01 '13 at 18:39
1

Ufff... I know what you mean. That tool eats time like it was peanuts. You waste 5 minutes on a full run, only to notice a fatal flaw in your code. Then repeat that 20 times... – Marko Topolnik Aug 01 '13 at 18:46

score 5 · Answer 3 · answered Aug 01 '13 at 16:05

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.

@MarkoTopolnik appreciate the effort. Thanks. +1. – Trying Aug 01 '13 at 17:48 — Trying, Aug 01 '13 at 17:48

zidsal · Answer 4 · 2013-08-01T16:12:25.230

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

score 3 · Answer 5 · answered Aug 01 '13 at 15:36

3

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

answered Aug 01 '13 at 15:36

Pablo Lozano

10,122
2
38
59

2

list.size() is a simple getter for most list implementations. – assylias Aug 01 '13 at 15:36

time complexity or hidden cost of .length in java

5 Answers5

Linked

Related