14.03.2023 16:37
teoadal 12 5500 Источник

Я много работаю с массивами, поэтому хотел бы освежить тему того, как наиболее быстро по нему перемещаться в C#. Речь пойдёт об экономии наносекунд и оптимизации на уровне IL-кода. Кажется, что в 99% случаев вам это знать не нужно и задумываться об этом не стоит. Тем не менее, для горячих сценариев или если мы из high-load или геймдева, нам это может пригодиться.

Проблема: проверка границ массива

Ранее все выбирали обычный for, чтобы просто пробежаться по массиву. Ну, во всяком случае те, кто топил за перформанс. Это ведь оптимально и естественно, очень похоже на C++. И должно быть максимально быстро, правда? Да, но есть нюанс.

Основная проблема в том, что dotnet это не C++. Код исполняется несколько иначе, чем так, как мы видим. Dotnet следит за тем, чтобы мы не выходили в область памяти, которая нам не принадлежит. Следовательно, чтобы выбросить правильный exception и перед доступом к элементу массива, нужно проверить границы массива (array bounds check).

Каждый раз, когда мы пишем array[i], внутри .NET должна происходить эта проверка. Естественно, есть нюансы. Например, когда мы работаем внутри цикла for. Если в for использовать var i = 0; i < array.Length; i++, то проверка осуществляется всего однажды, как раз вот в этой вот строчке.

Есть ещё более интересный способ избежать проверки границ массива: сделать магические (uint)index <= (uint)size. Это подсказка для компилятора, что программист сам проверил выход за границу массива и дополнительно вставлять проверку в IL-код не требуется. Этот хитрый ход может применятся в изощрённых случаях и, например, при написании собственных коллекций.

При этом, есть ещё один, максимально простой и всем известный способ избежать проверок выхода за границы массива.

Foreach - всё просто

Тест предельно простой. У нас есть массив int'ов определённого размера и мы хотим выяснить, как по нему бежать максимально быстро. Собственно, никаких новостей не будет в том, что бежать по нему быстрее всего (обычными способами) с помощью foreach. Результаты benchmark'a подтверждают:

Method

Runtime

Mean

Ratio

For

.NET 6.0

504.5 ns

2.00

Foreach

.NET 6.0

252.3 ns

1.00

ForeachCustom

.NET 6.0

254.8 ns

1.01

ForeachSpan

.NET 6.0

252.3 ns

1.00

Unsafe

.NET 6.0

260.3 ns

1.03

UnsafeFixed

.NET 6.0

251.6 ns

1.00

For

.NET Core 3.1

516.3 ns

1.02

Foreach

.NET Core 3.1

505.6 ns

1.00

ForeachCustom

.NET Core 3.1

503.9 ns

1.00

ForeachSpan

.NET Core 3.1

252.4 ns

0.50

Unsafe

.NET Core 3.1

261.4 ns

0.52

UnsafeFixed

.NET Core 3.1

251.8 ns

0.50

For

.NET Framework 4.8

506.1 ns

1.99

Foreach

.NET Framework 4.8

253.7 ns

1.00

ForeachCustom

.NET Framework 4.8

437.6 ns

1.72

ForeachSpan

.NET Framework 4.8

760.1 ns

3.00

Unsafe

.NET Framework 4.8

505.0 ns

1.99

UnsafeFixed

.NET Framework 4.8

252.2 ns

0.99

Обычный foreach (см. колонку Ratio) хороший вариант в популярных и используемых версиях .NET. Однако, в .NET Core 3.1 следует присмотреться к foreach по array.AsSpan() или воспользоваться собственным перечислителем, который очень похож на enumerator у Span'a, если нам, почему-то, не нравятся Span'ы. Ещё в .NET Core 3.1 стоит присмотреться к unsafe, если наши коллеги не против. Спасибо @onyxmaster за дополнение.

Почему же foreach такой быстрый? Ответ очевиден — enumerator проверяет границы массива только один раз, а далее прозрачно для dotnet'a бежит по нему.

