编译器为什么无法优化手写的memcmp()函数？

Question

给定：

#include <string.h>

bool test_data(void *data)
{
    return memcmp(data, "abcd", 4) == 0;
}

编译器可以将其优化为：

test_data:
    cmpl    $1684234849, (%rdi)
    sete    %al
    ret

这很好。但是如果我使用自己的memcmp()（而不是来自<string.h>），编译器无法将其优化为单个cmpl指令。相反，它会这样做：

static int memcmp(const void *s1, const void *s2, size_t n)
{
    const unsigned char *p1 = s1, *p2 = s2;
    size_t i;

    for (i = 0; i < n; i++) {
        int ret = p1[i] - p2[i];
        if (ret)
            return ret;
    }

    return 0;
}

bool test_data(void *data)
{
    return memcmp(data, "abcd", 4) == 0;
}

test_data:
    cmpb    $97, (%rdi)
    jne     .L5
    cmpb    $98, 1(%rdi)
    jne     .L5
    cmpb    $99, 2(%rdi)
    jne     .L5
    cmpb    $100, 3(%rdi)
    sete    %al
    ret
.L5:
    xorl    %eax, %eax
    ret

链接: https://godbolt.org/z/Kfhchr45a

• 编译器为什么无法进一步优化它？
• 我做了什么阻碍了优化吗？

- Ammar Faizi

---

我不确定godbolt是否告诉你的是你所想的。试着添加int main() { return test_data("abcd"); }。它将主函数优化为movl $1, %eax。 - David Wohlferd

@DavidWohlferd：是的，GCC可以在两个输入都是常量时通过循环进行常量折叠。但这不是问题所在；OP想知道编译器是否能够在大小为已知小常数时进行优化。我们只能得到一个完全展开的比较/分支链，与单个双字节cmp相比，这非常糟糕。 - Peter Cordes

虽然没有直接回答你的问题，但编译器通常会为memcmp和memcpy等函数提供特殊的内嵌函数。即使不使用内嵌函数，memcmp通常也会在源代码中以汇编语言编写（例如，在x86架构的glibc源代码中，你会看到memcmp.S而不是memcmp.c）。 - Weijun Zhou

@WeijunZhou：是的，确实如此。除非你使用-fno-builtin选项，否则GCC会将memcmp视为__builtin_memcmp；这就是它如何将其转换为单个cmp指令而不是call memcmp。请注意，memcpy / memcmp的内联扩展与libc.so和glibc源代码中手写的汇编实现完全不同。GCC有自己用于扩展"字符串"函数的模式。（至少在-O1优化级别下）它曾经有时对strlen使用repne scasb，但后来停止了，因为对于大型缓冲区来说速度非常慢。 - Peter Cordes

优化器并不能创造奇迹，它们只是匹配代码中已有的模式而已。你手写的memcp函数的模式不在其中，仅此而已。 - n. m. could be an AI

Answer 1

数据相关分支在GCC/Clang中阻碍了自动向量化（但不包括经典ICC）。在第一次迭代之前无法计算迭代次数（在抽象机器中），因此GCC和clang甚至不会尝试对大尺寸使用pcmpeqb/pmovmskb。（这是在x86-64上用于大输入的高效的memcmp方法。）

显然，这是一个难题，因为在GCC/Clang中已经有15到20年未解决（从GCC首次开始进行自动向量化的时候起）。

另请参阅如何自动向量化数组比较函数 - 将其编写为计算不匹配并始终涉及所有元素的循环可以实现自动向量化。 （或者使用OR归约而不是求和归约）。 但对于像4字节这样的小固定大小，这并没有帮助。 而完全删除提前退出对于具有第一个字节差异的1GiB memcmp来说是一场灾难。 （像glibc的SSE2 / AVX2版本那样的良好SIMD memcmp可能会在矢量比较结果上每64到128字节分支一次。）

---

显然，这种写法也没有成语识别，至少对于这种方式的写法来说是如此。（对于memcpy是有的；GCC和clang可以将简单的复制循环转换为call memcpy或call memset，或者内联展开这些函数。因此，如果你自己编写的话，需要使用-fno-builtin-memcpy，否则你的函数会变成调用自身... 选择一个不同的名称进行实验。）

将其作为一个无条件触及所有字节的循环编写可能会导致自动向量化，但在GCC的内部中可能不会被识别为memcmp的习语。我认为这对于处理小问题（例如我们想要进行单个dword cmp的情况）而言是必要的。

---

编译器在设计中必须避免通过引入超出抽象机器范围的读取来导致段错误。如果`void *data`指向一个包含字符`'z'`的1字节缓冲区，那么您手动编写的循环在抽象机器中具有明确定义的行为。读取所有4个字节将超出缓冲区的末尾。

