Fix S6602 FP: FirstOrDefault is faster than Find in .NET 9

[marco-carvalho]

Hello,

The rule S6602, which suggests using Find instead of FirstOrDefault, may no longer be applicable for projects targeting .NET 9.0.

Recent benchmarks indicate that starting with .NET 9.0, FirstOrDefault is actually faster than Find. Below are the benchmark results.

Code:

using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Jobs;
using BenchmarkDotNet.Running;

BenchmarkRunner.Run<FindVsFirstOrDefaultBenchmark>();

[SimpleJob(RuntimeMoniker.Net80)]
[SimpleJob(RuntimeMoniker.Net90)]
[MemoryDiagnoser]
[RankColumn]
public class FindVsFirstOrDefaultBenchmark
{
    private readonly List<int> _list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

    [Benchmark]
    public int Find()
    {
        return _list.Find(x => x == 9);
    }

    [Benchmark]
    public int FirstOrDefault()
    {
        return _list.FirstOrDefault(x => x == 9);
    }
}

Results:

| Method         | Job      | Runtime  | Mean      | Error     | StdDev    | Rank | Gen0   | Allocated |
|--------------- |--------- |--------- |----------:|----------:|----------:|-----:|-------:|----------:|
| Find           | .NET 8.0 | .NET 8.0 |  9.604 ns | 0.2962 ns | 0.8595 ns |    3 |      - |         - |
| FirstOrDefault | .NET 8.0 | .NET 8.0 | 26.801 ns | 0.5646 ns | 1.3956 ns |    4 | 0.0095 |      40 B |
| Find           | .NET 9.0 | .NET 9.0 |  8.665 ns | 0.2093 ns | 0.5971 ns |    2 |      - |         - |
| FirstOrDefault | .NET 9.0 | .NET 9.0 |  6.156 ns | 0.1857 ns | 0.5418 ns |    1 |      - |         - |

[marco-carvalho]

Maybe this rule for code targeting .NET 8.0 or below, and a new rule "FirstOrDefault" method should be used instead of the "Find" extension for code targeting .NET 9.0 or above?

[jilles-sg]

List.Find has been unchanged for a long time and reads the list's fields on every iteration of the loop, while FirstOrDefault was recently changed to read the fields once and efficiently loop over the resulting span. Perhaps dotnet/runtime should optimize List.Find too.

Note that FirstOrDefault's optimization may cause "impossible" values to be passed to the callback if the callback removes items from the list (which is wrong, but happened to work).

A rule to change Find back to FirstOrDefault would be bad churn. This kind of micro-optimizations tends to be unstable across versions.

[sebastien-marichal]

Hello @marco-carvalho,

Thank you for pointing this out. We will take a look when we prepare for the .NET 9 release!

Have a great day!

[jilles-sg]

Perhaps dotnet/runtime should optimize List.Find too.

According to https://github.com/dotnet/runtime/issues/108064 and https://github.com/dotnet/runtime/pull/65572#issuecomment-1044993127 , it is deliberate that Find has reasonable behaviour when the predicate mutates the list and is therefore slower.

The idea is that if performance really matters, one should not use a method that takes a delegate. If List<T> must be used, the fastest option is a foreach loop over CollectionsMarshal.AsSpan(list).

One special case may be RemoveAll which is O(N), where a simple loop based on RemoveAt would be quadratic. However, RemoveAll has no LINQ equivalent since it mutates the list.

As a result, S6605 and similar Sonar rules should not recommend anything about methods on List<T> that take delegates. It is still better to write list[0] instead of list.First(), list[^1] instead of list.Last() and list.Count instead of list.Count().

If corresponding methods on Array or ImmutableList<T> are slower than LINQ, Microsoft will probably accept a pull request to fix that, but it is still questionable whether S6605 and similar rules are worth the time for the methods that take delegates.

Regarding older versions of .NET, it is likely that code targeting .NET 5/6/7/8 or .NET Core will be migrated to .NET 9 or newer at some point; for .NET Framework, it might be less likely.