В предыдущих сериях
ThreadPool. async/await #dotnet #threadpool #il_code
yield return #dotnet #il-code
Пародия на замыкания #dotnet #methods #gc
ThreadPool.Intro #dotnet #threadpool
Инструменты анализа эффективности работы приложения. PerfView #performance_analysis #trace #perfview
Сказка про Method as Parameter #dotnet #methods #gc
Сказка про Guid.NewGuid() #os_specific #dotnet #microoptimization
Современные процессоры очень круты. Они таят в себе великое множество секретов и невероятных возможностей. И просто восхитительно, что некоторые из способностей процессоров легко продемонстрировать даже из такого высокоуровневого языка, как C#, буквально за десять строчек кода!
Художественное отступление, шутка на текущую тему. Для того, чтобы узнать самое интересное, читать текст под катом совершенно не обязательно.
Представьте себе ресторан. А в нём цех по готовке пиццы. Только рабочие в нём тупенькие-тупенькие.
Поскольку рабочие тупенькие, то и команды они могут выполнять очень простые. Да и памяти у них никакой нет. Вот архитектор цеха пицц и организовал для них процесс.
Он выстроил рабочих в конвейер. Первый разбирает корявый почерк официанта, какую пиццу нужно приготовить. Второй раскатывает тесто. Третий поливает соусом. Четвертый выкладывает начинку. Пятый ставит в печь.
Ого, дак теперь можно печь одновременно много пицц! Пока первый рабочий разбирает корявый почерк официанта на бумажке со следующим заказом, второй уже раскатал тесто для предыдущей пиццы. А как только третий полил соусом предыдущий круг теста, ему уже подсунули следующий. И так далее. Круто!
Вот только это всё работает до тех пор, пока пиццы в заказах независимые друг от друга. Ведь оказывается, что вся работа конвейера зависит от кривых рук официанта! Представьте себе, что официант накалякал на бумажке «Приготовить пиццу A. Когда пицца А будет готова, начать готовить пиццу Б». Получается, что конвейер оказался заблокирован на результате выполнения всего конвейера для предыдущей пиццы! Пока пицца А не доготовится, пиццу Б даже не начнут раскатывать. Конвейер будет простаивать, а рабочие расслабятся и ничего не будут делать какое-то время.
Вот такой вот печальный официант-driven pizza development.
Как всегда, удобно погружаться в курс дела, начиная с какого-нибудь очень простого и жизненного примера. Пусть у нас есть список чеков. И мы хотим дать пользователю сервис «покажи, сколько мы заработали за сегодня». То есть надо просто просуммировать все числа из чеков. Ну и, пусть чеков будет много. Десятки тысяч. Гипермаркет у нас, Metro какой-нибудь. Иначе неинтересно.
Вот у нас есть набор того, сколько нам заплатили. Просто чиселки в массиве:
private long[] array = new long[16_000];Большинство, наверное, сходу напишет такой код подсчета суммы:
public long EnumerableSum()
{
return array.Sum();
}И большинство будут правы, если мы не гонимся за эффективностью. Но для того, чтобы понять то, чему посвящена статья, давайте всё-таки попробуем написать этот код эффективнее. Мы намеренно будем оптимизировать этот алгоритм шаг за шагом, чтобы была понятна логика этих действий. Чтобы в самом конце прийти к тому, ради чего эта статья затевалась, без каких либо дополнительных вопросов.
Погнали оптимизировать
Говорим НЕТ LINQ
Все слышали, что LINQ очень далёк от «производительности». Поэтому давайте напишем код вот так:
public long SumNaive()
{
long result = 0;
var bound = array.Length;
for (int i = 0; i < bound; i++)
{
result += array[i];
}
return result;
}Напомню, мы пока что просто итеративно идём туда, куда должны прийти. Сравним эти две реализации, чтобы убедиться, что идём мы в верном направлении:
| Method | Mean | Allocated |
|------------------------ |------------:|----------:|
| EnumerableSum | 69.810 us | 32 B |
| SumNaive | 9.387 us | - |Всё верно, LINQ медленный, ещё и объектами в хипе намусорил. В печь его, на дрова для пицц.
Говорим НЕТ safety checks
Давайте подумаем, что в реализации метода SumNaive может мешать нам посчитать сумму очень быстро? Если заглянуть в asm-код, то легко заметить, что из-за того, что это массив, мы на каждое обращение к каждому элементу массива по индексу проверяем, а не вышли ли мы за границы массива.
; Сначала всякая подготовительная работа, которая выполняется один раз
; А внимания достоен только наш основной цикл
M00_L00:
mov r9,rdx ; берем указатель на массив, за ним идёт его длина
cmp r8d,[r9+8] ; проверка i на границу массива
jae short M00_L02 ; идём кидать исключение, если вышли за границы
movsxd r10,r8d
add rax,[r9+r10*8+10] ; само сложение чисел в RAX, где будет результат
inc r8d ; i++
cmp r8d,ecx ; сравнение с границей массива
jl short M00_L00 ; возвращаемся в начала цикла, если i < length
M00_L02:
call CORINFO_HELP_RNGCHKFAIL ; кидаем исключение, вышли за границы массива
int 3Если писать код на unsafe, то этой валидации не будет.
public unsafe long SumNaiveUnsafe()
{
long result = 0;
var length = array.Length;
fixed (long* ptr = array) //Взяли указатель на начало массива
{
var pointer = ptr; // Менять fixed переменную нельзя, поэтому копия
var bound = pointer + length; // Вычислили правую границу
while (pointer != bound) // Пока не достигли правой границы
{
result += *pointer; // Складываем со значением по адресу pointer
pointer += 1; // Сдвигаем указатель на 1 * sizeof(long)
}
}
return result;
}Такой C# код будет компилироваться вот в это:
; Сначала всякая подготовительная работа, которая выполняется один раз
; А внимания достоен только наш основной цикл
M00_L03:
add rax,[rdx] ; Складываем в RAX значение из массива по адресу RDX
add rdx,8 ; К смещению в массиве прибавляем 8 (sizeof(long))
cmp rdx,rcx ; В RCX лежит длина массива, проверяем границы
jne short M00_L03 ; Продолжаем цикл, если не дошли до концаТакой ASM код нам уже нравится. Он не делает абсолютно ничего лишнего. Забенчмаркаем и увидим, что это существенно помогло:
| Method | Mean | Allocated |
|------------------------ |------------:|----------:|
| EnumerableSum | 69.810 us | 32 B |
| SumNaive | 9.387 us | - |
| SumNaiveUnsafe | 5.761 us | - |Отлично. Дальше код будет только unsafe. Но самое главное — в таком ASM коде не осталось никакого мусора. На самом деле, цель была именно в этом :). Нам это будет необходимо для демонстрации того, ради чего это всё затевалось.
Говорим ДА некоторым хитростям
А теперь давайте добавим немного безумия. Как вам вот такая реализация?
public unsafe long SumTrickyUnsafe()
{
long x = 0;
var length = array.Length;
fixed (long* ptr = array)
{
var pointer = ptr;
var bound = pointer + length;
while (pointer != bound)
{
x += *pointer;
x += *(pointer + 1);
x += *(pointer + 2);
x += *(pointer + 3);
pointer += 4;
}
}
return x;
}Легко заметить, что алгоритм неверный. Да, если длина массива не делится на 4, мы посчитаем сумму чисел неверно (или, возможно, словим AccessViolation). И мы должны обработать хвостик в конце обычным способом. Давайте пока пренебрежем этим, ведь массивы огромные, и будем пользоваться массивами с длиной, делящейся на 4. Очевидно, что обработать хвостик, если длина не делится на 4, стоит эпсилон времени. А вот код из-за этого станет менее читабельный.
Также дотошный читатель может заметить, что в этом варианте сложений столько же, сколько и в предыдущем. Зачем тогда так извращаться? А давайте всё равно забенчмаркаем:
| Method | Mean | Allocated |
|------------------------ |----------:|----------:|
| EnumerableSum | 69.810 us | 32 B |
| SumNaive | 9.387 us | - |
| SumNaiveUnsafe | 5.761 us | - |
| SumTrickyUnsafe | 4.423 us | - |Ой! Неожиданно? Этот код на ~30% быстрее. В чем подвох? Давайте для начала посмотрим на ASM код:
; Сначала всякая подготовительная работа, которая выполняется один раз
; А внимания достоен только наш основной цикл
M00_L03:
add rax,[rdx]
add rax,[rdx+8]
add rax,[rdx+10]
add rax,[rdx+18] ; Собственно сами 4 сложения
add rdx,20 ; К смещению в массиве прибавляем 20 (т.е. 32, хекс же)
; 32 = 4 *(sizeof(long))
cmp rdx,rcx ; В RCX лежит длина массива, проверяем границы
jne short M00_L03 ; Продолжаем цикл, если не дошли до концаЗаметим, что этот код очень похож на то, что мы видели в предыдущий раз. Вот прям в точности такой же, только сложений не 1 на итерацию цикла, а сразу 4. Можно было бы подумать «ну конечно, всяких лишних CMP и JNE стало меньше, вот и быстрее!». И в целом это правда. Но есть тут кое что более интересное, осталось совсем чуть-чуть.
Кстати, почему бы компилятору тогда самому не написать очень-очень много строчек ADD?
Действительно, обошлись бы вообще без всяких сравнений и прыжков по меткам.
Так делать в общем случае нельзя. Всё потому, что размер кода на самом деле очень важен. Чем он меньше, тем лучше. И код уж точно не должен быть размера O(N) от размера input'а. Впрочем, такое преобразование кода, которое мы сделали руками, очень умные компиляторы (например, для C++) иногда проворачивают.
Говорим ДА знаниям* устройства процессоров
Приколы на этом не заканчивается. Как вам вот такое?
public unsafe long SumTrickyAndSmartUnsafe()
{
long w = 0;
long x = 0;
long y = 0;
long z = 0;
var length = array.Length;
fixed (long* ptr = array)
{
var pointer = ptr;
var bound = pointer + length;
while (pointer != bound)
{
w += *pointer;
x += *(pointer + 1);
y += *(pointer + 2);
z += *(pointer + 3);
pointer += 4;
}
}
w += x;
y += z;
return w + y;
}Да, складывать будем не в одну переменную X, а в четыре. А потом в конце будем вынуждены ещё и просуммировать их. Казалось бы, мы лишь добавили дополнительных вычислений, лишних переменных. Но раз это здесь, видимо, это ещё быстрее. Вот бенчмарк:
| Method | Mean | Allocated |
|------------------------ |----------:|----------:|
| EnumerableSum | 69.810 us | 32 B |
| SumNaive | 9.387 us | - |
| SumNaiveUnsafe | 5.761 us | - |
| SumTrickyUnsafe | 4.423 us | - |
| SumTrickyAndSmartUnsafe | 3.595 us | - |Catched!
Вот оно! Мы устроили всё это здесь ради того, чтобы добраться до вот этой разницы в ~23% между двумя последними вариантами кода. Давайте изучать ситуацию пристальнее, как обычно, с помощью ASM кода:
; Сначала всякая подготовительная работа, которая выполняется один раз
; А внимания достоен только наш основной цикл
M00_L03:
add rax,[rcx]
add rdx,[rcx+8]
add r8,[rcx+10]
add r9,[rcx+18]
add rcx,20
cmp rcx,r10
jne short M00_L03Код снова очень похож на предыдущий, где мы складывали всё в один регистр RAX. Только сейчас мы складываем это в 4 регистра: RAX, RDX, R8, R9. Это все регистры в x64, кто не знаком с R8 и R9 — это простые целочисленные регистры. А потом, вне цикла, мы вынуждены будем ещё и сложить друг с другом эти 4 регистра.
Погружаемся в устройство процессоров
Что за трюк? Почему складывать в 4 разных регистра быстрее, чем складывать в один регистр? Тут самое время вспомнить про архитектуру современных процессоров.
Вы думаете, что мы написали последовательную, «однопоточную» (если можно так выразиться) программу? Процессор так не думает.
Давайте для начала вспомним pipelining. Есть инструкции, на обработку которых процессор тратит несколько циклов. Вот только процессор может не ждать, пока такая инструкция завершится целиком, чтобы начать обрабатывать следующую инструкцию.
Процессор конвейерит и параллелит исполнение инструкций
Есть, например, инструкция MUL, умножение. Её latency = 3. То есть, чтобы выполнить умножение, нужно затратить 3 цикла процессора. Но давайте представим, что мы умножаем три раза 6 совершенно независимых чисел. A = A*B, C = C*D,E = E*F.
На первом цикле начнется выполнение
A*B.На втором цикле начнется выполнение
C*D, аA*Bбудет на втором шаге.На третьем цикле начнется выполнение
E*F,C*Dбудет на втором шаге, аA*Bбудет на завершающем третьем.На четвертом цикле
E*Fбудет на втором шаге умножения,C*Dна завершающем.На пятом цикле
E*Fбудет на завершающем шаге.
Итого, мы на 3 умножения потратили не 9 циклов, а всего 5. Потому что все 3 операции были в цепочке независимых инструкций. Но как только мы свяжем их друг с другом через какую-нибудь переменную (регистр), так возможность pipelining'а мгновенно исчезает. Так, умножения вида A = A*B, A = A*C и A = A*D образуют цепочку зависимых операций. Из-за того, что для выполнения каждого следующего умножения надо знать значение регистра A. А значение регистра A как раз в предыдущей инструкции и считается. И потому каждое умножение будет занимать 3 цикла не пуская никого в pipeline.
А сложения исполняются буквально одновременно
Вернёмся к нашим сложениям. Они чуть интереснее. Если для умножения у каждого ядра есть свой единственный mul-capable unit, то для сложения их, обычно, четыре! А latency одного сложения = 1. Это значит, что если все 4 сложения независимы и образуют independent chain, то все 4 сложения могут выполниться за 1 цикл!
Именно потому наш первый вариант с реализацией четырех сложений подряд оказался медленнее, чем второй. Потому что в первом варианте мы всё складывали в одну и ту же переменную. И в ASM коде соответственно было так же — мы складывали всё в один регистр RAX. А значит на 4 последовательных сложения потратили 4 процессорных цикла. А во втором варианте 4 сложения делались в разные переменные. И в ASM коде 4 сложения делались в 4 разных регистра соответственно. И все 4 сложения выполнились за 1 цикл.
Если что, то не только однотипные инструкции подвергаются конвейеризации. Существует множество других комбинаций разных инструкций, которые, при отсутствии зависимости друг от друга, могут выполняться в конвейере. Но не нужно путать конвейеризацию и параллельное исполнение однотипных инструкций!
Вот мы и вывели Reciprocal throughput
Величина, описывающая это свойство инструкций, называется Reciprocal throughput. Есть замечательный ресурс от Angner Fog, где этой величине дают хорошее определение:
Reciprocal throughput: the maximum number of instructions of the same kind that can be executed per clock cycle when the operands of each instruction are independent of the preceding instructions.
То есть для инструкции ADD latency = 1, а reciprocal throughput = 0.25. Это значит, что 1 / 0.25 инструкции могут работать «параллельно». То есть 4. А для инструкции MUL latency = 3, а reciprocal throughput = 1. Это значит, что мы можем исполнять 3 операции MUL одновременно, вот только каждая следующая будет начинать исполняться через 1 цикл после предыдущей.
В таблицах, ссылку на которые я дал выше, можно найти, какие инструкции обладают такой фичей и с каким reciprocal throughput. В разрезе по архитектурам процессоров. Да, не все инструкции так умеют.
Бонус
Если что, складывать числа в массиве нужно всё-таки не так. Для этого есть векторные инструкции (SIMD).
Без всяких заморочек, какая-то реализация в лоб.
public unsafe long SumSimd()
{
var vectorSum = Vector<long>.Zero;
var vectorSize = Vector<long>.Count;
var length = array.Length;
fixed (long* ptr = array)
{
var pointer = ptr;
var bound = pointer + length;
while (pointer != bound)
{
vectorSum += Unsafe.Read<Vector<long>>(pointer);
pointer += vectorSize;
}
}
return Vector.Dot(vectorSum, Vector<long>.One);
}По-хорошему, тут ещё нужно обрабатывать хвостик, если массив не делится на размер вектора. Но для простоты я опустил это, в нашем бенчмарке размер массива = 16000 long'ов, что делится нацело даже на 512-битный регистр. В предыдущих реализациях, где производилось по 4 сложения на одну итерацию цикла, мы тоже опирались на то, что размер массива делится на 4. В настоящем коде там тоже пришлось бы обрабатывать хвостики.
Для тех, кому очень интересно, вот ASM код:
M00_L03:
vmovupd ymm1,[rax]
vpaddq ymm0,ymm0,ymm1
add rax,20
cmp rax,rdx
jne short M00_L03Вот результат бенчмарка:
| Method | Mean | Allocated |
|------------------------ |----------:|----------:|
| EnumerableSum | 69.810 us | 32 B |
| SumNaive | 9.387 us | - |
| SumNaiveUnsafe | 5.761 us | - |
| SumTrickyUnsafe | 4.423 us | - |
| SumTrickyAndSmartUnsafe | 3.595 us | - |
| SumSimd | 1.998 us | - |И для полноты картины, скриншот полного бенчмарка. Важно отметить, что мы бенчмаркали на размере массива 16000 long'ов, что легко умещается в кеш процессора. Если взять массив на сотни мегабайт, пропорции длительности работы методов будут немного отличаться, но смысл останется тот же самый. Можете попробовать сделать это сами ;)
Заключение
Где могут применяться знания о reciprocal throughput? Действительно, тема довольно узкая. Ну, как минимум, эта способность процессоров вовсю эксплуатируется компиляторами. И иногда вы пользуетесь этой возможностью процессоров, даже не подозревая этого. Также, очевидно, изредка можно встретить ситуации, когда нужно выжать максимум производительности из каких-то алгоритмов. Например, когда такие вычисления составляют существенную часть всей работы приложения. Чаще такое встречается где-нибудь в геометрии, географии, машинном обучении (там, правда, есть и видеокарты для такого), научных и статистических вычислениях, различных моделированиях каких-нибудь процессов.
А вообще, я считаю, что в принципе очень полезно знать, как оно устроено внутри. Понимать, почему те или иные манипуляции с кодом, пусть и очень высокоуровневым (как C#), влияют на итоговый результат и качество работы программы.
А ещё, смотрите как красиво вышло. Тривиальной программой на таком языке, как C#, можно демонстрировать буквально самые низлежащие принципы работы современных процессоров. Это был отдельный небольшой вызов лично для меня.
Комментарии (38)
gotoxy
30.05.2023 09:05+1Байка о том, что при
(for i = 0; i < array.Length; i++)(array.Length непосредственно в for'е) компилятор отказывается от проверок выхода за границы - это таки байка?
KvanTTT
30.05.2023 09:05+3Нет, но по какой-то причине код в статье написан неоптимально и усложненно, с введением лишней переменной:
var bound = array.Length; for (int i = 0; i < bound; i++)Это и препятствует исполнению указанной оптимизации.
dyadyaSerezha
30.05.2023 09:05Специально так написано. Чтобы разница в следующей оптимизации была.
И кстати, не показана самая финальная оптимизация - параллельное выполнение частичных векторных сложений на разных ядра, например, используя Parallel.For().
deniaa Автор
30.05.2023 09:05+2Я старался явно и многократно делать акцент на том, что цель - продемонстрировать reciprocal throughput. Ну и показать новичкам такую особенность процессора. Жаль, что оставить фокус не цели статьи не получилось.
А цели "написать самый эффективный способ сложить 16_000 long'ов из массива на C# под .Net 6" не ставилось, хотя, выглядит как забавная задача :)
deniaa Автор
30.05.2023 09:05Код:
[Benchmark] public long SumNaive() { long result = 0; var bound = array.Length; for (int i = 0; i < bound; i++) { result += array[i]; } return result; } [Benchmark] public long SumNaive2() { long result = 0; for (var i = 0; i < array.Length; i++) { result += array[i]; } return result; }ASM:
## .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2 ```assembly ; benchmarks.ReciprocalThroughput.SumNaive() sub rsp,28 xor eax,eax mov rdx,[rcx+8] mov ecx,[rdx+8] xor r8d,r8d test ecx,ecx jle short M00_L01 nop dword ptr [rax] nop dword ptr [rax+rax] M00_L00: mov r9,rdx cmp r8d,[r9+8] jae short M00_L02 movsxd r10,r8d add rax,[r9+r10*8+10] inc r8d cmp r8d,ecx jl short M00_L00 M00_L01: add rsp,28 ret M00_L02: call CORINFO_HELP_RNGCHKFAIL int 3 ; Total bytes of code 68 ``` ## .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2 ```assembly ; benchmarks.ReciprocalThroughput.SumNaive2() sub rsp,28 xor eax,eax xor edx,edx mov rcx,[rcx+8] cmp dword ptr [rcx+8],0 jle short M00_L01 nop dword ptr [rax] nop dword ptr [rax] M00_L00: mov r8,rcx cmp edx,[r8+8] jae short M00_L02 movsxd r9,edx add rax,[r8+r9*8+10] inc edx cmp [rcx+8],edx jg short M00_L00 M00_L01: add rsp,28 ret M00_L02: call CORINFO_HELP_RNGCHKFAIL int 3 ; Total bytes of code 67 ```Бенчмарк:
// * Summary * BenchmarkDotNet=v0.13.4, OS=Windows 10 (10.0.19045.2965) Intel Core i7-4771 CPU 3.50GHz (Haswell), 1 CPU, 8 logical and 4 physical cores .NET SDK=7.0.105 [Host] : .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2 .Net 6.0 : .NET 6.0.16 (6.0.1623.17311), X64 RyuJIT AVX2 Job=.Net 6.0 Runtime=.NET 6.0 | Method | Mean | Code Size | |---------- |----------:|----------:| | SumNaive | 9.347 us | 68 B | | SumNaive2 | 9.465 us | 67 B |
onyxmaster
30.05.2023 09:05+1Нет, не байка.
onyxmaster
30.05.2023 09:05Автору минуса не хотелось спорить? Я ещё раз скажу что не байка, можно и сюда минус поставить, вместо диалога :) Там выше даже примеры есть, подтверждающие сказанное мной :)
ARad
30.05.2023 09:05Если идти до конца то надо ещё запараллелить https://dotnetfiddle.net/rXS8mF
Заодно переделал на Span, и убрал unsafe.
Скорость не проверял, но надеюсь будет быстрее...public static long SumSimdParallel(long[] array) { var degreeOfParallelism = Math.Max(Vector<long>.Count, (int)BitOperations.RoundUpToPowerOf2((uint)Environment.ProcessorCount)); var sums = new long[degreeOfParallelism]; var len = array.Length / degreeOfParallelism; //Console.WriteLine($"ProcessorCount = {Environment.ProcessorCount}"); //Console.WriteLine($"degreeOfParallelism = {degreeOfParallelism}"); //Console.WriteLine($"len = {len}"); //Console.WriteLine($"Count = {Vector<long>.Count}"); Parallel.For(0, degreeOfParallelism, idx => { var vectorSize = Vector<long>.Count; var span = array.AsSpan(idx * len, len); var vectorSum = new Vector<long>(span); span = span.Slice(vectorSize); while (span.Length >= vectorSize) { vectorSum += new Vector<long>(span); span = span.Slice(vectorSize); } sums[idx] = Vector.Dot(vectorSum, Vector<long>.One); }); return SumSimd(sums); }
LordDarklight
30.05.2023 09:05Добавил примитивный замер
// See https://habr.com/ru/companies/skbkontur/articles/737858/ using System; using System.Linq; using System.Numerics; using System.Threading.Tasks; public class Program { public static void Main() { Console.WriteLine("Hello"); var array = new long[16_000]; { var random = new Random(); for(var i = 0; i < array.Length; i++) array[i] = random.Next(100); } var t = DateTime.Now.Ticks; Console.WriteLine($"Sum = {array.Sum()} for {TimeSpan.FromTicks(DateTime.Now.Ticks- t).TotalMilliseconds} ms"); t = DateTime.Now.Ticks; Console.WriteLine($"SumSimd = {SumSimd(array)} for {TimeSpan.FromTicks(DateTime.Now.Ticks- t).TotalMilliseconds} ms"); t = DateTime.Now.Ticks; Console.WriteLine($"SumSimdParallel = {SumSimdParallel(array)} for {TimeSpan.FromTicks(DateTime.Now.Ticks- t).TotalMilliseconds} ms"); Console.WriteLine("Goodbye"); } public static long SumSimd(long[] array) { var vectorSize = Vector<long>.Count; var vectorSum = new Vector<long>(array); var span = array.AsSpan(vectorSize); while (span.Length >= vectorSize) { vectorSum += new Vector<long>(span); span = span.Slice(vectorSize); } return Vector.Dot(vectorSum, Vector<long>.One); } public static long SumSimdParallel(long[] array) { var degreeOfParallelism = Math.Max(Vector<long>.Count, (int)BitOperations.RoundUpToPowerOf2((uint)Environment.ProcessorCount)); var sums = new long[degreeOfParallelism]; var len = array.Length / degreeOfParallelism; //Console.WriteLine($"ProcessorCount = {Environment.ProcessorCount}"); //Console.WriteLine($"degreeOfParallelism = {degreeOfParallelism}"); //Console.WriteLine($"len = {len}"); //Console.WriteLine($"Count = {Vector<long>.Count}"); Parallel.For(0, degreeOfParallelism, idx => { var vectorSize = Vector<long>.Count; var span = array.AsSpan(idx * len, len); var vectorSum = new Vector<long>(span); span = span.Slice(vectorSize); while (span.Length >= vectorSize) { vectorSum += new Vector<long>(span); span = span.Slice(vectorSize); } sums[idx] = Vector.Dot(vectorSum, Vector<long>.One); }); return SumSimd(sums); } }Вот результат dotnetfiddle
Hello
Sum = 788052 for 7.5949 ms
SumSimd = 788052 for 2.7317 ms
SumSimdParallel = 788052 for 9.5434 ms
GoodbyeВаш вариант даже медленнее чем Linq
Попробовал на своей машине в NET 7 Release x86 64bit Windows 11 (VS 17.6.1): 8 потоков - тоже самое
Hello
Sum = 795477 for 21,0062 ms
SumSimd = 795477 for 3,8187 ms
SumSimdParallel = 795477 for 74,9511 sms
GoodbyeУвеличил количество элементов на 3 порядка (16 000 000)
Hello
Sum = 791918905 for 64,1259 ms
SumSimd = 791918905 for 17,5787 ms
SumSimdParallel = 791918905 for 181,2268 ms
GoodbyeПараллельность так же не дала успеха
ARad
30.05.2023 09:05Добавил время с прогревом 100 раз... https://dotnetfiddle.net/rXS8mF
У меня другие результаты:Sum = 788642 for 3,968,293 ticks SumSimd = 788642 for 33,301,980 ticks SumSimdParallel = 788642 for 13,453,915 ticksLinq самый быстрый и в 10 раз быстрее чем с инструкциями, параллельный примерно в 2 - 2,5 раза быстрее его же. Это в фидлере на NET 7.
LordDarklight
30.05.2023 09:05Вот тебе и ручная оптимизация - интересно что же там за ассемблерный код
У меня там (для 16 000) перевёл в ms раз уж начала писать замеры в миллисекундах:
Hello
Sum = 786064 for 402 ms
SumSimd = 786064 for 3,396 ms
SumSimdParallel = 786064 for 1,595 ms
Goodbye(для 1 600 000):
Hello
Sum = 79305705 for 8,093 ms
SumSimd = 79305705 for 62,382 ms
SumSimdParallel = 79305705 for 20,821 ms
Goodbye(для 16 000 000) на своём компьютере:
Hello
Sum = 791906725 for 80 ms
SumSimd = 791906725 for 22 ms
SumSimdParallel = 791906725 for 15 ms
GoodbyeСовершенно неожиданно!
Хотя.... это же JIT- про который все забыли ;-) при первом запуске функции идёт JIT-компиляция кода - она съедает большую часть времени - даже на больших массивах (вот это странно) - И ТУТ НЕ НУЖЕН 100-КРАТНЫЙ ПРОГРЕ (ЭТО НЕ JAVA ИЛИ JAVASCRIPT) ТУТ ДОСТАТОЧНО ВТОРОГО ЗАПУСКА (repeat = 2)
Хотя.... вот незадача провёл я ещё несколько тестов на своём компьютере (замер модифицировал выделено число повторов отдельно, число попыток оставлено везде 100, меняется лишь число элементов и число попыток прогрева)
16 000 0 повторов прогрева:
Hello
Sum = 792096 for 15 ms
SumSimd = 792096 for 20 ms
SumSimdParallel = 792096 for 111 ms
Goodbye1 600 000 0 повторов прогрева
Hello
Sum = 79218109 for 354 ms
SumSimd = 79218109 for 128 ms
SumSimdParallel = 79218109 for 210 ms
Goodbye16 000 000 0 повторов прогрева:
Hello
Sum = 792095353 for 2 397 ms
SumSimd = 792095353 for 1 111 ms
SumSimdParallel = 792095353 for 925 ms
Goodbye16 000 2 повтора:
Hello
Sum = 791278 for 5 ms
SumSimd = 791278 for 12 ms
SumSimdParallel = 791278 for 91 ms
Goodbye1 600 000 2 повтора:
Hello
Sum = 79217015 for 324 ms
SumSimd = 79217015 for 126 ms
SumSimdParallel = 79217015 for 129 ms
Goodbye16 000 000 2 повтора:
Hello
Sum = 791862400 for 2 396 ms
SumSimd = 791862400 for 1 155 ms
SumSimdParallel = 791862400 for 699 ms
Goodbye16 000 100 повторов:
Hello
Sum = 795938 for 6 ms
SumSimd = 795938 for 11 ms
SumSimdParallel = 795938 for 62 ms
Goodbye1 600 000 100 повторов:
Hello
Sum = 79240536 for 124 ms
SumSimd = 79240536 for 117 ms
SumSimdParallel = 79240536 for 99 ms
Goodbye16 000 000 100 повторов:
Hello
Sum = 791975144 for 1 145 ms
SumSimd = 791975144 for 886 ms
SumSimdParallel = 791975144 for 631 ms
GoodbyeДля разных случаев лидеры разные
SumSimdParallel лидер: при большом количестве элементов (в этот раз независимо от прогрева)
SumSimd лидер на средне числе элементов (но не всегда, скорее это результат погрешности, так что SumSimdParallel не отстаёт) : середняк - очень чувствителен к прогреву
Sum лидер: на малом числе элементов (тоже не зависимо от прогрева)
Так что всё очень не однозначно (число элементов перехода лидера может быть очень различным для разных систем - думаю в первую очередь зависит от работы процессора со своим кешем и его объёмом)
thevlad
30.05.2023 09:05Прямо магия какаято, интересно как она устроена. Если в linq sum однопоточка, то она в принципе не может быть, зняАчимо быстрее simd. Плюсовый компилятор выплюнул примерно такой же код.
dyadyaSerezha
30.05.2023 09:05Параллельное выполнение обязано создавать потоки, а это очень затратная операция. Вот если бы вынести их создание за измерение...
LordDarklight
30.05.2023 09:05Параллельное выполнение через LINQ берёт потоки из пула потоков - это очень быстро
dyadyaSerezha
30.05.2023 09:05А пул запускается до первого вызова Link?
LordDarklight
30.05.2023 09:05Если я правильно понимаю - пул системный. Но в любом случае он запускается до запуска теста бенчмарка
LordDarklight
30.05.2023 09:05+2насколько я знаю в NET 7 в LINQ применяют векторные инструкции (вероятно не всегда, а начиная с некоторого объёма данных) - на эту тему на хабре статья была - на вскидку нашёл эту, но кажется ещё была - а, вот ещё
Но всё же ручная векторная оптимизация на больших коллекциях у меня вот всё-таки быстрее - интересно как у других
thevlad
30.05.2023 09:05+3Тот же изначальный код на плюсах, если попросить -O3 и -mavx2: https://godbolt.org/z/nEKodK8c1
unsigned long sum_array(unsigned long* array, unsigned long size) { unsigned long sum = 0; for (unsigned long i = 0; i < size; ++i) sum += array[i]; return sum; }Сразу генерится, в такой внутренний цикл:
.L4: vpaddq ymm0, ymm0, YMMWORD PTR [rax] add rax, 32 cmp rax, rdx jne .L4и тут вряд ли что-то можно улучшить.
LittleAlien
30.05.2023 09:05+1Clang не согласен, он делает ещё развёртку SIMD-кода.
https://gcc.godbolt.org/z/3M8W81rMv
Можно добавить к статье, что сказанное про множественные скалярные арифметические модули справедливо и для SIMD, у Intel сейчас 2 * 256 бит, у AMD 4 * 128 бит. Получается, развёртка Clang 4 * 256 избыточна, ну вот такая у него "широкая душа", любит развернуть с настройками по умолчанию. Может, в расчёте на будущие процессоры.thevlad
30.05.2023 09:05Ради интереса сделал бенчмарк: https://gist.github.com/xmvlad/726961dfefe59e9fc0c77d4cd3795eed
У меня на Zen3 разница между gcc и clang в пределах погрешности(может быть максимум 5% шланг добрасывает).
LittleAlien
30.05.2023 09:05Вы же там ниже пишете, что в память упирается - ну правильно, 40 мб.
Автор статьи специально на небольшом размере тестировал, чтобы помещалось в самый быстрый кэш. Можно гонять тест коротких данных много раз.thevlad
30.05.2023 09:05Кэш L3 сопоставимый - 32МБ, плюсом здесь линейный паттерн доступа, то есть гарантированно должен срабатывать префетч. Но я попробовал уменьшить размер массива в десять раз, и добавить повторов, результат все те-же +5%.
По поводу "памяти", имелось как раз в виду производительность кэша, так как инструкция одно тактовая, то он мог просто больше 32 байт, за этот такт "не прокачивать", даже если делать сложение на разных параллельно работающих портах.
LittleAlien
30.05.2023 09:05Мне удалось выжать почти 2 раза (1.8), но это с минимальным размером массива (4096) и с двумя внешними циклами, один просто крутит 2000000 итераций, другой выбирает минимальное время из 20 попыток. Clang 14 / gcc 12.
В реальных условиях наверное чаще будет 5%, чем 2 раза.thevlad
30.05.2023 09:05Интересно, можете куда нибуть выложить исходник? (pastebin/gist) мне пришлось немного помучаться, чтобы вызов был внутри цикла, так как иначе результат "оптимизировался" чисто математически (накапливаемая сумма или чтото в этом духе)
LittleAlien
30.05.2023 09:05Только я вставлял в сишный проект, поэтому переправил всё с плюсов на чистый Си. Но вряд ли это влияет. И я тоже ожидал, что будет мухлевать с итерациями, но нет, время явно зависит от Cycles.
код
#include <windows.h> #include <stdio.h> #include <stdlib.h> unsigned long sum_array(unsigned long* array, unsigned long size) { unsigned long sum = 0; for (unsigned long i = 0; i < size; ++i) sum += array[i]; return sum; } int main() { const unsigned long n = 4096; const Cycles = 2000000; const Cycles2 = 20; unsigned long array[n]; srand(42); for (unsigned long i = 0; i < n; ++i) array[i] = rand(); LARGE_INTEGER frequency; LARGE_INTEGER t1, t2, t3, t4; QueryPerformanceFrequency(&frequency); unsigned long s = 0; double minTime = 100000000; for (int m = 0; m < Cycles2; m++) { QueryPerformanceCounter(&t1); for (int i = 0; i < Cycles; i++) { s = sum_array(array, n); } QueryPerformanceCounter(&t2); double elapsedTime=(double)(t2.QuadPart-t1.QuadPart)/frequency.QuadPart; if (elapsedTime < minTime) minTime = elapsedTime; } printf("sum: %lu\n", s); printf("microseconds: %.5f seconds\n", minTime); return 0; }thevlad
30.05.2023 09:05+2Да, шланг грамотно раскочегарил, развернул цикл и складывал в четыре независимых ymm регистра, на небольших массивах, в 2 раза ускоряется. (хотя avx2 порта 4, но load unit только 2)
ToSHiC
30.05.2023 09:05Если в процессоре 2 блока, которые умеют делать vpaddq - то есть смысл и анролл в цикле сделать, чтобы в разные регистры записывался результат и можно было это суммирование делать параллельно.
Вообще, я удивлён, что в статье нету какой-то похожей картинки:
https://upload.wikimedia.org/wikipedia/commons/c/c3/Skylake_architecture_diagram.pngLittleAlien
30.05.2023 09:05Получается, в Skylake уже 3 модуля для векторного сложения (Int Vect ALU), так что Clang где-то и прав.
Я брал информацию по вычислительным модулям у Агнера Фога, может он намеренно упоминал только "настоящие" модули с умножением и FMA:
https://www.agner.org/optimize/blog/read.php?i=838
LordDarklight
30.05.2023 09:05ну на NET 7 тоже есть vpaddq (Avx2.Add) но надо руками применять (для битных векторов) - может в бонусном коде так оно и делается - к сожалению, автор не привёл итоговый ассемблерный код
deniaa Автор
30.05.2023 09:05+3Спасибо, джентльмены, за интересные комментарии в этой ветке. Не хотел прерывать.
Действительно, почему бы и не добавить ассемблерный код, в который превратилась C#-реализация на SIMD:
M00_L03: vmovupd ymm1,[rax] vpaddq ymm0,ymm0,ymm1 add rax,20 cmp rax,rdx jne short M00_L03UPD: В статью тоже добавил.
LordDarklight
30.05.2023 09:05интересно бы анализ сравнения с эталонным кодом на C++ - всё-таки отличия есть
KvanTTT
30.05.2023 09:05+1Как всегда, удобно погружаться в курс дела, начиная с какого-нибудь очень простого и жизненного примера.
К сожалению, пример не особо жизненный — оптимизировать такие места как правило не имеет смысла, особенно с таким сильным усложнением кода. Максимум можно остановиться на первой оптимизации, которая, кстати, дает наибольший прирост.
Всё верно, LINQ медленный, ещё и объектами в хипе намусорил. В печь его, на дрова для пицц.
Есть подозрение, что конкретно в этом случае LINQ медленный из-за интерфейса в сигнатуре метода, и компилятор почему-то не смог нормально это соптимизировать. Возможно для других случаев деградации не будет или она будет не такой сильной.
vkomen
30.05.2023 09:05А вроде никто не написал такой трюк - если учитывать размер строки кэша, которая при обращении к памяти выбирается целиком, то может оказаться, что преобразование кода в два вложенных цикла, из которых внутренний будет перебирать данные, целиком помещаемые в такую строку, ускорит еще?
DBalashov
30.05.2023 09:05И почему-то никто не вспомнил про foreach, который для массивов не использует итератор и быстрее for.
LordDarklight
Вот пусть компиляторы этой оптимизацией и занимаются (и развиваются для всё большей и большей оптимизации). Оставьте такую глубокую оптимизацию человеку строго только для случаев когда такая оптимизация жизненно необходима (и такая необходимость уже явно определена и утверждена "свыше" по результатам бенчмарков с менее глубокой оптимизацией).
Ну а вторым способом даже глубокой явной оптимизации могут стать нейросети а-ля ChaptGPT - если какой-то код надо будет явно с оптимизировать - то можно было бы скармливать менее оптимальный код нейронке - а та уже преобразовывала его в более оптимальный и прогоняла тесты (чтобы убедиться, что ничего не сломалось). Но, в большинстве случаев, надо стремиться чтобы такую оптимизацию в большинстве случаев неявно выполняли компиляторы.
А чтобы компиляторы эффективнее развивались и могли эффективно оптимизировать выходной код - нужно больше развивать идею компиляции через единый промежуточный язык .
А то и даже целых два слоя промежуточных языков, между которыми можно разместить дополнительный оптимизатор - второй слой уже платформенно-зависимый, но ещё не конечный - тут я намекаю на то, приложение может компилироваться при установке под определённую платформу (среду исполнения) с оптимизацией под неё но оставаясь всё ещё на промежуточном ЯП (просто более низкоуровневом), который уже будет компилироваться при исполнении (с кешированием на будущие старты) с продолжающимся сбором статистики исполнения и возможностью динамически перекомпилироваться иначе.
Ну а первый слой промежуточного ЯП при этом может оставаться достаточно высокоуровневым, содержащим много метаданных и высокоуровневых инструкций. Он хорошо для этапа слияния библиотек, написанных в т.ч. на разных исходных ЯП, друг с другом - т.е. это по сути продвинутая линковка.
Вот тогда можно будет куда больше внимания уделять уже более-менее стандартизированным компиляторам из промежуточного ЯП - не распыляясь на кучу исходных языков программирования, с толков вкладывая ресурсы в разработку таких компиляторов, зная что эти вложения будут полезны очень большому числу потребителей (и программистам) и очень надолго, в т.ч. для будущих ЯП. Ну и производить анализ и компиляцию единого стандартизированного упрощённого промежуточного ЯП куда проще - чем плясать от исходников на высокоуровневых языках программирования.
Да да - я всецело повторяю идеологию заложенную Крисом Латтнером в LLVM и перешедшую в WASM и MLIR - надо продолжать её развитие