От юниора до гения: история оптимизации

Вот ограничения:

• C#/dotnet 6.Наличие компилятора JIT делает его более интересным.
• Однопоточный. Мы не собираемся исследовать распараллеливание.
• x86. ARM, WASM и другие цели будут исключены.

Без лишних слов, вот что я называю контрольной суммой Junior:

Метод довольно прост: суммирование сумм по 4 столбцам и их сведение к одному uint с использованием LSB из каждого аккумулятора. Учитывая требования, я ожидаю от образованного младшего разработчика именно этого.

Я знаю, о чем вы думаете: Джуниор только что скопировал это из StackOverflow. Если ты джуниор, я тебе говорю: все в порядке. Все так делают в той или иной степени — просто убедитесь, что вы понимаете, что копируете.

А вот и Про

Итак, теперь наша небольшая контрольная сумма передается в Pro. Про был немного и научился нескольким трюкам, но все еще не может быть назван старшим.

Первое, что делает Pro, — это тестирует код Junior, чтобы установить базовый уровень.

Тест использует буфер размером 1 МБ, заполненный случайными данными.

Вот результаты:

|   Method |  Length |     Mean |
|--------- |-------- |---------:|
|   Junior | 1000000 | 1.799 ms |

Эти цифры хорошие или плохие? 1,8 мс на 1 Мб данных кажутся довольно быстрыми, но задача ясна: сделать еще быстрее. Некоторое время почесав затылок, Pro решает развернуть цикл.

Развертывание цикла — это метод, который меняет размер кода на производительность. Идея состоит в том, чтобы выполнять больше работы за каждую итерацию цикла. Итак, вместо:

for (x = 0; x < 100; x++)
{
     work(x);
}

можно было бы написать:

for (x = 0; x < 100; x+=5)
{
    work(x);
    work(x+1);
    work(x+2);
    work(x+3);
    work(x+4);
}

Основная причина этого заключается в том, что на каждой итерации будет происходить сравнение ( x ‹ 100 ), добавление ( x++) и переход. Повторяя операторы, скомпилированный код приводит к меньшему количеству операций, так как теперь переход и сравнение происходят только один раз на каждые 5 вызовов work().

В большинстве компиляторов развертывание циклов является одним из инструментов оптимизации. Обычно, если цикл имеет фиксированное низкое количество итераций, вы можете заметить разворачивание, происходящее в сгенерированной сборке.

Про версия контрольной суммы:

Хотя это возможно, эта версия работает с 16 байтами на итерацию. После этого он выполняет пару 4-байтовых циклов и, наконец, добавляет последние 3, 2 или 1 оставшиеся байты. Это намного больше строк кода, но оно того стоило?

|   Method |  Length |       Mean |     Median | Ratio |
|--------- |-------- |-----------:|-----------:|------:|
|   Junior | 1000000 | 1,855.5 us | 1,825.4 us |  1.00 |
|      Pro | 1000000 |   373.8 us |   373.8 us |  0.20 |

Сравнительный тест кричит да. Это в 5 раз быстрее, чем у Джуниора.

Влияют ли годы в дороге?

Теперь мы передаем задачу старшему с тем же простым поручением: сделать ее быстрее.

Senior существует довольно давно, на самом деле так долго, что, когда они только начинали программировать, C# был шуткой. Старший написал много кода на C, знает указатели и понимает ассемблерный код.

Обратите внимание, что некоторые Gists отображают только наиболее релевантную петлю в решении. В конце этой статьи есть ссылка на репозиторий Github, который вы можете разветвить и играть.

Обновленный тест, улучшение в 1,6 раза по сравнению с Pro и в 7,8 раз по сравнению с Junior:

|   Method |  Length |       Mean | Ratio |
|--------- |-------- |-----------:|------:|
|    Junior| 1000000 | 1,803.0 us |  1.00 |
|      Pro | 1000000 |   365.2 us |  0.20 |
|   Senior | 1000000 |   231.6 us |  0.13 |

Код очень похож на Pro, поэтому давайте разберем изменения и разберемся, что происходит.

1. Маркировка метода как небезопасного

public static uint ChecksumPro(ReadOnlySpan<byte> arr)
public unsafe static uint ChecksumSenior(ReadOnlySpan<byte> arr)

