La strlen tenía un precio cómo optimizar la strlen en C - pt.2

cnel. Mortimer: ¿Que te pasa, muchacho?
El Manco: Nada, viejo. Que no me salia la cuenta. Ajora está bien.

Ok, estamos listos para la segunda parte de La muerte tenía un precio (oops... ¿pero no era La strlen tenia un precio?). Como bien decía El Manco, un buen programador siempre hace bien las cuentas, por lo que en este post analizaremos los resultados de un benchmark que escribí ad hoc para este propósito (... sí, lo sé, también le había prometido una sorpresa... La habrá...).

...nada viejo... la strlen es un poco lenta hoy...

Entonces, en el benchmark compararemos los resultados (de velocidad, por supuesto) de las cuatro versiones de strlen() vistos en el último post, o sea: K&R, FreeBSD, glibc, y musl libc y nuestro punto de referencia serà, evidentemente, la strlen() por defecto del sistema, también porque uno de nuestros objetivos es averiguar qué usa Linux, que es, como siempre, el nuestro sistema de referencia. Veamos el código del benchmark:

#include <stdint.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>

// prototipos locales
size_t strlenKaR(const char *s);
size_t strlenFreeBSD(const char *str);
size_t strlenGlibc(const char *str);
size_t strlenMusl(const char *s);

