为什么strcmp没有SIMD优化？

Question

我试图在x64计算机上编译这个程序:

#include <cstring>

int main(int argc, char* argv[])
{
  return ::std::strcmp(argv[0],
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really really really"
    "really really really really really really really long string"
  );
}

我编译它像这样:

g++ -std=c++11 -msse2 -O3 -g a.cpp -o a

但最终的反汇编是这样的:

   0x0000000000400480 <+0>:     mov    (%rsi),%rsi
   0x0000000000400483 <+3>:     mov    $0x400628,%edi
   0x0000000000400488 <+8>:     mov    $0x22d,%ecx
   0x000000000040048d <+13>:    repz cmpsb %es:(%rdi),%ds:(%rsi)
   0x000000000040048f <+15>:    seta   %al
   0x0000000000400492 <+18>:    setb   %dl
   0x0000000000400495 <+21>:    sub    %edx,%eax
   0x0000000000400497 <+23>:    movsbl %al,%eax
   0x000000000040049a <+26>:    retq 

为什么没有使用SIMD？我想可以一次比较16个字符.我应该编写自己的SIMD strcmp,还是出于某种原因这是一个荒谬的想法？

Answer 1

在SSE2实现中,编译器应该如何确保在字符串末尾没有发生内存访问？它必须首先知道长度,这需要扫描字符串以查找终止零字节.

如果你扫描字符串的长度,你已经完成了strcmp函数的大部分工作.因此使用SSE2没有任何好处.

但是,英特尔在SSE4.2指令集中添加了字符串处理指令.这些处理终止零字节问题.有关他们的好文章,请阅读此博客文章:

http://www.strchr.com/strcmp_and_strlen_using_sse_4.2

Answer 2

在这种情况下,GCC使用内置strcmp.如果你想让它使用glibc使用的版本-fno-builtin.但你不应该认为GCC的内置版本strcmp或glibc的实现strcmp是有效的.我从经验中知道,GCC的内置memcpy和glibc memcpy并不像它们那样高效.

我建议你看看Agner Fog的asmlib.他在汇编中优化了几个标准库函数.看文件strcmp64.asm.它有两个版本:没有SSE4.2的CPU的通用版本和带有SSE4.2的CPU版本.这是SSE4.2版本的主循环

compareloop:
        add     rax, 16                ; increment offset
        movdqu  xmm1, [rs1+rax]        ; read 16 bytes of string 1
        pcmpistri xmm1, [rs2+rax], 00011000B ; unsigned bytes, equal each, invert. returns index in ecx
        jnbe    compareloop            ; jump if not carry flag and not zero flag

对于他写的通用版本

这是一个非常简单的解决方案.使用SSE2或任何复杂的东西都没有太大的收获

这是通用版本的主循环:

_compareloop:
        mov     al, [ss1]
        cmp     al, [ss2]
        jne     _notequal
        test    al, al
        jz      _equal
        inc     ss1
        inc     ss2
        jmp     _compareloop 

我会比较GCC的内置strcmp,GLIBC strcmp和asmlib的性能strcmp.您应该查看反汇编以确保获得内置代码.例如,GCC memcpy不使用大于8192的内置版本.

编辑:关于字符串长度,Agner的SSE4.2版本读取超出字符串的15个字节.他认为这很少是一个问题,因为没有写任何东西.这对堆栈分配的数组来说不是问题.对于静态分配的数组,它可能是内存页边界的问题.为了解决这个问题,他在.data部分后面的.bss部分增加了16个字节.有关详细信息,请参阅asmlib的manaul中的1.7字符串说明和安全预防措施部分.

Answer 3

当设计用于C的标准库string.h时,在处理大量数据时最有效的方法的实现对于少量数据将是合理有效的,反之亦然.虽然可能存在一些字符串比较方案,但是复杂使用SIMD指令可以产生比"天真实现"更好的性能,在许多现实场景中,比较的字符串在前几个字符中会有所不同.在这种情况下,天真的实现可以产生比"更复杂"的方法花费更少的时间来决定应该如何执行比较的结果.请注意,即使SIMD代码一次能够处理16个字节并且在检测到不匹配或字符串结束条件时停止,它仍然需要执行额外的工作,相当于在扫描的最后16个字符上使用朴素方法.如果许多16字节的组匹配,则能够快速扫描它们可能有益于性能.但是在前16个字节不匹配的情况下,以字符逐个比较开始会更有效.

顺便提一下,"天真"方法的另一个潜在优势是可以将其内联定义为标题的一部分(或者编译器可能认为自己具有关于它的特殊"知识").考虑:

int strcmp(char *p1, char *p2)
{
  int idx=0,t1,t2;
  do
  {
    t1=*p1; t2=*p2;
    if (t1 != t2)
    {
      if (t1 > t2) return 1;
      return -1;
    }
    if (!t1)
      return 0;
    p1++; p2++;
  } while(1);
}
...invoked as:
if (strcmp(p1,p2) > 0) action1();
if (strcmp(p3,p4) != 0) action2();

虽然该方法有点大,但在第一种情况下,内联可以允许编译器消除代码以检查返回值是否大于零,并在第二种情况下消除检查是否为t1大于t2.如果通过间接跳转调度方法,则不可能进行这种优化.