Почему gcc -O3 автоматически векторизует факториал? Что много лишних инструкций выглядит хуже
Вот очень простая факториальная функция.
int factorial(int num) {
if (num == 0)
return 1;
return num*factorial(num-1);
}
Сборка GCC для этой функции на -O2 является разумной.
factorial(int):
mov eax, 1
test edi, edi
je .L1
.L2:
imul eax, edi
sub edi, 1
jne .L2
.L1:
ret
Тем не менее, на -O3 или -Ofast, он решает все усложнить (почти 100 строк!):
factorial(int):
test edi, edi
je .L28
lea edx, [rdi-1]
mov ecx, edi
cmp edx, 6
jbe .L8
mov DWORD PTR [rsp-12], edi
movd xmm5, DWORD PTR [rsp-12]
mov edx, edi
xor eax, eax
movdqa xmm0, XMMWORD PTR .LC0[rip]
movdqa xmm4, XMMWORD PTR .LC2[rip]
shr edx, 2
pshufd xmm2, xmm5, 0
paddd xmm2, XMMWORD PTR .LC1[rip]
.L5:
movdqa xmm3, xmm2
movdqa xmm1, xmm2
paddd xmm2, xmm4
add eax, 1
pmuludq xmm3, xmm0
psrlq xmm1, 32
psrlq xmm0, 32
pmuludq xmm1, xmm0
pshufd xmm0, xmm3, 8
pshufd xmm1, xmm1, 8
punpckldq xmm0, xmm1
cmp eax, edx
jne .L5
movdqa xmm2, xmm0
movdqa xmm1, xmm0
mov edx, edi
psrldq xmm2, 8
psrlq xmm0, 32
and edx, -4
pmuludq xmm1, xmm2
psrlq xmm2, 32
sub edi, edx
pmuludq xmm0, xmm2
pshufd xmm1, xmm1, 8
pshufd xmm0, xmm0, 8
punpckldq xmm1, xmm0
movdqa xmm0, xmm1
psrldq xmm1, 4
pmuludq xmm0, xmm1
movd eax, xmm0
cmp ecx, edx
je .L1
lea edx, [rdi-1]
.L3:
imul eax, edi
test edx, edx
je .L1
imul eax, edx
mov edx, edi
sub edx, 2
je .L1
imul eax, edx
mov edx, edi
sub edx, 3
je .L1
imul eax, edx
mov edx, edi
sub edx, 4
je .L1
imul eax, edx
mov edx, edi
sub edx, 5
je .L1
imul eax, edx
sub edi, 6
je .L1
imul eax, edi
.L1:
ret
.L28:
mov eax, 1
ret
.L8:
mov eax, 1
jmp .L3
.LC0:
.long 1
.long 1
.long 1
.long 1
.LC1:
.long 0
.long -1
.long -2
.long -3
.LC2:
.long -4
.long -4
.long -4
.long -4
Я получил эти результаты с помощью Compiler Explorer, поэтому он должен быть таким же в реальном случае использования.
Что с этим? Есть ли случаи, когда это будет быстрее? Кажется, что Clang тоже делает что-то подобное, но на -O2.
2 ответа
imul r32,r32 имеет 3 задержки цикла на типичных современных процессорах x86 ( http://agner.org/optimize/). Таким образом, скалярная реализация может делать одно умножение за 3 такта, потому что они зависимы. Тем не менее, он полностью конвейеризован, поэтому ваш скалярный цикл не использует 2/3 потенциальной пропускной способности.
В 3 циклах конвейер в Core2 или новее может подавать 12 мопов в неупорядоченную часть ядра. Для небольших входных данных, возможно, было бы лучше сохранить код небольшим и позволить неупорядоченному выполнению перекрывать цепочку зависимостей с более поздним кодом, особенно если этот более поздний код не все зависит от факторного результата. Но компиляторы плохо знают, когда нужно оптимизировать время ожидания или пропускную способность, и без оптимизации на основе профилей у них нет данных о том, насколько велика n обычно есть.
Я подозреваю, что авто-векторизатор gcc не смотрит на то, как быстро это переполнится для больших n,
Полезная скалярная оптимизация была бы развернута с несколькими аккумуляторами, например, использовать тот факт, что умножение ассоциативно, и делать это параллельно в цикле: prod(n*3/4 .. n) * prod(n/2 .. n*3/4) * prod(n/4 .. n/2) * prod(1..n/4) (с непересекающимися диапазонами, конечно). Умножение ассоциативно, даже когда оно оборачивается; биты продукта зависят только от битов в этой позиции и ниже, а не от (отбрасываемых) старших битов.
Или проще f0 *= i; f1 *= i+1; f2 *= i+2; f3 *= i+3; i+=4;, А потом за пределами цикла, return (f0*f1) * (f2*f3);, Это будет победой и в скалярном коде. Конечно, вы также должны учитывать n % 4 != 0 при развертывании.
Что GCC решил сделать, это в основном последний, используя pmuludq делать 2 упакованных умножения с одной инструкцией (пропускная способность 5c / 1c или 0.5c на процессорах Intel). Аналогично на процессорах AMD; см. таблицы инструкций Агнера Фога.Каждая итерация векторного цикла выполняет 4 итерации факториального цикла в вашем C-источнике, и в течение одной итерации существует значительный параллелизм на уровне команд
Внутренний цикл имеет длину всего 12 мопов (cmp/jcc макроплавки в 1), поэтому он может выдавать 1 итерацию на 3 цикла, такую же пропускную способность, как узкое место задержки в вашей скалярной версии, но выполняя в 4 раза больше работы на каждую итерацию.
.L5:
movdqa xmm3, xmm2 ; copy the old i vector
movdqa xmm1, xmm2
paddd xmm2, xmm4 ; [ i0, i1 | i2, i3 ] += 4
add eax, 1
pmuludq xmm3, xmm0 ; [ f0 | f2 ] *= [ i0 | i2 ]
psrlq xmm1, 32 ; bring odd 32 bit elements down to even: [ i1 | i3 ]
psrlq xmm0, 32
pmuludq xmm1, xmm0 ; [ f1 | f3 ] *= [ i1 | i3 ]
pshufd xmm0, xmm3, 8
pshufd xmm1, xmm1, 8
punpckldq xmm0, xmm1 ; merge back into [ f0 f1 f2 f3 ]
cmp eax, edx
jne .L5
Таким образом, gcc тратит немало усилий на эмуляцию упакованного 32-битного умножения вместо того, чтобы при использовании использовать два отдельных векторных аккумулятораpmuludq, Я также посмотрел на Clang6.0. Я думаю, что он попадает в ту же ловушку. ( Source + asm в проводнике компилятора Godbolt)
Вы не использовали-march=nativeили что-то еще, поэтому доступен только SSE2 (базовый уровень для x86-64), поэтому умножается только 32x32 => 64-битное SIMD, напримерpmuludq доступны для 32-битных элементов ввода. SSE4.1 pmulld равен 2 мопам на Haswell и позже (single-uop на Sandybridge), но позволит избежать всех глупых перетасовок gcc.
Конечно, здесь также есть узкое место с задержкой, особенно из-за пропущенных оптимизаций gcc, увеличивающих длину переносимой по циклу цепи депо с участием аккумуляторов.
Развертывание с большим количеством векторных аккумуляторов может скрыть много pmuludq задержка.
При хорошей векторизации целочисленные умножители SIMD могут в 2 или 4 раза увеличить пропускную способность скалярного целочисленного умножения. (Или, с AVX2, пропускная способность увеличивается в 8 раз, используя векторы из 8-ми 32-битных целых.)
Но чем шире векторы и чем больше развернутых, тем больше кода очистки вам нужно.
gcc -march=haswell
Мы получаем внутренний цикл, как это:
.L5:
inc eax
vpmulld ymm1, ymm1, ymm0
vpaddd ymm0, ymm0, ymm2
cmp eax, edx
jne .L5
Супер простая, но цепочка зависимостей с задержкой 10c:/ (pmulld 2 зависимых мопа от Haswell и позже). Развертывание с несколькими аккумуляторами может увеличить пропускную способность в 10 раз для больших входов, для 5c задержки / 0,5c пропускной способности для целочисленного умножения SIMD на Skylake.
Но 4 умножения на 5 циклов все еще намного лучше, чем 1 на 3 для скалярных.
Clang разворачивается с несколькими аккумуляторами по умолчанию, так что должно быть хорошо. Но кода много, поэтому я не анализировал его вручную. Подключите его к IACA или сравните его для больших входов. ( Что такое IACA и как мне его использовать?)
Эффективные стратегии обработки развернутого эпилога:
Таблица поиска для факториала [0..7] это, наверное, лучшая ставка. Расставьте вещи так, чтобы ваш вектор / развернутый цикл делал n%8 .. n, вместо 1 .. n/8*8Таким образом, оставшаяся часть всегда одинакова для всех n,
После горизонтального векторного произведения, сделайте еще одно скалярное умножение с результатом поиска в таблице. В цикле SIMD уже нужны некоторые векторные константы, так что вы все равно, вероятно, коснетесь памяти, и поиск в таблице может происходить параллельно с основным циклом.
8! равен 40320, что соответствует 16 битам, поэтому для таблицы поиска 1..8 требуется только 8 * 2 байта памяти. Или используйте 32-битные записи, чтобы вы могли использовать операнд источника памяти для imul вместо отдельного movzx,
Это не делает это хуже. Он работает быстрее для больших чисел. Вот результаты для factorial(1000000000):
-O2: 0,78 сек-O3: 0,5 сек
Конечно, использование этого большого числа - неопределенное поведение (из-за переполнения со знаком арифметики). Но время совпадает с числами без знака, для которых это не неопределенное поведение.
Обратите внимание, что использование факториала, как правило, бессмысленно, так как не рассчитывается num!, но num! & UINT_MAX, Но компилятор не знает об этом.
Возможно, с PGO компилятор не будет векторизовать этот код, если он всегда вызывается с небольшими числами.
Если вам не нравится это поведение, но вы хотите использовать -O3, отключите автовекторизацию с -fno-tree-loop-vectorize,