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

в 8:35, , рубрики: .net, C#, csharp, performance, высокая производительность

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

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

Ссылки

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

Автор:
WhiteBlackGoose

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js