c++ - sirve - strcpy

¿Por qué es strcmp mucho más rápido que mi función?

Question

Escribí una función, Str::Compare , que es básicamente un strcmp reescrito de otra manera. Mientras se comparan las dos funciones, en un bucle repetido 500''000''000 veces, strcmp ejecuta demasiado rápido, aproximadamente x750 veces más rápido.

Este código fue compilado en una biblioteca de C con el parámetro -Os activo:

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

El tiempo de ejecución de esa función es 3.058s , mientras que strcmp solo 0.004s .

¿Por qué sucede esto?

También así es como implementé el bucle de referencia:

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

Editar : Mientras probaba un código, escribí una optimización que mejoró drásticamente la velocidad de Str::Compare . Si antes, strcmp era x750 veces más rápido ahora solo es x250 . Este es el nuevo código:

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

El nuevo tiempo de ejecución es 0.994s .

Answer 1

Al comparar el rendimiento, he descubierto que es mejor colocar las funciones de prueba y el controlador de prueba en unidades de compilación separadas. Ponga sus funciones de prueba en unidades de compilación separadas, y compílelas al nivel de optimización que desee, pero compile el controlador de prueba sin optimizar. De lo contrario, se encontrará exactamente con el tipo de problema que ha visto aquí.

El problema es que strcmp compara dos cadenas de estilo C const . Si realiza un bucle 500,000,000 veces sobre strcmp(string_a, string_b) , un compilador de optimización será lo suficientemente inteligente como para reducir ese bucle para optimizar ese bucle, y luego tal vez lo suficientemente inteligente como para optimizar la única llamada restante a strcmp .

Su función de comparación toma dos cadenas no constantes. En lo que respecta al compilador, su función puede tener efectos secundarios. El compilador no sabe, por lo que no puede optimizar el bucle a nada. Tiene que generar código para realizar la comparación 500,000,000 veces.

Answer 2

Creo que la mayoría de las bibliotecas estándar están escritas en lenguaje ensamblador. Esa podría ser la razón por la que ves que la biblioteca estándar es más rápida que la tuya.

Answer 3

Tenía curiosidad al respecto y construí un programa de prueba:

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

Lo compilé en el ensamblador con gcc -S -Os test.c usando gcc 4.7.3 que resultó en el siguiente ensamblador:

    .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

No soy tan bueno en el ensamblador x86 pero, por lo que veo, la llamada a strcmp se elimina y simplemente se reemplaza por una expresión constante ( movl $1, %eax ). Por lo tanto, si usa una expresión constante para sus pruebas, gcc probablemente optimice el strcmp a una constante.