Почему unsafe оказался примерно на том же уровне, что и foreach в .NET 6 и в старом фреймворке? Для меня загадка. При этом, я уверен, что большинство программистов не захотят тащить в свой код unsafe без видимой на то причины. Увы, в этом месте я написал максимально тупой unsafe и разместил его тут скорее для формальности - проверить и этот вариант. Хороший код размещён в методе UnsafeFixed, который я взял из комментариев.

Однако, если возвращаться к foreach, то у него есть проблема, которая возникает при одновременном чтении и записи элементов в массив.

Проблема: чтение и запись одновременно

В чём проблема? Мы должны взять элемент массива, а затем заменить его на новый. Таким образом мы пытаемся имитировать случаи работы с массивами, как с основными коллекциями данных, когда нам нужно их не только читать, но и изменять содержимое.

Мы знаем, что лучше бы ходить в массив (использовать индексатор - array[i]) минимальное количество раз за итерацию. Как это сделать, если после чтения вам нужно присвоить array[i] = newValue? Всё опять-таки, всё просто. Но только начиная с C# 7.3. Именно тогда мы научились получать элемент массива по ref: ref var element = ref array[i]. Напомню, что это ссылка на элемент массива, присвоив которой новое значение, мы получим новое значение в самом массиве.

Кстати, почему нельзя использовать тот же самый foreach? Увы, дело в том, что foreach возвращает ref readonly, то есть ссылку на элемент массива, но только на чтение. Если нам всё-таки очень хочется работать с элементами массива в foreach like стиле, то можно снова воспользоваться собственным enumerator или просто сделать array.AsSpan(). Обе эти структуры возвращают изменяемую ссылку на элемент массива, что позволит нам выполнить чтение, а затем и присваивание.

Тестируем? Кажется, результаты benchmark'а будут интересные!

Method

Runtime

Mean

Ratio

ForeachCustom

.NET 6.0

471.5 ns

0.99

ForeachSpan

.NET 6.0

474.3 ns

1.00

Reference

.NET 6.0

518.7 ns

1.09

Terrible

.NET 6.0

523.3 ns

1.10

Unsafe

.NET 6.0

505.5 ns

1.07

ForeachCustom

.NET Core 3.1

438.8 ns

0.87

ForeachSpan

.NET Core 3.1

504.8 ns

1.00

Reference

.NET Core 3.1

532.0 ns

1.05

Terrible

.NET Core 3.1

529.5 ns

1.05

Unsafe

.NET Core 3.1

469.6 ns

0.93

ForeachCustom

.NET Framework 4.8

447.3 ns

0.85

ForeachSpan

.NET Framework 4.8

527.6 ns

1.00

Reference

.NET Framework 4.8

521.7 ns

0.99

Terrible

.NET Framework 4.8

522.0 ns

0.99

Unsafe

.NET Framework 4.8

466.8 ns

0.89

Да, действительно, интересные. Во-первых, в случае .NET Framework 4.8, победа уходит unsafe-коду. Это весьма очевидно, так как под капотом Span'a достаточно много похожего на unsafe-код. А старый framework может работать со Span только в качестве адаптера, чтобы обеспечить совместимость кода. Однако, если нам не хочется уходить в дебри unsafe, рекомендую опять таки воспользоваться возможностями собственного перечислителя.

Второй интересный момент заключается в том, что кастомный enumerator сильно опережает Span в версии .NET Framework 4.8 и .NET Core 3.1. Это странно, учитывая то, что код очень похож на код из Span'a. Честно говоря, я так и не понял почему так. Однако, это и не важно, так как лучше выбирать array.AsSpan(), чем долго и упорно оптимизировать и писать свои велосипеды.

В-третьих, unsafe закономерно показал хороший результат (кроме .NET 6). Мне кажется, это стоит запомнить и использовать. Если только ваши коллеги не против.

Случайный доступ к элементам массива

Для полноты теста, прогоним benchmark на случайный доступ к элементам массива по индексу. Как всегда, несколькими способами.

Method

Runtime

Mean

Ratio

ArrayIndex

.NET 6.0

514.3 ns

1.00

MemoryIndex

.NET 6.0

1,303.7 ns

2.54

Unsafe

.NET 6.0

