En los títulos y los textos vais a encontrar unas cuantas citaciones cinematográficas (y si, soy un cinéfilo). Si no os interesan podéis fingir no verlas, ya que no son fundamentales para la comprensión de los post...

Este blog es la versión en Español de mi blog en Italiano L'arte della programmazione in C. Espero que mis traducciones sean comprensibles...

domingo, 9 de septiembre de 2018

Lost in Translation
cómo cerrar un Blog de C

Bob: Tengo que irme, pero no voy a dejar que eso se interponga entre nosotros.
No sé si habéis visto Lost in Traslation, la bella película de Sofia Coppola. Bien, exactamente como Bob, el protagonista, yo también me he perdido en las traducciones.
...tengo que irme...
Me explico: como veis en la descripción del blog (aquí arriba) siempre escribo los post en italiano, que es mi lengua materna, y luego los traduzco al español. Pues, últimamente he notado algo un poco molesto: que el trabajo de la traducción me cuesta más que el de escribir el post. Supongo que esto se debe principalmente a dos factores: 1) soy un perfeccionista y 2) mi estilo de escritura no es plano y lineal. ¿Entonces qué pasa? Pasa que me cuesta mucho traducir a un español brillante lo que trato de escribir en un italiano brillante. Yo frecuentemente cito en los post dichos populares, frases extrañas, proverbios, etc. Y cuando traduzco, me doy cuenta de que a veces el significado y el ritmo original se pierde, y dado que soy un perfeccionista no consigo aceptarlo.

Pero aquí viene lo peor: últimamente me he dado cuenta de que, inconscientemente, también me limito en la versión italiana porque pienso "...este párrafo es demasiado largo, mejor corto unas cuantas frases porque si no luego tardaré demasiado en traducir... " o bien "... este doble significado es muy comprensible en italiano pero será muy difícil encontrar un equivalente en español, así que mejor lo quito...". Cuesta de creer pero incluso mientras escribo este post de despedida me está pasando lo mismo.

Conclusión: después de una larga reflexión, he decidido cerrar la versión en español de mi blog. Pero el blog continúa en italiano, así que si lo que realmente os interesa es sólo el código de los programas y las soluciones que propongo, bueno, eso es Lenguaje C y es universal: seguramente conseguiréis sacar algo interesante incluso si el post está en italiano (o al menos eso espero).

Saludos a todos, ¡ha sido un placer!

sábado, 11 de agosto de 2018

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!

sábado, 21 de julio de 2018

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

El Indio: ¿Donde vas?
El Manco: A dormir. Cuando tengo que disparar la noche antes me acuesto temprano.
Ya sabéis que Sergio Leone es muy querido en este blog. La muerte tenía un precio era el único film que aún no había mencionado de la trilogía del dólar (los otros dos están aquí y aquí), así que ha llegado su momento. Hoy vamos a hablar sobre la strlen() y os recomiendo: ir a dormir temprano solo por escribir un buen código a la mañana siguiente, y no por hacer lo que le sale  mejor a a El Manco...
...he venido aquí para escribir un buen Software...
Vamos al grano: la strlen() es una función muy simple, que realiza una tarea simple (devuelve la longitud de una cadena) y, de hecho, se puede escribir, literalmente, en cuatro líneas de código. Veamos la versión que se muestra en el mágico K&R:
int strlen(char *s)
{
    char *p = s;
    while (*p != '\0')
        p++;

    return p - s;
}
Esta versión, muy simple y perfecta (¡y solo faltaria, con esos autores legendarios!) funciona muy bien y es satisfactoria en el 99% de los casos, incluso más si se compila con optimización. Pero... si tuviéramos que hacer un uso intensivo de la strlen(), tal vez para medir enormes cadenas, ¿sería suficiente? Bueno, según los desarrolladores de las diversas libc disponibles, strlen() debe implementarse con algoritmos un poco más complicados que el visto anteriormente, asegurando (efectivamente) un rendimiento muy alto pero pagando el precio de usar un código complicado (y difícil de leer) para una operación realmente simple. Se podría hacer una disquisición muy filosófica sobre el tema y, si vais a volver a leer un mio antiguo post, os quedará claro lo que pienso al respecto.

