Почему strcmp намного быстрее, чем моя функция?

Я написал функцию Str::Compare, которая в основном перезаписывается strcmp по-другому. При сравнении двух функций в цикле, повторяющемся 500'000'000 раз, strcmp выполняется слишком быстро, примерно x750 раз быстрее.

Этот код был скомпилирован в C-библиотеке с активным параметром -Os:

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.058s, а strcmp только 0.004s.

Почему это происходит?

Также я реализовал цикл тестирования:

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

Edit: При тестировании кода, который я написал, и оптимизации, которая значительно улучшила скорость 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.994s.

Ответы

Ответ 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 -S -Os test.c, используя gcc 4.7.3, в результате чего появился следующий ассемблер:

    .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 для константы.

Ответ 2

При сравнении производительности я обнаружил, что лучше всего использовать тестовые функции и тестовый драйвер в отдельных единицах компиляции. Поместите свои тестовые функции в отдельные единицы компиляции и скомпилируйте их на любой уровень оптимизации, который вы хотите, но не скомпилируйте тестовый драйвер. В противном случае вы столкнетесь с той проблемой, которую вы здесь видели.

Проблема заключается в том, что strcmp сравнивает две строки const C-style. Если вы зацикливаете 500 000 000 раз на strcmp(string_a, string_b), оптимизирующий компилятор будет достаточно умным, чтобы уменьшить этот цикл, чтобы оптимизировать этот цикл, а затем, возможно, достаточно умный, чтобы оптимизировать оставшийся вызов до strcmp.

Ваша функция сравнения принимает две неконстантные строки. Что касается компилятора, ваша функция может иметь побочные эффекты. Компилятор не знает, поэтому он не может оптимизировать цикл до нуля. Он должен генерировать код для сравнения 500 000 000 раз.

Ответ 3

Я считаю, что большинство стандартных библиотек написаны на ассемблере. Это может быть причиной того, что стандартная библиотека работает быстрее, чем ваша.