为什么strcmp比我的函数快那么多？

Question

我编写了一个函数，Str::Compare，基本上是另一种方式重新编写的strcmp。 在比较这两个函数时，在循环中重复500'000'000次，strcmp执行得太快了，大约x750倍。

这段代码是在启用了-Os参数的C库中编译的：

int Str::Compare(char* String_1, char* String_2)
{
    char TempChar_1, TempChar_2;

   do
   {
        TempChar_1 = *String_1++;
        TempChar_2 = *String_2++;
   } while(TempChar_1 && TempChar_1 == TempChar_2);

   return TempChar_1 - TempChar_2;
}

那个函数的执行时间是3.058秒，而strcmp只需0.004秒。

为什么会这样呢？

这是我实现基准测试循环的方式：

int main()
{
     char Xx[] = {"huehuehuehuehuehuehuehuehuehuehuehuehuehue"},
          Yy[] = {"huehuehuehuehuehuehuehuehuehuehuehuehuehue"};
     for(int i = 0; i < 500000000; ++i)
         Str::Compare(Xx, Yy);
}

编辑：在测试我编写的一些代码时，我进行了优化，大大提高了Str::Compare 的速度。如果之前 strcmp 速度快x750倍，现在只有x250倍。以下是新代码：

int Str::Compare(char* String_1, char* String_2)
{
     char TempChar_1, TempChar_2, TempChar_3;

     while(TempChar_1 && !TempChar_3)
     {
          TempChar_1 = *String_1++;
          TempChar_2 = *String_2++;
          TempChar_3 = TempChar_1 ^ TempChar_2;
     }

     return TempChar_1 - TempChar_2;
}

新的执行时间为0.994秒。

- EnryFan

---

为什么不直接使用 while(*str1++ == *str2++); 呢？ - SwiftMango

因为那段代码是这个函数最低效的实现。 - EnryFan

1. 改编后的Str::Compare版本不好-在初始化之前就使用了TempChar_3。
2. 由VS2010生成的原函数代码几乎与strcmp一样快。
3. 很难用简单的实现方式击败大规模优化的函数（甚至是内置函数）。

- Roman R.

请解释一下，为什么这段代码与标准的strcpy函数相似？据我所知。 - SwiftMango

while(*str_1 && *str_1++ == *str_2++); 这是正确的形式。但这种方式更慢，因为处理器必须每次解析指针的地址，从而导致性能损失。 - EnryFan

Answer 1

我对此很好奇，于是编写了一个测试程序：

#include <string.h>

compare(char* String_1, char* String_2)
{
    char TempChar_1,
         TempChar_2;

   do
   {
        TempChar_1 = *String_1++;
        TempChar_2 = *String_2++;
   } while(TempChar_1 && TempChar_1 == TempChar_2);

   return TempChar_1 - TempChar_2;
}


int main(){
    int i=strcmp("foo","bar");
    int j=compare("foo","bar");

    return i;
}

我使用gcc 4.7.3将其编译为汇编代码，命令为gcc -S -Os test.c，生成的汇编如下：

    .file   "test.c"
    .text
    .globl  compare
    .type   compare, @function
compare:
.LFB24:
    .cfi_startproc
    xorl    %edx, %edx
.L2:
    movsbl  (%rdi,%rdx), %eax
    movsbl  (%rsi,%rdx), %ecx
    incq    %rdx
    cmpb    %cl, %al
    jne .L4
    testb   %al, %al
    jne .L2
.L4:
    subl    %ecx, %eax
    ret
    .cfi_endproc
.LFE24:
    .size   compare, .-compare
    .section    .rodata.str1.1,"aMS",@progbits,1
.LC0:
    .string "bar"
.LC1:
    .string "foo"
    .section    .text.startup,"ax",@progbits
    .globl  main
    .type   main, @function
main:
.LFB25:
    .cfi_startproc
    movl    $.LC0, %esi
    movl    $.LC1, %edi
    call    compare
    movl    $1, %eax
    ret
    .cfi_endproc
.LFE25:
    .size   main, .-main
    .ident  "GCC: (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3"
    .section    .note.GNU-stack,"",@progbits

我对x86汇编语言并不是很精通，但据我所知调用strcmp的操作被删除了，而且直接被一个常量表达式所替代（movl $1, %eax）。因此，如果您为测试使用一个常量表达式，那么gcc可能会优化strcmp为一个常量。

- lwi

---

Gcc 也可以用常量替换对 strlen 的调用。 - James

这是G++ 4.8.1在Coliru上将所有内容都简化为一个常量的结果。 - Casey

即使在我的程序中没有使用常量，strcmp也被替换为一个常量表达式。我将努力理解其中的原因。 - EnryFan

Answer 2

当比较性能时，最好将测试函数和测试驱动程序放在单独的编译单元中。将测试函数放在单独的编译单元中，并将其编译为任何您想要的优化级别，但是将测试驱动程序未经优化地编译。否则，您将遇到您在这里看到的问题。

问题在于strcmp比较两个const C风格的字符串。如果您循环500,000,000次以上的strcmp（string_a，string_b），那么优化编译器会聪明地将该循环减少到零，并且也许足够聪明以优化剩余的一个调用strcmp。

您的比较函数接受两个非const字符串。就编译器而言，您的函数可能具有副作用。编译器不知道，因此无法将循环优化为零。它必须生成代码以执行500,000,000次比较。

- David Hammen

---

指针参数的const限定通常不会影响编译器对副作用的推断。只要原始数组对象是非const的，去除const限定是可以的。此外，函数可能调用其他函数导致字符串被修改或别名化。 - Potatoswatter

Answer 3

我相信大多数标准库都是用汇编语言编写的。这可能是你看到标准库比你的代码更快的原因。

- kanagaraj palanisamy

---

这可能是真的，但它无法解释750倍的速度差异。这比解释语言和编译语言之间的差异还要大。通常当我看到如此大的差异时，我会怀疑缓存未命中和可能的分支预测失败等问题。 - Beefster