What Is the Cost of Calling Array.Length

What is the Cost of Calling array.length

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.

1. if you are debugging the enclosing method, or
2. if the loop body has enough local variables to force register spilling.

time complexity or hidden cost of Array Name .length in java

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

What is the runtime of array.length?

array.length is O(1) and the loop is O(n) overall (assuming the "something" is constant-time).

Is it different for c?

C is different in that, depending on how the array is allocated, you can either find out its size in O(1) time or not at all. By "not at all" I mean that you have to keep track of the size yourself.

(On a personal note, if that's the caliber of interviewers, I would have reservations about coming to work there.)

Is it costly to do array.length or list.count in a loop

It is not costly in C#. For one thing, there is no “calculation“: querying the length is basically an elementary operation thanks to inlining. And secondly, because (according to its developers), the compiler recognizes this pattern of access and will in fact optimize any (redundant) boundary checks for access on array elements.

And by the way, I believe that something similar is true for modern JavaScript virtual machines, and if it isn't already, it will be very soon since this is a trivial optimization.

Does java cache array length calculation in loops

As always for performance: write the simplest code you can, and test it to see whether it performs well enough.

If you only need the element (and not the index) I would encourage you to use the enhanced-for loop:

for (int value : array) {
    ...
}

As per JLS 14.14.2 that's basically equivalent to your first piece of code, but the code only talks about what you're actually interested in.

But if you do need the index, and assuming you don't change array anywhere, I believe the JIT compiler will optimize the native code to only fetch the length once. Obtaining the length is an O(1) operation, as it's basically just a field within the array, but obviously it does involve hitting memory, so it's better for the eventual code to only do this once... but that doesn't mean that your code has to do this. Note that I wouldn't expect the Java compiler (javac) to perform this optimization - I'd expect the JIT to.

In fact, I believe a good JIT will actually see code such as:

for (int i = 0; i < array.length; i++) {
    int value = array[i];
    ...
}

and be able to optimize away the array bounds checks - it can recognize that if it accesses the same array object all the time, that can't possibly fail with an array bounds error, so it can avoid the check. It may be able to do the same thing for more "clever" code that fetches the length beforehand, but JIT optimizations often deliberately target very common code patterns (in order to get the biggest "bang for buck") and the above way of iterating over an array is very common.

Cost of len() function

It's O(1) (constant time, not depending of actual length of the element - very fast) on every type you've mentioned, plus set and others such as array.array.

Time complexity of JavaScript's array.length

I think it would be constant since it seems that property is set automatically on all arrays and you're just looking it up?

Right. It's a property which is stored (not calculated) and automatically updated as necessary. The specification is explicit about that here and here amongst other places.

In theory, a JavaScript engine would be free to calculate length on access as though it were an accessor property as long as you couldn't tell (which would mean it couldn't literally be an accessor property, because you can detect that in code), but given that length is used repeatedly a lot (for (let n = 0; n < array.length; ++n) springs to mind), I think we can assume that all JavaScript engines in widespread use do what the spec says or at least something that's constant time access.

---

Just FWIW: Remember that JavaScript's standard arrays are, in theory, just objects with special behavior. And in theory, JavaScript objects are property bags. So looking up a property in a property bag could, in theory, depend on how many other properties are there, if the object is implemented as some kind of name->value hashmap (and they used to be, back in the bad old days). Modern engines optimize objects (Chrome's V8 famously creates dynamic classes on the fly and compiles them), but operations on those objects can still change property lookup performance. Adding a property can cause V8 to create a subclass, for instance. Deleting a property (actually using delete) can make V8 throw up its hands and fall back into "dictionary mode," which substantially degrades property access on the object.

In other words: It may vary, engine to engine, even object to object. But if you use arrays purely as arrays (not storing other non-array properties on them), odds are you'll get constant-time lookup.

Java: Why is getting the length of an array O(1)?

No, Java arrays have a length property that stores their length (i.e. every arrays knows its own length). No counting is necessary.

---

Related Topics