搜索一个短的双精度浮点数排序数组

Question

搜索一个短的双精度浮点数排序数组

cgccassemblycompiler-optimizationmicro-optimization

4

我正在尝试通过一组非常短的已排序的双精度数组来优化搜索，以定位给定的value所属的 bucket。假设数组大小为8个双精度数，我已经想出了以下AVX指令序列：

_data = _mm256_load_pd(array);
temp  = _mm256_movemask_pd(_mm256_cmp_pd(_data, _value, _CMP_LT_OQ));
pos   = _mm_popcnt_u32(temp);
_data = _mm256_load_pd(array+4);
temp  = _mm256_movemask_pd(_mm256_cmp_pd(_data, _value, _CMP_LT_OQ));
pos  += _mm_popcnt_u32(temp);

出乎意料（我没有指令延迟规格在我的脑海中..），gcc为以下C循环生成了更快的代码：

for(i=0; i<7; ++i) if(array[i+1]>=value) break;

这个循环编译后变成了非常高效的代码：

lea ecx, [rax+1]
vmovsd  xmm1, QWORD PTR [rdx+rcx*8]
vucomisd    xmm1, xmm0
jae .L7

lea ecx, [rax+2]
vmovsd  xmm1, QWORD PTR [rdx+rcx*8]
vucomisd    xmm1, xmm0
jae .L8

[... repeat for all elements of array]

所以，每检查一个存储桶需要4个指令(lea, vmovsd, vucomisd, jae)。假设value均匀分布，平均而言，我需要检查约3.5个存储桶才能找到相应的value。显然，这足以超越前面列出的AVX代码。

现在，在一般情况下，数组可能大于8个元素。如果我像这样编写C循环：

for(i=0; u<n-1; i++) if(array[i+1]>=value) break;

我会尽力为您翻译以下内容：

我获得了循环体的以下指令序列：

.L76:
mov eax, edx
.L67:
cmp eax, esi
jae .L77
lea edx, [rax+1]
mov ecx, edx
vmovsd  xmm1, QWORD PTR [rdi+rcx*8]
vucomisd    xmm1, xmm0
jb  .L76

我可以让gcc展开循环，但每个元素的指令数量比具有常量边界的循环更大，代码会变慢。此外，我不明白在vmovsd中使用额外的rcx寄存器进行寻址的原因。

我可以手动修改循环的汇编代码，使其类似于第一个示例，这样做确实可以更快。

.L76:
cmp edx, esi            # eax -> edx
jae .L77
lea edx, [rdx+1]        # rax -> rdx
vmovsd  xmm1, QWORD PTR [rdi+rdx*8]
vucomisd    xmm1, xmm0
jb  .L76

但是我似乎无法让gcc实现它。我知道它可以 - 第一个示例中生成的汇编代码是正确的。

您有没有其他想法可以不使用内联汇编来实现它？或者更好的是 - 您能否建议一种更快的搜索实现方式？

- angainor

+1 但是“我可以告诉gcc展开循环...在这种情况下，代码会变慢”，针对你特定的处理器。我认为你在优化方面有点过于前进，风险是只匹配测试机器的架构（可能在其他方面性能较差）。当然，如果你不是为嵌入式系统优化某些东西，其中CPU是固定的且随时间不会改变。 - Adriano Repetti

@Adriano 我表述不够准确 - 对于一般边界的循环展开代码比针对常数边界生成的代码要慢。我不认为这与平台有很大关系 - 只是少了两个指令。或者我还漏掉了其他什么？ - angainor

@angainor，现在，在一般情况下，数组可能比8个元素更大。正如你所提到的，它是一个排序数组，使用O(log(n))搜索可以（稍微）提高性能。 - starrify

@starrify 谢谢，当然我已经为大数组做了这个。我有一个八叉树结构 - 这就是为什么我需要在8个元素的数组中进行搜索。此外，我还需要在树叶中进行一般的短搜索。 - angainor

你能分享一下你是如何初始化_value的吗？另外，你尝试过为后半部分使用不同的指针吗？这可以让编译器使用更多的寄存器。 - egur

显示剩余3条评论

2个回答

0

您可以尝试整数比较。双精度浮点数比较等同于相同位数的int64_t比较，但NaN除外。这样可能会更快。CPU拥有比SIMD更多的整数执行单元。只需在函数参数中发送double*并接收int64_t*即可。

- Aleksandr Pakhomov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- egur · Accepted Answer

虽然不是一个答案，但评论区没有足够的空间。

我对AVX函数进行了测试，并与简单的C实现进行了比较，结果完全不同。我在Windows 7 x64上进行了测试，而不是Linux，但生成的代码非常相似。测试过程如下： 1）我禁用了CPU的SpeedStep。 2）在main（）中，我将进程优先级和线程优先级提高到最大（实时）。 3）我运行了1000万次对被测试函数的调用以加热CPU-激活Turbo。 4）我调用Sleep（0）以避免上下文切换 5）我调用__rdtscp开始测量 6）在循环中，我调用AVX查找索引函数或简单的C版本-就像你所做的那样。其他实现被注释掉并未使用。循环大小为1000万次。 7）我再次调用__rdtscp来完成基准测试。 8）我打印ticks / iterations。以获得每个调用的平均滴答数

注意：我已将“查找索引”函数都声明为内联函数，并确认它们已被内联处理。AVX函数和您描述的C函数不完全相同，C函数返回基于零的索引，而AVX函数返回基于1的索引。在我的系统上，AVX函数每次迭代花费1.1个周期，而C函数每次迭代花费4.4个周期。

我无法强制MSVC编译器使用超过ymm寄存器:(

所使用的数组：

double A[8] = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 };

结果 (平均ticks/iter)： value = 0.3 (index = 2): AVX: 1.1 | C: 4.4 value = 0.5 (index = 3): AVX: 1.1 | C: 11.1 value = 0.9 (index = 7): AVX: 1.1 | C: 18.1

如果AVX函数被更正为返回pos-1，则速度将慢50%。您可以看到AVX函数在恒定时间内工作，而平凡的C循环函数性能取决于您要查找的索引。

使用clock()进行计时并运行100M得出类似的结果，第一个测试中AVX几乎快了4倍。还要注意，运行更长时间的测试会显示不同的结果，但每次AVX都保持类似的优势。