Repository navigation
Poor performance/code-gen with struct enumerators, especially when containing ReadOnlySpan #71510
Description
Description
Struct enumerators have a lot of potential for high-performance iteration of custom structures. I've seen 'struct-linq' discussed in several places. The following is a simple but practical example.
Try changing the type of arr to T[] and inds to ReadOnlySpan<int> and observe differences in stack spill and x86.
I'd love a way to write this code fully with spans and have it be performant.
Even the T[] and int[] version doesn't compare to the equivalent hand-written version (Test2). It looks like loop-cloning doesn't see the enumerator as eligible.
public ref struct FilteredSpanEnumerator<T>
{
private readonly ReadOnlySpan<T> arr;
private readonly int[] inds;
private T current;
private int i;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public FilteredSpanEnumerator(ReadOnlySpan<T> arr, int[] inds) {
this.arr = arr;
this.inds = inds;
current = default;
i = 0;
}
public T Current => current;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public bool MoveNext() {
if (i >= inds.Length)
return false;
current = arr[inds[i++]];
return true;
}
public FilteredSpanEnumerator<T> GetEnumerator() => this;
public static void Test() => Test3(new T[100], new int[] {0, 5, 6, 12, 47, 99});
public static void Test(ReadOnlySpan<T> elements, int[] inds) {
foreach (var s in new FilteredSpanEnumerator<T>(elements, inds)) {
Console.WriteLine(s);
}
}
public static void Test2(ReadOnlySpan<T> elements, ReadOnlySpan<int> inds) {
int i = 0;
while (i < inds.Length) {
Console.WriteLine(elements[inds[i++]]);
}
}
}Configuration
.NET 6.0.6, Win x64
Analysis
Probably a duplicate of a number of issues like #68797 #9977 related to struct promotion and loop cloning heuristics.
category:cq
theme:structs
skill-level:expert
cost:large
impact:medium
Activity
JulieLeeMSFT commentedon Jul 5, 2022
cc @BruceForstall for further triaging.
BruceForstall commentedon Jul 5, 2022
Maybe also related? #9304
Chicken-Bones commentedon Jul 5, 2022
CollectionsMarshal.AsSpanallows for avoiding the versioning overhead and size vs length that list enumerator has, but the "critical block (fork/join)." issue is probably related.Additional reasoning about lengths and bound checks is a generally valuable feature, not applicable in this example, but consider a
Zipenumerator that initializesint len = a.Length < b.Length ? a.Length : b.Length;and iterates fromi = 0tolenEliminating bounds checks can be key in some hot loop scenarios and there's no way to use
unsafewith managed types so we're trying to make the most ofSpanChicken-Bones commentedon Mar 31, 2023
Adding to this, the x86 produced by
ReadOnlySpan<T>.Enumeratoris significantly worse/longer than the for-i loop version (which is produced by the compiler when usingforeachon a span directly). This means that structs/classes which essentially wrap an array or span cannot achieve peak performance with code likepublic ReadOnlySpan<T>.Enumerator GetEnumerator() => _span.GetEnumerator();Instead, such wrappers must force the caller to convert them to a
Span/Arrayexplicitly in order to useforeachjakobbotsch commentedon Apr 4, 2023
@Chicken-Bones Thanks for the example. The problem with the existing JIT is, as you mention, essentially the same as #68797 -- the existing struct promotion the JIT supports cannot handle recursive promotion, so we do not enregister the fields of
FilteredSpanEnumerator.I am working on more general handling for struct promotion in #76928, with a (by default disabled) prototype coming in #83388. The prototype can handle the recursive patterns like in this case. I've turned your code into a benchmark here that shows good results at around 2.5x the speed.
If you have more examples then please feel free to share them. It is very helpful to have as many concrete cases as possible.
Chicken-Bones commentedon Apr 4, 2023
Thanks, this is great to see! The other benchmark I'd like to provide is simple:
and then compare
foreach (var s in span)toforeach (var s in spanWrapper)jakobbotsch commentedon Apr 25, 2023
Thanks! I benchmarked that and it's better, and approaches the
ReadOnlySpan<T>version with tiered PGO. The benchmark is the following:Benchmark code
The results are:
The inner loop of the baseline is
The inner loop without physical promotion of the wrapped version is:
With physical promotion (
DOTNET_JitEnablePhysicalPromotion=1) the generated code is:Seems like this misses one important physical promotion (the
[rsp+40H]). With tiered PGO enabled (DOTNET_TieredPGO=1) we realize that promotion is important and then the codegen is:Which still has an unnecessary bounds check but is very close to the ideal version in performance.
With synthetic PGO instead of tiered PGO (
DOTNET_JitSynthesizeCounts=1, not available in release JIT builds) we do get the extra promotion as well, but we seem to end up with some odd unoptimal flow:(cc @AndyAyersMS in case you are interested)
@Chicken-Bones Are you ok with me adding your benchmarks to our collection of benchmarks at https://github.com/dotnet/performance/, under the MIT license? It will allow us to track the performance of these scenarios better.
Chicken-Bones commentedon Apr 25, 2023
Yes absolutely, please do!