为什么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，还是出于某些原因这个想法是无意义的？

- user1095108

---

说实话谁在乎呢？使用 std::string::operator== 进行字符串比较。提前检查字符串长度是非常有效的优化方法。另外：使用哪个编译器，哪些设置？ - MSalters

空终止符不会让这变得困难吗？因为编译器无法简单地假设要读取16个字节的字符。可能只有1个。 - ta.speot.is

这就是为什么std::string的O(1)长度测试很棒。你不仅知道是否有比较内容的必要，而且当长度相等时，你还知道需要比较多少内容。因此，我不相信strcmp是出于性能原因而被使用的说法。（GCC的std::string实现已过时，这也可能很重要） - MSalters

strcmp是用于比较两个以NULL结尾的C字符串的函数。因此，如果您想使用SIMD，需要先找到长度以确保没有超出范围。但是要找到长度，您需要在两个字符串中将每个字符与NULL进行比较。因此，在您比较C字符串中的每个字符与NULL之前，strcmp将返回一个结果，而您将加载SIMD指令。 - JustAnotherCurious

实际上， std::string 在进行任何更改时都会存储字符串的长度。因此，如果在所有地方都使用 std::string 进行比较，可能会更快。 - RamblingMad

Answer 1

在SSE2实现中，编译器应该如何确保没有超出字符串结尾的内存访问？它必须先知道长度并且这需要扫描字符串以获取终止零字节。如果您扫描字符串的长度，则已完成大部分strcmp函数的工作。因此，使用SSE2没有好处。然而，英特尔在SSE4.2指令集中添加了用于处理字符串的指令。这些指令处理终止零字节问题。有关它们的详细信息，请阅读此博客文章：http://www.strchr.com/strcmp_and_strlen_using_sse_4.2。

- Nils Pipenbrinck

---

我立即尝试使用“-msse4.2”进行编译，生成了相同的机器代码。好在我并没有完全错，它是可以完成的。 - user1095108

它不必确保没有超出字符串结尾的内存访问。它只需确保未在字符串部分存在的页面上发生内存访问，这要容易得多。 - harold

@Zboson：你怎么知道你比较的对象不是堆分配的，而且正好在页面的末尾，使得超出 '\0' 的任何访问都会立即引发页错误？你怎么知道系统首先使用基于页面的内存保护，而且永远会使用呢？ - DevSolar

@DevSolar，你可以安全地做出这些假设，并且不能使用对齐读取进入下一页。 - harold

这是一个虚假的论点。优化的C库strcmp可以使用SIMD。然而，对于两个可能相对错位的指针来说，要安全地执行这个操作就比较困难了。请参见在x86和x64上同一页内读取缓冲区末尾是否安全？。答案：在ASM中是可以的，在C中因为读取对象外部的UB而存在风险。编译器直接发出汇编代码，因此它知道什么是安全的。 - Peter Cordes

Answer 2

在这种情况下，GCC使用内置的strcmp。如果您想要使用glibc版本，请使用-fno-builtin。但是您不应该假设GCC的内置版本或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段之后添加了16个字节到.bss段中。有关更多详细信息，请参见asmlib手册中的第1.7节“字符串指令和安全预防措施”。

- Z boson

---

一次比较16个字节真的很赞，即使你需要检查空值和实际字符串。美妙之处在于，一旦你编写了这段代码，就可以在新程序中永久使用并获益。 - Surt

@Surt，您能再详细解释一下您的意思吗？您是说通用版本可以做得更好，还是说 SSE4.2 版本是正确的选择？ - Z boson

我认为非SSE循环可以通过在开始之前从一个指针中减去另一个指针，然后使用索引寻址模式来改进，或者这种优化在新处理器上没有帮助吗？ - supercat

@supercat，我不知道。从理论上讲，我们需要考虑延迟和吞吐量以及需要多少个周期。例如，如果一个端口始终需要两个周期，而其余端口只需要一个周期，则在另一个端口添加另一个指令可能没有任何区别。这可以使用IACA进行检查。但是我从未对strcmp进行过分析，所以我只知道我读到的内容。 - Z boson

一个字节一个字节的循环肯定不是最优的！glibc的sse2 strcmp 检查页面交叉，然后使用非对齐加载。当然，它是完全安全的，永远不会从不包含任何字符串部分的页面中读取，因为在标准库中使用其他方式是不可接受的。如果您可以安排跳过这些检查，则可以实现更少的开销，但它看起来相当合理。它使用pcmpeqb和pminub来检查非匹配或0（字符串结尾）。 - Peter Cordes