Pero... vale, debemos distinguir entre el código de librería (como libc) y el código de aplicación: se supone que el primero es utilizado por muchos usuarios para varios proyectos en muchas plataformas, por lo que se supone, con razón, que tine que estar optimizado al máximo y, por lo tanto, la legibilidad y facilidad de mantenimiento se convierten en problemas secundarios. El código de aplicación, sin embargo, debe estar bien escrito y debe ser eficiente (¡solo faltaría!), pero cuidando también la legibilidad y la facilidad de mantenimiento, ya que una aplicación, a menudo, es tocada y retocada en el tiempo por varios programadores (...así que mirar lo que está escrito bajo el título del blog aquí arriba: es la declaración de la filosofía del blog, y cae perfecta en este caso...).

Resumiendo, las súper-optimizaciones son ciertamente recomendables para pequeñas funciones de uso frecuente (como las de la familia str, por ejemplo), y aún más cuando pueden manejar grandes volúmenes de datos (como cadenas y/o bloques de memoria muy grandes). En algunos casos, estas funciones incluso pueden estar inlineadas y/o escritas en ensamblador. En cambio, para el "código normal" es mejor seguir las indicaciones de uno mucho mejor que yo, que dijo hace unos años:
"The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming" (Donald Knuth, "Computer Programming as an Art", 1974).
Ok, volvamos al argumento del post: la strlen() que usamos todos los días está, casi siempre, súper-optimizada. Veamos, por lo tanto, algunos ejemplos reales:
   
implementación en FreeBSD
/* Magic numbers for the algorithm */
static const unsigned long mask01 = 0x0101010101010101;
static const unsigned long mask80 = 0x8080808080808080;

#define LONGPTR_MASK (sizeof(long) - 1)

// Helper macro to return string length if we caught the zero byte.
#define testbyte(x)               \
    do {                          \
        if (p[x] == '\0')         \
            return (p - str + x); \
    } while (0)

size_t strlen(const char *str)
{
    const char *p;
    const unsigned long *lp;
    long va, vb;

    /* Before trying the hard (unaligned byte-by-byte access) way
     * to figure out whether there is a nul character, try to see
     * if there is a nul character is within this accessible word
     * first.
     * p and (p & ~LONGPTR_MASK) must be equally accessible since
     * they always fall in the same memory page, as long as page
     * boundaries is integral multiple of word size.
     */
    lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK);
    va = (*lp - mask01);
    vb = ((~*lp) & mask80);
    lp++;
    if (va & vb)
        /* Check if we have \0 in the first part */
        for (p = str; p < (const char *)lp; p++)
            if (*p == '\0')
                return (p - str);

    /* Scan the rest of the string using word sized operation */
    for (; ; lp++) {
        va = (*lp - mask01);
        vb = ((~*lp) & mask80);
        if (va & vb) {
            p = (const char *)(lp);
            testbyte(0);
            testbyte(1);
            testbyte(2);
            testbyte(3);
            testbyte(4);
            testbyte(5);
            testbyte(6);
            testbyte(7);
        }
    }

    /* NOTREACHED */
    return (0);
}
implementación en glibc
/* Return the length of the null-terminated string STR.  Scan for
   the null terminator quickly by testing four bytes at a time. */