int main(int argc, char* argv[])
{
    static char s[1000000000];
    clock_t t_start;
    size_t  result;
    clock_t t_end;
    double  t_passed;
    int i;

    // escribo el string de test
    for (i = 0; i < sizeof(s); i++) {
        if (i % 2)
            s[i] = 'a';
        else
            s[i] = 'u';
    }
    s[i - 1] = 0; // terminador

    // ejecuta con strlen() de default y calcula tiempo
    t_start  = clock();
    result   = strlen(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlen(s)        = %zu - Tiempo transcurrido: %f segundos\n", result, t_passed);

    // ejecuta con strlenKaR() y calcula tiempo
    t_start  = clock();
    result   = strlenKaR(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlenKaR(s)     = %zu - Tiempo transcurrido: %f segundos\n", result, t_passed);

    // ejecuta con strlenFreeBSD() y calcula tiempo
    t_start  = clock();
    result   = strlenFreeBSD(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlenFreeBSD(s) = %zu - Tiempo transcurrido: %f segundos\n", result, t_passed);

    // ejecuta con strlenGlibc() y calcula tiempo
    t_start  = clock();
    result   = strlenGlibc(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlenGlibc(s)   = %zu - Tiempo transcurrido: %f segundos\n", result, t_passed);

    // ejecuta con strlenMusl() y calcula tiempo
    t_start  = clock();
    result   = strlenMusl(s);
    t_end    = clock();
    t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("strlenMusl(s)    = %zu - Tiempo transcurrido: %f segundos\n", result, t_passed);

    return 0;
}

Como habreis visto, hemos creado una cadena enorme (¿y si no que test seria?) y la hemos llenado con una secuencia de "au" (...bueno, se hubiera podido llenar con cualquier cosa, pero ese día me desperté con un "au" en la cabeza imposible de aguantar...). hemos agregado el terminador de string requerido y llamado en secuencia a las diversas strlen() usando un método confiable (con clock()) para verificar el tiempo de actividad real (un método que ya hemos usado en un post anterior). Las strlen() son, por supuesto, las de el último post (los códigos los podéis encontrar ahí), renombrados como strlenKaR(), strlenFreeBSD(), strlenGlibc() y strlenMusl(), para distinguirlos de la única función no local, que es la strlen() de librería. Como se puede ver en la versión K&R he modificado el prototipo (y la definición) para uniformarlo al de la strlen() estándar.

Ahora veamos los resultados del benchmark con compilación normal (-O0, que es el valor predeterminado y se puede omitir) y con una optimización considerable (-O2, que es la que se usa normalmente en casos reales):

usando gcc -O0

aldo@mylinux:~/blogtest$ ./strlens 
strlen(s)        = 999999999 - Tiempo transcurrido: 0.054814 secondi
strlenKaR(s)     = 999999999 - Tiempo transcurrido: 2.173237 secondi
strlenFreeBSD(s) = 999999999 - Tiempo transcurrido: 0.308145 secondi
strlenGlibc(s)   = 999999999 - Tiempo transcurrido: 0.252466 secondi
strlenMusl(s)    = 999999999 - Tiempo transcurrido: 0.304617 secondi

usando gcc -O2

aldo@mylinux:~/blogtest$ ./strlens 
strlen(s)        = 999999999 - Tiempo transcurrido: 0.164509 secondi
strlenKaR(s)     = 999999999 - Tiempo transcurrido: 0.395466 secondi
strlenFreeBSD(s) = 999999999 - Tiempo transcurrido: 0.091599 secondi
strlenGlibc(s)   = 999999999 - Tiempo transcurrido: 0.102967 secondi
strlenMusl(s)    = 999999999 - Tiempo transcurrido: 0.091931 secondi

Los resultados son realmente interesantes. La strlenKaR() es, como se esperaba, mucho más lenta que las versiones que utilizan el algoritmo descrito en ZeroInWord e, incluso compilando con -O2, es más lenta que las otras compilada con -O0, aunque, sin embargo, la diferencia entre las versiones optimizadas son menores que las diferencias entre las no optimizadas. Repito, estamos en un caso extremo: el string analizado es realmente enorme, y con cadenas "normales" la diferencia de rendimiento sería mucho menor, sin embargo, está claro que las versiones con algoritmo especial son mejores y son justamente preferidas, especialmente recordando que "las súper-optimizaciones son ciertamente recomendables para pequeñas funciones de uso frecuente" (...y esta es una miá autocitación de mi último post...). Las tres funciones strlenFreeBSD(), strlenGlibc y strlenMusl() tienen rendimiento excelentes y similares, ya que utilizan el mismo algoritmo, y la versión de glibc prevalece ligeramente compilando con -O0, mientra que compilando con -O2 la mejor es la musl con la FreeBSD muy cerca.

Y llegamos a la parte sorprendente: parece que la strlen() por defecto es claramente más rápido que todos los demás compilando con -O0 mientras que pierde la ventaja al compilar con -O2. Así que, al menos sin optimizaciones, en mi sistema Linux la strlen() predeterminada no es la de la glibc (como uno esperaría) y es algo diferente. ¿Y qué es, entonces? Intentemos comentar la línea "#include <string.h>" y recompilar, y veamos qué nos dice el compilador...

aldo@mylinux:~/blogtest$ gcc -c -O0 strlens.c -o strlens.o
strlens.c: In function 'main':
strlens.c:35:16: warning: implicit declaration of function 'strlen'
     result   = strlen(s);
                ^
strlens.c:35:16: warning: incompatible implicit declaration of built-in function 'strlen'
strlens.c:35:16: note: include '<string.h>' or provide a declaration of 'strlen'

ya està, parece que  la strlen() predeterminada es una función implícita del compilador gcc, y por lo tanto no se usa la versión de librería y, además, "...En algunos casos, estas funciones incluso pueden estar inlineadas y/o escritas en ensamblador..." (...y esta es otra autocitación de mi último post...). Para confirmar todo esto, he buscado una versión en ensamblador de la strlen() y la he encontrado aquí en stackoverflow. He modificado ligeramente el código (el original no devolvia el resultado correctamente) y he modificado el benchmark para usarlo. El código es el siguiente:

#include <immintrin.h>

// una posible implementación en assembler de la strlen() implicita en gcc
size_t strlenAsm(const char* src)
{
    size_t result = 0;
    unsigned int tmp1;
    __m128i zero = _mm_setzero_si128(), vectmp;

    // A pointer-increment may perform better than an indexed addressing mode
    asm(
        "\n.Lloop:\n\t"
            "movdqu   (%[src], %[res]), %[vectmp]\n\t" // result reg is used as the loop counter
            "pcmpeqb  %[zerovec], %[vectmp]\n\t"
            "pmovmskb %[vectmp], %[itmp]\n\t"
            "add      $0x10, %[res]\n\t"
            "test     %[itmp], %[itmp]\n\t"
            "jz  .Lloop\n\t"

        "bsf %[itmp], %[itmp]\n\t"
        "add %q[itmp], %q[res]\n\t"                // q modifier to get quadword register.
        : [res] "+r"(result), [vectmp] "=&x" (vectmp), [itmp] "=&r" (tmp1)
        : [zerovec] "x" (zero)  // There might already be a zeroed vector reg when inlining
            , [src] "r" (src)
            , [dummy] "m" (*(const char (*)[])src) // this reads the whole object, however
                                                   // long gcc thinks it is not needed
                                                   // because of the dummy input
    );

    return result - tmp1 - 1;
}

y los resultados se vuelven así (con -O0, y con -O2 el resultado de strlenAsm() no cambia ya que, al estar en ensamblador, se compila por separado y sin optimizaciones, como se puede ver en las siguientes líneas): 

usando gcc -O0

aldo@mylinux:~/blogtest$ gcc -c strlenasm.c -o strlenasm.o
aldo@mylinux:~/blogtest$ gcc -c -O0 strlens.c -o strlens.o
aldo@mylinux:~/blogtest$ gcc strlens.o strlenasm.o -o strlens
aldo@mylinux:~/blogtest$ ./strlens 
strlen(s)        = 999999999 - Tiempo transcurrido: 0.054087 secondi
strlenKaR(s)     = 999999999 - Tiempo transcurrido: 2.163937 secondi
strlenFreeBSD(s) = 999999999 - Tiempo transcurrido: 0.306909 secondi
strlenGlibc(s)   = 999999999 - Tiempo transcurrido: 0.251383 secondi
strlenMusl(s)    = 999999999 - Tiempo transcurrido: 0.305544 secondi
strlenAsm(s)     = 999999999 - Tiempo transcurrido: 0.061378 secondi

Aquí, el resultado canta: la versión implícita de gcc está escrita en ensamblador (y repito: no es en absoluto una opción muy extraña para pequeñas funciones de librería de uso frecuente). Sigue estando el misterio de por qué compilando con -O2 (mirar los resultados más arriba) la strlen() predeterminada parece que ya no es la versión implícita, ya que su rendimiento empeora. Este es un misterio que me prometo resolver tarde o temprano.

(...pero, ya que estamos en Agosto, ciertamente durante las vacaciones lo olvidaré, generalmente mientras estoy en la playa pienso en otras cosas...)
 
¡Hasta el próximo post!