Первое изменение — добавление ключевого слова unsafe в подпись. Это позволяет нам, например, использовать указатели внутри метода. В мире C# это заявление разработчика, которое переводится как «Я знаю, что делаю, компилятор, будь крут».

2. Собственно получение указателя

fixed (byte* ptr = arr)

Наиболее распространенный способ использования указателя в C# — внутри фиксированной области. По собственным словам документации C#:

Оператор fixed запрещает сборщику мусора перемещать перемещаемую переменную и объявляет указатель на эту переменную.

По сути, это гарантирует, что полученный нами указатель останется действительным, и CLR не будет перемещать базовые данные. Такая проблема возникает только здесь, потому что мы работаем в среде управляемой памяти. CLR добавляет уровень абстракции между тем, что мы считаем переменными, и фактическим адресом памяти, по которому они расположены. (Ну, честно говоря, ОС также добавляет уровень абстракции, предлагая процессам виртуальную память, но здесь это выходит за рамки нашего рассмотрения). Каждая абстракция неизбежно вводит накладные расходы. Это цена, которую разработчики платят за удобство сборщика мусора. Использовать указатели в C# означает временно обойти эту абстракцию.

Отсюда код выглядит почти точно так же, но вместо индексации массива он индексирует указатель:

arr[z + 0] //indexed array 
ptr[z + 0] //indexed pointer

3. Следите за ASM

В конце дня код C# будет преобразован в машинный код для выполнения. Когда вы достигаете этого уровня детализации, учитывается каждая инструкция, удаленная из пути выполнения. Возьмем, к примеру, эти два метода:

Версия, использующая целые числа без знака, имеет на одну инструкцию меньше. Поскольку в первом методе мы используем int, компилятор добавляет movsxd перед каждым доступом к памяти (movzx).

movsxd isПеремещение с расширением подписи

По сути, это преобразование целого числа со знаком в беззнаковое для индексации указателя. Вы можете подумать, что одна дополнительная инструкция не повредит, но если это происходит в тесном цикле, 6 инструкций против 7 могут привести к 15%-ной разнице в производительности.

Я знаю, что некоторые скажут дальше: вам нужно учитывать взаимную пропускную способность, задержку и конвейерную обработку инструкций, чтобы на самом деле сделать утверждение выше. Правда, я упрощаю, чтобы подчеркнуть суть.

Также стоит упомянуть, что в нашем случае, хотя и отображается код X86 ASM, на самом деле происходит то, что компилятор выводит код IL, который затем компилируется в машинный код JIT-компилятором в зависимости от платформы. Заявления, сделанные здесь, могут быть недействительны, например, для набора инструкций ARM.

Кроме того, нет никакой гарантии, что JIT всегда будет выводить одни и те же инструкции ASM. JIT — это инженерный подвиг, полный эвристики и постоянно развивающийся. Код, который мы пишем сегодня, завтра может быть скомпилирован с другим набором инструкций, потому что в JIT были добавлены новые приемы повышения производительности. Это яркая сторона работы над фреймворком с компилятором «точно в срок» — наш код может работать быстрее без фактической доставки обновлений. С другой стороны, это делает производительность менее предсказуемой.

Хорошо, но что на самом деле изменилось между версиями Pro и Senior? Давайте посмотрим на часть декомпилированного ASM из обоих:

Легко заметить закономерность, даже не зная точно, что делает каждая инструкция ASM:

lea      ebx, [r11+0CH]
cmp      ebx, ecx
jae      G_M000_IG17
mov      ebx, ebx
movzx    rbx, byte  ptr [rdx+rbx]
add      eax, ebx

против:

lea      ebx, [r11+08H]
movzx    rbx, byte  ptr [rdx+rbx]
add      eax, ebx

Разберем первые строки:

lea      ebx, [r11+0CH] //loads data into ebx
cmp      ebx, ecx       //compares ebx to ecx
jae      G_M000_IG17    //jump to G_M000_IG17 if result from compare
                        //is above or equal 0
mov      ebx, ebx       //moves data from address in ebx into ebx
                        //this is a pointer dereferencing (*ptr)

Что здесь делает этот прыжок?

