Ускоряем цикл foreach до for / forpes.ru

Главная
Ускоряем цикл foreach до for

Ускоряем цикл foreach до for +45

01.09.2021 11:35

WhiteBlackGoose 21 15000 Источник

Привет! Хочу рассказать об интересном опыте, как я писал енумератор для типа 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) => ...
}

Baseline (на что равняемся)

Вообще-то 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;
}

(мы выгрузили все проперти в локальные переменные чтобы исключить чтение из памяти при итерации)

Кодген for-а:

    L000f: add edx, r8d
    L0012: add r8d, ecx
    L0015: cmp r8d, eax
    L0018: jl short L000f

Мы будем смотреть только на код одной итерации цикла, начальный оверхед и окружающий мусор нас не интересует.

Эксперимент 1. Enumerable.Range

Конечно, сначала стоит попробовать вариант из BCL: Enumerable.Range, исходный код которого можно поизучать здесь.

Так выглядит наш бенчмарк:

[Benchmark]
public int ForeachWithEnumerableRange()
{
    var a = 0;
    foreach (var i in Enumerable.Range(0, Iterations))
        a += i;
    return a;
}

Этот код Розлином раскрывается как

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

Эксперимент 2. yield return

Второй по простоте способ - написать метод-генератор, и вызывать его енумератор:

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

Эксперимент 3. Собственный енумератор

Теперь будем писать собственный енумератор. Чтобы оно работало с 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. Время взглянуть на кодген!

Одна итерация цикла выглядит так:

    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

Да, у нас референс-типов нет, но все данные-то все равно в памяти! Хоть и на стеке.

Эксперимент 4. Собственный енумератор прячем в локальную функцию

Что за магия? Дело в том, что чтобы получить наш енумератор таким же быстрым, как 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 - это как раз вариант с локальной функцией. И... он почти в шесть раз быстрее, чем заинлайненный! Как же так вышло-то?

Смотрим кодген:

В нашем методе локальная функция не заинлайнилась:

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 итераций).

Спасибо за внимание!

UPD: поведение совершенно разное на винде и линуксе. Например, разбирая WithLocal метод-бенчмарк, у @DistortNeo получился совсем иной от винды кодген. Вот здесь я сделал гист с кодгеном метода WithLocal для винды и линукса. В случае последнего, джит заменил call на jmp, а локальные переменные локальной функции разместил на стеке.

Ссылки

Весь код, который я писал, размещен в репозитории на github.

Бенчмарки
Код енумератора
Тесты, если есть подозрение на неправильный код
BenchmarkDotNet - утилита/библиотека для бенчинга

Бенчилось на винде

Комментарии (21)

WhiteBlackGoose Автор
01.09.2021 11:43
#23435228
+2
Проводил эксперименты на x64 шестом дотнете, все ссылки с шарплаба тоже настроены x64, хоть там пятый, разницы это не дало (в коде бенчмарка я закомментил аттрибут DisassemblyDiagnoser, с которым вы можете посмотреть именно тот асм, который гоняет бенчмарк)

Кстати, интересно то, что если поставить Default на шарплабе, т. е. 32-битный рантайм, то мы в последнем эксперименте получили бы:
```
    L0007: add eax, edx
    L0009: mov edx, [ebp+0x10]
    L000c: add edx, [ebp+0xc]
    L000f: mov [ebp+0x10], edx
    L0012: cmp edx, [ebp+8]
    L0015: jne short L0007
```
Так что... используйте 64 бита! :)

А еще можно попробовать включить Dynamic PGO, запустив бенчмарк так:
```
dotnet run -c release --envVars DOTNET_TieredPGO:1 DOTNET_ReadyToRun:0 DOTNET_TC_QuickJitForLoops:1
```
Но у меня получились те же результаты, что и в статье, так что я решил оставить это в комментарии.

DistortNeo

01.09.2021 13:51

#23435670

Странно. У меня получилось немного по-другому:

BenchmarkDotNet=v0.13.1, OS=arch
Intel Core i7-2600K CPU 3.40GHz (Sandy Bridge), 1 CPU, 4 logical and 4 physical cores
.NET SDK=6.0.100-preview.7.21379.14
  [Host]     : .NET 6.0.0 (6.0.21.37719), X64 RyuJIT
  DefaultJob : .NET 6.0.0 (6.0.21.37719), X64 RyuJIT

|                                 Method | Iterations |      Mean |     Error |    StdDev |
|--------------------------------------- |----------- |----------:|----------:|----------:|
|                 ForWithCustomIncrement |      10000 |  4.535 us | 0.0007 us | 0.0007 us |
|             ForeachWithEnumerableRange |      10000 | 50.097 us | 0.0050 us | 0.0044 us |
|                 ForeachWithYieldReturn |      10000 | 52.565 us | 0.0055 us | 0.0049 us |
|             ForeachWithRangeEnumerator |      10000 |  4.453 us | 0.0005 us | 0.0004 us |
|          ForeachWithRangeEnumeratorRaw |      10000 |  4.453 us | 0.0007 us | 0.0006 us |
| ForeachWithRangeEnumeratorRawWithLocal |      10000 | 17.543 us | 0.0100 us | 0.0094 us |

WhiteBlackGoose Автор

01.09.2021 14:44

#23435902

Ух ты. А кодген покажете? Там нужно в моем бенчмарке раскомментить DisassemblyDiagnoser, а потом посмотреть Artifacts папку

А еще я смотрю у вас Линукс, на нем может по-другому такие вещи работать (я на винде). Интересно посмотреть кодген!

DistortNeo

01.09.2021 16:20

#23436300

Возможно, у нас просто немного разные релизы .NET.
Вот дизассемблер:

Benchmarks-asm.md