AVX性能对于按位XOR运算和POP计数较慢 [英] AVX performance slower for bitwise xor op and popcount
问题描述
我对编写一些基于AVX内部函数的代码是新手，所以需要一些帮助来理解我的观察结果。我有两个实现距离计算的方法，这两个方法都接受2个浮点数组及其维度，并返回一个浮点距离。第一种方法计算欧几里得距离
static float
compute_l2Square(const void *pVect1v, const void *pVect2v, const void *qty_ptr) {
float *pVect1 = (float *) pVect1v;
float *pVect2 = (float *) pVect2v;
size_t qty = *((size_t *) qty_ptr);
float __attribute__((aligned(32))) TmpRes[8];
size_t qty16 = qty >> 4;
const float *pEnd1 = pVect1 + (qty16 << 4);
__m256 diff, v1, v2;
__m256 sum = _mm256_set1_ps(0);
while (pVect1 < pEnd1) {
v1 = _mm256_loadu_ps(pVect1);
pVect1 += 8;
v2 = _mm256_loadu_ps(pVect2);
pVect2 += 8;
diff = _mm256_sub_ps(v1, v2);
sum = _mm256_add_ps(sum, _mm256_mul_ps(diff, diff));
v1 = _mm256_loadu_ps(pVect1);
pVect1 += 8;
v2 = _mm256_loadu_ps(pVect2);
pVect2 += 8;
diff = _mm256_sub_ps(v1, v2);
sum = _mm256_add_ps(sum, _mm256_mul_ps(diff, diff));
}
_mm256_store_ps(TmpRes, sum);
return TmpRes[0] + TmpRes[1] + TmpRes[2] + TmpRes[3] + TmpRes[4] + TmpRes[5] + TmpRes[6] + TmpRes[7];
}
第二种方法计算逐位XOR，然后计算1的个数，即汉明距离
static float compute_hamming(const void* __restrict pVect1v,
const void* __restrict pVect2v,
const void* __restrict qty_ptr) {
float *pVect1 = (float *) pVect1v;
float *pVect2 = (float *) pVect2v;
size_t qty = *((size_t *)qty_ptr);
uint64_t __attribute__((aligned(32))) TmpRes[4];
size_t qty16 = qty >> 4;
const float *pEnd1 = pVect1 + (qty16 << 4);
int res = 0;
__m256 diff, v1, v2;
while (pVect1 < pEnd1) {
v1 = _mm256_loadu_ps(pVect1);
pVect1 += 8;
v2 = _mm256_loadu_ps(pVect2);
pVect2 += 8;
diff = _mm256_xor_ps(v1, v2);
_mm256_store_si256( (__m256i*)TmpRes, _mm256_castps_si256(diff));
res += __builtin_popcountll(TmpRes[0]) + __builtin_popcountll(TmpRes[1])
+ __builtin_popcountll(TmpRes[2]) + __builtin_popcountll(TmpRes[3]);
v1 = _mm256_loadu_ps(pVect1);
pVect1 += 8;
v2 = _mm256_loadu_ps(pVect2);
pVect2 += 8;
diff = _mm256_xor_ps(v1, v2);
_mm256_store_si256( (__m256i*)TmpRes, _mm256_castps_si256(diff));
res += __builtin_popcountll(TmpRes[0]) + __builtin_popcountll(TmpRes[1])
+ __builtin_popcountll(TmpRes[2]) + __builtin_popcountll(TmpRes[3]);
}
return res;
}
_mm256_sub_ps替换为_mm256_xor_ps时，L2计算变得更快。
我在Mac OS上进行基准测试，它支持AVX指令。另一个观察结果是使用Just循环的Hamming距离的非AVX实现：sum+=opcount(vec_a[i]^vec_b[i])也给出了与AVX实现类似的数字。我还检查了调用AVX指令和方法是否仅用于健全性检查。
非矢量化实现：
static float compute_hamming(const void* __restrict pVect1,
const void* __restrict pVect2,
const void* __restrict qty_ptr) {
size_t qty = *((size_t *)qty_ptr);
int res = 0;
const float *pVect1LL = (const float *)pVect1;
const float *pVect2LL = (const float *)pVect2;
for (unsigned i = 0; i < qty; i = i + 2) {
if (i + 1 == qty) {
unsigned int v1;
unsigned int v2;
memcpy(&v1, &pVect1LL[i], sizeof(float));
memcpy(&v2, &pVect2LL[i], sizeof(float));
res += __builtin_popcount(v1 ^ v2);
break;
}
uint64_t v1;
uint64_t v2;
memcpy(&v1, &pVect1LL[i], sizeof(float) * 2);
memcpy(&v2, &pVect2LL[i], sizeof(float) * 2);
res += __builtin_popcountll(v1 ^ v2);
}
return res;
}
需要一些帮助和建议来提高性能，因为瓶颈是距离计算方法。
推荐答案
如果您的目标是Haswell和更高版本，则可以使用_mm256_fmadd_ps更快地提高l2Square版本的速度。(还有Piledriver，除非你是在Mac上，而且你可能不关心AMD Hackintosh机器。)
__m256 sum0, sum1累加器来隐藏FP延迟，在减少之前将它们加在一起。(使用an efficient hsum，不仅仅是存储，然后依次对每个元素进行标量相加。)- How to sum __m256 horizontally?特别适用于
__m256。 - Why does mulss take only 3 cycles on Haswell, different from Agner's instruction tables? (Unrolling FP loops with multiple accumulators)-有关使用多个累加器隐藏FP延迟的更多信息：对于较大的问题大小，越多越好。对于迭代次数非常少(小数组)的情况，乱序执行可能会隐藏大量延迟。
如果没有硬件SIMD POP COUNT(AVX512 VPOPCOUNTDQ)，是的当然会更慢，特别是如果编译器没有使用半字节LUT或其他(vpshufb)将这些每个元素的__builtin_popcountll(vec[0]) + ...向量化为SIMD POP COUNT。
这样做实际上是让clang的情况变得更糟，让它执行SIMD XOR，但随后实际上提取到标量，而不是一开始只使用标量XOR和Popcnt；注意ASM中的vpextrq指令。Clang可以在循环中自动向量化__builtin_popcountll(以一种不太糟糕但不太好的方式)，但不是这样的。(实际上，对popcnt执行SIMD XOR，然后对popcnt进行标量抽取并不像我想象的那么糟糕，但只有在使用128位向量的情况下才会如此；请参阅下面Wojciech Mula的git repo中的"；sse-cpu"；结果，即使是针对纯加载的SSE也不会降低太多速度。)
例如，clang使用循环中的YMM向量自动向量化。(Godbolt showing this and your code)遗憾的是，它在处理char*数组时做得很差，并且它只使用unsigned long而不是unsigned数组。
float compute_hamming_autovec(const unsigned long* __restrict a,
const unsigned long* __restrict b,
size_t qty) // by value to keep it simpler, IDK why you'd want to pass this by reference with a void*
{
//const unsigned char *__restrict a = pVect1v, *__restrict b = pVect2v;
unsigned long sum = 0;
for (size_t i=0 ; i<qty*4 ; i++){
unsigned long tmp1=a[i], tmp2=b[i];
//memcpy(&tmp1, a+i, 4);
//memcpy(&tmp2, b+i, 4);
sum += __builtin_popcountll(tmp1 ^ tmp2);
}
return sum; // why are we returning this integer count as a float? IDK
}
对char*中的未对齐的别名安全加载使用memcpy似乎也失败了向量化，或此使用的标量加载的某些变体和xor；您可能需要typdef uint64_t aliasing_unaligned_u64 __attribute__((aligned(4), may_alias))。(我使用aligned(4)是因为假设您将它指向对齐的浮动。)
但是，最好的办法是手动向量化SIMD POP计数。请参阅https://github.com/WojciechMula/sse-popcount/。这也避免了使用类型来生成严格别名安全的代码，这些代码将很好地在float数据数组上自动向量化。
vpshufb ymm/垂直SUM内循环/vpsadbw在qword溢出之前hsum to qword的良好实现更快。例如，对于大小为4096字节的数组，该repo中的Harley Seal SIMD Popcount代码在Skylake上比同一repo中的最佳实现AVX-Lookup和Popcount快约20%。(而且速度是avx2-lookup-Origal的两倍；我忘了有什么区别。)请参见results for clang on Skylake
将popcnt_AVX2_lookup改为两个指针和_mm256_xor_si256很简单，只需将 __m256i vec = _mm256_loadu替换为这些语句即可。或者对Harley-Seal执行同样的操作，如果您的数组足够大以保证它的话；它应该不会造成任何额外的寄存器压力，因为它可以编译为加载/内存-源-vpxor。
还将其展开系数调整为适合您的典型问题大小。
因为小尺寸显然在您的用例中很常见(我最初没有意识到这一点)：
在您的实际用例中需要考虑的另一件事是，您拥有奇怪大小的频率有多高。如果AVX2-lookup只适用于展开系数的倍数，并且需要展开才能跟上，那么您的大量输入可能会在其后备路径上花费大量时间。因此，提高效率很重要，或者有充分理由放弃它，只使用SSE2XOR+标量Popcnt，它可以轻松地执行16字节的粒度，而不会出现问题。这篇关于AVX性能对于按位XOR运算和POP计数较慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
