Per qualche strlen in più come ottimizzare la strlen in C - pt.1

El Indio: Dove vai?
Il Monco: A dormire. Quando devo sparare la sera prima vado a letto presto.

Sapete bene che Sergio Leone è molto amato in questo blog. Per qualche dollaro in più era l'unico che non avevo ancora citato della trilogia del dollaro (gli altri due sono qui e qui), quindi è venuto il suo momento. Oggi parleremo della strlen() e mi raccomando: andate a dormire presto solo per scrivere del buon codice la mattina seguente, e non per fare quello che riesce meglio al Monco...

...sono venuto qui per scrivere del buon Software...

Veniamo al dunque: la strlen() è una funzione molto semplice, che esegue un compito semplice (restituire la lunghezza di una stringa), e infatti si può scrivere, letteralmente, in quattro linee di codice. Vediamo la versione riportata sul magico K&R:

int strlen(char *s)
{
    char *p = s;
    while (*p != '\0')
        p++;

    return p - s;
}

Questa versione, semplicissima e perfetta (e ci mancherebbe solo, visti i mitici autori!) va benissimo ed è soddisfacente nel 99% dei casi, a maggior ragione se compilata con ottimizzazione. Ma... se dovessimo fare un uso intensivo della strlen(), magari per misurare stringhe enormi, sarebbe sufficiente? Beh, secondo gli estensori delle varie libc disponibili, la strlen() deve essere implementata con algoritmi un po' più complicati di quello visto sopra, garantendo (effettivamente) prestazioni elevatissime a patto di pagare il prezzo di usare un codice complicato (e difficile da leggere) per una operazione veramente semplice. Si potrebbe fare una disquisizione molto filosofica sull'argomento e, se andate a rileggervi un mio vecchio post, vi sarà chiaro ciò che penso al riguardo.

Però... ecco, bisogna distinguere tra il codice di libreria (come la libc) e il codice applicativo: il primo si suppone che verrà usato da molti utenti per svariati progetti su molte piattaforme, quindi si presume, giustamente, che sia ottimizzato al massimo e, pertanto, leggibilità e manutenibilità diventano problemi secondari. Il codice applicativo, invece, deve essere scritto bene e deve essere efficiente (ci mancherebbe solo!), ma con un occhio di riguardo anche a leggibilità e manutenibilità, perché una applicazione, spesso, viene toccata e ritoccata nel tempo e da più programmatori (...quindi occhio a quello che c'è scritto sotto il titolo del blog qua sopra: è la dichiarazione della filosofia del blog, e cade a pennello in questo caso...).

Alla fine della fiera, le super-ottimizzazioni sono sicuramente raccomandabili per le piccole funzioni di uso frequente (come quelle della famiglia str, ad esempio), e a maggior ragione quando possono trattare volumi elevati di dati (come stringhe e/o blocchi di memoria molto grandi). In alcuni casi queste funzioni possono essere addirittura inlineate e/o scritte in assembler. Invece, per il "codice normale" è meglio seguire le indicazioni di uno molto più bravo di me che disse, qualche annetto fa:

"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, torniamo al punto: la strlen() che usiamo tutti i giorni è, quasi sempre, super-ottimizzata. Vediamo, quindi, alcuni esempi reali:
   
implementazione in 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);
}

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

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

Come avrete notato sono tutte abbastanza più complicate della versione K&R, perché, invece di effettuare un semplice test a 0 un byte alla volta, effettuano il test su 4 bytes alla volta (usando un algoritmo tipo quello descritto in ZeroInWord): evidentemente questo sistema moltiplica la velocità di ricerca del fine stringa, permettendo un notevole risparmio di tempo per stringhe molto grandi. I codici FreeBSD e glibc sono ben commentati (ho lasciato quasi tutti i commenti originali) e, a prima vista, si nota che la versione FreeBSD è un po' più compatta della versione glibc. La vera sorpresa è la versione della musl libc che è veramente geniale: non è molto più lunga della implementazione del K&R! Ricordatevi della musl (che ho gia citato qui a proposito dei C11 Threads): è veramente una notevole alternativa alla glibc per i sistemi Linux embedded, visto che compattezza e efficienza sono i suoi segni distintivi.

Per oggi può bastare, nella seconda parte del post vi proporrò un programma che ho scritto per eseguire un benchmark di un po' di implementazioni della strlen(): ci sarà quella di default del sistema (Linux, nel mio caso, e uno si aspetterebbe che usa la versione glibc, ma... sorpresa in arrivo!) e poi ci saranno, ovviamente, le quattro di questo post (K&R, FreeBSD, glibc e musl). Vi anticipo che i risultati del test sono sorprendenti e, per spiegarli, vi proporrò una sesta (ancora più sorprendente) versione della strlen() che dovrebbe risolvere il dubbio su cosa usa in realtà Linux quando chiamiamo la strlen(). E, anche se so che non vedete l'ora di sapere quale è la sesta versione, vi raccomando (come al solito) di non trattenere il respiro nell'attesa...

Ciao e al prossimo post!