搜索一个短排序的双打数组

发布时间：2020-12-16 07:06:43 所属栏目：百科来源：网络整理

导读：我试图通过一个非常短的排序的双精度数组来优化搜索,以找到给定值所属的存储桶.假设数组的大小是8倍,我提出了以下AVX内在函数序列： _data = _mm256_load_pd(array);temp = _mm256_movemask_pd(_mm256_cmp_pd(_data,_value,_CMP_LT_OQ));pos = _mm_popcnt_u3

我试图通过一个非常短的排序的双精度数组来优化搜索,以找到给定值所属的存储桶.假设数组的大小是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,_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,xmm0
jae .L8

[... repeat for all elements of array]

因此需要4条指令来检查1个桶(lea,vmovsd,vucomisd,jae).假设值均匀分布,平均每个值必须检查~3.5个桶.显然,这足以胜过前面列出的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做到这一点.我知道它可以 – 第一个例子中生成的asm就可以了.

除了使用内联asm之外,你有什么想法吗？甚至更好 – 你能建议更快地实施搜索吗？

解决方法

不是真正的答案,但在评论中没有空间.

我针对简单的C实现测试了AVX功能,并得到了完全不同的结果.
我测试的是Windows 7 x64而不是Linux,但生成的代码非常相似.
测试如何进行：
1)我禁用了CPU的SpeedStep.
2)在main()中,我将进程优先级和线程优先级提高到最大值(实时).
3)我对测试功能进行了10M调用以加热CPU – 激活turbo.
4)我调用Sleep(0)以避免上下文切换
5)我调用了__rdtscp来开始测量
6)在一个循环中我调用了AVX查找索引函数或简单的C版本 – 就像你做的那样.其他实现已被注释掉而未被使用.循环大小为10M呼叫.
7)我再次调用__rdtscp来完成基准测试.
8)我打印了刻度/迭代.获取呼叫的平均滴答计数

注意：我将’find index’函数声明为内联,并在反汇编中确认它们是内联的.
您描述的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 };

结果(平均滴答声/ 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在第一次测试时几乎快了x4.另请注意,运行更长时间的测试会显示不同的结果,但每次AVX都具有类似的优势.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!