Если проверить, что находится на метке G_M000_IG17, мы находим:

G_M000_IG17:                ;; offset=0445H
        E8E675C15F           call     CORINFO_HELP_RNGCHKFAIL
        CC                   int3

Хорошо — похоже, это ошибка проверки диапазона. Теперь становится ясно: дополнительные инструкции отвечают за генерацию исключения, если код пытается получить доступ к позиции за пределами массива. Это то, что заставляет приведенный выше фрагмент выдавать исключение вместо чтения неопределенных данных в arr[2]:

var arr = new byte[1] { 0 };
var invalid = arr[2];       // IndexOutOfRangeException thrown

Что произойдет, если границы не проверяются и обращаются к недопустимым адресам? Всевозможные гадости, включая SEGFAUTS и тому подобное. Не красиво. Это C#, который ставит тренировочные колеса на ваш велосипед.

Код Senior, используя ключевое слово unsafe и указатели, позволяет избежать этих связанных проверок в узком цикле. В результате в большинстве шаблонов чтения/записи используется 3 инструкции вместо 6.

Компилятор JIT может удалить проверки привязки, если он может доказать, что индекс никогда не выйдет за границы массива. Pro допустил ошибку, которая, если ее исправить, заставила бы JIT-компилятор удалить связанные проверки и приблизить его производительность к Senior без использования указателей. Я призываю вас заметить это.

Кто-то может возразить, что наиболее важным аспектом является удаление всех этих переходов, поскольку переход означает ветвление, а ветвление означает, что ЦП должен выполнять спекулятивное выполнение и пытаться предсказать, по какому пути пойдет переход. Я понимаю, но в этом упражнении давайте для простоты просто посчитаем, что меньше инструкций означает меньше работы.

Кому нужен хакер?

Решение Senior отличное. Чтобы выйти за рамки этого, требуется нестандартное мышление. Передаем его Хакеру. Задача все та же: сделать быстрее.

Мы получаем это:

|   Method |  Length |       Mean | Ratio |
|--------- |-------- |-----------:|------:|
| Baseline | 1000000 | 1,761.0 us |  1.00 |
|      Pro | 1000000 |   363.6 us |  0.21 |
|   Senior | 1000000 |   224.6 us |  0.13 |
|   Hacker | 1000000 |   120.0 us |  0.07 |

Двукратное улучшение по сравнению с Senior, что может показаться мусором для неопытного глаза. Однако некоторые из вас, читатели, возможно, уже поняли этот трюк. Вы? Оставьте комментарий и расскажите мне :)

В контексте нашей задачи определение хакера таково:

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

Часто, когда вы читаете исходный код действительно чувствительных к производительности проектов, таких как, например, ядро ​​Linux, вы сталкиваетесь с разделами, которые выглядят как колдовские заклинания, написанные символами ASCII. Отличное упражнение — понять эти фрагменты и разбить используемые методы, чтобы они стали строительными блоками, которые вы можете использовать для составления умных решений проблем, с которыми вы сами, возможно, столкнетесь в будущем.

Хитрость здесь заключается в перепрофилировании longкак вектора 4-ширины short. Давайте разберем соответствующий раздел:

ulong l1 = *(ulong*)(ptr + z);
//1. a=(ptr + z) adds offset z to pointer ptr ( ptr is byte* )
//2. b=(ulong*)(a) casts that pointer to a ulong*
//3. *(b) dereferences the pointer and reads the long value

Итак, этот первый маленький трюк — чтение 8 байтов в ulong. Предполагая, что мы находимся на машине x64, это одна выборка памяти. Затем это проделывается еще 3 раза:

ulong l1 = *(ulong*)(ptr + z);
ulong l2 = *(ulong*)(ptr + z + 8);
ulong l3 = *(ulong*)(ptr + z + 16);
ulong l4 = *(ulong*)(ptr + z + 24);

На данный момент мы эффективно читаем 4 ulong, или 32 байта данных, за счет 4 инструкций вместо 32, необходимых для чтения байт за байтом.

l1 & 0x00FF00FF00FF00FF;

Следующий трюк — применение маски к первому long. Если мы аннотируем байты в l1 в системе с прямым порядком байтов, это будет выглядеть так:

