El Indio: ¿Donde vas?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...
El Manco: A dormir. Cuando tengo que disparar la noche antes me acuesto temprano.
 |
| ...he venido aquí para escribir un buen Software... |
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!