size_t strlen(const char *str)
{
    const char *char_ptr;
    const unsigned long int *longword_ptr;
    unsigned long int longword, himagic, lomagic;

    /* Handle the first few characters by reading one character at a time.
       Do this until CHAR_PTR is aligned on a longword boundary. */
    for (char_ptr = str; ((unsigned long int)char_ptr & (sizeof(longword) - 1)) != 0; ++char_ptr)
        if (*char_ptr == '\0')
            return char_ptr - str;

    /* All these elucidatory comments refer to 4-byte longwords,
       but the theory applies equally well to 8-byte longwords. */
    longword_ptr = (unsigned long int *) char_ptr;

    /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
    the "holes."  Note that there is a hole just to the left of
    each byte, with an extra at the end:
        bits:  01111110 11111110 11111110 11111111
        bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
    The 1-bits make sure that carries propagate to the next 0-bit.
    The 0-bits provide holes for carries to fall into. */
    himagic = 0x80808080L;
    lomagic = 0x01010101L;
    if (sizeof (longword) > 4) {
        /* 64-bit version of the magic. */
        /* Do the shift in two steps to avoid a warning if long has 32 bits. */
        himagic = ((himagic << 16) << 16) | himagic;
        lomagic = ((lomagic << 16) << 16) | lomagic;
    }
    if (sizeof (longword) > 8)
        abort();

    /* Instead of the traditional loop which tests each character,
       we will test a longword at a time.  The tricky part is testing
       if *any of the four* bytes in the longword in question are zero. */
    for (;;) {
        longword = *longword_ptr++;
        if (((longword - lomagic) & ~longword & himagic) != 0) {
            /* Which of the bytes was the zero?  If none of them were, it was
               a misfire; continue the search. */
            const char *cp = (const char *) (longword_ptr - 1);
            if (cp[0] == 0)
                return cp - str;
            if (cp[1] == 0)
                return cp - str + 1;
            if (cp[2] == 0)
                return cp - str + 2;
            if (cp[3] == 0)
                return cp - str + 3;
            if (sizeof (longword) > 4) {
                if (cp[4] == 0)
                    return cp - str + 4;
                if (cp[5] == 0)
                    return cp - str + 5;
                if (cp[6] == 0)
                    return cp - str + 6;
                if (cp[7] == 0)
                    return cp - str + 7;
            }
        }
    }
}
implementación en musl libc
#define ALIGN (sizeof(size_t))
#define ONES ((size_t)-1/UCHAR_MAX)
#define HIGHS (ONES * (UCHAR_MAX/2+1))
#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS)

size_t strlen(const char *s)
{
    const char *a = s;
    const size_t *w;

    for (; (uintptr_t)s % ALIGN; s++)
        if (!*s)
            return s-a;

    for (w = (const void *)s; !HASZERO(*w); w++)
        ;

    for (s = (const void *)w; *s; s++)
        ;

    return s-a;
}
Como habreis visto, son bastante más complicados que la versión K&R, porque en lugar de realizar una simple test en 0 un byte a la vez, realizan el test en 4 bytes a la vez (usando un algoritmo como el descrito en ZeroInWord): obviamente este sistema multiplica la velocidad de búsqueda del final de la cadena, lo que permite un considerable ahorro de tiempo para cadenas muy grandes. Los códigos FreeBSD y glibc están bien comentados (he dejado casi todos los comentarios originales) y, a primera vista, notamos que la versión de FreeBSD es un poco más compacta que la versión glibc. La verdadera sorpresa es la versión de musl libc que es realmente brillante: ¡no es mucho más larga que la implementación de K&R! Acordaros de musl (que ya he mencionado aquí hablando sobre los C11 Threads): es verdaderamente una alternativa notable a glibc para sistemas Linux embedded, ya que la implementacion compacta y la eficiencia son sus señas de identidad.

Para hoy puede ser suficiente, en la segunda parte del post os propondré un programa que he escrito para realizar un benchmark de algunas implementaciones de strlen(): habrá la que usa por defecto el sistema (Linux, en mi caso, y uno se esperaría el uso de la versión glibc, pero... ¡hay una sorpresa!) y luego, por supuesto, estaran las cuatro de este post (K&R, FreeBSD, glibc y musl). Os anticipo que los resultados del test son sorprendentes y, para explicarlos, os propondré una sexta versión (aún más sorprendente) de strlen() que debería resolver la cuestión de qué es lo que realmente usa Linux cuando llamamos la strlen(). Y, aunque sé que ya estais ansiosos de saber cuál es la sexta versión, os recomiendo (como siempre) de no aguantar la respiración en la espera...

¡Hasta el próximo post!