Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

I know that in JavaScript, creating a for loop like this: for(int i = 0; i < arr.length; i++) is costly as it computes the array length each time. Is this behavior costly in c# for lists and arrays as well. Or at compile-time is it optimized? Also what about other languages such as Java, how is this handled?

like image 302
maxfridbe Avatar asked Nov 04 '08 18:11

maxfridbe


People also ask

Which is more efficient array or List?

The array is faster in case of access to an element while List is faster in case of adding/deleting an element from the collection.

Is List slower than array?

Short answer: In . NET List<T> and Array<T> have the same speed/performance because in . NET List is wrapper around Array .

How can use length of array in for loop?

As already mentioned, you can iterate through an array using the length attribute. The loop for this will iterate through all the elements one by one till (length-1) the element is reached (since arrays start from 0). Using this loop you can search if a specific value is present in the array or not.

Which List is faster in C#?

From the link Difference between O(n) and O(log(n)) - which is better and what exactly is O(log(n))? We can know O(log n) is better than O(n), therefore List<T>. BinarySearch will be faster than List<T>.


2 Answers

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.

like image 156
Konrad Rudolph Avatar answered Sep 22 '22 23:09

Konrad Rudolph


  1. All .Net arrays have a field containing the length of the array, so the length is not computed at usage but at creation time.

  2. The .Net virtual machine is very good at eliminating bounds checks whenever possible, this is one of those cases, where the bounds check is moved outside the loop (in most situations, and if not it's just 2 instructions overhead).

Edit:

Array Bounds Check Elimination

like image 27
Pop Catalin Avatar answered Sep 22 '22 23:09

Pop Catalin