B7_B6_B5_B4_B3_B2_B1_B0

И применяя эту маску, мы получаем

  B7_B6_B5_B4_B3_B2_B1_B0 & 0x00_FF_00_FF_00_FF00_FF
= 00_B6_00_B4_00_B2_00_B0

Что произойдет, если мы будем смотреть на эти замаскированные длинные два байта за раз?

0x00_B6 0x00_B4 x00_B2 0x00_B0

Это B0, B2, B4 и B4, расширенные от однобайтового слова до двухбайтового слова. Мы преобразовали каждый байт в шорт.

(l1 & 0xFF_00_FF_00_FF_00_FF_00) >> 8

Это делает то же самое для нечетных байтов, сдвигая один байт, чтобы получить их в правильном положении. Делая это для всех 4 ulongпрочитанных нами, мы теперь имеем:

M1= 00_B6__00_B4__00_B2__00_B0
M2= 00_B7__00_B5__00_B3__00_B1
M3= 00_B14_00_B12_00_B10_00_B8
M4= 00_B15_00_B13_00_B11_00_B9
M5= 00_B22_00_B20_00_B18_00_B16
M6= 00_B23_00_B21_00_B19_00_B17
M7= 00_B30_00_B28_00_B26_00_B24
M8= 00_B31_00_B29_00_B27_00_B25

Что произойдет, если мы суммируем M1 с M3, M5 и M7? Предполагая, что человек

  00_B6__00_B4__00_B2__00_B0
+ 00_B14_00_B12_00_B10_00_B8
+ 00_B22_00_B20_00_B18_00_B16
+ 00_B30_00_B28_00_B26_00_B24
= [B6+B14+B22+B30]_[B4+B12+B20+B28]_[B2+B10+B18+B26]_[B0+B8+B16+B24]

Назовем краткий обзор этих S1, S2, S3 и S4:

S1= [B6+B14+B22+B30] = (M1+M5)& 0xFF_FF_00_00_00_00_00_00 >> 48
S2= [B4+B12+B20+B28] = (M1+M5)& 0x00_00_FF_FF_00_00_00_00 >> 32
S3= [B2+B10+B18+B26] = (M1+M5)& 0x00_00_00_00_FF_FF_00_00 >> 16
S4= [B0+B8+B16+B24]  = (M1+M5)& 0x00_00_00_00_00_00_FF_FF

Вспоминая предыдущую версию, аккумуляторы были:

sum0 += (B0 + B4 + B8 + B12 + B16 + B20 + B24 + B28)
sum1 += (B1 + B5 + B9 + B13 + B17 + B21 + B25 + B29)
sum2 += (B2 + B6 + B10 + B14 + B18 + B22 + B26 + B30)
sum3 += (B4 + B7 + B11 + B15 + B19 + B23 + B27 + B31)

Понятно, что мы можем добиться того же накопления, используя эти битовые манипуляции.

sum0 = (S2 + S4)
sum2 = (S1 + S3)
...

Но что, если вместо этого мы продолжим суммировать эти длинные позиции, прежде чем объединять короткие в суммы sum0, sum1 и т. д.?

while(...)
{
    tmp1 += M1+M3+M5+M7
    ...
}

Теперь мы взламываем ulong, перепрофилируя его в 4-ширинный shortvector. Но есть одна загвоздка: мы не можем допустить, чтобы сумма любого отдельного элемента превышала максимальное значение беззнакового короткого 0xFFFF.

Мы добавляем 4 байта к каждому шорту на каждой итерации, поэтому мы можем безопасно сделать это 64 раза, прежде чем достигнем 0xFF.

0xFF * 4 *64 = 0xFF00

После этого любой из шортов может переполниться, и наш взломанный вектор будет поврежден. Итак, когда мы делаем 64 итерации, мы извлекаем каждое значение вектора и добавляем его к исходным суммам, сбрасывая векторы. Это именно то, что делает этот раздел:

if (limit2 != 64)
   sum0= ...
   sum1= ...
   sum2= ...
   sum3= ...
}

Вот как выглядит код ASM для узкого цикла:

А вот расширенная и аннотированная версия с промежуточными переменными, за которыми может быть проще следить:

