是什么阻止编译器优化手写的memcmp()?

d6kp6zgx  于 2023-10-16  发布在  其他
关注(0)|答案(3)|浏览(97)

给出:

#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

  • 是什么阻止编译器进一步优化它?
  • 我做了什么妨碍优化的事情吗?
iyr7buue

iyr7buue1#

Data-dependent branching defeats auto-vectorization in GCC/Clang(但不是经典ICC)。在第一次迭代之前(在抽象机器中)不能计算出trip-count,所以GCC和clang甚至不会尝试使用pcmpeqb/pmovmskb来处理大尺寸。(对于大输入,这是在x86-64上实现memcmp的有效方法。)
显然,这是一个很难解决的问题,因为GCC/Clang已经有15到20年没有解决这个问题了(从现在开始,GCC第一次开始做自动向量化)。
另请参阅 * how to auto vectorization array comparison function * -将其编写为一个循环,该循环计数不匹配并始终接触所有元素,可以给予自动向量化。(或减少而不是减少)。但这对于像4字节这样的小的固定大小没有帮助。对于第一个字节有差异的1GiB memcmp来说,完全删除early-out是一场灾难。(一个好的SIMD memcmp,比如glibc的SSE 2/AVX 2版本,可能会在向量比较结果上每隔64到128字节进行一次分支。)
显然也没有习语识别,至少这种写作方式没有。(memcpy)GCC和clang可以将简单的复制循环转换为call memcpycall memset,或者这些函数的内联扩展。所以如果你自己写,你需要-fno-builtin-memcpy,否则你的函数会变成一个对自身的调用。为实验取一个不同的名字。)
将其编写为无条件接触所有字节的循环可以给予自动向量化,但在GCC的内部可能不会被识别为memcmp习惯用法。我认为这对于有小问题的好代码来说是必要的,比如我们想要一个单一的dword cmp

**编译器必须避免引入segfaults,因为它会在抽象机器停止的地方进行读取。**如果void *data指向一个保存'z'的1字节缓冲区,则您的手动循环在抽象机器中具有定义良好的行为。阅读所有4个字节将超过缓冲区的末尾。

但是memcmp是UB,如果数组的任何部分是不可访问的,所以编译器 * 可以 * 接触所有4个字节,而不检查早期或指针对齐。(* Can std::memcmp read any bytes past the first difference? * 是的,与您的循环不同。)
(In x86-64 asm,超过结尾可能会进入未Map的页面,导致segfault,违反as-if规则。* Is it safe to read past the end of a buffer within the same page on x86 and x64? * -是的,但仅在同一页内。对于strlenstrchr的对齐加载,这是可以解决的问题,但是对于使用不同对齐的指针对strcmp进行矢量化,这是一个更大的障碍。
我没有比较函数args中的两个未知指针,而是将test_data调用者改为将指针传递给两个全局数组char foo[4], bar[4];,编译器肯定知道这两个数组都是可读的。但那没有帮助,所以还是没有。

k7fdbhmy

k7fdbhmy2#

正如所编写的那样,编译器无法针对您的特殊情况优化实现,因为它无法确定如果第一个字节与'a'不同,则是否允许阅读data指向的第二个字节,并以此类推。memcmp在C标准中被指定为具有未定义的行为,如果两个指针指向的任何n字节都不可访问。编译器和/或标准库假设4个字节是可访问的,并且目标体系结构上支持非对齐访问。
如果你修改你的实现来读取所有4个字节,假设目标架构的非对齐访问是可以的,gcc和clang都会像预期的那样优化test_datagenerating 3 instructions

#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;
}
q9rjltbz

q9rjltbz3#

除了已经说过的内容之外,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,这就很好。在这种情况下,这些库通常会突然中断,所以如果您自己构建库,请遵循库的构建说明。请参阅本答案中关于glibc的strlen的部分:“* 为什么作为glibc的一部分这是安全的,而不是其他的。*”
但这个答案中的代码实际上是安全的; memcpy对于混叠和对齐是安全的。

相关问题