Description
Description
While benchmarking my code I found that by using a List<T> and Linq.FirstOrDefault() with a specific predicate we have better performance instead of using the List<T>.Find() method. So, digging, I found that Linq.FirstOrDefault() has a new implementation where, based on the type (whether List<T> or T[]), it gets a span from it and then iterates it. I have now implemented the same behavior in List<T>.Find() and it seems in line with Linq.FirstOrDefault(), if not slightly better. I have the changes ready in this draft PR #108068.
Let me know what you think :)
NOTE: I wasn't able to find the microbenchmarks regarding both the .Find() and .FirstOrDefault() in the performance repo. I'm going to create them right away and have a PR so we can also have better comparison than the one I did.
Configuration
BenchmarkDotNet v0.14.0, macOS Sonoma 14.6.1 (23G93) [Darwin 23.6.0]
Apple M2 Pro, 1 CPU, 12 logical and 12 physical cores
.NET SDK 9.0.100-rc.1.24452.12
[Host] : .NET 9.0.0 (9.0.24.43107), Arm64 RyuJIT AdvSIMD
DefaultJob : .NET 9.0.0 (9.0.24.43107), Arm64 RyuJIT AdvSIMD
Regression?
No regression
Data
Here you can find my benchmarks: https://github.com/DevisTedeschi99/ListFindBenchmarks
| Method | TotalItemCount | SearchValue | Mean | Error | StdDev | Ratio | RatioSD | Gen0 | Gen1 | Allocated | Alloc Ratio |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Before_Find | 50 | 10 | 1,185.1 us | 4.40 us | 4.12 us | baseline | 763.6719 | - | 6.1 MB | ||
| After_Find | 50 | 10 | 957.9 us | 4.26 us | 3.33 us | -19% | 0.5% | 764.6484 | - | 6.1 MB | +0% |
| Before_Find | 50 | 100 | 4,121.1 us | 7.69 us | 7.19 us | baseline | 757.8125 | - | 6.1 MB | ||
| After_Find | 50 | 100 | 2,680.6 us | 4.66 us | 4.36 us | -35% | 0.2% | 761.7188 | - | 6.1 MB | -0% |
| Before_Find | 50 | 1000 | 4,109.9 us | 6.55 us | 5.47 us | baseline | 757.8125 | - | 6.1 MB | ||
| After_Find | 50 | 1000 | 2,678.7 us | 11.11 us | 10.39 us | -35% | 0.4% | 761.7188 | - | 6.1 MB | -0% |
| Before_Find | 50 | 1000000 | 4,105.8 us | 7.47 us | 6.62 us | baseline | 757.8125 | - | 6.1 MB | ||
| After_Find | 50 | 1000000 | 2,663.2 us | 7.38 us | 6.90 us | -35% | 0.3% | 761.7188 | - | 6.1 MB | -0% |
| Before_Find | 500 | 10 | 1,196.5 us | 2.83 us | 2.64 us | baseline | 763.6719 | - | 6.1 MB | ||
| After_Find | 500 | 10 | 961.1 us | 2.12 us | 1.98 us | -20% | 0.3% | 764.6484 | - | 6.1 MB | +0% |
| Before_Find | 500 | 100 | 9,417.8 us | 30.95 us | 28.95 us | baseline | 750.0000 | - | 6.1 MB | ||
| After_Find | 500 | 100 | 4,766.6 us | 6.64 us | 5.88 us | -49% | 0.3% | 757.8125 | - | 6.1 MB | -0% |
| Before_Find | 500 | 1000 | 38,104.2 us | 72.95 us | 68.24 us | baseline | 714.2857 | - | 6.1 MB | ||
| After_Find | 500 | 1000 | 22,230.1 us | 53.18 us | 44.41 us | -42% | 0.3% | 750.0000 | - | 6.1 MB | -0% |
| Before_Find | 500 | 1000000 | 38,158.9 us | 44.88 us | 37.47 us | baseline | 714.2857 | - | 6.1 MB | ||
| After_Find | 500 | 1000000 | 22,217.7 us | 60.56 us | 53.69 us | -42% | 0.3% | 750.0000 | - | 6.1 MB | -0% |
| Before_Find | 5000 | 10 | 1,193.5 us | 2.17 us | 2.03 us | baseline | 763.6719 | - | 6.1 MB | ||
| After_Find | 5000 | 10 | 959.8 us | 6.63 us | 5.18 us | -20% | 0.5% | 764.6484 | - | 6.1 MB | +0% |
| Before_Find | 5000 | 100 | 8,629.3 us | 17.27 us | 14.43 us | baseline | 750.0000 | - | 6.1 MB | ||
| After_Find | 5000 | 100 | 4,766.7 us | 10.54 us | 9.86 us | -45% | 0.3% | 757.8125 | - | 6.1 MB | -0% |
| Before_Find | 5000 | 1000 | 132,489.1 us | 526.54 us | 439.69 us | baseline | 666.6667 | - | 6.1 MB | ||
| After_Find | 5000 | 1000 | 48,045.4 us | 74.33 us | 69.53 us | -64% | 0.3% | 727.2727 | - | 6.1 MB | -0% |
| Before_Find | 5000 | 1000000 | 753,268.3 us | 2,081.67 us | 1,947.19 us | baseline | - | - | 6.1 MB | ||
| After_Find | 5000 | 1000000 | 526,462.1 us | 2,192.92 us | 2,051.26 us | -30% | 0.5% | - | - | 6.1 MB | +0% |
| Before_Find | 5000000 | 10 | 1,188.5 us | 2.63 us | 2.46 us | baseline | 763.6719 | 763.6719 | 6.1 MB | ||
| After_Find | 5000000 | 10 | 954.5 us | 1.35 us | 1.05 us | -20% | 0.2% | 763.6719 | 763.6719 | 6.1 MB | +0% |
| Before_Find | 5000000 | 100 | 8,671.3 us | 17.55 us | 16.42 us | baseline | 750.0000 | 750.0000 | 6.1 MB | ||
| After_Find | 5000000 | 100 | 4,773.8 us | 6.82 us | 6.04 us | -45% | 0.2% | 757.8125 | 757.8125 | 6.1 MB | -0% |
| Before_Find | 5000000 | 1000 | 139,832.1 us | 727.72 us | 607.68 us | baseline | 666.6667 | 666.6667 | 6.1 MB | ||
| After_Find | 5000000 | 1000 | 50,787.4 us | 270.26 us | 239.58 us | -64% | 0.6% | 700.0000 | 700.0000 | 6.1 MB | -0% |
| Before_Find | 5000000 | 1000000 | 279,197,157.0 us | 1,347,861.75 us | 1,260,790.72 us | baseline | - | - | 6.1 MB | ||
| After_Find | 5000000 | 1000000 | 273,651,062.9 us | 502,296.80 us | 445,273.03 us | -2% | 0.5% | - | - | 6.1 MB | +0% |
Small code snippet of the change
Analysis
No Analysis