https://blog.ndepend.com/net-9-0-linq-performance-improvements/

[                                                                           ]
[Search]
x
NDepend New Version v2024.1

  *  
  * Search

  * Product
      + Meet ndepend.

      + NewNDepend v2024.1 Released!
      + NewSample Web Reports
      + Use Cases
      + Getting Started
      + Features
      + Sample Reports
      + Screenshots
      + Default Rules
      + Testimonials
      + Need more information?

      + Case Studies and Resources
      + NDepend User Voice
      + Developer   vs
        Build-Machine   vs
        Azure DevOps / TFS extension
      + What's New
      + Release Notes
        -------------------------------------------------------------
      + JArchitect, NDepend for Java
      + CppDepend, NDepend for C++
  * Free Trial
  * Buy & Renew
  * Docs
  * Videos
  * About
      + Contact Us
      + Partners
      + Trainings
      + EULA
  * Blog

NDepend Blog

Improve your .NET code quality with NDepend

.NET 9.0 LINQ Performance Improvements

Share this:

  * Facebook
  * Twitter
  * LinkedIn
  * 

October 17, 2024 5 minutes read

.NET 9.0 LINQ Performance Improvements NET 9.0 brings significant
improvements to LINQ performance, with some scenarios showing
remarkable gains. Let's take a closer look at what's driving these
enhancements. The lessons learned will be relevant to your code.

Index

Toggle

  * Iterating with Span<T> when Possible
      + The TryGetSpan() Method
      + TryGetSpan() Callers
  * Specialized Iterators
      + The Astute
      + The implementation: Iterator<T> and its Derived Class
      + Case Study: ListWhereSelectIterator<TSource, TResult>
      + Case Study: IListSkipTakeIterator<TSource>
  * Conclusion

Iterating with Span<T> when Possible

Let's start by running this benchmark on .NET 8 versus .NET 9.

C
[using BenchmarkDotNe]

   using BenchmarkDotNet.Configs;
1  using BenchmarkDotNet.Running;
2  using BenchmarkDotNet.Attributes;
3  using BenchmarkDotNet.Jobs;
4   
5  BenchmarkRunner.Run<Benchmarks>();
6   
7  [MemoryDiagnoser]
8  [HideColumns("StdDev", "Median", "Job", "RatioSD", "Error", "Gen0"
9  , "Alloc Ratio")]
10 [SimpleJob(RuntimeMoniker.Net80, baseline: true)]
11 [SimpleJob(RuntimeMoniker.Net90)]
12 public class Benchmarks {
13    private IEnumerable<int> _array = Enumerable.Range(1, 10_000).
14 ToArray();
15  
16    [Benchmark] public int Count() => _array.Count(i => i > 0);
17    [Benchmark] public bool All() => _array.All(i => i > 500);
18    [Benchmark] public bool Any() => _array.Any(i => i == 9_999);
19    [Benchmark] public int First() => _array.First(i => i > 9_000);
20    [Benchmark] public int Single() => _array.Single(i => i == 
21 9_999);
      [Benchmark] public int Last() => _array.Last(i => i > 0);
   }

As a reminder, the .csproj file should look like this to run the
benchmark with BenchmarkDotNet and the project must be compiled in
Release mode.

