In this recent video by Nick Chapsas at the end he commented that the Find method on List<T> was “unoptimized” because the code doesn’t iterate on the Span of the array, but on the array itself:
public T? Find(Predicate<T> match) {
if (match == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
for (int i = 0; i < _size; i++) {
if (match(_items[i])) {
return _items[i];
}
}
return default;
}
I thought that iterating on spans can be made as fast as on arrays (but not faster) from this paragraph of the (updated?) blogpost by Stephen Toub on Spans:
The assembly code is so similar in part because of the elimination of
bounds checks. But also relevant is the JIT’s recognition of the span
indexer as an intrinsic, meaning that the JIT generates special code
for the indexer, rather than translating its actual IL code into
assembly.All of this is to illustrate that the runtime can apply for spans the
same kinds of optimizations it does for arrays, making spans an
efficient mechanism for accessing data.
When did it become self-evident that iterating on the Span of an array would be as fast and maybe faster than just iterating on the array itself? What .NET version introduced these JIT Span optimizations that couldn’t be used for arrays?
9
Iterating over a span has two advantages here:
- it avoids an indirection into a field (rather than a local) for the array
- the span’s length is known in a predictable way
If it wasn’t for _size also being in play, it might be possible to fix the code; i.e. given:
for(int i = 0 ; i < _arr.Length ; i++)
{
DoSomething(_arr[i]);
}
simply hoisting _arr into a local allows the JIT to elide the bounds checks, because the array can’t be reassigned:
var arr = _arr;
for(int i = 0 ; i < arr.Length ; i++)
{
DoSomething(arr[i]);
}
Note also that both foreach (var x in _arr) and foreach (var x in arr) would be fine and allow the bounds checks to be elided. However, the pesky _size means that the bounds checks cannot be elided, and if the _size doesn’t match _arr.Length (oversized buffers), we can’t use simple foreach. Span fixes this indirectly, because the span is bounded; creating a span of length _size means that once the span has been constructed (with bounds validation in the constructor) the JIT can trust it, and elide the bounds checks.
5