Почему эксперта называют экспертом?

Одной из основных характеристик, которые я использую для описания эксперта, является способность анализировать проблемы с их основ. Видите ли, все наши коллеги-разработчики с легкостью справились с этой задачей, вывалив все свои знания поверх своих предшественников. Никто из них не подвергал сомнению аргументацию — они просто улучшили ее, используя инструменты, которые у них были.

Наш Эксперт вспоминает первую версию метода:

//Compute a 32-bit big-endian checksum on arr

Подсказка здесь заключается в том, что это контрольная сумма с обратным порядком байтов. Это можно понять, разобравшись в самом коде, но эта строка комментария была там все время, излагая фундаментальный момент этого метода.

Подводя итог, Endianness относится к порядку, в котором байты появляются в слове. Для чисел это относится к первому байту, являющемуся MSB или LSB.

Большинство современных систем имеют порядок байтов с прямым порядком байтов, но что произойдет, если мы на самом деле окажемся в системе с обратным порядком байтов? Основной цикл метода может быть таким простым, как:

while (z < limit){
  sum += *(uint*)(ptr + z);
  z += 4;
}

Это ровно 32-битная сумма входного массива. Но поскольку мы работаем с прямым порядком байтов, при чтении 4 байтов их порядок меняется на обратный по сравнению с тем, каким он должен быть, чтобы простая сумма работала. Все, что нужно, это прочитать int, поменять местами их байты и просуммировать.

Наконец, вот версия эксперта:

|         Method |  Length |        Mean | Ratio |
|--------------- |-------- |------------:|------:|
|         Junior | 1000000 | 1,785.46 us |  1.00 |
|            Pro | 1000000 |   362.37 us |  0.20 |
|         Senior | 1000000 |   224.11 us |  0.13 |
|         Hacker | 1000000 |   120.26 us |  0.07 |
|         Expert | 1000000 |    79.83 us |  0.04 |

Почти в два раза быстрее, чем у Hacker's, с дополнительным преимуществом читабельного кода.
Это строка, которая решает фундаментальную проблему со всеми другими решениями:

sum += BinaryPrimitives.ReverseEndianness(*(uint*)(ptr + z));

Он меняет порядок байтов для каждого из 4 прочитанных байтов. Это переводится в одну инструкцию ASM.

movbe    r11d, dword ptr [rdx+r10+08H]

Вот определение MOVBE:Переместить данные после замены байтов. Он читает и обменивает байты за один раз. Другой инструкцией для этой цели будет BSWAP, которая работает на месте в регистре. Итак, теперь Эксперт показал нам, что мы можем работать с порядком байтов без добавления дополнительных инструкций.

Эксперт 2.0 с SIMD

SIMD расшифровывается как Single Instruction Multiple Data, и я знаю, что многие из вас, читатели, ожидали увидеть решение SIMD. Ключевым моментом является то, что SIMD-инструкции позволяют нам оперировать большим количеством байтов за раз. Наша контрольная сумма кажется идеальным кандидатом для такой векторизации.

Это примерный график доступности расширений SIMD на процессорах Intel. Мы собираемся сосредоточиться на AVX и AVX2, которые имеют ширину 128 и 256 бит соответственно. Нацеливание на AVX и AVX2 означает нацеливание на любой процессор, выпущенный с 2011 года.

Dotnet представила Hardware Intrinsics еще в dotnet core 3. Подробнее об этом можно прочитать здесь: Hardware Intrinsics в .NET Core — блог .NET (microsoft.com). В настоящее время он поддерживает до AVX2. AVX512 в конечном итоге также должен быть доступен.

Давайте сначала посмотрим на решение AVX:

Звездной функцией здесь является Avx.Shuffle, которая компилируется в vpshufb. Эта инструкция позволяет нам переупорядочивать и маскировать байты за один раз, предоставляя аргумент маски. Мы создали маску, которая меняет порядок следования байтов для каждого 4-байтового блока.

Затем он интерпретирует вектор как вектор unsigned int и добавляет его к вектору-аккумулятору. В ASM это выглядит так:

vmovdqu  xmm2, xmmword ptr [rdx+r9]
vpshufb  xmm2, xmm2, xmmword ptr [reloc @RWD00]
vpaddd   xmm1, xmm1, xmm2
RWD00      dq    0405060700010203h, 0C0D0E0F08090A0Bh