478.1 ns

0.93

UnsafePined

.NET 6.0

503.2 ns

0.98

ArrayIndex

.NET Core 3.1

509.1 ns

1.00

MemoryIndex

.NET Core 3.1

1,314.6 ns

2.58

Unsafe

.NET Core 3.1

512.0 ns

1.00

UnsafePined

.NET Core 3.1

503.9 ns

0.99

ArrayIndex

.NET Framework 4.8

518.8 ns

1.00

MemoryIndex

.NET Framework 4.8

4,179.8 ns

8.06

Unsafe

.NET Framework 4.8

478.9 ns

0.92

UnsafePined

.NET Framework 4.8

515.5 ns

0.99

Магии не случилось, старый‑добрый доступ по индексу один из самых быстрых, без ухода в unsafe. При этом, мы можем заметить, что доступ через unsafe затрачивает примерно то же самое время. Но так делать не надо, вас заклюют коллеги. Если даже вам что‑то получится «выкружить» из unsafe, то это копейки по сравнению с тем, какое возрастание сложности кода мы получаем.

При этом, для меня стало неожиданным то, что доступ через Memory почти в три раза медленнее. Очень странно, учитывая то, что кода там не так чтобы много. Лишнего — тем более.

Выводы

  1. Используем foreach там, где нам необходимо быстро прочитать элементы из массива.

  2. Если нам нужно изменять значения в массиве, используем array.AsSpan и бужим по элементам, получаемым из его enumerator'a. В этом случае необходимо получать ссылку на элемент массива - foreach (ref var element in array.AsSpan()).

  3. Если мы не используем современный .NET, то... снова используемforeach, так как собственные имплементации Enumerator'a по array не всегда эффективны.

  4. Доступ по индексу, конечно, самый эффективный при случайном доступе. Мы можем "уйти в unsafe", но, чаще всего, результат не стоит усложнения кода.

  5. Не надо использовать unsafe. Во-первых, это надо уметь. А во-вторых, этого не одобрят коллеги. Ну и в-третьих, это не всегда так быстро, как рассказывают.

Где это тестировалось

Статья была опубликована в моём канале почти год назад. За это время многое изменилось. Изменился код .NET, люди удалили статьи с Хабра, изменили адреса в Youtube. Я тоже поменял машину. Извините, если в статье что-то не работает. Я очень старался сделать так, чтобы чтение было приятным. Наконец, я заново прогнал все бенчмарки. Машина для тестирования за год тоже изменилась, теперь она вот такая:

BenchmarkDotNet=v0.13.5, OS=Windows 11 (10.0.22621.1265/22H2/2022Update/SunValley2)
AMD Ryzen 7 5800H with Radeon Graphics, 1 CPU, 16 logical and 8 physical cores
.NET SDK=7.0.102
  [Host]             : .NET 6.0.13 (6.0.1322.58009), X64 RyuJIT AVX2
  .NET 6.0           : .NET 6.0.13 (6.0.1322.58009), X64 RyuJIT AVX2
  .NET Core 3.1      : .NET Core 3.1.22 (CoreCLR 4.700.21.56803, CoreFX 4.700.21.57101), X64 RyuJIT AVX2
  .NET Framework 4.8 : .NET Framework 4.8.1 (4.8.9139.0), X64 RyuJIT VectorSize=256

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


  1. duck_alan
    00.00.0000 00:00
    #25325780

    Почему unsafe оказался медленнее? Для меня в этом загадка.

    Затраты на fixed? Можно было бы и приложить код


    1. teoadal Автор
      00.00.0000 00:00
      #25325792
      +1

      Возможно. Код не приложил, извините - за давностью лет немного потерялся. Попробую восстановить.


    1. teoadal Автор
      00.00.0000 00:00
      #25325890
      +1

      Спасибо большое за замечание! Ссылку обновил - https://gist.github.com/teoadal/9297c0b574a175fc295bb29c01782fa2


  1. onyxmaster
    00.00.0000 00:00
    #25326046
    +4

    А зачем цикл в unsafe по int? Можно высчитать указатель на конечный элемент и сделать цикл по указателю.

    [Benchmark]