但是，如果数组的任何部分不可访问，那么`memcmp`就会产生未定义行为，因此编译器可以在不检查提前退出或指针对齐的情况下访问所有4个字节。（与您的循环不同，Can std::memcmp read any bytes past the first difference? 是的。）

（在x86-64汇编中，超出末尾可能会进入一个未映射的页面，导致段错误，违反了as-if规则。在x86和x64上，在同一页内读取超过缓冲区末尾是安全的吗？ - 是的，但只能在同一页内进行。这是你可以通过对strlen和strchr使用对齐加载来解决的问题，但对于具有不同对齐指针的strcmp来说，这是一个更大的障碍。）

不是比较函数参数中的两个未知指针，而是我将您的“test_data”调用者更改为传递指向两个全局数组“char foo[4]，bar[4]”的指针，编译器可以确定这两个数组都是可读的（Godbolt）。但这并没有帮助，所以还是不行。

- Peter Cordes

---

这么讽刺的是，如果我们在找到循环退出条件后仍然保持循环，代码可能会更快？int ret = 0; for (i = 0; i < n; i++) { ret |= p1[i] - p2[i]; } return ret;得到完全不同的代码——也许更高效？两个编译器都展开了循环，而且clang甚至提供了一个pcmpeqb。https://godbolt.org/z/adcG8nPhf - Lundin

@Lundin：是的，尽管从某种角度来看，这并不具有讽刺意味，因为我们真正想要的汇编代码也会比较所有4个字节。使用SSE2时，clang的策略非常糟糕；它没有意识到这只是一个相等比较，所以在将字节解包成32位元素后，实际上会添加负数，就像源代码一样。使用SSE4.1的pmovzxbd加载会好一些：https://godbolt.org/z/xEc1zx7vK 执行pmovzxbd mem, %xmm0 / padd constant, %xmm0 / ptest %xmm0,%xmm0 / setz %al。如果不同位置的不匹配导致了早期退出的分支错误，无分支可能是一个很大的优势。 - Peter Cordes

@Lundin: 使用short ret，GCC也尝试进行自动向量化：https://godbolt.org/z/TsqjMP5oP （而且即使这意味着需要2个向量来表示8字节，clang仍然扩展为32位元素）。除非我们还将返回类型更改为short，否则clang使用pmovzxbw，而GCC在OR约简中使用4个pshufb的操作。哎呀。https://godbolt.org/z/f5c4dq3oY - Peter Cordes

Answer 2

编译器无法针对您的特殊情况进行优化实现，因为它无法确定在第一个字节与 'a' 不同时，是否允许读取由 data 指向的第二个字节，以及后续字节的情况。根据 C 标准规定，如果两个指针所指向的任何 n 个字节中有任何一个是不可访问的，则 memcmp 的行为是未定义的。编译器和/或标准库假设4个字节是可访问的，并且目标架构支持非对齐访问。

如果您修改实现以读取所有4个字节，并假设目标架构支持非对齐访问，那么无论是 gcc 还是 clang 都将按预期进行优化 test_data，生成3条指令。

#include <string.h>
#include <arpa/inet.h>

static int my_memcmp(const void *s1, const void *s2, size_t n)
{
    const unsigned char *p1 = s1, *p2 = s2;
    while (n >= sizeof(unsigned)) {
        unsigned u1, u2;
        memcpy(&u1, p1, sizeof u1);
        memcpy(&u2, p2, sizeof u2);
        if (u1 != u2)
            return htonl(u1) < htonl(u2) ? -1 : 1;
        n -= sizeof(unsigned);
        p1 += sizeof(unsigned);
        p1 += sizeof(unsigned);
    }
    for (size_t i = 0; i < n; i++) {
        int ret = p1[i] - p2[i];
        if (ret)
           return ret;
    }
    return 0;
}

- chqrlie

---

这将导致严格别名未定义行为，除非源数据是unsigned或int类型。此外，未经告知编译器的情况下，不对齐访问是不可接受的，无论目标架构如何。通常在与汇编语言兼容的目标平台上可能会正常运行，但这并不安全。请使用memcpy（也称为__builtin_memcpy）来执行4字节不对齐且符合严格别名规则的加载，或者使用GNU C中的 typedef uint32_t aliasing_u32 __attribute__((aligned(1), may_alias))，具体示例参见Why does unaligned access to mmap'ed memory sometimes segfault on AMD64?。 - Peter Cordes

关于这个问题，你也可以参考为什么glibc的strlen函数需要如此复杂才能运行得快？，它提供了一个类似的使用案例（逐字节处理字符串函数）。 - Peter Cordes

通过执行memcpy(&u1, s1, 4)可以避免严格别名问题，而且这不会对性能产生太大影响。 - Lundin