Теперь, используя всего 3 инструкции, мы смогли обработать 16 байт. Как быстро это было?

|    Method |  Length |        Mean | Ratio |
|---------- |-------- |------------:|------:|
|    Junior | 1000000 | 1,774.14 us |  1.00 |
|       Pro | 1000000 |   359.41 us |  0.20 |
|    Senior | 1000000 |   223.97 us |  0.13 |
|    Hacker | 1000000 |   117.98 us |  0.07 |
|    Expert | 1000000 |    78.27 us |  0.04 |
| ExpertAvx | 1000000 |    30.62 us |  0.02 |

Неплохо! Еще одно двукратное улучшение. Теперь, благодаря Expert, примерно в 57 раз быстрее, чем Junior.

Следующим шагом будет переход от векторов шириной 128 к векторам ширины 256. Реализация очень похожа, но есть некоторые ошибки, на которые следует обратить внимание. Например, для большинства операций Vector256 фактически считается двумя полосами шириной 128. Здесь это выходит за рамки — давайте посмотрим, сможем ли мы, наконец, достичь в 100 разбыстрее, на что мы надеялись:

|    Method  |  Length |        Mean | Ratio |
|----------- |-------- |------------:|------:|
|     Junior | 1000000 | 1,774.14 us |  1.00 |
|        Pro | 1000000 |   359.41 us |  0.20 |
|     Senior | 1000000 |   223.97 us |  0.13 |
|     Hacker | 1000000 |   117.98 us |  0.07 |
|     Expert | 1000000 |    78.27 us |  0.04 |
|  ExpertAvx | 1000000 |    30.62 us |  0.02 |
| ExpertAvx2 | 1000000 |    20.83 us |  0.02 |

Примерно в 85 раз быстрее, чем Junior. Почти готово!

Иногда на пути есть стена

Важно отметить, что мы перешли от обработки 563 МБ/с к 48 ГБ/с. При таких скоростях узким местом становится доступ к памяти, а не ЦП.

Давайте остановимся и немного подумаем. Система, которую я использую, имеет память DDR4, которая, согласно Википедии, не должна работать лучше, чем 25 ГБ. Так как же наш тест может работать со скоростью 48 ГБ/с?

Единственная причина, по которой мы наблюдаем такие показатели, заключается в том, что наши тестовые данные полностью помещаются в кэш-память L3 процессора, которая в случае с Intel i7 10875H, которую я здесь использую, имеет 16 МБ. Кэш L3 находится намного ближе к ядрам ЦП и может достигать максимальной скорости 200 ГБ/с, но это сильно зависит от ЦП. Если бы наши данные соответствовали L2 или даже L1, мы увидели бы еще более высокие цифры.

Запуск того же теста с массивом 100 МБ должен выявить узкие места в оперативной памяти, и действительно:

|     Method |    Length |       Mean | Ratio |     Bandwidth |
|----------- |---------- |-----------:|------:|--------------:|
|     Junior | 100000000 | 180.620 ms |  1.00 |   555.55 MB/s |
| ExpertAvx2 | 100000000 |  5.7772 ms |  0.03 | 17320.00 MB/s |

Скорость 17 ГБ/с соответствует характеристикам конкретных модулей памяти, которые у меня есть. Если бы мы читали файл из хранилища, нас бы ограничивала скорость диска, а не оперативная память, не кэш L3 и уж точно не ЦП.

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

Как насчет распараллеливания нескольких ядер?

Я изначально заявил, что это то, что мы не будем исследовать. Теперь причина должна быть очевидна. Помимо узкого места в ОЗУ, кеш L3 распределяется между всеми ядрами типичного ЦП, поэтому в нем нет смысла.

Может ли гений продвинуть нас дальше?

С учетом ограничений — я знаю, что из решений, представленных здесь, в этой статье, можно выжать больше.

Вот репозиторий, который вы можете клонировать и отправить запрос на включение вашей собственной версии:

github.com/israellot/checksum-challenge

Я обновлю эту статью лучшими. Мне любопытно посмотреть, что вы придумаете.