Array iteration performance in C# — ArraySegment<T>

Dinokart, Lourinhã, Portugal by aalmada

In my previous post I left out ArraySegment<T>. This is a value type that implements a way to slice arrays but that has now been replaced by Span<T> or Memory<T>.

Span<T> supports other types of contiguous memory collections but, if you’re using just arrays, ArraySegment<T> has a few advantages.

Span<T> cannot be used as a generics type and can only be used as a field type in a ref struct. With any other struct, or class, you’ll have to use a Memory<T> field type. To enumerate a Memory<T>, you have to call its Span property, which creates a new instance of Span<T>. This may be a big performance hit if, for example, the type containing this field has a method that accesses just one item. It takes time to create the Span<T> instance to then simply access a memory location.

Span<T> and Memory<T> don’t implement IEnumerable<T> so the LINQ operations defined in System.Linq cannot be used. You’ll have to use NetFabric.Hyperlinq or SpanLinq. ArraySegment<T> can be used with any LINQ implementation.

So, how do these fair in terms of performance?

All the benchmarks calculate the sum of the items in a slice/segment of an array of int.

For comparison, the two first lines are the slice iteration examples defined in the previous post. Array_For uses a for loop to iterate an array between two indices. Span_ForEach uses a foreach loop to iterate a ReadOnlySpan<T>.

ArraySegment_For uses a for loop, ArraySegment_ForEach uses a foreach loop, and ArraySegment_Linq uses the Sum() operator defined in System.Linq.

Unlike arrays and Span<T>, the C# compiler does not treat ArraySegment<T> as a special case. It does not remove bounds checking, and foreach does not use the indexer. It allocates an instance of an enumerator and uses it.

This makes ArraySegment<T> perform much worse than the other methods of slicing an array. Using the for loop is 1.27 times slower, using the foreach loop is 5 times slower, and using System.Linq is 11 times slower.

Fortunately, there are two very simple workarounds to this:

1. Unlike Span<T>, ArraySegment<T> provides access to the inner array. This allows very fast access to a single item and also the use of the first iteration method on the SegmentArray<T>.
2. There’s an extension method AsSpan() that converts the ArraySegment<T> to a Span<T>. This allows the use of the second iteration method on the SegmentArray<T>.

Just to confirm, lets now run the benchmarks for these two:

As expected, these have the same performance as the methods defined in the previous post.

For LINQ operations, the only option is to use an alternative implementation…

Conclusion

Using the indexer or the enumerator of a ArraySegment<T> is slow. Given that it’s possible to access its inner array, it’s just like having the array and the slice bounds in a value type. Using it this way, allows to work around a few of the Memory<T> performance limitations, with simple APIs without having to declare a new type.

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