public unsafe int UnsafeFixed()
{
    var sum = 0;
    fixed (int* arrayPtr = _array)
    {
        var ptr = arrayPtr;
        var endPtr = arrayPtr + _array.Length;
        while (ptr < endPtr)
        {
            sum += *ptr++;
        }
    }

    return sum;
}

    Ожидаемо разрывает всё что угодно:

    |      Method |                  Job |              Runtime |     Mean |   Error |  StdDev | Ratio |
|------------ |--------------------- |--------------------- |---------:|--------:|--------:|------:|
|         For |             .NET 6.0 |             .NET 6.0 | 409.5 ns | 3.77 ns | 3.53 ns |  1.10 |
|     Foreach |             .NET 6.0 |             .NET 6.0 | 373.2 ns | 0.32 ns | 0.25 ns |  1.00 |
| ForeachSpan |             .NET 6.0 |             .NET 6.0 | 372.4 ns | 0.42 ns | 0.39 ns |  1.00 |
|      Unsafe |             .NET 6.0 |             .NET 6.0 | 362.7 ns | 2.35 ns | 2.20 ns |  0.97 |
| UnsafeFixed |             .NET 6.0 |             .NET 6.0 | 316.6 ns | 2.00 ns | 1.77 ns |  0.85 |
|             |                      |                      |          |         |         |       |
|         For | .NET Framework 4.7.2 | .NET Framework 4.7.2 | 391.7 ns | 0.22 ns | 0.19 ns |  1.05 |
|     Foreach | .NET Framework 4.7.2 | .NET Framework 4.7.2 | 373.4 ns | 0.07 ns | 0.06 ns |  1.00 |
| ForeachSpan | .NET Framework 4.7.2 | .NET Framework 4.7.2 | 544.2 ns | 0.26 ns | 0.23 ns |  1.46 |
|      Unsafe | .NET Framework 4.7.2 | .NET Framework 4.7.2 | 364.9 ns | 0.97 ns | 0.91 ns |  0.98 |
| UnsafeFixed | .NET Framework 4.7.2 | .NET Framework 4.7.2 | 317.6 ns | 0.70 ns | 0.62 ns |  0.85 |


    1. teoadal Автор
      00.00.0000 00:00
      #25326176
      +2

      Спасибо! Я добавлю ваш комментарий в статью. Однако, я должен отметить, что мои измерения несколько иные. Действительно "рвёт" только в .NET Core 3.1. Код обновил.

      Окружение:

      BenchmarkDotNet=v0.13.5, OS=Windows 11 (10.0.22621.1265/22H2/2022Update/SunValley2)
AMD Ryzen 7 5800H with Radeon Graphics, 1 CPU, 16 logical and 8 physical cores
.NET SDK=7.0.102
  [Host]             : .NET 6.0.13 (6.0.1322.58009), X64 RyuJIT AVX2
  .NET 6.0           : .NET 6.0.13 (6.0.1322.58009), X64 RyuJIT AVX2
  .NET Core 3.1      : .NET Core 3.1.22 (CoreCLR 4.700.21.56803, CoreFX 4.700.21.57101), X64 RyuJIT AVX2
  .NET Framework 4.8 : .NET Framework 4.8.1 (4.8.9139.0), X64 RyuJIT VectorSize=256

      Результаты:

      |        Method |                Job |            Runtime |     Mean |    Error |   StdDev | Ratio | RatioSD |
