assembly - 进行水平 SSE 向量求和(或其他缩减)的最快方法

Question

给定一个包含三个(或四个)浮点数的向量。对它们求和的最快方法是什么？

SSE(movaps、shuffle、add、movd)总是比x87快吗？ SSE3 中的水平添加指令值得吗？

转移到 FPU 的成本是多少，然后是 faddp、faddp？最快的特定指令序列是什么？

“尝试安排事物以便您一次可以总结四个向量”将不被接受作为答案。 :-) 例如为了对数组求和，您可以使用多个向量累加器进行垂直求和(以隐藏 addps 延迟)，并在循环后减少到一个，但是您需要对最后一个向量进行水平求和。

Answer 1

一般来说，对于任何类型的向量水平减少，提取/混洗高半到低，然后垂直添加(或最小/最大/或/和/异或/乘/任何)；重复直到剩下一个元素。 如果您从大于 128 位的向量开始，将其缩小一半，直到达到 128(然后您可以在该向量上使用此答案中的函数之一)。除非最后需要将结果广播到所有元素，否则可以考虑一直做全宽shuffle。
宽向量、整数和 FP 的相关问答

__m128 和 __m128d 这个答案(见下文)

__m256d 与 Ryzen 1 与 Intel 的性能分析(说明了为什么 vextractf128 比 0x251812231343125141 1325134312513241318 好得多)

vperm2f128 Get sum of values stored in __m256d with SSE/AVX

How to sum __m256 horizontally? 单个向量。

数组的点积 (不仅仅是 3 或 4 个元素的单个向量):在 h 的末尾对 0x251811223 进行垂直 mul/add 或 FMA。 Intel AVX: 256-bits version of dot product for double precision floating point variables ，包括循环后的有效hsum。 (对于数组的简单求和或其他缩减，使用该模式但没有乘法部分，例如添加而不是 fma)。不要为每个 SIMD 向量单独做水平工作；最后做一次。
multiple accumulators 作为计数 __m256 的整数示例，同样在整个数组中匹配，仅在最后进行求和。 (特别值得一提的是，先进行一些 8 位累加，然后扩大 8 -> 64 位以避免溢出，而无需在此时执行完整的 hsum。)

整数

_mm256_cmpeq_epi8 32 位元素:这个答案(见下文)。 64 位元素应该是显而易见的:只有一个 pshufd/paddq 步骤。

__m128i 8 位无符号元素: Complete AVX+FMA array dot-product example 对 __m128i ，然后对两个 qword 一半(或更宽的向量 4 或 4)求和。 How to count character occurrences using SIMD 显示带有 SSE2 的 128 位。
psadbw 有一个 AVX512 示例。 Fastest way to horizontally sum SSE unsigned byte vector 有一个 AVX2 _mm_setzero_si128() 示例。
(对于有符号字节，您可以 XOR set1(0x80) 在 SAD 之前翻转为无符号，然后从最终的 hsum 中减去偏差)。

__m256i 使用 set1(1) 作为窄整数的单 uop 加宽水平添加构建块:Summing 8-bit integers in __m512i with AVX intrinsics

_mm_madd_epi16 和 __m256i 具有 32 位元素。
How to count character occurrences using SIMD。对于 AVX512，英特尔添加了一堆“减少”内联函数(不是硬件指令)来为您执行此操作，例如 __m512i(以及 pd、epi32 和 epi64)。还有reduce_min/max/mul/和/或。手动执行会导致基本相同的 asm。

水平最大值(而不是添加):SIMD: Accumulate Adjacent Pairs

