Social Icons

Thursday, June 25, 2015

C# : Efficiently Looping Over An Array

This Tricks can improve the speed of programs that spend a lot of time looping over arrays.

Propably you know from experience, that when you try to access an invalid array element (say, index 11 in an array of size 10) you will get an IndexOutOfRangeException. To be able to generate this exception and prohibit the dangerous access of memory beyond your array storage, the runtime performs an array bounds check everytime you access an array, which checks that the index you supply is lower then the array size.

For example, take a look at this code:



int count = 0;
int[] array = new int[10];
// omitted: fill array with some values
for (int i = 0; i < 10; i++)
    count += array[i];

Here, we simply loop over all elements of the array and add them together.
But what the compiler actually produces looks something like the result of this code:

for (int i = 0; i < 10; i++)
{
    if (i >= array.Length)
        throw new IndexOutOfRangeException();
    count += array[i];
}

Now the hidden cost is only a simple if expression for each array access, but if you have many or very large arrays which get looped over often, it can add up.

But there are two ways to let the compiler skip the bounds checks and speed up array code:

The first way is to use Array.Length as the upper bound of the loop variable, and use the unmodified loop variable to index the array:

for (int i = 0; i < array.Length; i++)
    count += array[i];

The second way is to loop over the array with foreach:
foreach (int x in array)
    count += x;

In both cases, the compiler can be sure that the array index will never be outside its bounds, and skip the bounds check.


No comments:

Post a Comment