|-------------- |------------------- |------------------- |---------:|---------:|---------:|------:|--------:|
|           For |           .NET 6.0 |           .NET 6.0 | 504.5 ns |  2.37 ns |  2.22 ns |  2.00 |    0.03 |
|       Foreach |           .NET 6.0 |           .NET 6.0 | 252.3 ns |  3.69 ns |  3.08 ns |  1.00 |    0.00 |
| ForeachCustom |           .NET 6.0 |           .NET 6.0 | 254.8 ns |  2.63 ns |  2.46 ns |  1.01 |    0.02 |
|   ForeachSpan |           .NET 6.0 |           .NET 6.0 | 252.3 ns |  3.82 ns |  3.39 ns |  1.00 |    0.02 |
|        Unsafe |           .NET 6.0 |           .NET 6.0 | 260.3 ns |  3.01 ns |  2.67 ns |  1.03 |    0.02 |
|   UnsafeFixed |           .NET 6.0 |           .NET 6.0 | 251.6 ns |  3.88 ns |  3.24 ns |  1.00 |    0.02 |
|               |                    |                    |          |          |          |       |         |
|           For |      .NET Core 3.1 |      .NET Core 3.1 | 516.3 ns | 10.07 ns | 10.34 ns |  1.02 |    0.03 |
|       Foreach |      .NET Core 3.1 |      .NET Core 3.1 | 505.6 ns |  5.50 ns |  5.14 ns |  1.00 |    0.00 |
| ForeachCustom |      .NET Core 3.1 |      .NET Core 3.1 | 503.9 ns |  5.28 ns |  4.94 ns |  1.00 |    0.01 |
|   ForeachSpan |      .NET Core 3.1 |      .NET Core 3.1 | 252.4 ns |  2.86 ns |  2.67 ns |  0.50 |    0.01 |
|        Unsafe |      .NET Core 3.1 |      .NET Core 3.1 | 261.4 ns |  2.78 ns |  2.60 ns |  0.52 |    0.01 |
|   UnsafeFixed |      .NET Core 3.1 |      .NET Core 3.1 | 251.8 ns |  2.13 ns |  1.99 ns |  0.50 |    0.01 |
|               |                    |                    |          |          |          |       |         |
|           For | .NET Framework 4.8 | .NET Framework 4.8 | 506.1 ns |  7.55 ns |  7.07 ns |  1.99 |    0.02 |
|       Foreach | .NET Framework 4.8 | .NET Framework 4.8 | 253.7 ns |  1.96 ns |  1.73 ns |  1.00 |    0.00 |
| ForeachCustom | .NET Framework 4.8 | .NET Framework 4.8 | 437.6 ns |  8.57 ns |  8.80 ns |  1.72 |    0.04 |
|   ForeachSpan | .NET Framework 4.8 | .NET Framework 4.8 | 760.1 ns |  9.50 ns |  8.89 ns |  3.00 |    0.04 |
|        Unsafe | .NET Framework 4.8 | .NET Framework 4.8 | 505.0 ns |  3.33 ns |  2.95 ns |  1.99 |    0.02 |
|   UnsafeFixed | .NET Framework 4.8 | .NET Framework 4.8 | 252.2 ns |  2.79 ns |  2.61 ns |  0.99 |    0.01 |


      1. onyxmaster
        00.00.0000 00:00
        #25327424

        Я 3.1 для себя уже списал, на нём не тестировал. Думаю что разница из-за того что у нас с вами разные процессоры, у которых разная архитектура, в т.ч. Доступа к памяти.


    1. VBDUnit
      00.00.0000 00:00
      #25337668
      +1

      Интересно ещё попробовать в анроллинг (пока у меня нет возможности проверить скорость):

      [Benchmark]
