Ответ 1
Ниже приведены некоторые версии, настроенные на основе Руководство по микроархиву Agner Fog. См. Также x86 теги wiki. Они должны быть эффективными на любом процессоре, без каких-либо серьезных узких мест. (например, я избегал вещей, которые могли бы помочь одному уарху немного, но медленнее на другом уархе). Размер кода также минимизирован.
Общая идиома 2x hadd хороша только для размера кода, а не для скорости для любых существующих ЦП. Для него есть прецеденты (см. Ниже), но это не один из них.
Я также включил версию AVX. Любое горизонтальное сокращение с помощью AVX/AVX2 должно начинаться с операции vextractf128 и "вертикальной", чтобы уменьшить до одного вектора XMM (__m128).
См. вывод asm из всего этого кода в проводнике компиляторов Godbolt. См. также мои улучшения в Библиотека векторных классов Agner Fog С++ horizontal_add. (поток сообщений и код github), Я использовал макросы CPP для выбора оптимальных перетасовки для размера кода для SSE2, SSE4 и AVX и для избежания movdqa, когда AVX недоступен.
Есть компромиссы:
- размер кода: меньше для причин I1 кеша L1 и для извлечения кода с диска (меньшие двоичные файлы). Общий двоичный размер в основном имеет значение для решений компилятора, которые неоднократно повторяются во всей программе. Если вы пытаетесь скомпоновать что-то со встроенными функциями, стоит потратить несколько байтов кода, если он дает какое-либо ускорение для всей программы (будьте осторожны с микрообъектами, которые делают просмотр в обратном порядке).
- Размер кэша uop: Часто более ценный, чем L1 я $. 4 инструкции с одним-уходом могут занимать меньше места, чем 2
haddps, поэтому это очень важно здесь. - латентность: иногда релевантная
- пропускная способность: обычно несущественная, горизонтальные суммы не должны быть в самом внутреннем цикле.
- Total fused-domain uops: Если окружающий код не является узким местом на том же порту, который использует hsum, это прокси-сервер для воздействия hsum на пропускную способность всего этого.
Если горизонтальное добавление нечасто:
Процессоры без uop-cache могут использовать 2x haddps: он замедляется, когда он запускается, но это не часто. Только 2 инструкции минимизируют влияние на окружающий код (размер я $).
Процессоры с uop-cache, вероятно, будут одобрять то, что занимает меньше uops, даже если это больше инструкций/больше размера кода x86. Используемые нами общие кэш-строки uops - это то, что мы хотим свести к минимуму, что не так просто, как сведение к минимуму общих uops (принятые ветки и границы 32B всегда запускают новую строку кэша uop).
В любом случае, с учетом сказанного, горизонтальные суммы приходят очень много, поэтому я попытался тщательно обработать некоторые версии, которые компилируются красиво. Не тестируется на каком-либо реальном оборудовании или даже тщательно проверяется. Могут быть ошибки в константах тасования или что-то в этом роде.
Если вы делаете резервную/базовую версию своего кода, помните, что только старые процессоры будут запускать ее; более новые процессоры будут запускать вашу версию AVX или SSE4.1 или что-то еще.
Старые процессоры, такие как K8 и Core2 (merom) и ранее, имеют только 64-битные единицы тасования. Core2 имеет 128 бит исполнения для большинства инструкций, но не для перетасовки. (Pentium M и K8 управляют всеми 128b векторными инструкциями в виде двух 64-битных половинок).
Перемешивается как movhlps, которые перемещают данные в 64-битных кусках (без перетасовки в пределах 64-битных половинок) тоже.
На старых процессорах с медленными тасованиями:
-
movhlps(Merom: 1uop) значительно быстрее, чемshufps(Merom: 3uops). На Pentium-M дешевле, чемmovaps. Кроме того, он работает в домене FP на Core2, избегая задержек при переходе из других тасов. -
unpcklpdбыстрее, чемunpcklps. -
pshufdмедленный,pshuflw/pshufhwбыстр (потому что они только перемешивают 64-битную половину) -
pshufb mm0(MMX) работает быстро,pshufb xmm0медленнее. -
haddpsочень медленный (6 точек на Merom и Pentium M) -
movshdup(Merom: 1uop) интересен: он единственный 1uop insn, который перемещается в пределах элементов 64b.
shufps на Core2 (включая Penryn) выводит данные в целочисленный домен, заставляя задержку байпаса возвращать его в исполнительные блоки FP для addps, но movhlps полностью находится в домене FP. shufpd также работает в домене с плавающей точкой.
movshdup выполняется в целочисленной области, но только один uop.
AMD K10, Intel Core2 (Penryn/Wolfdale) и все последующие процессоры, запускают все xmm shuffles как один uop. (Но обратите внимание на задержку байпаса с shufps на Penryn, избегайте с помощью movhlps)
Без AVX, избегая расточительных инструкций movaps/movdqa, требуется тщательный выбор тасов. Только несколько перетасовки работают как копирование и перетасовка, а не изменение назначения. Перемешивания, которые объединяют данные с двух входов (например, unpck* или movhlps), могут использоваться с переменной tmp, которая больше не нужна, а не _mm_movehl_ps(same,same).
Некоторые из них могут быть сделаны быстрее (кроме MOVAPS), но более уродливые/менее "чистые", взяв фиктивный аргумент arg для использования в качестве места назначения для первоначального тасования. Например:
// Use dummy = a recently-dead variable that vec depends on,
// so it doesn't introduce a false dependency,
// and the compiler probably still has it in a register
__m128d highhalf_pd(__m128d dummy, __m128d vec) {
#ifdef __AVX__
// With 3-operand AVX instructions, don't create an extra dependency on something we don't need anymore.
(void)dummy;
return _mm_unpackhi_pd(vec, vec);
#else
// Without AVX, we can save a MOVAPS with MOVHLPS into a dead register
__m128 tmp = _mm_castpd_ps(dummy);
__m128d high = _mm_castps_pd(_mm_movehl_ps(tmp, _mm_castpd_ps(vec)));
return high;
#endif
}
SSE1 (aka SSE):
float hsum_ps_sse1(__m128 v) { // v = [ D C | B A ]
__m128 shuf = _mm_shuffle_ps(v, v, _MM_SHUFFLE(2, 3, 0, 1)); // [ C D | A B ]
__m128 sums = _mm_add_ps(v, shuf); // sums = [ D+C C+D | B+A A+B ]
shuf = _mm_movehl_ps(shuf, sums); // [ C D | D+C C+D ] // let the compiler avoid a mov by reusing shuf
sums = _mm_add_ss(sums, shuf);
return _mm_cvtss_f32(sums);
}
# gcc 5.3 -O3: looks optimal
movaps xmm1, xmm0 # I think one movaps is unavoidable, unless we have a 2nd register with known-safe floats in the upper 2 elements
shufps xmm1, xmm0, 177
addps xmm0, xmm1
movhlps xmm1, xmm0 # note the reuse of shuf, avoiding a movaps
addss xmm0, xmm1
# clang 3.7.1 -O3:
movaps xmm1, xmm0
shufps xmm1, xmm1, 177
addps xmm1, xmm0
movaps xmm0, xmm1
shufpd xmm0, xmm0, 1
addss xmm0, xmm1
Я сообщил о ошибке о пессимистическом перетасовке. Он имеет собственное внутреннее представление для перетасовки и превращается в тасование. gcc чаще всего использует инструкции, которые непосредственно соответствуют встроенной вами функции.
Часто clang делает лучше, чем gcc, в коде, где выбор команды не настроен вручную, или постоянное распространение может упростить ситуацию, даже если intrinsics являются оптимальными для непостоянного случая. В целом хорошо, что компиляторы работают как правильный компилятор для встроенных функций, а не только для ассемблера. Компиляторы часто генерируют хороший asm из скаляра C, который даже не пытается работать так, как было бы хорошо. В конечном итоге компиляторы будут рассматривать intrinsics как просто еще один оператор C в качестве входных данных для оптимизатора.
SSE3
float hsum_ps_sse3(__m128 v) {
__m128 shuf = _mm_movehdup_ps(v); // broadcast elements 3,1 to 2,0
__m128 sums = _mm_add_ps(v, shuf);
shuf = _mm_movehl_ps(shuf, sums); // high half -> low half
sums = _mm_add_ss(sums, shuf);
return _mm_cvtss_f32(sums);
}
# gcc 5.3 -O3: perfectly optimal code
movshdup xmm1, xmm0
addps xmm0, xmm1
movhlps xmm1, xmm0
addss xmm0, xmm1
Это имеет ряд преимуществ:
-
не требует каких-либо копий
movapsдля работы с деструктивными тасованиями (без AVX):movshdup xmm1, xmm2destination - только для записи, поэтому он создаетtmpиз мертвого регистра для нас. Вот почему я использовалmovehl_ps(tmp, sums)вместоmovehl_ps(sums, sums). -
маленький размер кода. Команды перетасовки малы:
movhlps- 3 байта,movshdup- 4 байта (то же, что иshufps). Не требуется немедленный байт, поэтому с AVXvshufpsсоставляет 5 байтов, ноvmovhlpsиvmovshdupравны 4.
Я мог бы сохранить еще один байт с addps вместо addss. Поскольку это не будет использоваться внутри внутренних петель, дополнительная энергия для переключения дополнительных транзисторов, вероятно, незначительна. Исключения FP из трех верхних элементов не являются риском, поскольку все элементы содержат достоверные данные FP. Тем не менее, clang/LLVM фактически "понимает" векторные перетасовки и испускает лучший код, если он знает, что имеет значение только низкий элемент.
Как и версия SSE1, добавление нечетных элементов к себе может привести к тому, что исключения FP (например, переполнение) не будут происходить иначе, но это не должно быть проблемой. Денормалы медленные, но IIRC, производящий результат + Inf, не на большинстве uarches.
Оптимизация SSE3 для размера кода
Если размер кода является вашей главной проблемой, две инструкции haddps (_mm_hadd_ps) будут делать трюк (ответ Paul R). Это также самый легкий тип и запоминание. Это не быстро. Даже Intel Skylake по-прежнему расшифровывает каждый haddps до 3-х часов, с задержкой 6 циклов. Таким образом, хотя он сохраняет байты машинного кода (I-кеш L1), он занимает больше места в более ценном uop-кеше. Реальные прецеденты для haddps: проблема транспонирования и суммирования или выполнение некоторого масштабирования на промежуточном этапе в это реализация SSE atoi().
AVX:
Эта версия сохраняет байты кода и Марат отвечает на вопрос AVX.
#ifdef __AVX__
float hsum256_ps_avx(__m256 v) {
__m128 vlow = _mm256_castps256_ps128(v);
__m128 vhigh = _mm256_extractf128_ps(v, 1); // high 128
vlow = _mm_add_ps(vlow, vhigh); // add the low 128
return hsum_ps_sse3(vlow); // and inline the sse3 version, which is optimal for AVX
// (no wasted instructions, and all of them are the 4B minimum)
}
#endif
vmovaps xmm1,xmm0 # huh, what the heck gcc? Just extract to xmm1
vextractf128 xmm0,ymm0,0x1
vaddps xmm0,xmm1,xmm0
vmovshdup xmm1,xmm0
vaddps xmm0,xmm1,xmm0
vmovhlps xmm1,xmm1,xmm0
vaddss xmm0,xmm0,xmm1
vzeroupper
ret
двойной точности:
double hsum_pd_sse2(__m128d vd) { // v = [ B | A ]
__m128 undef = _mm_undefined_ps(); // don't worry, we only use addSD, never touching the garbage bits with an FP add
__m128 shuftmp= _mm_movehl_ps(undef, _mm_castpd_ps(vd)); // there is no movhlpd
__m128d shuf = _mm_castps_pd(shuftmp);
return _mm_cvtsd_f64(_mm_add_sd(vd, shuf));
}
# gcc 5.3.0 -O3
pxor xmm1, xmm1 # hopefully when inlined, gcc could pick a register it knew wouldn't cause a false dep problem, and avoid the zeroing
movhlps xmm1, xmm0
addsd xmm0, xmm1
# clang 3.7.1 -O3 again doesn't use movhlps:
xorpd xmm2, xmm2 # with #define _mm_undefined_ps _mm_setzero_ps
movapd xmm1, xmm0
unpckhpd xmm1, xmm2
addsd xmm1, xmm0
movapd xmm0, xmm1 # another clang bug: wrong choice of operand order
// This doesn't compile the way it written
double hsum_pd_scalar_sse2(__m128d vd) {
double tmp;
_mm_storeh_pd(&tmp, vd); // store the high half
double lo = _mm_cvtsd_f64(vd); // cast the low half
return lo+tmp;
}
# gcc 5.3 -O3
haddpd xmm0, xmm0 # Lower latency but less throughput than storing to memory
# ICC13
movhpd QWORD PTR [-8+rsp], xmm0 # only needs the store port, not the shuffle unit
addsd xmm0, QWORD PTR [-8+rsp]
Сохранение памяти и обратно позволяет избежать ALU uop. Это хорошо, если давление в канале в случайном порядке или ALU в общем случае являются узким местом. (Обратите внимание, что ему не нужно sub rsp, 8 или что-то еще, потому что x86-64 SysV ABI обеспечивает красную зону, в которой обработчики сигналов не будут наступать.)
Некоторые люди хранят массив и суммируют все элементы, но компиляторы обычно не понимают, что нижний элемент массива все еще находится в регистре из хранилища.
Integer:
pshufd - удобная копия и перетасовка. Бит и байтовые сдвиги, к сожалению, на месте, а punpckhqdq помещает большую половину адресата в низкую половину результата, напротив способа movhlps может извлечь верхнюю половину в другой регистр.
Использование movhlps для первого шага может быть хорошим для некоторых процессоров, но только если у нас есть коррекция нуля. pshufd - это безопасный выбор, и быстро все после Merom.
int hsum_epi32_sse2(__m128i x) {
#ifdef __AVX__
__m128i hi64 = _mm_unpackhi_epi64(x, x); // 3-operand non-destructive AVX lets us save a byte without needing a mov
#else
__m128i hi64 = _mm_shuffle_epi32(x, _MM_SHUFFLE(1, 0, 3, 2));
#endif
__m128i sum64 = _mm_add_epi32(hi64, x);
__m128i hi32 = _mm_shufflelo_epi16(sum64, _MM_SHUFFLE(1, 0, 3, 2)); // Swap the low two elements
__m128i sum32 = _mm_add_epi32(sum64, hi32);
return _mm_cvtsi128_si32(sum32); // SSE2 movd
//return _mm_extract_epi32(hl, 0); // SSE4, even though it compiles to movd instead of a literal pextrd r32,xmm,0
}
# gcc 5.3 -O3
pshufd xmm1,xmm0,0x4e
paddd xmm0,xmm1
pshuflw xmm1,xmm0,0x4e
paddd xmm0,xmm1
movd eax,xmm0
int hsum_epi32_ssse3_slow_smallcode(__m128i x){
x = _mm_hadd_epi32(x, x);
x = _mm_hadd_epi32(x, x);
return _mm_cvtsi128_si32(x);
}
На некоторых процессорах безопасно использовать FP-перетасовку для целочисленных данных. Я не делал этого, так как на современных процессорах, которые будут в большинстве случаев сохранять 1 или 2 байта кода, без увеличения скорости (кроме эффектов размера кода/выравнивания).