顺便提一下，为什么启用GCC优化后，此代码使用strlen会慢6.5倍？ 基本上是相同的GCC错误，即在-O1时内联缓慢的repe scasb导致长字符串灾难。该错误现已得到修复：GCC调用libc函数。（它们使用pcmpeqb或AVX2版本，而不是pcmpistri。**pcmpistri对于strlen或strcmp并不比SSE2更快**。） - Peter Cordes

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的代码。如果通过间接跳转调度该方法，则无法进行此类优化。

- supercat

---

虽然你说的听起来很有道理，但你没有提供任何证据表明“但在前16个字节不匹配的情况下，仅从逐字符比较开始会更有效率。”实际上，当我查看SSE4.2和_asmlib_中通用函数的主循环的序言和尾声时，它们几乎是相同的。即使对于小于或等于16个字节的数组，我也不会惊讶SSE4.2版本永远不会比通用版本慢。 - Z boson

@Zboson：我不知道SSE 4.2的新增内容；字符串比较代码可以从早期的SSE函数中受益，但效果不会太大。如果库代码只为4.2编译，我可以看到字符串函数作为潜在的“无条件胜利”，但如果代码必须在执行它们之前检查其可用性，则这样的检查将在不支持它们的处理器上造成100％的损失（我了解仍然相当多），即使在支持它们的处理器上，当字符串在第一个字符上不同时，也可能不会取得优势。 - supercat

使用CPU分派程序，strcmp函数只需要在第一次调用时检查CPUID。之后的每个调用都将直接跳转到SSE4.2或通用版本。这就是asmlib的工作原理。因此，只有在第一次调用时才会有开销。您还可以调用一个初始化函数，将所有要替换的函数放入库中，使所有函数指针指向适当的版本。 - Z boson

@Zboson：CPU分派程序将添加一个间接跳转；我知道这比以前小得多，但我不知道有多小。此外，strcmp()足够小，一个积极的内联优化器可能会尝试解决它（如果定义了一个头文件使其能够这样做）。请参见上面的编辑。 - supercat

这是一个很好的观点。实际上，GCC已经在OPs示例中内联了strcmp。正如我在我的答案中所说，有趣的是对内联、glibc和asmlib方法进行分析和比较。不过我暂时不会去做... - Z boson

Answer 4

制作一个 SSE2 版本的 strcmp 对我来说是一个有趣的挑战。 我不太喜欢编译器内置函数，因为会导致代码膨胀，所以我决定选择自动向量化方法。我的方法基于模板，并将 SIMD 寄存器近似为不同大小的字数组。

我尝试编写自动向量化实现，并使用 GCC 和 MSVC++ 编译器进行测试。

所以，我学到了：
1. GCC 的自动向量化器很好（很棒？）
2. MSVC 的自动向量化器比 GCC 差（无法向量化我的打包函数）
3. 所有编译器都拒绝生成 PMOVMSKB 指令，这真的很遗憾

结果：
在线 GCC 编译的版本通过 SSE2 自动向量化获得了 ~40% 的性能提升。在我的 Windows 机器上，使用 Bulldozer 架构的 CPU 自动向量化的代码比在线编译器的代码更快，并且结果与 strcmp 的本地实现相匹配。但这个想法最好的一点是，同样的代码可以编译成任何 SIMD 指令集，至少在 ARM 和 X86 上是如此。

注：
如果有人找到使编译器生成 PMOVMSKB 指令的方法，则整体性能应该会显著提高。

GCC 的命令行选项：-std=c++11 -O2 -m64 -mfpmath=sse -march=native -ftree-vectorize -msse2 -march=native -Wall -Wextra

Links:
Source code compiled by Coliru online compiler
Assembly + Source code (Compiler Explorer)

@PeterCordes，感谢您的帮助。

- Roman

---

只使用godbolt短链接进行评论，因为完整链接可能会失效。当没有相关字符限制时，只需创建不在帖子文本中显示的完整链接即可。（godbolt短链接已在内部使用goo.gl。哦，这很奇怪，我认为短链接按钮可能已经损坏了。我几乎从不使用它。） - Peter Cordes

看起来 g++ 在 -O3（其中包括 -ftree-vectorize）实际上没有自动向量化您的代码。我只看到一个 pcmpeqd，它用于生成一个全为1的向量以存储到堆栈中。我看到了很多逐字节复制和比较，以及位域测试。如果这比内置的 strcmp 更快，我想知道它有多糟糕... - Peter Cordes