public unsafe long UnsafeFixedWithUnroll()
{
    int sum = 0;
    fixed (int* arrayPtr = _array)
    {
        var ptr = arrayPtr;
        
        var endPtrFast = arrayPtr + _array.LongLength / 32 * 32;
        //Сравнение ptr < endPtrFast происходит в 32 раза реже  
        while (ptr < endPtrFast)
        {
            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;

            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;

            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;

            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;

            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;

            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;

            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;

            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;
            sum += *ptr++;
        }
      
        var endPtr = arrayPtr + _array.LongLength;
        //Досчитываем хвостик
        while (ptr < endPtr)
          sum += *ptr++;
    }

    return sum;
}

      Ещё можно попробовать прикрутить к этому циклу SIMDы через Vector<int>, но тут уже всё зависеть будет от архитектуры ЦП — выигрыш будет не всегда. Ну и банальная многопоточность по всем доступным ядрам, но она будет выгодна начиная с определённого размера массива, т.к. появляются накладные расходы. Однако, можно прямо в алгоритм запихнуть автоматическую адаптацию к конкретной системе и условиям, чтобы алгоритм сам решал, когда запускать многопоточность, а когда достаточно 1 потока.


      1. teoadal Автор
        00.00.0000 00:00
        #25337726
        +1

        Ого! Спасибо, я попробую. С SIMD обращусь к специалисту, у меня с ним нет опыта.


  1. ARad
    00.00.0000 00:00
    #25326848
    +3

    Добавил методы ForUnsafeRef и ForUnsafe2Refs их лучше использовать вместо методов с указателями, потому что ссылки это более современные указатели. Исходники тут.

    ForUnsafe2Refs работает быстрее в .NET 6.0 и младше, в последних версиях .NET 7.0 и старше скорость обычного цикла не отличается. Тут уже компилятор похоже выжимает максимум на целых массивах.

    Для других типов данных не тестировал, думаю для больших типов значений (value types) эти методы и особенно ForUnsafe2Refs будут работать быстрее чем обычный цикл на любой версии .NET, так как не будет выполняться копирование.

    Вот их производительность на моем компьютере:

    |         Method |                Job |            Runtime |       Mean |    Error |   StdDev | Ratio | RatioSD |
|--------------- |------------------- |------------------- |-----------:|---------:|---------:|------:|--------:|
|   ForUnsafeRef |           .NET 6.0 |           .NET 6.0 |   748.2 ns | 14.15 ns | 21.61 ns |  1.02 |    0.03 |
| ForUnsafe2Refs |           .NET 6.0 |           .NET 6.0 |   593.9 ns | 11.85 ns | 21.06 ns |  0.80 |    0.04 |
|                |                    |                    |            |          |          |       |         |
|   ForUnsafeRef |           .NET 7.0 |           .NET 7.0 |   726.0 ns | 14.54 ns | 13.60 ns |  1.27 |    0.03 |
| ForUnsafe2Refs |           .NET 7.0 |           .NET 7.0 |   591.5 ns | 11.47 ns | 13.65 ns |  1.04 |    0.03 |
|                |                    |                    |            |          |          |       |         |
|   ForUnsafeRef |           .NET 8.0 |           .NET 8.0 |   769.5 ns | 13.36 ns | 12.49 ns |  1.28 |    0.03 |
| ForUnsafe2Refs |           .NET 8.0 |           .NET 8.0 |   596.1 ns | 11.48 ns | 12.29 ns |  0.99 |    0.03 |
|                |                    |                    |            |          |          |       |         |
|   ForUnsafeRef |      .NET Core 3.1 |      .NET Core 3.1 |   741.4 ns | 13.16 ns | 12.31 ns |  0.85 |    0.02 |
| ForUnsafe2Refs |      .NET Core 3.1 |      .NET Core 3.1 |   595.3 ns | 11.93 ns | 13.26 ns |  0.68 |    0.02 |
|                |                    |                    |            |          |          |       |         |
|   ForUnsafeRef | .NET Framework 4.8 | .NET Framework 4.8 |   928.3 ns |  9.07 ns |  8.48 ns |  1.18 |    0.03 |
| ForUnsafe2Refs | .NET Framework 4.8 | .NET Framework 4.8 |   618.0 ns | 11.87 ns | 12.70 ns |  0.78 |    0.02


    1. teoadal Автор
      00.00.0000 00:00
      #25327192
      +2

      Спасибо большое! Как дойдут руки, я обязательно добавлю ваш код в статью.


  1. arTk_ev
    00.00.0000 00:00
    #25339262

    Linq и foreach использует кучу и генерят мусор, это тоже нужно учитывать. Это делает их бесполезными и медленными. При этом оригинальный linq из F# сделан адекватно.


    1. teoadal Автор
      00.00.0000 00:00
      #25339380

      Foreach не генерит мусор, если Enumerator это struct. Вроде как struct enumerator'ы реализованы уже для всех основных коллекций.

      Если же вы бежите по IList или другим интерфейсам коллекций, то да, struct enumerator будет упакован и будет аллокация.

      Про Linq согласен. Linq в "горячем месте кода" надо разворачивать в foreach.