Performance regression of ~+50% in LINQ(?) in .NET 10 compared to .NET 9

[martincostello]

Description

I've been doing various testing with previews of .NET 10 and have noticed a regression of ~+50% in a benchmark I have.

This appears to have been introduced in .NET 10 preview 5, but I only just noticed it when reviewing the results after updating to .NET 10 preview 6.

The benchmark is of a solution to an Advent of Code puzzle. Based on what the code does (Max(), Min(), First()), I think the regression is in LINQ, but I haven't drilled into exactly where the time is being spent yet.

The runtime performance of the code was significantly improved when updated from .NET 8 to .NET 9, but this improvement has noticeably regressed with .NET 10 since preview 5:

Running a distillation of the original code into a dedicated benchmark gives me the following results:

BenchmarkDotNet v0.15.2, Windows 11 (10.0.26100.4652/24H2/2024Update/HudsonValley)
13th Gen Intel Core i7-13700H 2.90GHz, 1 CPU, 20 logical and 14 physical cores
.NET SDK 10.0.100-preview.6.25358.103
  [Host]     : .NET 8.0.18 (8.0.1825.31117), X64 RyuJIT AVX2
  Job-HFWDAV : .NET 10.0.0 (10.0.25.35903), X64 RyuJIT AVX2
  Job-XMDLXS : .NET 8.0.18 (8.0.1825.31117), X64 RyuJIT AVX2
  Job-NFJGQR : .NET 9.0.7 (9.0.725.31616), X64 RyuJIT AVX2

Method	Runtime	Mean	Error	StdDev	Ratio	Gen0	Gen1	Allocated	Alloc Ratio
Solve	.NET 8.0	2.918 ms	0.0351 ms	0.0293 ms	1.00	46.8750	11.7188	600.94 KB	1.00
Solve	.NET 9.0	1.139 ms	0.0127 ms	0.0113 ms	0.39	44.9219	11.7188	562.14 KB	0.94
Solve	.NET 10.0	1.775 ms	0.0065 ms	0.0058 ms	0.61	44.9219	11.7188	562.14 KB	0.94

I'll freely admit that the absolute performance of the solution to the puzzle could no doubt be improved, but I would expect the relative performance to remain the same or improve.

It may be that the performance regression is the result of an intentional change to improve other use cases and this is just an outlier that has to pay the price, but I thought I would raise it anyway.

Reproduction Steps

1. Clone https://github.com/martincostello/dotnet-10-performance-regression.git
2. Run the following commands from the root of the repository:

   $env:PUZZLE_INPUT = Resolve-Path (Join-Path "." "input.txt")
   dotnet run --configuration Release --framework net8.0 --runtimes net8.0 net9.0 net10.0

Expected behavior

Runtime performance is equivalent to .NET 9.

Actual behavior

Runtime performance is ~150% that of .NET 9.

Regression?

Yes

Known Workarounds

None

Configuration

.NET SDK 10.0.100-preview.6.25358.103

Other information

No response

[BoyBaykiller]

Replacing the linq usage here with for-loop removes the regression for me:

Node node = null;
for (int i = 0; i < nodes.Count; i++)
{
    node = nodes[i];
    if (node.Location.X == x && node.Location.Y == y)
    {
        break;
    }
}

Out of the box:

Method	Runtime	Mean	Error	StdDev	Ratio	Gen0	Gen1	Allocated	Alloc Ratio
Solve	.NET 10.0	2.057 ms	0.0077 ms	0.0065 ms	0.62	7.8125	-	562.14 KB	0.94
Solve	.NET 8.0	3.326 ms	0.0178 ms	0.0167 ms	1.00	11.7188	-	600.94 KB	1.00
Solve	.NET 9.0	1.439 ms	0.0028 ms	0.0024 ms	0.43	9.7656	1.9531	562.14 KB	0.94

With for-loop fix:

Method	Runtime	Mean	Error	StdDev	Ratio	Gen0	Gen1	Allocated	Alloc Ratio
Solve	.NET 10.0	1.441 ms	0.0106 ms	0.0094 ms	0.97	9.7656	1.9531	499.12 KB	1.00
Solve	.NET 8.0	1.483 ms	0.0095 ms	0.0088 ms	1.00	9.7656	1.9531	499.16 KB	1.00
Solve	.NET 9.0	1.459 ms	0.0024 ms	0.0020 ms	0.98	9.7656	1.9531	499.12 KB	1.00

[AndyAyersMS]

Likely codegen related, seems like we no longer inline the delegate method Puzzle+<>c__DisplayClass0_1.<Solve>b__6(class Node)

9.0

