- PVSM.RU - https://www.pvsm.ru -
Привет! Хочу рассказать об интересном опыте, как я писал енумератор для типа Range
, который был бы таким же дешевым, как цикл for
.
У System.Range, как известно, очень красивый синтаксис создания:
var a = 1..2; // эквивалент new Range(1, 2)
Поэтому, как эксперимент, я решил абузить его для цикла foreach
, как замена for
:
foreach (var i in 1..5)
Console.Write(i);
(выводит 12345)
Для foreach Розлин требует метод GetEnumerator
, который возвращал бы что-то, у чего есть bool MoveNext()
и T Current. Этот метод можно добавить как метод расширения:
public static class Extensions
{
public ... GetEnumerator(this System.Range range) => ...
}
Вообще-то for
это куда больше, чем пройтись по последовательности. Но так как очень часто мы видим
for (int i = 0; i < n; i++)
то это стоит своего кейса использования for
. Сравнивать мы будем с циклом for
у которого в качестве итерации стоит i += inc
:
for (int i = 0; i < n; i += inc)
По производительности он идентичен версии с i++:
Method |
Iterations |
Mean |
Error |
StdDev |
---|---|---|---|---|
i++ |
10000 |
3.380 us |
0.0534 us |
0.0446 us |
i += inc |
10000 |
3.385 us |
0.0575 us |
0.0685 us |
Код метода с for-ом:
[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;
}
(мы выгрузили все проперти в локальные переменные чтобы исключить чтение из памяти при итерации)
Кодген [1]for-а:
L000f: add edx, r8d
L0012: add r8d, ecx
L0015: cmp r8d, eax
L0018: jl short L000f
Мы будем смотреть только на код одной итерации цикла, начальный оверхед и окружающий мусор нас не интересует.
Конечно, сначала стоит попробовать вариант из BCL: Enumerable.Range, исходный код которого можно поизучать здесь [2].
Так выглядит наш бенчмарк:
[Benchmark]
public int ForeachWithEnumerableRange()
{
var a = 0;
foreach (var i in Enumerable.Range(0, Iterations))
a += i;
return a;
}
Этот код Розлином раскрывается [3]как
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();
}
}
}
Изучать ассемблерный кодген смысла нет, достаточно взглянуть на бенчмарк:
Method |
Iterations |
Mean |
Error |
StdDev |
---|---|---|---|---|
ForWithCustomIncrement |
10000 |
3.448 us |
0.0689 us |
0.0896 us |
ForeachWithEnumerableRange |
10000 |
43.946 us |
0.8685 us |
1.2456 us |
Второй по простоте способ - написать метод-генератор, и вызывать его енумератор:
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;
}
Принципиально нового мы ничего не получаем, наш енумератор это все еще огромный референс тип с кучей полей. Бенчмарки сообщают, что с yield-ом даже хуже, чем с Enumerable.Range:
Method |
Iterations |
Mean |
Error |
StdDev |
---|---|---|---|---|
ForWithCustomIncrement |
10000 |
3.548 us |
0.0661 us |
0.1320 us |
ForeachWithEnumerableRange |
10000 |
51.663 us |
0.9103 us |
1.2460 us |
ForeachWithYieldReturn |
10000 |
56.580 us |
0.3561 us |
0.2780 us |
Теперь будем писать собственный енумератор. Чтобы оно работало с foreach-ем, нужно, чтобы был метод bool MoveNext()
и свойство T Current
(в нашем случае int Current
).
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;
}
Чтобы Розлин увидел, что по System.Range
можно форычиться, нужно сделать метод расширения:
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")
};
}
Код бенчмарка выглядит так:
[Benchmark]
public int ForeachWithRangeEnumerator()
{
var a = 0;
foreach (var i in 0..(Iterations - 1))
a += i;
return a;
}
И раскрывается Розлином так:
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;
}
На этот раз нет референс типов, а так как RangeEnumerator
не имплементит IDisposable
, то и нет try-catch блоков вокруг. Взглянем на бенчмарк:
Method |
Iterations |
Mean |
Error |
StdDev |
---|---|---|---|---|
ForWithCustomIncrement |
10000 |
3.477 us |
0.0690 us |
0.0989 us |
ForeachWithEnumerableRange |
10000 |
50.501 us |
0.9984 us |
1.2627 us |
ForeachWithYieldReturn |
10000 |
53.782 us |
1.0583 us |
0.9900 us |
ForeachWithRangeEnumerator |
10000 |
18.061 us |
0.1731 us |
0.1619 us |
18 микросекунд на 10000 операций. Намного лучше, чем аналоги до этого, но сильно хуже, чем for
. Время взглянуть на кодген!
Одна итерация цикла выглядит [4]так:
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
Да, у нас референс-типов нет, но все данные-то все равно в памяти! Хоть и на стеке.
Что за магия? Дело в том, что чтобы получить наш енумератор таким же быстрым, как for
, следует поместить его поля в регистры. Но компилятор сам этого не сделал, слишком много локальных переменных в методе было, и он не положил нужные. Давайте облегчим задачу.
Из эксперимента 3:
[Benchmark]
public int ForeachWithRangeEnumeratorRaw()
{
var a = 0;
var enumerator = (0..(Iterations - 1)).GetEnumerator();
while (enumerator.MoveNext())
a += enumerator.Current;
return a;
}
(я заменил foreach
на точно то же самое с постфиксом Raw
, только написанное ручками, для наглядности. См. эксперимент 3, там показано, как Розлин раскрывает foreach
).
Чтобы уменьшить количество локальных переменных, спрячем цикл в локальную функцию:
[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;
}
}
И побенчим:
Method |
Iterations |
Mean |
Error |
StdDev |
---|---|---|---|---|
ForWithCustomIncrement |
10000 |
3.498 us |
0.0658 us |
0.1153 us |
ForeachWithEnumerableRange |
10000 |
43.313 us |
0.8207 us |
1.0079 us |
ForeachWithYieldReturn |
10000 |
56.963 us |
1.0638 us |
1.0448 us |
ForeachWithRangeEnumerator |
10000 |
17.931 us |
0.2047 us |
0.1915 us |
ForeachWithRangeEnumeratorRaw |
10000 |
17.932 us |
0.1486 us |
0.1390 us |
ForeachWithRangeEnumeratorRawWithLocal |
10000 |
3.501 us |
0.0678 us |
0.0807 us |
ForeachWithRangeEnumeratorRawWithLocal
- это как раз вариант с локальной функцией. И... он почти в шесть раз быстрее, чем заинлайненный! Как же так вышло-то?
Смотрим кодген [5]:
В нашем методе локальная функция не заинлайнилась:
Benchmarks.ForeachWithRangeEnumeratorRawWithLocal()
...
L0044: call Benchmarks.<ForeachWithRangeEnumeratorRawWithLocal>g__EnumerateItAll|8_0(RangeEnumerator)
И это нам на руку. Смотрим эту локальную функцию:
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
Отмеченные четыре строчки,
L000d: add r8d, ecx
L0010: add ecx, edx
L0012: cmp ecx, eax
L0014: jne short L000d
это и есть наша победа, так как этот код идентичен итерации for
-а.
Первые три строчки
L0000: mov eax, [rcx]
L0002: mov edx, [rcx+4]
L0005: mov ecx, [rcx+8]
Выгружают все, что нужно, в регистры, и поэтому так быстро работает наш метод.
Во-первых, хоть и желаемое получилось, в реальной жизни проще написать for
, чем проверять, догадался ли компилятор положить ваш енумератор в регистры.
Во-вторых, это очень показательный пример, что инлайнинг может сделать не только не лучше, но и сильно хуже (в данном случае он увеличил время работы с 3.5 до 18 us на 10000 итераций).
Спасибо за внимание!
Весь код, который я писал, размещен в репозитории на github [6].
Бенчмарки [7]
Код енумератора [8]
Тесты [9], если есть подозрение на неправильный код
BenchmarkDotNet [10] - утилита/библиотека для бенчинга
Автор:
WhiteBlackGoose
Источник [11]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-2/367527
Ссылки в тексте:
[1] Кодген : https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8ABAJgEYBYAKBuIGYACMxgIRgDswALfbKANa4aAbxqMJjcZIaMAlhwyMAkhhhRsGORA65GIxgHMYGANyNcJ8wF8a0iQAcocgG6aY8xSq76jVi/7WjAC8jOTmAPQRjMAAnoyw2AAmCoaMAGZQEPgZcjAANkkRThAO6hixaIwY3B4AUsoAKoyQ+A5y+eqMAO46AORKpVr4cgBeHnJKGBCeYJ64GFAArmBaOnbUklKbMkwKSgBi0ADqk9zKXLD4nBisseQAFACU9vqvW25Q8mpQeqGq6k02l0pnekk+jGwIUYAAZQTsthJ0tBGA99vJoXCMQAeb7qXDmOQAaiJLwRiK2UKJoTk8IpEmIAHZIXTJLZaOTXrJ0UcoKcagBhJYLbIXMBXG7PV5ickffh437QgEaNYgsESCFQ0Jw9WMCEKOb/LisinIr5orxyTGExi4yb4m3U2Zk+mIqk0k2Ipks17s6xAA===
[2] здесь: https://source.dot.net/#System.Linq/System/Linq/Range.cs,11
[3] раскрывается : https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA+ABATARgLABQGADAAQY4B0AMgJYB2AjgNyGEYDM5WpAQjPTAALALYBDKAGsAzoQDehUktKLlnUgwAupAJKaYUMZtoR600nNIBzGJualpt+wF82BZaQAOUWgDcjMBr02jqCFtZODpHOpAC8pDj2APRJpMAAnqSwYgAmDFakAGZQECJFtDAANjlJ3hCeBprpADSkmkKBAFI6ACqkkCKetJUGpADupgDk2vXGIrQAXoG02poQQWBB0ppQAK5gxqZuHqpK6lqkAGLQMGLCAOorQgCi9LsiBmLAIwBKYvQ2AAUAEpThYwR5/FBSGI4qRiKx3B5lIUbnchKRAVCNEFSK93p9vjBKH8ATBAcRWnpPoczMDQUjkcjYQBqeK0RFMs4AdhhnOUrgIziAA
[4] выглядит : https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8ABAJgEYBYAKBuIGYACMxgIRgDswALfbKANa4aAbxqMJzJgEsOGRgEkMMKNgzSIHXIxGMA5jAwBuRrkMmAvjXGSADlGkA3NTEaz5Crjv3nTvi4wAvIzkJgD0YYzAAJ6MsNgAJrJ6jABmUBD4adIwADYJYfYQtioY0WiMGNyuAFIKACqMkPi20rkqjADumgDk8sXq+NIAXq7S8hgQbl6yuBhQAK5g6prW1JKMaxsM0/IAYtAw2DwA6uPcAErYHAYAohwL+Cpq0AAUAJQ2EmLrG5LOUEY2CCjAADEYvn9UodjtxGK8AW5pmCAHQo15KZ4rLSMOAhd6fX5/P7AgDUwWkEKJf2IAHYgVSNlZqMydsRyEhmKRGLcEMotBotJCfsSJGyOYwrjcYPdHljoIwAOKGWVPVSTKCvKrSbRSgzMYja3CE0V/QIAPnhxEN3B1KIAyhh+BgKtajSj7gl3qZOuMeJDTSLTaLXroFLg9hl8J6QJVFjAKgA1bC5BYwWOgxgWCphiNRmNxtNJlNpjNZ70WxgcGCdSXXO4PNUvTWgiruFEAWWwCGTqYT+LQAeDElDijzmQL8yLjF7pbBWZzY8jE44CVjqRTZmLfdjiMm5aClurtb1Msb8pbFX3pJCFXI70H1OHI9zy+jq/Xm/7s/TjER6UyBdvHDN9J3jbc50zCwKyPGs62lVUL1eAD8DbORO27H87wfIdh1HED8w/NIvwg39/yjIDX0ItdiNyLcZxLMj+EqKZoNw58JErZCKIAHhY71cF9DB/SfDjJCDMTgynVxK2PeCGzldU3hQq8IGwx9JOHDc6Jk2CT3rM9FObbjMlUio4HvDTNKZKzJIAfUPSpuAyWs5M8ZxcmkBIAHkSnVQVeTAGBbGxV4ACJ3JTLy4gMsKTWfCxGUkZktkkHY5kWZZ5MMpsNWFdj7CcFw4iOBJNFyWJ3BYpLiUK5xlBKxJysquRTGUWwqQKhx6rGVqwAWKAoE60SJHcFQOBTZgUEYAARGBIC0KdlleCAFnkKrrRUxhVvW1rJgqHbdja4L4uHLjNqjMzjtsCt4X6war1tXAUX2py7TmE7hvYsaoAm3JssQpTNQ24gtqq16qo+m72IkqSnpeqZgmva6arh972pBKHUdNd17sBYILsAvEsfYlLaBGqQoggCB/o7CBHBgAA5GA+Q+GH2I2PHGHJFGObS+kuYAQiRiBseS1LiR2KqAGEBtgVrKzx1GLCAA==
[5] кодген: https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8ABAJgEYBYAKBuIGYACMxgIRgDswALfbKANa4aAbxqMJzJgEsOGRgEkMMKNgzSIHXIxGMA5jAwBuRrkMmAvjXGSADlGkA3NTEaz5Crjv3nTvi4wAvIzkJgD0YYzAAJ6MsNgAJrJ6jABmUBD4adIwADYJYfYQtioY0WiMGNyuAFIKACqMkPi20rkqjADumgDk8sXq+NIAXq7S8hgQbl6yuBhQAK5g6prW1JKMaxsM0/IAYtAw2DwA6uPcAErYHAYAohwL+Cpq0FedZ1UAMhBg2LkAFABKGwSMTrDaSZxQRicR7PSbQ4L/AAMADpUf8lPCNFpGHAQoDAaiAOKGe5w1QIoEmCESEEQ4gAdkY5KelJgSgAgrkAbC2S8oICjFtacxyEhdiyHvzlFyef8rjcYKz4dAYdLVYL6RswaKIVDGNggoxkcLwXqJJ1uG1XP8+ZrUQBZCCOGAAORgCAwQOB5otGyNAGpgvbKdBUQBhBZQWByM3+iRMw3x0VWP1pjb0mhpnbEcXMUgsr2cXA44R+3Wi3P5xV3DVh6GkjAqhv/KrSbS11zEYjt3C+hNBAB8jH+Pb7qIAyhh+BgKuPrbhUfcEoDTJ1xjxtaLK4OJP9dApcHsMvgVyBKosYBUAGp/BYwC/IxgWCqH4+n8+Xh+3++Pk0vmugQjhwMCdIwXYtgKKIVO4TrYAgd65D+BJoNu/oHooH6ZF+8woUhD5Pi+b5YSeOEcAkF6pH8Zi/sh/4GpMgHDowoHgZB9bQciFRMYGIQVOQgJoX6g6YUeZFnhRVE0dejAEQx/BpKexHeOJn5Sd+snyURFhASBYEQdcdYUtB6SZLBcjwYhf4CUJ6EWmJ2GSZRaQyXRhGMAaZlZK+qlOV+1G5LRcl/hejFTLp9mDsBo7eYwAA8lQQGuuAbhgW4iXuoJRVlmksWxhlKlBVLeTxEC2cJuUWoFZj5QZHEmSVp5lRUcCCZVVWSK+OW0gA+ixVQZOBBWeM4uTSAkADyJSUjitwIGAMC2CsHD/AARKNfwTXERkwGtA4JhYKYSGmIqJkwcyLMshXGTK0D0ruEL2E4LhxEcCSaLksTuElx1PQ4zjKG9iSfd9cimMothmvZz2A2M4NgNGUDQ5lEjuCoHB/MwKCMAAIjAkBaHhyz/BACzyD9PalYwZMU+DkwVLTkpzEtB3+jFY7ENTDMQ6zxr/IjMY8YuqI8xOLO2EKaz2ejUCY7kN3KpxVKU1zzWSjzP0S2zEKPXqE5McEvG81DPWVCLEvGhLf36yLguIswauZHiJs2110uo1IUQQBACvOq6HpekC9l66K9uMMGrtm0m4cAIRGxAbsnWdDIyODUYxpw8gxfbf0WEAA=
[6] репозитории на github: https://github.com/WhiteBlackGoose/FastForeachEnumeratorArticle
[7] Бенчмарки: https://github.com/WhiteBlackGoose/FastForeachEnumeratorArticle/blob/main/FastEnum/Benchmarks/Program.cs
[8] Код енумератора: https://github.com/WhiteBlackGoose/FastForeachEnumeratorArticle/blob/main/FastEnum/Library/RangeEnumerator.cs
[9] Тесты: https://github.com/WhiteBlackGoose/FastForeachEnumeratorArticle/blob/main/FastEnum/Tests/UnitTest1.cs
[10] BenchmarkDotNet: https://github.com/dotnet/BenchmarkDotNet
[11] Источник: https://habr.com/ru/post/575664/?utm_source=habrahabr&utm_medium=rss&utm_campaign=575664
Нажмите здесь для печати.