@Lundin：确实，这就是我在第一条评论中的意思。根据我的经验，在具有非对齐加载的目标上，GCC和Clang完全可以识别出这样的memcpy。在像MIPS这样的目标上，非对齐加载是特殊的，它们可能会调用库函数将数据复制到堆栈上的本地变量，但对于指向__attribute__((aligned(1)))类型定义的指针，可能会采取其他操作。哦，也许最近有所改变；MIPS64el GCC将这些memcpy内联为lwl/lwr：https://godbolt.org/z/bjPzGjGP4（除非你使用`-march=mips64r6`编译，那么只是`lw`）。 - Peter Cordes

@PeterCordes：我更新了代码，以消除严格别名违规。新代码仍然可以在针对x86_64的两个编译器上编译为简单的3条指令，只要启用了优化选项-O2。对于-O0生成的代码效率太低效了 :) - chqrlie

没错，就是这样。如果你在GNU C中真的关心-O0代码生成，你可以使用一个__attribute__((aligned(1),may_alias))版本的unsigned或unsigned long的typedef，从指向该类型的指针加载，但当然它仍然会复制到栈上的局部变量，除非你声明它们为register。 - Peter Cordes

Answer 3

除了已经提到的内容之外，一个64位计算机的库实现memcmp可能会尝试在一条指令中进行比较，只要它能推断出数据足够小。

因此，一个针对64位CPU的优化memcmp的天真实现可能如下所示：

static int memcmp1 (const void* s1, const void* s2, size_t n)
{
  if(n>8)
  {
    // call some other function suitable for larger chunks
    // e.g. the loop in chqrlie's answer, preferably using unsigned long
    // I used the real memcmp for illustration purposes here    
    return memcmp(s1,s2,n); 
  }

  uint64_t i1=0;
  memcpy(&i1, s1, n);  // clang manages to optimize a 4-byte write to an 8-byte
  uint64_t i2=0;
  memcpy(&i2, s2, n);
  
  if(i1 < i2)   // assume i1 and i2 are big-endian, unlike on x86-64.
    return -1;  // Use be64toh if you care about < vs >, not just != vs. ==
  if(i2 > i1)
    return 1;
  return 0;
}

https://godbolt.org/z/edjn4hx8h

尽管代码相对简单，但它仍然能生成相当高效的汇编代码。编译器应该在内联memcmp1函数时丢弃调用更复杂函数的选择，因为它在编译时知道数据的大小。gcc在这种情况下未能做到这一点，而clang则成功了，但无论哪种结果看起来都还不错。

至于“适用于较大块的函数”，它可能会首先检查对齐方式，然后将数据开头和结尾的不对齐字节视为特殊情况处理。然后，在x86_64上每次以8字节的方式执行其余的检查。

而且正如我们所指出的，实现这样的库函数而不滥用严格别名可能会很棘手 - 在glibc和类似的函数中有许多明显违反严格别名规定的函数，只要该库不是以严格符合标准C编译的，这是可以接受的。在这种情况下，这些库通常会出现严重故障，因此如果您自己构建它，请遵循该库的构建说明。请参阅this answer about glibc's strlen的一部分：“为什么这在glibc中是安全的，但在其他情况下不安全。”

但是，这个答案中的代码实际上是安全的；memcpy对于别名和对齐是安全的。

- Lundin

---

词汇比较需要将块视为大端整数，如果您关心更大/更小，而不仅仅是相等/不相等。可移植代码应使用GNU的endian.h函数（https://man7.org/linux/man-pages/man3/endian.3.html），具体来说是`be64toh`。 - Peter Cordes

此外，将4个字节复制到8字节的整数中并不是很好；您的Godbolt链接显示GCC实际上通过对堆栈进行双字存储来存储0x64636261，然后通过四字加载重新加载它和4个字节的未初始化垃圾，并导致存储转发停顿。GCC选择从data（s1）进行零扩展的4字节加载，用于将4字节复制到8字节的uint64_t i1中，这是很好的。如果我们使用uint64_t i1=0;，仍然会得到相同的良好代码生成。（在内联到调用者时，为其他临时结果初始化会导致额外的堆栈存储。）Clang生成了良好的汇编代码。 - Peter Cordes

是的，我的错，它们需要被归零、修复。然而，对于结果来说并没有太大关系，无论如何，clang都会给出相同的输出。 - Lundin

“didn't matter much for the outcome”这种说法有点奇怪。我想我们都同意，正确的代码和UB或实现定义行为之间存在很大的区别，只是碰巧在某个编译器中的某种情况下编译成了我们想要的汇编代码，而不是内联到更大的函数中。希望你只是指你不必重写关于编译成高效汇编代码的部分回答，如果这就是你所说的“结果”。（未来的读者请记住，在C语言中，测试不能证明正确性。具有UB的代码可能在某个上下文中偶然工作。） - Peter Cordes

@PeterCordes 在修复之后，clang 生成了相同的机器码，只有 gcc 改变了其行为。 - Lundin