这个问题的主要答案:主要是 float 和 _mm512_reduce_add_ps以下是一些基于 Fastest method to calculate sum of all packed 32-bit integers using AVX512 or AVX2 的微架构指南和指令表调整的版本。另请参阅 Getting max value in a __m128i vector with SSE? 标签维基。它们在任何 CPU 上都应该是高效的，没有大的瓶颈。 (例如，我避免了会帮助一个 uarch 但对另一个 uarch 缓慢的事情)。代码大小也被最小化。
常见的 SSE3/SSSE3 2x __m128 习惯用法仅适用于代码大小，不适用于任何现有 CPU 的速度。它有一些用例(如转置和添加，见下文)，但单个向量不是其中之一。
我还包含了一个 AVX 版本。任何使用 AVX/AVX2 的水平缩减都应以 hadd 和“垂直”操作开始，以缩减为一个 XMM ( vextractf128 ) 向量。一般来说，对于宽向量，最好的办法是反复缩小一半，直到缩小到 128 位向量，无论元素类型如何。 (除了 8 位整数，如果你想在不溢出到更宽元素的情况下进行 hsum，那么第一步是 __m128。)
查看所有代码 Agner Fog's microarch guide 的 asm 输出。 另见我对 x86 vpsadbw 函数的改进。 ( on the Godbolt Compiler Explorer ，以及 Agner Fog's C++ Vector Class Library 上的代码)。我使用 CPP 宏为 SSE2、SSE4 和 AVX 的代码大小选择最佳洗牌，并在 AVX 不可用时避免 horizontal_add。

有一些权衡需要考虑:

代码大小:对于 L1 I-cache 和从磁盘获取代码(较小的二进制文件)，越小越好。总二进制大小对于在整个程序中重复做出的编译器决策来说最重要。如果您不想使用内在函数手动编写某些代码，那么如果它为整个程序提供了任何加速，那么花几个代码字节是值得的(请注意使展开看起来不错的微基准测试)。

uop-cache size:通常比L1 I$更宝贵。 4 条单 uop 指令占用的空间少于 2 条 movdqa ，因此这在这里非常相关。

延迟:有时相关

吞吐量(后端端口):通常不相关，水平总和不应是最内层循环中的唯一内容。端口压力仅作为包含此内容的整个循环的一部分而重要。

吞吐量(总前端融合域 uops):如果周围代码在 hsum 使用的同一端口上没有瓶颈，则这是 hsum 对整个事物吞吐量影响的代理。

当水平添加不频繁时 :
没有 uop-cache 的 CPU 可能更喜欢 2x haddps 如果它很少使用:它运行时很慢，但这并不经常。只有 2 条指令最大限度地减少了对周围代码(I$ 大小)的影响。
带有 uop 缓存 的 CPU 可能会支持使用较少 uop 的东西，即使它有更多指令/更多 x86 代码大小。使用的总 uops 缓存线是我们想要最小化的，这不像最小化总 uops 那么简单(采用的分支和 32B 边界总是开始一个新的 uop 缓存线)。
无论如何，话虽如此，水平总和出现了很多，所以这是我尝试精心制作一些编译良好的版本。未在任何真实硬件上进行基准测试，甚至未经过仔细测试。 shuffle 常量或其他东西中可能存在错误。

如果您正在制作代码的回退/基线版本，请记住只有旧 CPU 才能运行它 ；较新的 CPU 将运行您的 AVX 版本或 SSE4.1 或其他任何版本。
像 K8、Core2(merom) 和更早版本的旧 CPU 只有 64 位 shuffle 单元 。 Core2 为大多数指令提供 128 位执行单元，但对于 shuffle 则没有。 (Pentium M 和 K8 将所有 128b 向量指令作为两个 64 位一半处理)。
像 haddps 这样在 64 位块中移动数据(在 64 位一半内没有混洗)的混洗也很快。
相关:新 CPU 上的 shuffle，以及避免 Haswell 及更高版本上 1/clock shuffle 吞吐量瓶颈的技巧:message board thread
在旧 CPU 上使用慢 shuffle :

movhlps (Merom: 1uop) 明显快于 movhlps (Merom: 3uops)。在 Pentium-M 上，比 shufps 便宜。此外，它在 Core2 上的 FP 域中运行，避免了其他 shuffle 的旁路延迟。

movaps 比 unpcklpd 快。

unpcklps 很慢，pshufd/pshuflw 很快(因为它们只洗 64 位 91341 的一半) 1122

pshufhw (MMX) 快，pshufb mm0 慢。

pshufb xmm0 非常慢(Merom 和 Pentium M 上为 6uops)

haddps (Merom: 1uop) 很有趣 :这是唯一的 1uop insn 元素。

Core2(包括 Penryn)上的 movshdup 将数据带入整数域，导致绕过延迟将其返回到 shufps 的 FP 执行单元，但 addps 完全在 FP 域中。 movhlps 也在 float 域中运行。shufpd 在整数域中运行，但只有一个 uop。
AMD K10、Intel Core2(Penryn/Wolfdale) 和所有后来的 CPU，将所有 xmm shuffle 作为单个 uop 运行。 (但请注意 Penryn 上 movshdup 的旁路延迟，避免了 shufps )