C
[<Project Sdk="Micros]

1  <Project Sdk="Microsoft.NET.Sdk">
2    <PropertyGroup>
3      <OutputType>Exe</OutputType>
4      <TargetFrameworks>net8.0;net9.0</TargetFrameworks>
5      <ImplicitUsings>enable</ImplicitUsings>
6      <Nullable>enable</Nullable>
7    </PropertyGroup>
8    <ItemGroup>
9      <PackageReference Include="BenchmarkDotNet" Version="0.14.0" /
10 >
11   </ItemGroup>
   </Project>

Here are the results, which clearly speak for themselves.

C
[| Method     | Runti]

1  | Method     | Runtime  | Mean          | Ratio | Allocated |
2  |----------- |--------- |--------------:|------:|----------:|
3  | LinqCount  | .NET 8.0 | 16,198.490 ns |  1.00 |      32 B |
4  | LinqCount  | .NET 9.0 |  3,043.563 ns |  0.19 |         - |
5  |            |          |               |       |           |
6  | LinqAll    | .NET 8.0 |     10.588 ns |  1.00 |      32 B |
7  | LinqAll    | .NET 9.0 |      2.562 ns |  0.24 |         - |
8  |            |          |               |       |           |
9  | LinqAny    | .NET 8.0 | 17,096.735 ns |  1.00 |      32 B |
10 | LinqAny    | .NET 9.0 |  2,483.927 ns |  0.15 |         - |
11 |            |          |               |       |           |
12 | LinqFirst  | .NET 8.0 | 15,289.747 ns |  1.00 |      32 B |
13 | LinqFirst  | .NET 9.0 |  2,243.341 ns |  0.15 |         - |
14 |            |          |               |       |           |
15 | LinqSingle | .NET 8.0 | 21,684.114 ns |  1.00 |      32 B |
16 | LinqSingle | .NET 9.0 |  4,884.329 ns |  0.23 |         - |
17 |            |          |               |       |           |
18 | LinqLast   | .NET 8.0 |     15.967 ns |  1.00 |         - |
19 | LinqLast   | .NET 9.0 |      6.918 ns |  0.43 |         - |

The TryGetSpan() Method

In the post C# Array and List Fastest Loop, we demonstrated that
using a Span<T> for iterating over an array is faster than regular
for and foreach loops. In the benchmark above, the performance
enhancement is primarily due to the use of the method TryGetSpan().
If the enumerable being iterated is an array or list, the method
TryGetSpan() returns a ReadOnlySpan<T> for faster iteration. Here is
the code extracted from TryGetSpan() to test if the source to
enumerate is an array or a list, and then to obtain the span from the
array or the list.

C
[   if (source.GetTyp]

1    if (source.GetType() == typeof(TSource[])) {
2      span = Unsafe.As<TSource[]>(source);
3    } else if (source.GetType() == typeof(List<TSource>)){
4      span = CollectionsMarshal.AsSpan(Unsafe.As<List<TSource>>(
5 source));
     }

To me, this code does not look optimized.

  * source.GetType() is called twice!
  * Why not try to cast source to TSource[] or List<TSource> only
    once and then test the nullity of the obtained reference and use
    it?

This code was written by Stephen Toub and his team, who are THE .NET
performance experts. They have a deep understanding of the C#
compiler and JIT compiler optimizations, so it's clear that this
approach is the optimal one. The good news is that you can reuse this
code in your own performance-critical code. And there is a lesson: In
today's highly optimized .NET stack, micro-optimizations in code are
not obvious at all. Therefore, the advice to avoid premature
optimization has never been more relevant.

One final note: List<TSource> internally references an array. When
the list's capacity needs to grow or shrink, a new array is created
and then referenced. The call to CollectionsMarshal.AsSpan(Unsafe.As
<List<TSource>>(source)) retrieves a Span<TSource> from this internal
array. Do you see the risk? If the list's capacity changes somehow,
the array obtained through this method might become invalid.

Definitely, the class System.Runtime.CompilerServices.Unsafe is
well-named.

TryGetSpan() Callers

Now, let's examine which methods call TryGetSpan(). Using NDepend, we
scanned the assembly located at C:\Program Files\dotnet\shared\
Microsoft.NETCore.App\9.0.0-rc.1.24431.7\System.Linq.dll. From the
TryGetSpan() method, we generated a code query to identify both
direct and indirect callers. We then exported the 56 matched methods
to the dependency graph. This analysis reveals that many standard
Enumerable methods attempt to iterate over a span when the collection
is an array or a list.

However, since holding the internal array of a list obtained via
CollectionsMarshal.AsSpan() is not a safe option (as mentioned
earlier), certain Enumerable operations that defer iteration (like
when using the yield C# keyword) cannot rely on this optimization.

Call Graph To TryGetSpan

Specialized Iterators

Now let's run the following benchmark found into this PR: Consolidate
LINQ's internal IIListProvider/IPartition into base Iterator class

C
[using Perfolizer.Hor]

   using Perfolizer.Horology;
   using BenchmarkDotNet.Configs;
   using BenchmarkDotNet.Running;
   using BenchmarkDotNet.Attributes;
   using BenchmarkDotNet.Jobs;
    
   BenchmarkRunner.Run<Benchmarks>();
    
1  [MemoryDiagnoser]
2  [HideColumns("StdDev", "Median", "Job", "RatioSD", "Error", "Gen0"
3  , "Alloc Ratio")]
4  [SimpleJob(RuntimeMoniker.Net80, baseline: true)]
5  [SimpleJob(RuntimeMoniker.Net90)]
6  public class Benchmarks {
7     private IEnumerable<int> _arrayDistinct = Enumerable.Range(0, 
8  1000).ToArray().Distinct();
9     private IEnumerable<int> _appendSelect = Enumerable.Range(0, 
10 1000).ToArray().Append(42).Select(i => i * 2);
11    private IEnumerable<int> _rangeReverse = Enumerable.Range(0, 
12 1000).Reverse();
13    private IEnumerable<int> _listDefaultIfEmptySelect = Enumerable
14 .Range(0, 1000).ToList().DefaultIfEmpty().Select(i => i * 2);
15    private IEnumerable<int> _listSkipTake = Enumerable.Range(0, 
16 1000).ToList().Skip(500).Take(100);
17    private IEnumerable<int> _rangeUnion = Enumerable.Range(0, 1000
18 ).Union(Enumerable.Range(500, 1000));
19    private IEnumerable<int> _selectWhereSelect = Enumerable.Range(
20 0, 1000).Select(i => i * 2).Where(i => i % 2 == 0).Select(i => i *
21 2);
22  
23    [Benchmark] public int DistinctFirst() => _arrayDistinct.First(
24 );
25    [Benchmark] public int AppendSelectLast() => _appendSelect.Last
26 ();
27    [Benchmark] public int RangeReverseCount() => _rangeReverse.
28 Count();
29    [Benchmark] public int DefaultIfEmptySelectElementAt() => 
   _listDefaultIfEmptySelect.ElementAt(999);
      [Benchmark] public int ListSkipTakeElementAt() => _listSkipTake
   .ElementAt(99);
      [Benchmark] public int RangeUnionFirst() => _rangeUnion.First()
   ;
      [Benchmark] public int SelectWhereSelectSum() => 
   _selectWhereSelect.Sum();
   }

The performance improvements are even more remarkable! What caused
this?

C
[| Method            ]

   | Method                        | Runtime  | Mean         | Ratio 
   | Allocated |
   |------------------------------ |--------- |-------------:|------:
   |----------:|
   | DistinctFirst                 | .NET 8.0 |    65.318 ns |  1.00 
   |     328 B |
   | DistinctFirst                 | .NET 9.0 |    11.192 ns |  0.17 
   |         - |
   |                               |          |              |       
   |           |
   | AppendSelectLast              | .NET 8.0 | 4,122.007 ns | 1.000 
1  |     144 B |
2  | AppendSelectLast              | .NET 9.0 |     2.661 ns | 0.001 
3  |         - |
4  |                               |          |              |       
5  |           |
6  | RangeReverseCount             | .NET 8.0 |    11.024 ns |  1.00 
7  |         - |
8  | RangeReverseCount             | .NET 9.0 |     6.134 ns |  0.56 
9  |         - |
10 |                               |          |              |       
11 |           |
12 | DefaultIfEmptySelectElementAt | .NET 8.0 | 4,090.818 ns | 1.000 
13 |     144 B |
14 | DefaultIfEmptySelectElementAt | .NET 9.0 |     5.724 ns | 0.001 
15 |         - |
16 |                               |          |              |       
17 |           |
18 | ListSkipTakeElementAt         | .NET 8.0 |     6.268 ns |  1.00 
19 |         - |
20 | ListSkipTakeElementAt         | .NET 9.0 |     2.916 ns |  0.47 
21 |         - |
22 |                               |          |              |       
   |           |
   | RangeUnionFirst               | .NET 8.0 |    66.309 ns |  1.00 
   |     344 B |
   | RangeUnionFirst               | .NET 9.0 |     6.193 ns |  0.09 
   |         - |
   |                               |          |              |       
   |           |
   | SelectWhereSelectSum          | .NET 8.0 | 3,959.622 ns |  1.00 
   |     112 B |
   | SelectWhereSelectSum          | .NET 9.0 | 4,460.008 ns |  1.13 
   |     112 B |

The Astute

In summary, the .NET performance team designed the code to recognize
common LINQ call chains. When such a chain is detected, some special
iterators are created to handle the workflow more efficiently. Some
more optimizations can happen when the chain ends up with methods
like Count(), First(), Last(), ElementAt() or Sum(). For instance,
OrderBy(criteria).First() can be optimized to execute as Min
(criteria).

The implementation: Iterator<T> and its Derived Class

Let's have a look at the abstract base class Iterator<T> and its 40
derivatives. They are all nested in the class Enumerable.

Iterator<T> is an abstract class but its methods are virtual. Hence
its derivatives only override the required methods.

Iterators Methods

Here are the derivatives classes listed and exported to the graph:

Iterators Derived

Case Study: ListWhereSelectIterator<TSource, TResult>

Let's focus on the iterator ListWhereSelectIterator<TSource, TResult>
.

It is instantiated from the override of the Select() method in
ListWhereIterator<TSource, TResult>.

C
[public override IEnu]

  public override IEnumerable<TResult> Select<TResult>(Func<TSource, 
1 TResult> selector) =>
2     new ListWhereSelectIterator<TSource, TResult>(_source, 
  _predicate, selector);

ListWhereIterator<TSource, TResult> is instantiated within the
Enumerable.Where() method using the following code:

C
[if (source is List<T]

1 if (source is List<TSource> list){
2   return new ListWhereIterator<TSource>(list, predicate);
3 }

The ListWhereSelectIterator<TSource, TResult> doesn't override
methods like TryGetFirst() or TryGetLast(), so how does it improve
performance? The key optimization is that it acts as a single
iterator for the supercommon Where(...).Select(...) chain on a list,
which would typically require two separate iterators. By
consolidating both operations into one, it inherently improves
efficiency. You can see it in its implementation of MoveNext() where
both delegates _predicate and _selector are invoked:

C
[while (_enumerator.M]

1 while (_enumerator.MoveNext()) {
2    TSource item = _enumerator.Current;
3    if (_predicate(item)) {
4       _current = _selector(item);
5       return true;
6    }
7 }

Case Study: IListSkipTakeIterator<TSource>

Here is the implementation of MoveNext() in the IListSkipTakeIterator
<TSource> class:

C
[public override bool]

   public override bool MoveNext() {
      // _state - 1 represents the zero-based index into the list.
1     // Having a separate field for the index would be more
2  readable. However, we save it
3     // into _state with a bias to minimize field size of the
4  iterator.
5     int index = _state - 1;
6     if ((uint)index <= (uint)(_maxIndexInclusive - 
7  _minIndexInclusive) && index < _source.Count - _minIndexInclusive)
8  {
9        _current = _source[_minIndexInclusive + index];
10       ++_state;
11       return true;
12    }
13  
14    Dispose();
      return false;
   }

Using the same approach as described above, this iterator is
instantiated when applicable. Its optimization lies in avoiding
unnecessary iteration by skipping elements that fall outside the
_minIndexInclusive and _maxIndexInclusive range.

Conclusion

With .NET 9, LINQ becomes faster in several common scenarios. As with
every new version of .NET, you simply need to migrate and recompile
to take advantage of these improvements. Additionally, LINQ has been
optimized in other ways: SIMD is utilized whenever possible, such as
when summing a sequence of integers. Moreover, enumerating empty
sequences incurs lower costs due to early detection.

If you have the opportunity, I highly recommend watching the
DeepDotnet videos featuring Scott Hanselman and Stephen Toub. If your
schedule is tight, consider using work hours for this, and explain to
your boss that it's valuable learning time.

 

One final note: the web is increasingly inundated with AI-generated
crap content. Search engines struggles to differentiate between
valuable, handcrafted content and inferior material. If you
appreciate this article and others like it that are thoughtfully
created, please consider sharing it.

 

 

Share this:

  * Facebook
  * Twitter
  * LinkedIn
  * 

Make your .NET code beautiful with NDepend

Download the NDepend Trial and gain valuable insights into your .NET
code within a few minutes

Download the 14 day trial now

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked 
*

          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
Comment * [                                             ]

Name * [                              ]

Email * [                              ]

Website [                              ]

[ ] Notify me of follow-up comments by email.

[ ] Notify me of new posts by email.

[Post Comment] 

 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
D[                                             ] 

Download Free
NDepend Trial


x
Video Thumbnail



Get informed about our latest blog post.

Type your email... [                    ]

Subscribe

Scott Hanselman

Innovative

    "NDepend is giving me insight into my apps that I hadn't had
    before. Once I realized the depth and breadth of the information
    I was looking at, I was like a kid in a candy shop."

Scott Hanselman Program Manager at Microsoft
David Shifflet

Architecture

    "The issues NDepend raised for me seemed to be more related to
    architecture issues versus the other tools. It definitely gave me
    insight into what to refactor and how to reduce technical debt."

David Shifflet Senior Software Developer

  * .NET 52
  * Architecture 40
  * C# 50
  * Case Study 7
  * NDepend 21
  * Performance 8
  * Visual Studio 58

Recent Posts

  * .NET 9.0 LINQ Performance Improvements October 17, 2024
  * NDepend vs. ReSharper October 14, 2024
  * Reporting ReSharper Code Inspections from Your CI/CD Pipeline 
    October 11, 2024
  * Alternate Lookup for Dictionary and HashSet in .NET 9 September
    10, 2024
  * Faster Dictionary in C# September 2, 2024

  * about

  * What's new in NDepend
  * Download 14-Day Free Trial
  * Buy
  * EULA

  * product

  * Features
  * Walkthrough Videos
  * Sample Reports
  * Screenshots
  * Default Rules
  * Resources
  * Release Notes

  * documentation

  * Getting Started
  * Code Metrics definitions
  * Intro to code queries and rules
  * Trending
  * Dependency Graph
  * Dependency Matrix
  * Code Diff

  * connect

  * Email
  * Twitter
  * Facebook
  * LinkedIn
  * extras

  * Default Code Rules
  * NDepend API

  * Home
  * Product
  * Blog
  * Docs
  * Download
  * Buy
  * About
  * Privacy Policy

  * Copyright (c) 2004-2023 ZEN PROGRAM

Made with love by Growth Labs