T[]) and a List<T> in C# have been ongoing. Results can vary with each .NET version update. To get a clearer picture, we conducted our own benchmarks using .NET 8 and BenchmarkDotNet.At NDepend we value your time, so here are our key findings:
- When iterating over a C# array, the
foreachway is the quickest. - In a
forloop, storing thearray.Lengthorlist.Countin a variable does not improve performance and may actually decrease it. forloop is most efficient on aList<T>thanforeach.- However, the most efficient way to loop over a
List<T>involves accessing the internal array via aSpan<T>usingSpan<int> span = CollectionsMarshal.AsSpan(list). This approach is beneficial in performance-critical situations, provided that no elements are added or removed from the list. - Using a lambda for iterating the LINQ way, like in
Array.Foreach(array, item => ...)orlist.ForEach(item => ...)is unsurprisingly, way slower than regularforandforeachloops.
Let’s go through the experiments and investigations that led us to these conclusions:
Array int[] Fastest Loop
Here are the results obtained through 9 ways to loop over an int[].
Here is the code that you can copy straight into a Program.cs file, assuming the project imports BenchmarkDotNet:
|
1 2 3 4 5 6 7 8 9 10 11 |
<Project Sdk="Microsoft.NET.Sdk"> <PropertyGroup> <OutputType>Exe</OutputType> <TargetFramework>net8.0</TargetFramework> <ImplicitUsings>enable</ImplicitUsings> <Nullable>enable</Nullable> </PropertyGroup> <ItemGroup> <PackageReference Include="BenchmarkDotNet" Version="0.13.12" /> </ItemGroup> </Project> |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Running; BenchmarkRunner.Run<Benchmarks>(); public class Benchmarks { [Params(100, 1_000, 10_000)] public int Length { get; set; } private void AssertResult(int result) { if (result != (Length * (Length - 1)) / 2) { Environment.FailFast(""); } } private int[] m_Items; [GlobalSetup] public void Setup() { m_Items = Enumerable.Range(0, Length).ToArray(); } [Benchmark] public void ForLoop() { int result = 0; for (int i = 0; i < m_Items.Length; i++) { result += m_Items[i]; } AssertResult(result); } [Benchmark] public void ForLoop_LengthAsVariable() { int result = 0; int length = m_Items.Length; for (int i = 0; i < length; i++) { result += m_Items[i]; } AssertResult(result); } [Benchmark] public void ForeachLoop() { int result = 0; foreach (int item in m_Items) { result += item; } AssertResult(result); } [Benchmark] public void ArrayForEach() { int result = 0; Array.ForEach(m_Items, item => { result += item; }); AssertResult(result); } [Benchmark] public void ForSpanLoop() { int result = 0; Span<int> span = m_Items; for (int i = 0; i < span.Length; i++) { result += span[i]; } AssertResult(result); } [Benchmark] public void ForSpanLoop_LengthAsVariable() { int result = 0; Span<int> span = m_Items; int length = span.Length; for (int i = 0; i < length; i++) { result += span[i]; } AssertResult(result); } [Benchmark] public void ForSpanRefLoop() { int result = 0; Span<int> span = m_Items; ref int ptr = ref MemoryMarshal.GetReference(span); for (int i = 0; i < span.Length; i++) { int item = Unsafe.Add(ref ptr, i); result += item; } AssertResult(result); } [Benchmark] public void ForSpanRefLoop_LengthAsVariable() { int result = 0; Span<int> span = m_Items; ref int ptr = ref MemoryMarshal.GetReference(span); int length = span.Length; for (int i = 0; i < length; i++) { int item = Unsafe.Add(ref ptr, i); result += item; } AssertResult(result); } [Benchmark] public void ForSpanRefLoop2() { int result = 0; Span<int> span = m_Items; ref int start = ref MemoryMarshal.GetReference(span); ref int end = ref Unsafe.Add(ref start, m_Items.Length); while (Unsafe.IsAddressLessThan(ref start, ref end)) { result += start; start = ref Unsafe.Add(ref start, 1); } AssertResult(result); } } |
foreach wins, why?
While the foreach loop over an array can sometimes be marginally slower than when using Span<T>, the difference is negligible. Additionally, introducing Span<T> can complicate the code, which may not justify the tiny performance benefit.
However, let’s investigate why foreach is faster than for. Let’s use SharpLab to decompile this program and investigate:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
using System.Linq; var array = Enumerable.Range(0, 100).ToArray(); ForLoop(array); ForeachLoop(array); void ForLoop(int[] array) { int result = 0; for (int i = 0; i < array.Length; i++) { result += array[i]; } AssertResult(result); } void ForeachLoop(int[] array) { int result = 0; foreach (int item in array) { result += item; } AssertResult(result); } void AssertResult(int result) { if (result != (100 * (99)) / 2) { System.Environment.FailFast(""); } } |
Here is the result from the C# compiler:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
using System.Linq; var b = new Benchmarks(); b.ForLoop(); b.ForeachLoop(); class Benchmarks { private int[] m_Items = Enumerable.Range(0, 100).ToArray(); internal void ForLoop() { int result = 0; for (int i = 0; i < m_Items.Length; i++) { result += m_Items[i]; } AssertResult(result); } internal void ForeachLoop() { int result = 0; foreach (int item in m_Items) { result += item; } AssertResult(result); } void AssertResult(int result) { if (result != (100 * (99)) / 2) { System.Environment.FailFast(""); } } } |
These are quite similar. However the foreach loop introduces a reference to the array as a local variable. This modification enables the JIT compiler to eliminate bounds checking, significantly speeding up each loop. Observe the variations in the generated assembly code. To make it easier to read, the loop is highlighted in both cases.
Managed pointers and the C# keyword ref
The ForSpanRefLoop() and ForSpanRefLoop2() ways are extracted from two Nick Chapsas’ videos here and here. They involve ref variables. In C# the keyword ref means managed pointers. In C# 1.0 the keyword ref was only used for passing parameters by reference. Since C# 7.0 almost every version of C# adds new areas where managed pointers can be used: ref variable, ref return, struct ref…
Managed pointers constitute a unique feature of the .NET runtime that offers considerable benefits:
- They can target various types of memory: local variables, in or out method parameters, stack locations, heap objects, object fields, array elements, strings, string locations, and unmanaged memory buffers.
- The Garbage Collector recognizes managed pointers and adjusts them appropriately when the targeted objects are relocated.
- They function efficiently.
The main restriction is that managed pointers must remain on the thread stack. This restriction also makes them faster than usual .NET references since the location of a managed pointer cannot change during a GC operation.
Span<T> implementation is based on managed pointers. All in all, Span<T> is a way to work with pointers like in C, in a safe context even though calls to method like Unsafe.Add() makes the code, well, unsafe.
While Span<T> doesn’t help improve performance when looping over an array, we’ll see that it is valuable when looping over a List<T>.
References:
List<T> Fastest Loop
We slightly modified the program above to make it work on a List<int>. Here are the results:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Running; BenchmarkRunner.Run<Benchmarks>(); public class Benchmarks { [Params(100, 1_000, 10_000)] public int Length { get; set; } private void AssertResult(int result) { if (result != (Length * (Length - 1)) / 2) { Environment.FailFast(""); } } private List<int> m_Items; [GlobalSetup] public void Setup() { m_Items = Enumerable.Range(0, Length).ToList(); } [Benchmark] public void ForLoop() { int result = 0; for (int i = 0; i < m_Items.Count; i++) { result += m_Items[i]; } AssertResult(result); } [Benchmark] public void ForLoop_CountAsVariable() { int result = 0; int length = m_Items.Count; for (int i = 0; i < length; i++) { result += m_Items[i]; } AssertResult(result); } [Benchmark] public void ForeachLoop() { int result = 0; foreach (int item in m_Items) { result += item; } AssertResult(result); } [Benchmark] public void ListForEach() { int result = 0; m_Items.ForEach(item => { result += item; }); AssertResult(result); } [Benchmark] public void ForSpanLoop() { int result = 0; Span<int> span = CollectionsMarshal.AsSpan(m_Items); for (int i = 0; i < span.Length; i++) { result += span[i]; } AssertResult(result); } [Benchmark] public void ForSpanLoop_LengthAsVariable() { int result = 0; Span<int> span = CollectionsMarshal.AsSpan(m_Items); int length = span.Length; for (int i = 0; i < length; i++) { result += span[i]; } AssertResult(result); } [Benchmark] public void ForSpanRefLoop() { int result = 0; Span<int> span = CollectionsMarshal.AsSpan(m_Items); ref int ptr = ref MemoryMarshal.GetReference(span); for (int i = 0; i < span.Length; i++) { int item = Unsafe.Add(ref ptr, i); result += item; } AssertResult(result); } [Benchmark] public void ForSpanRefLoop_LengthAsVariable() { int result = 0; Span<int> span = CollectionsMarshal.AsSpan(m_Items); ref int ptr = ref MemoryMarshal.GetReference(span); int length = span.Length; for (int i = 0; i < length; i++) { int item = Unsafe.Add(ref ptr, i); result += item; } AssertResult(result); } [Benchmark] public void ForSpanRefLoop2() { int result = 0; Span<int> span = CollectionsMarshal.AsSpan(m_Items); ref int start = ref MemoryMarshal.GetReference(span); ref int end = ref Unsafe.Add(ref start, m_Items.Count); while (Unsafe.IsAddressLessThan(ref start, ref end)) { result += start; start = ref Unsafe.Add(ref start, 1); } AssertResult(result); } } |
Array vs. List Loop
First, let’s compare array and list results. Looping over a list is generally slower than looping over an array. This makes sense since List<T> internally holds a T[]. Thus, it necessarily adds a layer of complexity.
Span<T> makes list loops faster
The real surprise is that using a Span<T> to loop over a list is significantly faster than for and foreach regular ways. What happens is that the call to CollectionsMarshal.AsSpan(list) obtains a managed pointer to the list’s internal array. This call is generally a bad idea because if some elements are added or removed, the list might internally allocate a new array. Thus the span obtained now points toward void memory. This is demonstrated by this program:
|
1 2 3 4 5 6 7 8 9 10 11 |
var list = Enumerable.Range(0, 6).ToList(); var span = CollectionsMarshal.AsSpan(list); Assert.IsTrue(span[0] == list[0]); // Force to replace the list internal array with a large array list.AddRange(Enumerable.Range(0, 6)); list[0] = 173; // The span still references the previous array Assert.IsTrue(list[0] == 173); Assert.IsTrue(span[0] == 0); |
However, assuming that the number of elements in the list and its capacity doesn’t get modified, using CollectionsMarshal.AsSpan(list) does help improve the performance of looping over a list in critical scenarios.
for loop is faster on list than foreach
Unlike array, for loops are faster on lists than foreach loop. The reason is obvious when investigating this program in SharpLap:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
using System.Linq; using System.Collections.Generic; var b = new Benchmarks(); b.ForLoop(); b.ForeachLoop(); class Benchmarks { private List<int> m_Items = Enumerable.Range(0, 100).ToList(); internal void ForLoop() { int result = 0; for (int i = 0; i < m_Items.Count; i++) { result += m_Items[i]; } AssertResult(result); } internal void ForeachLoop() { int result = 0; foreach (int item in m_Items) { result += item; } AssertResult(result); } void AssertResult(int result) { if (result != (100 * (99)) / 2) { System.Environment.FailFast(""); } } } |
The C# compiler produces this code. The call to enumerator.MoveNext() and the try/catch block necessarily degrade the performances:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
internal void ForLoop() { int num = 0; int num2 = 0; while (num2 < m_Items.Count) { num += m_Items[num2]; num2++; } AssertResult(num); } internal void ForeachLoop() { int num = 0; List<int>.Enumerator enumerator = m_Items.GetEnumerator(); try { while (enumerator.MoveNext()) { int current = enumerator.Current; num += current; } } finally { ((IDisposable)enumerator).Dispose(); } AssertResult(num); } |
Conclusion
We listed the key findings in the introduction. Let’s conclude that future versions of .NET and C# might change these results. For example, in the future, the C# compiler might assert that a list doesn’t get modified and use the Span<T> based optimization. We will update this post regularly to find out.
As passionate programmers, we find all these insights intriguing. However, it’s important to remember that in most scenarios, code readability outweighs the benefits of minor performance enhancements. Therefore, let’s reserve the use of MemoryMarshal, CollectionsMarshal, and Unsafe stuff for those parts of the code where performance is absolutely critical.
Forward this article to the Sonar folks. It’s constantly yelling to use linq versus a foreach, despite ther performance hit. This making code reviews… slower.