Комментарии 39
Вот пусть компиляторы этой оптимизацией и занимаются (и развиваются для всё большей и большей оптимизации). Оставьте такую глубокую оптимизацию человеку строго только для случаев когда такая оптимизация жизненно необходима (и такая необходимость уже явно определена и утверждена "свыше" по результатам бенчмарков с менее глубокой оптимизацией).
Ну а вторым способом даже глубокой явной оптимизации могут стать нейросети а-ля ChaptGPT - если какой-то код надо будет явно с оптимизировать - то можно было бы скармливать менее оптимальный код нейронке - а та уже преобразовывала его в более оптимальный и прогоняла тесты (чтобы убедиться, что ничего не сломалось). Но, в большинстве случаев, надо стремиться чтобы такую оптимизацию в большинстве случаев неявно выполняли компиляторы.
А чтобы компиляторы эффективнее развивались и могли эффективно оптимизировать выходной код - нужно больше развивать идею компиляции через единый промежуточный язык .
А то и даже целых два слоя промежуточных языков, между которыми можно разместить дополнительный оптимизатор - второй слой уже платформенно-зависимый, но ещё не конечный - тут я намекаю на то, приложение может компилироваться при установке под определённую платформу (среду исполнения) с оптимизацией под неё но оставаясь всё ещё на промежуточном ЯП (просто более низкоуровневом), который уже будет компилироваться при исполнении (с кешированием на будущие старты) с продолжающимся сбором статистики исполнения и возможностью динамически перекомпилироваться иначе.
Ну а первый слой промежуточного ЯП при этом может оставаться достаточно высокоуровневым, содержащим много метаданных и высокоуровневых инструкций. Он хорошо для этапа слияния библиотек, написанных в т.ч. на разных исходных ЯП, друг с другом - т.е. это по сути продвинутая линковка.
Вот тогда можно будет куда больше внимания уделять уже более-менее стандартизированным компиляторам из промежуточного ЯП - не распыляясь на кучу исходных языков программирования, с толков вкладывая ресурсы в разработку таких компиляторов, зная что эти вложения будут полезны очень большому числу потребителей (и программистам) и очень надолго, в т.ч. для будущих ЯП. Ну и производить анализ и компиляцию единого стандартизированного упрощённого промежуточного ЯП куда проще - чем плясать от исходников на высокоуровневых языках программирования.
Да да - я всецело повторяю идеологию заложенную Крисом Латтнером в LLVM и перешедшую в WASM и MLIR - надо продолжать её развитие
Байка о том, что при(for i = 0; i < array.Length; i++)
(array.Length непосредственно в for'е) компилятор отказывается от проверок выхода за границы - это таки байка?
Нет, но по какой-то причине код в статье написан неоптимально и усложненно, с введением лишней переменной:
var bound = array.Length;
for (int i = 0; i < bound; i++)
Это и препятствует исполнению указанной оптимизации.
Специально так написано. Чтобы разница в следующей оптимизации была.
И кстати, не показана самая финальная оптимизация - параллельное выполнение частичных векторных сложений на разных ядра, например, используя Parallel.For().
ниже в комментария уже написали и даже тесты привели
Я старался явно и многократно делать акцент на том, что цель - продемонстрировать reciprocal throughput. Ну и показать новичкам такую особенность процессора. Жаль, что оставить фокус не цели статьи не получилось.
А цели "написать самый эффективный способ сложить 16_000 long'ов из массива на C# под .Net 6" не ставилось, хотя, выглядит как забавная задача :)
Код:
[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 |
Нет, не байка.
Если идти до конца то надо ещё запараллелить 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);
}
Добавил примитивный замер
// 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
Параллельность так же не дала успеха
Добавил время с прогревом 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 ticks
Linq самый быстрый и в 10 раз быстрее чем с инструкциями, параллельный примерно в 2 - 2,5 раза быстрее его же. Это в фидлере на NET 7.
Вот тебе и ручная оптимизация - интересно что же там за ассемблерный код
У меня там (для 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
Goodbye
1 600 000 0 повторов прогрева
Hello
Sum = 79218109 for 354 ms
SumSimd = 79218109 for 128 ms
SumSimdParallel = 79218109 for 210 ms
Goodbye
16 000 000 0 повторов прогрева:
Hello
Sum = 792095353 for 2 397 ms
SumSimd = 792095353 for 1 111 ms
SumSimdParallel = 792095353 for 925 ms
Goodbye
16 000 2 повтора:
Hello
Sum = 791278 for 5 ms
SumSimd = 791278 for 12 ms
SumSimdParallel = 791278 for 91 ms
Goodbye
1 600 000 2 повтора:
Hello
Sum = 79217015 for 324 ms
SumSimd = 79217015 for 126 ms
SumSimdParallel = 79217015 for 129 ms
Goodbye
16 000 000 2 повтора:
Hello
Sum = 791862400 for 2 396 ms
SumSimd = 791862400 for 1 155 ms
SumSimdParallel = 791862400 for 699 ms
Goodbye
16 000 100 повторов:
Hello
Sum = 795938 for 6 ms
SumSimd = 795938 for 11 ms
SumSimdParallel = 795938 for 62 ms
Goodbye
1 600 000 100 повторов:
Hello
Sum = 79240536 for 124 ms
SumSimd = 79240536 for 117 ms
SumSimdParallel = 79240536 for 99 ms
Goodbye
16 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 лидер: на малом числе элементов (тоже не зависимо от прогрева)
Так что всё очень не однозначно (число элементов перехода лидера может быть очень различным для разных систем - думаю в первую очередь зависит от работы процессора со своим кешем и его объёмом)
Прямо магия какаято, интересно как она устроена. Если в linq sum однопоточка, то она в принципе не может быть, зняАчимо быстрее simd. Плюсовый компилятор выплюнул примерно такой же код.
Параллельное выполнение обязано создавать потоки, а это очень затратная операция. Вот если бы вынести их создание за измерение...
насколько я знаю в NET 7 в LINQ применяют векторные инструкции (вероятно не всегда, а начиная с некоторого объёма данных) - на эту тему на хабре статья была - на вскидку нашёл эту, но кажется ещё была - а, вот ещё
Но всё же ручная векторная оптимизация на больших коллекциях у меня вот всё-таки быстрее - интересно как у других
Тот же изначальный код на плюсах, если попросить -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
и тут вряд ли что-то можно улучшить.
Clang не согласен, он делает ещё развёртку SIMD-кода.
https://gcc.godbolt.org/z/3M8W81rMv
Можно добавить к статье, что сказанное про множественные скалярные арифметические модули справедливо и для SIMD, у Intel сейчас 2 * 256 бит, у AMD 4 * 128 бит. Получается, развёртка Clang 4 * 256 избыточна, ну вот такая у него "широкая душа", любит развернуть с настройками по умолчанию. Может, в расчёте на будущие процессоры.
Ради интереса сделал бенчмарк: https://gist.github.com/xmvlad/726961dfefe59e9fc0c77d4cd3795eed
У меня на Zen3 разница между gcc и clang в пределах погрешности(может быть максимум 5% шланг добрасывает).
Вы же там ниже пишете, что в память упирается - ну правильно, 40 мб.
Автор статьи специально на небольшом размере тестировал, чтобы помещалось в самый быстрый кэш. Можно гонять тест коротких данных много раз.
Кэш L3 сопоставимый - 32МБ, плюсом здесь линейный паттерн доступа, то есть гарантированно должен срабатывать префетч. Но я попробовал уменьшить размер массива в десять раз, и добавить повторов, результат все те-же +5%.
По поводу "памяти", имелось как раз в виду производительность кэша, так как инструкция одно тактовая, то он мог просто больше 32 байт, за этот такт "не прокачивать", даже если делать сложение на разных параллельно работающих портах.
Мне удалось выжать почти 2 раза (1.8), но это с минимальным размером массива (4096) и с двумя внешними циклами, один просто крутит 2000000 итераций, другой выбирает минимальное время из 20 попыток. Clang 14 / gcc 12.
В реальных условиях наверное чаще будет 5%, чем 2 раза.
Интересно, можете куда нибуть выложить исходник? (pastebin/gist) мне пришлось немного помучаться, чтобы вызов был внутри цикла, так как иначе результат "оптимизировался" чисто математически (накапливаемая сумма или чтото в этом духе)
Только я вставлял в сишный проект, поэтому переправил всё с плюсов на чистый Си. Но вряд ли это влияет. И я тоже ожидал, что будет мухлевать с итерациями, но нет, время явно зависит от 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;
}
Если в процессоре 2 блока, которые умеют делать vpaddq - то есть смысл и анролл в цикле сделать, чтобы в разные регистры записывался результат и можно было это суммирование делать параллельно.
Вообще, я удивлён, что в статье нету какой-то похожей картинки:
https://upload.wikimedia.org/wikipedia/commons/c/c3/Skylake_architecture_diagram.png
Получается, в Skylake уже 3 модуля для векторного сложения (Int Vect ALU), так что Clang где-то и прав.
Я брал информацию по вычислительным модулям у Агнера Фога, может он намеренно упоминал только "настоящие" модули с умножением и FMA:
https://www.agner.org/optimize/blog/read.php?i=838
Скорее всего, упирается в "память" (кэши) поэтому больше разворачивать, возможно не имеет смысла.
ну на NET 7 тоже есть vpaddq (Avx2.Add) но надо руками применять (для битных векторов) - может в бонусном коде так оно и делается - к сожалению, автор не привёл итоговый ассемблерный код
Спасибо, джентльмены, за интересные комментарии в этой ветке. Не хотел прерывать.
Действительно, почему бы и не добавить ассемблерный код, в который превратилась C#-реализация на SIMD:
M00_L03:
vmovupd ymm1,[rax]
vpaddq ymm0,ymm0,ymm1
add rax,20
cmp rax,rdx
jne short M00_L03
UPD: В статью тоже добавил.
Как всегда, удобно погружаться в курс дела, начиная с какого-нибудь очень простого и жизненного примера.
К сожалению, пример не особо жизненный — оптимизировать такие места как правило не имеет смысла, особенно с таким сильным усложнением кода. Максимум можно остановиться на первой оптимизации, которая, кстати, дает наибольший прирост.
Всё верно, LINQ медленный, ещё и объектами в хипе намусорил. В печь его, на дрова для пицц.
Есть подозрение, что конкретно в этом случае LINQ медленный из-за интерфейса в сигнатуре метода, и компилятор почему-то не смог нормально это соптимизировать. Возможно для других случаев деградации не будет или она будет не такой сильной.
К сожалению, пример не особо жизненный — оптимизировать такие места как правило не имеет смысла, особенно с таким сильным усложнением кода.
Все так - в реальном мире бОльшая часть (наверно 95%) кода IO bound, а не CPU bound. Т.е. тупо ждем, сокет, файл и пр. Единственное применение что приходит в голову - обработка видео, аудио, возможно ML
А вроде никто не написал такой трюк - если учитывать размер строки кэша, которая при обращении к памяти выбирается целиком, то может оказаться, что преобразование кода в два вложенных цикла, из которых внутренний будет перебирать данные, целиком помещаемые в такую строку, ускорит еще?
И почему-то никто не вспомнил про foreach, который для массивов не использует итератор и быстрее for.
Reciprocal throughput