AVX 中的水平异或
Horizontal XOR in AVX
有没有办法对 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];
}
XOR 的 _mm256_hadd_epi32() 直接模拟的实现看起来像这样：
#include <immintrin.h>
template<int imm> inline __m256i _mm256_shuffle_epi32(__m256i a, __m256i b)
{
return _mm256_castps_si256(_mm256_shuffle_ps(_mm256_castsi256_ps(a), _mm256_castsi256_ps(b), imm));
}
inline __m256i _mm256_hxor_epi32(__m256i a, __m256i b)
{
return _mm256_xor_si256(_mm256_shuffle_epi32<0x88>(a, b), _mm256_shuffle_epi32<0xDD>(a, b));
}
int main()
{
__m256i a = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
__m256i b = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 7, 8);
__m256i c = _mm256_hxor_epi32(a, b);
return 0;
}
如评论中所述，最快的代码很可能使用标量运算，在整数寄存器中执行所有操作。您需要做的就是提取四个打包的 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。如果这准确地反映了您的需要（标量 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
（我在第一次发布这个答案后在睡觉的路上想到了这个，并计划回来更新答案，但我看到 在发布它时先发制人.哦，它仍然比我最初的方法更好，所以它仍然值得被包括在这里。）
当然，如果你想在整数寄存器中使用它，你只需要一个简单的 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 shuffles/permutes/extracts 更少，这意味着开销更少。因此，我可能还不得不食言，标量代码是最快的实现。但这实际上取决于您在做什么以及说明如何 scheduled/interleaved.
如果水平 xor 函数的输入已经在
一个 AVX 寄存器，即你的 t 是一些 SIMD 计算的结果。
否则，标量代码可能会更快，正如@Cody Gray 已经提到的那样。
通常，您可以在大约 log_2(SIMD_width) 'steps' 内执行水平 SIMD 操作。
在这种情况下，一步是 'shuffle/permute' 和 'xor'。这比@Cody Gray 的 _mm256_hxor 函数稍微高效：
__m256i _mm256_hxor_v2(__m256i x)
{
__m256i x0 = _mm256_permute2x128_si256(x,x,1); // swap the 128 bit high and low lane
__m256i x1 = _mm256_xor_si256(x,x0);
__m256i x2 = _mm256_shuffle_epi32(x1,0b01001110); // swap 64 bit lanes
__m256i x3 = _mm256_xor_si256(x1,x2);
return x3;
}
编译为：
vperm2i128 , %ymm0, %ymm0, %ymm1
vpxor %ymm1, %ymm0, %ymm0
vpshufd , %ymm0, %ymm1
vpxor %ymm1, %ymm0, %ymm0
如果你想在标量寄存器中得到结果：
uint64_t _mm256_hxor_v2_uint64(__m256i x)
{
__m256i x0 = _mm256_permute2x128_si256(x,x,1);
__m256i x1 = _mm256_xor_si256(x,x0);
__m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);
__m256i x3 = _mm256_xor_si256(x1,x2);
return _mm_cvtsi128_si64x(_mm256_castsi256_si128(x3)) ;
}
编译为：
vperm2i128 , %ymm0, %ymm0, %ymm1
vpxor %ymm1, %ymm0, %ymm0
vpshufd , %ymm0, %ymm1
vpxor %ymm1, %ymm0, %ymm0
vmovq %xmm0, %rax
完整测试代码：
#include <stdio.h>
#include <x86intrin.h>
#include <stdint.h>
/* gcc -O3 -Wall -m64 -march=broadwell hor_xor.c */
int print_vec_uint64(__m256i v);
__m256i _mm256_hxor_v2(__m256i x)
{
__m256i x0 = _mm256_permute2x128_si256(x,x,1);
__m256i x1 = _mm256_xor_si256(x,x0);
__m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);
__m256i x3 = _mm256_xor_si256(x1,x2);
/* Uncomment the next few lines to print the values of the intermediate variables */
/*
printf("3...0 = 3 2 1 0\n");
printf("x = ");print_vec_uint64(x );
printf("x0 = ");print_vec_uint64(x0 );
printf("x1 = ");print_vec_uint64(x1 );
printf("x2 = ");print_vec_uint64(x2 );
printf("x3 = ");print_vec_uint64(x3 );
*/
return x3;
}
uint64_t _mm256_hxor_v2_uint64(__m256i x)
{
__m256i x0 = _mm256_permute2x128_si256(x,x,1);
__m256i x1 = _mm256_xor_si256(x,x0);
__m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);
__m256i x3 = _mm256_xor_si256(x1,x2);
return _mm_cvtsi128_si64x(_mm256_castsi256_si128(x3)) ;
}
int main() {
__m256i x = _mm256_set_epi64x(0x7, 0x5, 0x2, 0xB);
// __m256i x = _mm256_set_epi64x(4235566778345231, 1123312566778345423, 72345566778345673, 967856775433457);
printf("x = ");print_vec_uint64(x);
__m256i y = _mm256_hxor_v2(x);
printf("y = ");print_vec_uint64(y);
uint64_t z = _mm256_hxor_v2_uint64(x);
printf("z = %10lX \n",z);
return 0;
}
int print_vec_uint64(__m256i v){
uint64_t t[4];
_mm256_storeu_si256((__m256i *)t,v);
printf("%10lX %10lX %10lX %10lX \n",t[3],t[2],t[1],t[0]);
return 0;
}
有没有办法对 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];
}
XOR 的 _mm256_hadd_epi32() 直接模拟的实现看起来像这样：
#include <immintrin.h>
template<int imm> inline __m256i _mm256_shuffle_epi32(__m256i a, __m256i b)
{
return _mm256_castps_si256(_mm256_shuffle_ps(_mm256_castsi256_ps(a), _mm256_castsi256_ps(b), imm));
}
inline __m256i _mm256_hxor_epi32(__m256i a, __m256i b)
{
return _mm256_xor_si256(_mm256_shuffle_epi32<0x88>(a, b), _mm256_shuffle_epi32<0xDD>(a, b));
}
int main()
{
__m256i a = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
__m256i b = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 7, 8);
__m256i c = _mm256_hxor_epi32(a, b);
return 0;
}
如评论中所述，最快的代码很可能使用标量运算，在整数寄存器中执行所有操作。您需要做的就是提取四个打包的 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。如果这准确地反映了您的需要（标量 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
（我在第一次发布这个答案后在睡觉的路上想到了这个，并计划回来更新答案，但我看到
当然，如果你想在整数寄存器中使用它，你只需要一个简单的 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 shuffles/permutes/extracts 更少，这意味着开销更少。因此，我可能还不得不食言，标量代码是最快的实现。但这实际上取决于您在做什么以及说明如何 scheduled/interleaved.
如果水平 xor 函数的输入已经在
一个 AVX 寄存器，即你的 t 是一些 SIMD 计算的结果。
否则，标量代码可能会更快，正如@Cody Gray 已经提到的那样。
通常，您可以在大约 log_2(SIMD_width) 'steps' 内执行水平 SIMD 操作。
在这种情况下，一步是 'shuffle/permute' 和 'xor'。这比@Cody Gray 的 _mm256_hxor 函数稍微高效：
__m256i _mm256_hxor_v2(__m256i x)
{
__m256i x0 = _mm256_permute2x128_si256(x,x,1); // swap the 128 bit high and low lane
__m256i x1 = _mm256_xor_si256(x,x0);
__m256i x2 = _mm256_shuffle_epi32(x1,0b01001110); // swap 64 bit lanes
__m256i x3 = _mm256_xor_si256(x1,x2);
return x3;
}
编译为：
vperm2i128 , %ymm0, %ymm0, %ymm1
vpxor %ymm1, %ymm0, %ymm0
vpshufd , %ymm0, %ymm1
vpxor %ymm1, %ymm0, %ymm0
如果你想在标量寄存器中得到结果：
uint64_t _mm256_hxor_v2_uint64(__m256i x)
{
__m256i x0 = _mm256_permute2x128_si256(x,x,1);
__m256i x1 = _mm256_xor_si256(x,x0);
__m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);
__m256i x3 = _mm256_xor_si256(x1,x2);
return _mm_cvtsi128_si64x(_mm256_castsi256_si128(x3)) ;
}
编译为：
vperm2i128 , %ymm0, %ymm0, %ymm1
vpxor %ymm1, %ymm0, %ymm0
vpshufd , %ymm0, %ymm1
vpxor %ymm1, %ymm0, %ymm0
vmovq %xmm0, %rax
完整测试代码：
#include <stdio.h>
#include <x86intrin.h>
#include <stdint.h>
/* gcc -O3 -Wall -m64 -march=broadwell hor_xor.c */
int print_vec_uint64(__m256i v);
__m256i _mm256_hxor_v2(__m256i x)
{
__m256i x0 = _mm256_permute2x128_si256(x,x,1);
__m256i x1 = _mm256_xor_si256(x,x0);
__m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);
__m256i x3 = _mm256_xor_si256(x1,x2);
/* Uncomment the next few lines to print the values of the intermediate variables */
/*
printf("3...0 = 3 2 1 0\n");
printf("x = ");print_vec_uint64(x );
printf("x0 = ");print_vec_uint64(x0 );
printf("x1 = ");print_vec_uint64(x1 );
printf("x2 = ");print_vec_uint64(x2 );
printf("x3 = ");print_vec_uint64(x3 );
*/
return x3;
}
uint64_t _mm256_hxor_v2_uint64(__m256i x)
{
__m256i x0 = _mm256_permute2x128_si256(x,x,1);
__m256i x1 = _mm256_xor_si256(x,x0);
__m256i x2 = _mm256_shuffle_epi32(x1,0b01001110);
__m256i x3 = _mm256_xor_si256(x1,x2);
return _mm_cvtsi128_si64x(_mm256_castsi256_si128(x3)) ;
}
int main() {
__m256i x = _mm256_set_epi64x(0x7, 0x5, 0x2, 0xB);
// __m256i x = _mm256_set_epi64x(4235566778345231, 1123312566778345423, 72345566778345673, 967856775433457);
printf("x = ");print_vec_uint64(x);
__m256i y = _mm256_hxor_v2(x);
printf("y = ");print_vec_uint64(y);
uint64_t z = _mm256_hxor_v2_uint64(x);
printf("z = %10lX \n",z);
return 0;
}
int print_vec_uint64(__m256i v){
uint64_t t[4];
_mm256_storeu_si256((__m256i *)t,v);
printf("%10lX %10lX %10lX %10lX \n",t[3],t[2],t[1],t[0]);
return 0;
}