00.80%   8E+05       ?        Unknown
59.84%   6.004E+07   Tier-1   [Benchmarks]Puzzle.Solve(class System.Collections.Generic.IEnumerable`1<class System.String>)
21.85%   2.192E+07   Tier-1   [System.Linq]Enumerable.TryGetFirst(class System.Collections.Generic.IEnumerable`1<!!0>,class System.Func`2<!!0,bool>,bool&)
05.28%   5.3E+06     native   coreclr.dll
02.45%   2.46E+06    Tier-1   [System.Private.CoreLib]String.SplitWithPostProcessing(value class System.ReadOnlySpan`1<int32>,value class System.ReadOnlySpan`1<int32>,int32,int32,value class System.StringSplitOptions)
01.86%   1.87E+06    Tier-1   [System.Private.CoreLib]String.MakeSeparatorListVectorized(value class System.ReadOnlySpan`1<wchar>,value class System.Collections.Generic.ValueListBuilder`1<int32>&,wchar,wchar,wchar)
01.16%   1.16E+06    native   ntoskrnl.exe
01.01%   1.01E+06    Tier-1   [System.Private.CoreLib]Number.TryParseBinaryIntegerStyle(value class System.ReadOnlySpan`1<!!0>,value class System.Globalization.NumberStyles,class System.Globalization.NumberFormatInfo,!!1&)
00.98%   9.8E+05     Tier-1   [System.Private.CoreLib]String.Ctor(value class System.ReadOnlySpan`1<wchar>)
00.70%   7E+05       Tier-1   [System.Private.CoreLib]String.TrimHelper(wchar*,int32,value class System.Text.TrimType)
00.65%   6.5E+05     Tier-1   [Benchmarks]Puzzle+Node.Parse(class System.String)
00.50%   5E+05       Tier-1   [System.Private.CoreLib]String.SplitInternal(value class System.ReadOnlySpan`1<wchar>,int32,value class System.StringSplitOptions)
00.36%   3.6E+05     Tier-1   [System.Private.CoreLib]PackedSpanHelpers.IndexOf(int16&,int16,int32)
00.34%   3.4E+05     Tier-1   [System.Private.CoreLib]System.ReadOnlySpan`1[System.Char].ToString()
00.33%   3.3E+05     Tier-1   [System.Linq]Enumerable.MaxInteger(class System.Collections.Generic.IEnumerable`1<!!0>,class System.Func`2<!!0,!!1>)
00.33%   3.3E+05     native   clrjit.dll
00.31%   3.1E+05     Tier-1   [System.Private.CoreLib]String.MakeSeparatorListAny(value class System.ReadOnlySpan`1<wchar>,value class System.ReadOnlySpan`1<wchar>,value class System.Collections.Generic.ValueListBuilder`1<int32>&)
00.28%   2.8E+05     Tier-1   [System.Private.CoreLib]SpanHelpers.Memmove(unsigned int8&,unsigned int8&,unsigned int)
00.28%   2.8E+05     Tier-1   [System.Private.CoreLib]NumberFormatInfo.<GetInstance>g__GetProviderNonNull|58_0(class System.IFormatProvider)
00.25%   2.5E+05     Tier-1   [System.Linq]Enumerable.MinInteger(class System.Collections.Generic.IEnumerable`1<!!0>,class System.Func`2<!!0,!!1>)
00.12%   1.2E+05     Tier-1   [System.Linq]System.Linq.Enumerable+OrderedIterator`2[System.__Canon,System.Int32].TryGetFirst(bool&)
00.11%   1.1E+05     native   ntdll.dll

Benchmark: found 20 intervals; mean interval 498.610ms

10.0 (preview 6)

07.35%   1.09E+07    ?        Unknown
60.07%   8.928E+07   Tier-1   [Benchmarks]Puzzle.Solve(class System.Collections.Generic.IEnumerable`1<class System.String>)
21.24%   3.157E+07   Tier-1   [Benchmarks]Puzzle+<>c__DisplayClass0_1.<Solve>b__6(class Node)
03.67%   5.46E+06    native   coreclr.dll
02.62%   3.9E+06     Tier-1   [System.Private.CoreLib]String.SplitInternal(value class System.ReadOnlySpan`1<wchar>,int32,value class System.StringSplitOptions)
01.29%   1.91E+06    native   ntoskrnl.exe
00.70%   1.04E+06    Tier-1   [System.Private.CoreLib]Number.TryParseBinaryIntegerStyle(value class System.ReadOnlySpan`1<!!0>,value class System.Globalization.NumberStyles,class System.Globalization.NumberFormatInfo,!!1&)
00.66%   9.8E+05     Tier-1   [System.Private.CoreLib]String.Ctor(value class System.ReadOnlySpan`1<wchar>)
00.36%   5.3E+05     Tier-1   [System.Private.CoreLib]String.TrimHelper(wchar*,int32,value class System.Text.TrimType)
00.36%   5.3E+05     Tier-1   [Benchmarks]Puzzle+Node.Parse(class System.String)
00.30%   4.5E+05     Tier-1   [System.Private.CoreLib]System.Collections.Generic.List`1+Enumerator[System.__Canon].MoveNext()
00.29%   4.3E+05     native   clrjit.dll
00.25%   3.7E+05     Tier-1   [System.Private.CoreLib]SpanHelpers.Memmove(unsigned int8&,unsigned int8&,unsigned int)
00.24%   3.5E+05     Tier-1   [System.Private.CoreLib]PackedSpanHelpers.IndexOf(int16&,int16,int32)
00.19%   2.8E+05     Tier-1   [System.Private.CoreLib]NumberFormatInfo.<GetInstance>g__GetProviderNonNull|58_0(class System.IFormatProvider)
00.10%   1.5E+05     Tier-1   [System.Private.CoreLib]System.Collections.Generic.List`1+Enumerator[System.__Canon].get_Current()
00.06%   9E+04       native   ntdll.dll
00.05%   8E+04       Tier-1   [System.Private.CoreLib]String.FastAllocateString(int32)

Benchmark: found 20 intervals; mean interval 739.019ms

[AndyAyersMS]

At first glance I'd say we are being foiled by BDN's own use of Linq colliding with the benchmark's use of Linq, so that PGO is making nonsensical-looking choices.

EG looking at compilation of Puzzle.Solve, we see things like:

Importing BB08 (PC=040) of 'System.Linq.Enumerable:MaxInteger[System.__Canon,int](System.Collections.Generic.IEnumerable`1[System.__Canon],System.Func`2[System.__Canon,int]):int'
    [ 0]  40 (0x028) ldarg.1
    [ 1]  41 (0x029) ldloc.1
    [ 2]  42 (0x02a) callvirt 0A000044
In Compiler::impImportCall: opcode is callvirt, kind=2, callRetType is ref, structSize is 0

impDevirtualizeCall: Trying to devirtualize interface call:
    class for 'this' is System.Collections.Generic.IEnumerator`1[Puzzle+Node] (attrib 20200600)
    base method is System.Collections.Generic.IEnumerator`1[System.__Canon]::get_Current
Considering guarded devirtualization at IL offset 42 (0x2a)
Likely classes for call [001577] on class 00007FFC90C96640 (System.Collections.Generic.IEnumerator`1[Puzzle+Node])
  1) 00007FFC906E6860 (System.SZGenericArrayEnumerator`1[System.String]) [likelihood:100%]
Accepting type System.SZGenericArrayEnumerator`1[System.String] with likelihood 100 as a candidate
GDV likely: resolveVirtualMethod (method 00007FFC8FF119E8 class 00007FFC906E6860 context 00007FFC90C96641)
Can't figure out which method would be invoked, sorry. [object class could not be cast to interface class]
INLINER: during 'impMarkInlineCandidate' result 'failed this call site' reason 'target not direct' for 'System.Linq.Enumerable:MaxInteger[System.__Canon,int](System.Collections.Generic.IEnumerable`1[System.__Canon],System.Func`2[System.__Canon,int]):int' calling 'System.Collections.Generic.IEnumerator`1[System.__Canon]:get_Current():System.__Canon:this'
INLINER: during 'impMarkInlineCandidate' result 'failed this call site' reason 'target not direct'

Saving generic context 00007FFC90C96641 and inline context 00000103033450A8 for call [001577]

    [ 2]  47 (0x02f) callvirt 0A000068
In Compiler::impImportCall: opcode is callvirt, kind=0, callRetType is int, structSize is 0
Considering guarded devirtualization at IL offset 47 (0x2f)
Likely methods for call [001578] to method System.Func`2[System.__Canon,int]:Invoke(System.__Canon):int:this
  1) 00007FFC90AF14E8 (BenchmarkDotNet.Reports.Measurement+<>c:<.cctor>b__31_0(System.String):int:this) [likelihood:50%]
  2) 00007FFC90AF1500 (BenchmarkDotNet.Reports.Measurement+<>c:<.cctor>b__31_1(System.String):int:this) [likelihood:50%]
delegate call would invoke method BenchmarkDotNet.Reports.Measurement+<>c:<.cctor>b__31_0(System.String):int:this
Marking call [001578] as guarded devirtualization candidate; will guess for method BenchmarkDotNet.Reports.Measurement+<>c:<.cctor>b__31_0(System.String):int:this

[AndyAyersMS]

Probably the first question to answer is why the profile at offset 47 in MaxInteger looks the way it does -- there are no samples for the expected method, just bits of BDN. One possibility is that we may be seeing the impact of overly aggressive Tier1+Instr here too (like what lead to #117492). However latest main builds don't show any improvement.

Note that the main benchmark method loops enough to trigger OSR, so our only opportunity to instrument is at Tier1.

[AndyAyersMS]

Think I can extend the fix from #117492 to also cover OSR (basically restoring OSR inlining to .NET 9 behavior).