没有AVX，避免浪费 movhlps/movaps 指令需要仔细选择shuffle 。只有少数洗牌作为复制和洗牌工作，而不是修改目的地。组合来自两个输入的数据(如 movdqa 或 unpck* )的混洗可以与不再需要的 tmp 变量一起使用，而不是 movhlps 。
通过将虚拟 arg 用作初始 shuffle 的目的地，其中一些可以更快(保存 MOVAPS)但更丑/不那么“干净”。 例如:

// 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(又名 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

我报告了一个 github 。它有自己的洗牌内部表示，并将其转回洗牌。 gcc 更经常使用与您使用的内在函数直接匹配的指令。
通常 clang 比 gcc 做得更好，在指令选择不是手动调整的代码中，或者即使当内在函数对于非常量情况是最佳的时，常量传播也可以简化事情。总的来说，编译器可以像内部函数的合适编译器一样工作，而不仅仅是汇编器，这是一件好事。编译器通常可以从标量 C 生成好的 asm，甚至不会尝试像好的 asm 那样工作。最终编译器会将内在函数视为另一个 C 运算符作为优化器的输入。

上证三

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

这有几个优点:

不需要任何 _mm_movehl_ps(same,same) 副本来解决破坏性洗牌(没有 AVX): movaps 的目的地是只写的，因此它为 a43412 创建了 0x3118312 的死寄存器这也是我使用 movshdup xmm1, xmm2 而不是 tmp 的原因。

小代码大小。混洗指令很小: movehl_ps(tmp, sums) 是 3 个字节， movehl_ps(sums, sums) 是 4 个字节(与 movhlps 相同)。不需要立即字节，因此对于 AVX，movshdup 是 5 个字节，但 shufps 和 vshufps 都是 4 个字节。

我可以用 vmovhlps 而不是 vmovshdup 保存另一个字节。由于这不会在内部循环内使用，因此切换额外晶体管的额外能量可能可以忽略不计。来自上面 3 个元素的 FP 异常没有风险，因为所有元素都保存有效的 FP 数据。然而，clang/LLVM 实际上“理解”向量混洗，并且如果它知道只有低元素重要的话，它会发出更好的代码。
与 SSE1 版本一样，向自身添加奇数元素可能会导致 FP 异常(如溢出)，否则不会发生，但这应该不是问题。 Denormals 很慢，但 IIRC 产生 +Inf 结果不是在大多数 uarches 上。

SSE3 优化代码大小
如果代码大小是您的主要关注点，那么两条 addps ( addss ) 指令就可以解决问题(Paul R 的回答)。这也是最容易输入和记住的。不过，它是 不快 。甚至英特尔 Skylake 仍然将每个 haddps 解码为 3 uop，具有 6 个周期的延迟。因此，即使它节省了机器代码字节(L1 I-cache)，它也会在更有值(value)的 uop-cache 中占用更多空间。 _mm_hadd_ps 的实际用例: Do 128bit cross lane operations in AVX512 give better performance? ，或者在中间步骤 clang bug about pessimizing the shuffles 进行一些缩放。

AVX:
与 a transpose-and-sum problem 相比，此版本节省了一个代码字节。

#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 :

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's 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。如果 shuffle 端口压力或一般的 ALU uops 是瓶颈，那很好。 (请注意，它不需要 haddps 或任何东西，因为 x86-64 SysV ABI 提供了信号处理程序不会踩到的红色区域。)
有些人存储到一个数组并将所有元素相加，但编译器通常没有意识到数组的低元素仍然存在于存储之前的寄存器中。

整数:haddps 是一个方便的复制和洗牌。不幸的是，位和字节移位是就地的，atoi() 将目标的高半部分放在结果的低半部分，与 sub rsp, 8 可以将高半部分提取到不同寄存器的方式相反。
在某些 CPU 上，第一步使用 pshufd 可能会很好，但前提是我们有一个临时注册。 punpckhqdq 是一个安全的选择，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);
}

在某些 CPU 上，对整数数据使用 FP shuffle 是安全的。我没有这样做，因为在现代 CPU 上最多可以节省 1 或 2 个代码字节，而没有速度提升(代码大小/对齐效果除外)。