{"id":414405,"date":"2024-06-29T23:44:15","date_gmt":"2024-06-29T23:44:15","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=414405"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-06-29T23:44:15","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=414405","title":{"rendered":"Making \u00abforeach\u00bb loop as fast as \u00abfor\u00bb loop<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

Hi. I want to share some experience on creating a enumerator for foreach<\/code> loop so that it would be as performant as if it was a for<\/code> loop.<\/p>\n

Problem statement<\/h2>\n

As we know, System.Range<\/code> has a nice syntax sugar:<\/p>\n

var a = 1..2; \/\/ same as new Range(1, 2)<\/code><\/pre>\n
That’s why I decided to abuse it as a replacement for a for<\/code> loop:<\/p>\n
foreach (var i in 1..5)     Console.Write(i);<\/code><\/pre>\n
(prints «12345»)<\/p>\n
When you iterate over something with foreach<\/code>, Roslyn requires that «something» to have a GetEnumerator<\/code> method, which should return something, which has bool MoveNext()<\/code> and T Current<\/code>. We can add it as an extension method:<\/p>\n
public static class Extensions {     public ... GetEnumerator(this System.Range range) => ... }<\/code><\/pre>\n
Baseline (our goal)<\/h2>\n
Theoretically, for<\/code> is more functional than just going over a sequence of natural numbers. But because so often we see<\/p>\n
for (int i = 0; i < n; i++)<\/code><\/pre>\n
that it deserves its own use case of for<\/code>. We are going to compare against a for<\/code> loop with i += inc<\/code> as a step:<\/p>\n
for (int i = 0; i < n; i += inc)<\/code><\/pre>\n
In terms of performance, it’s identical to the one with i++<\/code>:<\/p>\n
\n\n\n\n\n\n
\n
Method<\/p>\n<\/th>\n
\n
Iterations<\/p>\n<\/th>\n
\n
Mean<\/p>\n<\/th>\n
\n
Error<\/p>\n<\/th>\n
\n
StdDev<\/p>\n<\/th>\n<\/tr>\n
\n
i++<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
3.380 us<\/p>\n<\/td>\n
\n
0.0534 us<\/p>\n<\/td>\n
\n
0.0446 us<\/p>\n<\/td>\n<\/tr>\n
\n
i += inc<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
3.385 us<\/p>\n<\/td>\n
\n
0.0575 us<\/p>\n<\/td>\n
\n
0.0685 us<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
The code for baseline for<\/code>:<\/p>\n
[Benchmark] public int ForWithCustomIncrement() {     var iters = Iterations;     var a = 0;     var inc = Inc;     for (int i = 0; i < iters; i += inc)         a += i;     return a; }<\/code><\/pre>\n
(we loaded all fields\/properties onto local variables to avoid repeatitive reading from far RAM)<\/p>\n
Codegen <\/a>for it:<\/p>\n
    L000f: add edx, r8d     L0012: add r8d, ecx     L0015: cmp r8d, eax     L0018: jl short L000f<\/code><\/pre>\n
\n
We only care about codegen of iteration<\/em> of the loop, ignoring the initial overhead and all other operations around.<\/p>\n<\/blockquote>\n
Experiment 1. Enumerable.Range<\/h2>\n
It might make sense to start with trying the already existing API from BCL: Enumerable.Range, whose source code we can find here<\/a>.<\/p>\n
Here’s what our benchmark looks like:<\/p>\n
[Benchmark] public int ForeachWithEnumerableRange() {     var a = 0;     foreach (var i in Enumerable.Range(0, Iterations))         a += i;     return a; }<\/code><\/pre>\n
This code is interpreted by roslyn<\/a> as<\/p>\n
public int ForeachWithEnumerableRange() {     int num = 0;     IEnumerator<int> enumerator = Enumerable.Range(0, Iterations).GetEnumerator();     try     {         while (enumerator.MoveNext())         {             int current = enumerator.Current;             num += current;         }         return num;     }     finally     {         if (enumerator != null)         {             enumerator.Dispose();         }     } }<\/code><\/pre>\n
No need to study the asm codegen, as long as the benchmarks are pretty illustrative:<\/p>\n
\n\n\n\n\n\n
\n
Method<\/p>\n<\/th>\n
\n
Iterations<\/p>\n<\/th>\n
\n
Mean<\/p>\n<\/th>\n
\n
Error<\/p>\n<\/th>\n
\n
StdDev<\/p>\n<\/th>\n<\/tr>\n
\n
ForWithCustomIncrement<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
3.448 us<\/p>\n<\/td>\n
\n
0.0689 us<\/p>\n<\/td>\n
\n
0.0896 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithEnumerableRange<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
43.946 us<\/p>\n<\/td>\n
\n
0.8685 us<\/p>\n<\/td>\n
\n
1.2456 us<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
Experiment 2. yield return<\/h2>\n
The second easiest way is to create a custom generator:<\/p>\n
private static IEnumerable<int> MyRange(int from, int to, int inc) {     for (int i = from; i <= to; i += inc)         yield return i; }  [Benchmark] public int ForeachWithYieldReturn() {     var a = 0;     foreach (var i in MyRange(0, Iterations - 1, 1))         a += i;     return a; }<\/code><\/pre>\n
Nothing completely new, our enumerator is still a big reference type with a dozen of fields. The performance is even worse than that with Enumerable.Range:<\/p>\n
\n\n\n\n\n\n\n
\n
Method<\/p>\n<\/th>\n
\n
Iterations<\/p>\n<\/th>\n
\n
Mean<\/p>\n<\/th>\n
\n
Error<\/p>\n<\/th>\n
\n
StdDev<\/p>\n<\/th>\n<\/tr>\n
\n
ForWithCustomIncrement<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
3.548 us<\/p>\n<\/td>\n
\n
0.0661 us<\/p>\n<\/td>\n
\n
0.1320 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithEnumerableRange<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
51.663 us<\/p>\n<\/td>\n
\n
0.9103 us<\/p>\n<\/td>\n
\n
1.2460 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithYieldReturn<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
56.580 us<\/p>\n<\/td>\n
\n
0.3561 us<\/p>\n<\/td>\n
\n
0.2780 us<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
Experiment 3. Custom enumerator<\/h2>\n
Now we are going to write our own enumerator. First of all, it will be a struct<\/code>. To make it work with foreach<\/code>, we will need a method bool MoveNext()<\/code> and a property int Current<\/code>.<\/p>\n
public struct RangeEnumerator {     private readonly int to;     private readonly int step;      private int curr;      public RangeEnumerator(int @from, int to, int step)     {         this.to = to + step;         this.step = step;         this.curr = @from - step;     }      public bool MoveNext()     {         curr += step;         return curr != to;     }          public int Current => curr; }<\/code><\/pre>\n
To make System.Range<\/code> iterable with foreach<\/code>, we are making an extension method:<\/p>\n
public static class Extensions {     public static RangeEnumerator GetEnumerator(this Range @this)         => (@this.Start, @this.End) switch         {             ({ IsFromEnd: true, Value: 0 }, { IsFromEnd: true, Value: 0 }) => new RangeEnumerator(0, int.MaxValue, 1),             ({ IsFromEnd: true, Value: 0 }, { IsFromEnd: false, Value: var to }) => new RangeEnumerator(0, to + 1, 1),             ({ IsFromEnd: false, Value: var from }, { IsFromEnd: true, Value: 0 }) => new RangeEnumerator(from, int.MaxValue, 1),             ({ IsFromEnd: false, Value: var from }, { IsFromEnd: false, Value: var to })                 => (from < to) switch                 {                     true => new RangeEnumerator(from, to, 1),                     false => new RangeEnumerator(from, to, -1),                 },             _ => throw new InvalidOperationException(\"Invalid range\")         }; }<\/code><\/pre>\n
The code of the benching method:<\/p>\n
[Benchmark] public int ForeachWithRangeEnumerator() {     var a = 0;     foreach (var i in 0..(Iterations - 1))         a += i;     return a; }<\/code><\/pre>\n
and is interpreted by Roslyn as:<\/p>\n
public int ForeachWithRangeEnumerator() {     int num = 0;     RangeEnumerator enumerator = Extensions.GetEnumerator(new Range(0, Iterations - 1));     while (enumerator.MoveNext())     {         int current = enumerator.Current;         num += current;     }     return num; }<\/code><\/pre>\n
This time it’s not a reference type. Also, because our struct does not implement IDisposable<\/code>, Roslyn does not wrap it with try-finally block. Let’s have a look at the benchmark results:<\/p>\n
\n\n\n\n\n\n\n\n
\n
Method<\/p>\n<\/th>\n
\n
Iterations<\/p>\n<\/th>\n
\n
Mean<\/p>\n<\/th>\n
\n
Error<\/p>\n<\/th>\n
\n
StdDev<\/p>\n<\/th>\n<\/tr>\n
\n
ForWithCustomIncrement<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
3.477 us<\/p>\n<\/td>\n
\n
0.0690 us<\/p>\n<\/td>\n
\n
0.0989 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithEnumerableRange<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
50.501 us<\/p>\n<\/td>\n
\n
0.9984 us<\/p>\n<\/td>\n
\n
1.2627 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithYieldReturn<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
53.782 us<\/p>\n<\/td>\n
\n
1.0583 us<\/p>\n<\/td>\n
\n
0.9900 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithRangeEnumerator<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
18.061 us<\/p>\n<\/td>\n
\n
0.1731 us<\/p>\n<\/td>\n
\n
0.1619 us<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
18 microseconds per 10k operations. That’s much better than the previous attempts, but still worse than for<\/code>. Let’s check the codegen:<\/p>\n
One loop iteration looks like<\/a>:<\/p>\n
    L003e: add esi, eax     L0040: mov eax, [rsp+0x38]     L0044: add eax, [rsp+0x34]     L0048: mov [rsp+0x38], eax     L004c: mov eax, [rsp+0x38]     L0050: cmp eax, [rsp+0x30]     L0054: jne short L003a<\/code><\/pre>\n
Despite the enumerator being a struct, and hence, on stack, it’s still read from RAM. Let’s see what else we can do!<\/p>\n
Experiment 4. Separating the enumerator into a local function<\/h2>\n
Why…? Because what we want<\/em> is in fact to put the enumerator itself onto registers<\/em> instead of reading\/writing from\/to RAM all the time. But probably because of too many local variables, the JIT compiler decided not to put our struct onto registers, so let us help it a bit.<\/p>\n
From experiment 3 we have<\/p>\n
[Benchmark] public int ForeachWithRangeEnumeratorRaw() {     var a = 0;     var enumerator = (0..(Iterations - 1)).GetEnumerator();     while (enumerator.MoveNext())         a += enumerator.Current;     return a; }<\/code><\/pre>\n
Note, that I replaced foreach<\/code> with the equivalent code, and added Raw<\/code> as postfix. In Experiment 3 it’s shown how foreach<\/code> works under the hood — the same as I wrote manually.<\/p>\n
To reduce the number of local variables, we move the loop to a local function:<\/p>\n
[Benchmark] public int ForeachWithRangeEnumeratorRawWithLocal() {     var enumerator = (0..(Iterations - 1)).GetEnumerator();             return EnumerateItAll(enumerator);      static int EnumerateItAll(RangeEnumerator enumerator)     {         var a = 0;         while (enumerator.MoveNext())             a += enumerator.Current;         return a;     } }<\/code><\/pre>\n
And run the benchmark:<\/p>\n
\n\n\n\n\n\n\n\n\n\n
\n
Method<\/p>\n<\/th>\n
\n
Iterations<\/p>\n<\/th>\n
\n
Mean<\/p>\n<\/th>\n
\n
Error<\/p>\n<\/th>\n
\n
StdDev<\/p>\n<\/th>\n<\/tr>\n
\n
ForWithCustomIncrement<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
3.498 us<\/p>\n<\/td>\n
\n
0.0658 us<\/p>\n<\/td>\n
\n
0.1153 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithEnumerableRange<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
43.313 us<\/p>\n<\/td>\n
\n
0.8207 us<\/p>\n<\/td>\n
\n
1.0079 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithYieldReturn<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
56.963 us<\/p>\n<\/td>\n
\n
1.0638 us<\/p>\n<\/td>\n
\n
1.0448 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithRangeEnumerator<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
17.931 us<\/p>\n<\/td>\n
\n
0.2047 us<\/p>\n<\/td>\n
\n
0.1915 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithRangeEnumeratorRaw<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
17.932 us<\/p>\n<\/td>\n
\n
0.1486 us<\/p>\n<\/td>\n
\n
0.1390 us<\/p>\n<\/td>\n<\/tr>\n
\n
ForeachWithRangeEnumeratorRawWithLocal<\/p>\n<\/td>\n
\n
10000<\/p>\n<\/td>\n
\n
3.501 us<\/p>\n<\/td>\n
\n
0.0678 us<\/p>\n<\/td>\n
\n
0.0807 us<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
ForeachWithRangeEnumeratorRawWithLocal<\/code> is the last method we wrote — and it’s almost 6 times<\/strong> faster, than the one with the loop inlined into the body! What happened?<\/p>\n
Let’s look at the codegen<\/a>.<\/p>\n
In our method the local function hasn’t been inlined:<\/p>\n
Benchmarks.ForeachWithRangeEnumeratorRawWithLocal()     ...     L0044: call Benchmarks.<ForeachWithRangeEnumeratorRawWithLocal>g__EnumerateItAll|8_0(RangeEnumerator)<\/code><\/pre>\n
And it’s good news. Let’s have a look at our local function:<\/p>\n
    L0000: mov eax, [rcx]     L0002: mov edx, [rcx+4]     L0005: mov ecx, [rcx+8]     L0008: xor r8d, r8d     L000b: jmp short L0010 >>  L000d: add r8d, ecx          >>  L0010: add ecx, edx          >>  L0012: cmp ecx, eax          >>  L0014: jne short L000d           L0016: mov eax, r8d     L0019: ret<\/code><\/pre>\n
The four marked lines<\/p>\n
    L000d: add r8d, ecx     L0010: add ecx, edx     L0012: cmp ecx, eax     L0014: jne short L000d<\/code><\/pre>\n
are what we were trying to do. It’s identical to the codegen for the for<\/code> loop!<\/p>\n
The first three lines<\/p>\n
    L0000: mov eax, [rcx]     L0002: mov edx, [rcx+4]     L0005: mov ecx, [rcx+8]<\/code><\/pre>\n
simply load the local variables from stack onto registers. That is why our method is so fast.<\/p>\n
Windows vs Linux<\/h2>\n
There is in fact a huge difference between what was generated on windows vs linux. What I wrote before is how it works on Windows.<\/p>\n
To illustrate the difference I created a gist<\/a> for comparing codegens for ForeachWithRangeEnumeratorRaw<\/code> and ForeachWithRangeEnumeratorRawWithLocal<\/code>. Let me go over the key differences:<\/p>\n
In case of ForeachWithRangeEnumeratorRaw<\/code> method, Linux’s JIT generates:<\/p>\n
M00_L00:        add       ebx,esi        add       esi,edi        cmp       esi,eax        jne       short M00_L00<\/code><\/pre>\n
Whereas Windows’ JIT yields this:<\/p>\n
M00_L00:        add       esi,[rsp+38]        mov       eax,[rsp+38]        add       eax,[rsp+34]        mov       [rsp+38],eax        mov       eax,[rsp+38]        cmp       eax,[rsp+30]        jne       short M00_L00<\/code><\/pre>\n
Unlike that one, in case of ForeachWithRangeEnumeratorRawWithLocal<\/code> Linux gives<\/p>\n
jmp       near ptr Benchmarks.<ForeachWithRangeEnumeratorRawWithLocal>g__EnumerateItAll|14_0(Library.RangeEnumerator)<\/code><\/pre>\n
in the method, and in local function it generates:<\/p>\n
M02_L00:        mov       edi,[rbp-8]        add       eax,edi        add       edi,[rbp-0C]        mov       [rbp-8],edi        cmp       edi,esi        jne       short M02_L00<\/code><\/pre>\n
Meanwhile, Windows’s JIT gives call:<\/p>\n
call      Benchmarks.<ForeachWithRangeEnumeratorRawWithLocal>g__EnumerateItAll|14_0(Library.RangeEnumerator) <\/code><\/pre>\n
and the iteration codegen:<\/p>\n
M02_L00:        add       r8d,ecx        add       ecx,edx        cmp       ecx,eax        jne       short M02_L00<\/code><\/pre>\n
(all that codegen see in the gist<\/a>)<\/p>\n
Conclusion<\/h2>\n
First, although we got what we wanted, it’s definitely easier to write a for<\/code> loop than caring about whether the compiler put our values onto registers.<\/p>\n
Second, it’s an interesting example how sometimes inlining can literally ruin the performance (in our case, on Windows it took 5-6 times more time on 10k iterations, 3.5 us vs 18 us).<\/p>\n
References<\/h2>\n
All the code I wrote is on a github repo<\/a>.<\/p>\n