Array iteration performance in C#

Snails, Parque Urbano Vale da Montanha, Lisbon, Portugal by aalmada

Implementing the sum of the items in an array is very simple. I think most developers would implement it this way:

There’s actually a simpler alternative in C#:

Another alternative is to use the operation provided by LINQ. It can be applied to any enumerable, including arrays.

So, how do these fair in terms of performance?

You can see that, comparing to using a loop, using a loop is almost 1.4 times faster, while using LINQ is almost 7 times slower and allocates on the heap. Why is that?

NOTE: All benchmarks were performed on .NET 6.0 Preview 5. The results may vary on other target frameworks.

LINQ

NOTE: In this article I’m refering to the LINQ implementation that comes with .NET, in the namespace. There are many alternative implementation that optimize for when the source is an array.

If you check the source code for the in , you’ll find that it uses a loop. So, if using a is faster than a , why is it so slow in this case?

Notice that is an extension method for the type . Unlike the operation, does not have a special case for when the source in an array.

ReSharper and Roslyn analyzers may suggest changing to IGNORE THEM when is an array! doesn’t have a special case for when the source in an array, making it slower.

implementation in LINQ expands to something like this:

There are several performance issues with this code.

, for an interface, allocates an enumerator on the heap. It requires a to dispose the enumerator, making it impossible to inline this method.

For each item in the collection, it calls the method and the property, which are virtual calls in the case of interfaces. This makes the enumeration of the array almost 7 times slower.

ReSharper and Roslyn analyzers may suggest changing parameters of type array to an interface, IGNORE THEM! Create an overload if you need to support other enumerable types.

Foreach

How can be faster than a loop?

The in C# usually generates code very similar to the one expanded for the LINQ case. In case of arrays, it’s handled differently. It expands to code equivalent to the one generated for a loop.

So, how can it still be faster than in the first example?

The code generated for the is slightly different. It uses a temporary variable for the array. It then uses the property and the indexer of this variable. This way the JIT compiler can remove bounds checking throughout the iteration.

NOTE: The temporary variable should only be needed for non-local variables. It’s been pointed out in the comments that is a parameter, so it’s already a local variable. For some reason RyuJIT misses the optimization in this case.

So, how do these fair in terms of performance?

As you can see, the optimized version has the same performance as . Having temporary variables may actually improve performance.

ReSharper and Roslyn analyzers may suggest to inline the temporary variable, IGNORE THEM!

Slice

Sometimes we may want to iterate just a portion of the array. I think most developers would implement the following:

Once again, there’s a simpler alternative:

Notice that the parameter now is of type . It represents a slice/portion of contiguous memory. This way, a portion of an array can be passed into the method. The will only iterate through that portion.

So, how do these fair in terms of performance?

Both implementations have similar performance but around 1.33 time slower than when iterating the full array. If you know you’re iterating the full array, prefer the first implementation.

In this case using temporary variables doesn’t make much difference. The compiler cannot infer if and are always within bounds.

SIMD

All the iteration above were sequencial, meaning that the items in the array were handled one element at the time.

CPUs may allow the simultaneous handling of multiple items using SIMD. This is available in .NET through the namespace, or the more recent namespace.

Here is an implementation of using :

It performs the following:

  1. Checks if SIMD is available and if it’s worth using it, otherwise go to 7.
  2. Casts the array of to an array of .
  3. Creates a initialized to zeros ().
  4. Sums all the vectors from the array of into .
  5. Each item contains a partial sum. Sum them all.
  6. The length of the original array may not be a multiple of the size of . Calculate the number of items not handled and slice the original .
  7. Sum all the not handled items.

So, how do these fair in terms of performance?

It’s almost 5 times faster than the fastest until now.

List<T>

can also be iterated in two different ways. Using a loop, which will use its indexer, or using a or LINQ, which will use an enumerator.

To guarantee performance, we can implement one more overload of using a loop:

ReSharper and Roslyn analyzers may suggest changing parameters of type to an interface, IGNORE THEM! uses a value type enumerator to avoid heap allocations and virtual calls. Using the indexer will still be slower. Create an overload if you need to support other enumerable types.

Starting from .NET 5.0, there’s a method that returns a reference to the inner array as a .

We can then implement a that calls the SIMD version of declared above:

Using makes it 1.28 times slower, while using makes it 5.6 times faster.

Conclusions

Iteration of an array is a special case for the compiler. It may optimize the iteration but small changes may confuse it. The compiler does not optimize the iteration on other types of collections.

ReSharper and Roslyn analyzer are not always to be trusted in terms of performance.

is slow for arrays in most cases. Avoid its use when the source is an array or use one of the many alternatives.

can be iterated as a .

Sequential processing is inherently slow. Favor the use of SIMD.

The benchmarking source code is available at https://github.com/aalmada/ArrayIteration

--

--

Principal Engineer @ Farfetch - R&D https://about.me/antao.almada

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store