c++ - AVX 中的水平异或

Question

有没有办法对 AVX 寄存器进行水平异或——特别是对 256 位寄存器的四个 64 位组件进行异或？

目标是获得 AVX 寄存器的所有 4 个 64 位组件的异或。它本质上与水平添加( _mm256_hadd_epi32() )做同样的事情，除了我想要 XOR 而不是 ADD。

标量代码是:

inline uint64_t HorizontalXor(__m256i t) {
  return t.m256i_u64[0] ^ t.m256i_u64[1] ^ t.m256i_u64[2] ^ t.m256i_u64[3];
}

Answer 1

正如评论中所述，最快的代码很可能使用标量运算，在整数寄存器中执行所有操作。您需要做的就是提取四个压缩的 64 位整数，然后您就有了三个 XOR指令，你就完成了。这可以非常有效地完成，并将结果留在一个整数寄存器中，这是您的示例代码建议您想要的。

MSVC 已经为您在问题中作为示例显示的标量函数生成了非常好的代码:

inline uint64_t HorizontalXor(__m256i t) {
  return t.m256i_u64[0] ^ t.m256i_u64[1] ^ t.m256i_u64[2] ^ t.m256i_u64[3];
}

假设 t在 ymm1 ，由此产生的反汇编将是这样的:

vextractf128 xmm0, ymm1, 1
vpextrq      rax,  xmm0, 1
vmovq        rcx,  xmm1
xor          rax,  rcx
vpextrq      rcx,  xmm1, 1
vextractf128 xmm0, ymm1, 1
xor          rax,  rcx
vmovq        rcx,  xmm0
xor          rax,  rcx

...结果留在 RAX .如果这准确地反射(reflect)了您的需要(标量 uint64_t 结果)，那么此代码就足够了。

您可以使用内在函数稍微改进它:

inline uint64_t _mm256_hxor_epu64(__m256i x)
{
   const __m128i temp = _mm256_extracti128_si256(x, 1);
   return (uint64_t&)x
          ^ (uint64_t)(_mm_extract_epi64(_mm256_castsi256_si128(x), 1))
          ^ (uint64_t&)(temp)
          ^ (uint64_t)(_mm_extract_epi64(temp, 1));
}

然后你会得到以下反汇编(再次假设 x 在 ymm1 中):

vextracti128 xmm2, ymm1, 1
vpextrq      rcx,  xmm2, 1
vpextrq      rax,  xmm1, 1
xor          rax,  rcx
vmovq        rcx,  xmm1
xor          rax,  rcx
vmovq        rcx,  xmm2
xor          rax,  rcx

请注意，我们能够省略一个提取指令，并且我们已经确保 VEXTRACTI128被用来代替 VEXTRACTF128 (尽管， this choice probably does not matter )。

您将在其他编译器上看到类似的输出。例如，这里是 GCC 7.1(假设 x 位于 ymm0 中):

vextracti128 xmm2, ymm0, 0x1
vpextrq      rax,  xmm0, 1
vmovq        rdx,  xmm2
vpextrq      rcx,  xmm2, 1
xor          rax,  rdx
vmovq        rdx,  xmm0
xor          rax,  rdx
xor          rax,  rcx

那里有相同的说明，但它们已经稍微重新排序。内在函数允许编译器的调度程序按照它认为最好的方式进行排序。 Clang 4.0 以不同的方式调度它们:

vmovq        rax,  xmm0
vpextrq      rcx,  xmm0, 1
xor          rcx,  rax
vextracti128 xmm0, ymm0, 1
vmovq        rdx,  xmm0
xor          rdx,  rcx
vpextrq      rax,  xmm0, 1
xor          rax,  rdx

而且，当然，当代码被内联时，这种顺序总是会发生变化。

另一方面，如果您希望结果在 AVX 寄存器中，那么您首先需要决定如何存储它。我猜你只会将单个 64 位结果存储为标量，例如:

inline __m256i _mm256_hxor(__m256i x)
{
   const __m128i temp = _mm256_extracti128_si256(x, 1);
   return _mm256_set1_epi64x((uint64_t&)x
                             ^ (uint64_t)(_mm_extract_epi64(_mm256_castsi256_si128(x), 1))
                             ^ (uint64_t&)(temp)
                             ^ (uint64_t)(_mm_extract_epi64(temp, 1)));
}

但是现在您正在进行大量数据混洗，从而抵消了您可能从代码矢量化中看到的任何性能提升。

说到这里，我不太确定你是如何让自己陷入需要进行这样的横向操作的情况的。 SIMD 操作旨在垂直扩展，而不是水平扩展。如果您仍处于实现阶段，则重新考虑设计可能是合适的。特别是，您应该在 4 个不同的 AVX 寄存器中生成 4 个整数值，而不是将它们全部打包成一个。

如果您确实想要将结果的 4 个拷贝打包到 AVX 寄存器中，那么您可以执行以下操作:

inline __m256i _mm256_hxor(__m256i x)
{
   const __m256i temp = _mm256_xor_si256(x,
                                         _mm256_permute2f128_si256(x, x, 1));    
   return _mm256_xor_si256(temp,
                           _mm256_shuffle_epi32(temp, _MM_SHUFFLE(1, 0, 3, 2)));
}

这仍然通过一次执行两个 XOR 来利用一些并行性，这意味着总共只需要两个 XOR 操作，而不是三个。

如果它有助于可视化它，这基本上可以:

   A         B         C         D           ⟵ input
  XOR       XOR       XOR       XOR
   C         D         A         B           ⟵ permuted input
=====================================
  A^C       B^D       A^C        B^D         ⟵ intermediate result
  XOR       XOR       XOR        XOR
  B^D       A^C       B^D        A^C         ⟵ shuffled intermediate result
======================================
A^C^B^D   A^C^B^D   A^C^B^D    A^C^B^D      ⟵ final result

在几乎所有编译器上，这些内在函数将产生以下汇编代码:

vperm2f128  ymm0, ymm1, ymm1, 1    ; input is in YMM1
vpxor       ymm2, ymm0, ymm1
vpshufd     ymm1, ymm2, 78
vpxor       ymm0, ymm1, ymm2

(我在第一次发布这个答案后在 sleep 的路上想出了这个，并计划回来更新答案，但我看到 wim 在发布它时让我大吃一惊。哦，它仍然是一个比我第一次使用的方法更好，所以它仍然值得被包括在这里。)

而且，当然，如果您想在整数寄存器中使用它，您只需要一个简单的 VMOVQ :

vperm2f128  ymm0, ymm1, ymm1, 1    ; input is in YMM1
vpxor       ymm2, ymm0, ymm1
vpshufd     ymm1, ymm2, 78
vpxor       ymm0, ymm1, ymm2
vmovq       rax,  xmm0

问题是，这会比上面的标量代码更快吗？答案是，是的，可能。尽管您使用 AVX 执行单元进行 XOR，而不是完全独立的整数执行单元，但需要完成的 AVX shuffle/permutes/extracts 更少，这意味着更少的开销。所以我可能也不得不承认标量代码是最快的实现。但这实际上取决于您在做什么以及如何安排/交错指令。