@PeterCordes 我已经在我的帖子中更新了Compiler Explorer的链接，麻烦你去看一下。 - Roman

你为什么没加上-Wall -Wextra呢？不过没错，这就是我在上一条评论中所评论的汇编代码。它进行了向量化比较，但随后又将每个比较结果字节中的一个位逐一打包到一个通用寄存器中。 - Peter Cordes

让我们在聊天室中继续此讨论。 - Roman

Answer 5

我认为对于那些计算量极小的库函数而言，使用SIMD版本并没有什么意义。我想像 strcmp, memcpy等函数实际上是由内存带宽而非CPU速度所限制。

- Frerich Raabe

---

如果数组不适合缓存，它只受内存带宽的限制。您可以在不受内存带宽限制的紧密内部循环中使用memcpy或strcmp。 - Z boson

《优化手册》在“memcpy实现技术”方面花费了相当多的时间，关注Ivy Bridge及其后续CPU上的性能优化。其中，“REP STOSB”触发了微代码高性能“memset”，但启动开销比128b或256b宽的SSE / AVX实现要高。请参见3.7.5节，或搜索memcpy。 CPUID特征位用于ERMSB（增强Rep Movsb和StosB）。 - Peter Cordes

Answer 6

这取决于你的实现方式。在MacOS X上，像memcpy、memmove和memset这样的函数有根据你使用的硬件进行优化的实现（同一次调用将根据处理器执行不同的代码，这是在启动时设置的）；这些实现使用SIMD技术，对于大量数据（兆字节级别），还使用了一些相当花巧的技巧来优化缓存使用。据我所知，strcpy和strcmp没有类似的实现。

说服C++标准库使用这种代码很困难。

- gnasher729

---

你能展示一些针对strcmp的优化Mac反汇编吗？ - user1095108

是的，根据Agner Fog的研究，MacOS X版本相当不错，但Linux和Windows版本效率低下。因此，MacOS X汇编可能很有趣。 - Z boson

Answer 7

AVX 2.0实际上会更快

编辑：这与寄存器和IPC有关

您可以使用大量的SIMD指令和16个32字节的寄存器，而不是依赖于一个大型指令，好吧，在UTF16中，它为您提供了265个字符！

几年后，使用avx512可将其加倍！

AVX指令还具有高吞吐量。

根据此博客：https://blog.cloudflare.com/improving-picohttpparser-further-with-avx2/

今天在最新的Haswell处理器上，我们拥有强大的AVX2指令。 AVX2指令操作32字节，大多数布尔/逻辑指令的吞吐量为每条指令的0.5周期。这意味着我们可以在执行单个PCMPESTRI需要的时间内执行大约22个AVX2指令。为什么不试试呢？

编辑 2.0 SSE/AVX单元是电源门控的，混合使用SSE和/或AVX指令与常规指令涉及上下文切换，会带来性能惩罚，而使用strcmp指令则不会。

- Avlin

---

虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。仅有链接的答案可能会因为链接页面的更改而失效。 - Paul R

Answer 8

我不明白为什么要“优化”像strcmp这样的函数。

在应用任何形式的并行处理之前，您需要找到字符串的长度，这将强制您至少读取一次内存。顺便说一下，您可以使用数据即时执行比较。

如果您想快速处理字符串，您需要使用专门的工具，例如有限状态机（对于解析器，可以考虑使用lexx）。

至于C++的std::string，由于许多原因，它们效率低下且速度慢，因此在比较中检查长度的收益微乎其微。

- kuroi neko

---

我以前使用过lex和bison，它们生成了很多代码。虽然这些代码通常是有效的C++，但效率呢？我有点怀疑。总之，在我的问题中解析并不是相关话题。 - user1095108

更好的性能 => 更低的能源消耗 => 更长的电池使用时间 => 使环保意识强的客户感到满意。 - Surt

std::string 在某些方面可能效率不高，但用于确定字符串长度很好。 - phuclv

C++的狂热者群体一如既往地对异端说三道四...Surt的评论完全不相关；你应该待在你的市场部门，让程序员发言，伙计。至于你，OP先生，如果你害怕lexx生成的代码，那么SIMD指令会让你感到恐惧。掌握它们要困难得多（我的意思是使用它们很容易，但编写实际运行更好的代码则是另外一个完全不同的故事）。 - kuroi neko