Estaba mirando el strlencódigo aquí y me preguntaba si las optimizaciones utilizadas en el código son realmente necesarias. Por ejemplo, ¿por qué algo como lo siguiente no funcionaría igual de bien o mejor?
unsigned long strlen(char s[]) {
unsigned long i;
for (i = 0; s[i] != '\0'; i++)
continue;
return i;
}
¿No es el código más simple mejor y / o más fácil de optimizar para el compilador?
El código de strlenen la página detrás del enlace se ve así:
/* Copyright (C) 1991, 1993, 1997, 2000, 2003 Free Software Foundation, Inc. This file is part of the GNU C Library. Written by Torbjorn Granlund ([email protected]), with help from Dan Sahlin ([email protected]); commentary by Jim Blandy ([email protected]). The GNU C Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. The GNU C Library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with the GNU C Library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */ #include <string.h> #include <stdlib.h> #undef strlen /* 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 (str) const char *str; { const char *char_ptr; const unsigned long int *longword_ptr; unsigned long int longword, magic_bits, 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. */ magic_bits = 0x7efefeffL; 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. */ magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL; 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 (;;) { /* We tentatively exit the loop if adding MAGIC_BITS to LONGWORD fails to change any of the hole bits of LONGWORD. 1) Is this safe? Will it catch all the zero bytes? Suppose there is a byte with all zeros. Any carry bits propagating from its left will fall into the hole at its least significant bit and stop. Since there will be no carry from its most significant bit, the LSB of the byte to the left will be unchanged, and the zero will be detected. 2) Is this worthwhile? Will it ignore everything except zero bytes? Suppose every byte of LONGWORD has a bit set somewhere. There will be a carry into bit 8. If bit 8 is set, this will carry into bit 16. If bit 8 is clear, one of bits 9-15 must be set, so there will be a carry into bit 16. Similarly, there will be a carry into bit 24. If one of bits 24-30 is set, there will be a carry into bit 31, so all of the hole bits will be changed. The one misfire occurs when bits 24-30 are clear and bit 31 is set; in this case, the hole at bit 31 is not changed. If we had access to the processor carry flag, we could close this loophole by putting the fourth hole at bit 32! So it ignores everything except 128's, when they're aligned properly. */ longword = *longword_ptr++; if ( #if 0 /* Add MAGIC_BITS to LONGWORD. */ (((longword + magic_bits) /* Set those bits that were unchanged by the addition. */ ^ ~longword) /* Look at only the hole bits. If any of the hole bits are unchanged, most likely one of the bytes was a zero. */ & ~magic_bits) #else ((longword - lomagic) & himagic) #endif != 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; } } } } libc_hidden_builtin_def (strlen)
¿Por qué esta versión se ejecuta rápidamente?
¿No está haciendo mucho trabajo innecesario?
c
optimization
glibc
portability
strlen
Carreras de ligereza en órbita
fuente
fuente
sysdepsse usará una implementación de lenguaje ensamblador escrita a mano desde el directorio, en la mayoría de las arquitecturas compatibles de glibc (la arquitectura más utilizada que no tiene un reemplazo es MIPS).Respuestas:
Usted no necesita y que nunca debe escribir código como que - sobre todo si no eres un / proveedor biblioteca estándar C compilador. Es un código utilizado para implementar
strlencon algunos trucos y suposiciones de velocidad muy cuestionables (que no se prueban con afirmaciones ni se mencionan en los comentarios):unsigned longes de 4 u 8 bytesunsigned long longy nouintptr_tunsigned longsAdemás, un buen compilador podría incluso reemplazar el código escrito como
(observe que tiene que ser un tipo compatible con
size_t) con una versión en línea del compilador incorporadostrlen, o vectorice el código; pero es poco probable que un compilador pueda optimizar la versión compleja.La
strlenfunción se describe en C11 7.24.6.3 como:Ahora, si la cadena a la que apuntaba
sestaba en una matriz de caracteres lo suficientemente larga como para contener la cadena y el NUL de terminación, el comportamiento será indefinido si accedemos a la cadena más allá del terminador nulo, por ejemplo enEntonces, la única forma en que C es totalmente portátil / compatible con los estándares para implementar esto correctamente es la forma en que está escrito en su pregunta , a excepción de las transformaciones triviales: puede pretender ser más rápido desenrollando el bucle, etc., pero aún debe hacerse un byte a la vez
(Como han señalado los comentaristas, cuando la portabilidad estricta es una carga excesiva, aprovechar supuestos razonables o seguros no siempre es algo malo. Especialmente en el código que forma parte de una implementación específica de C. Pero hay que entender el reglas antes de saber cómo / cuándo puedes doblarlas).
La
strlenimplementación vinculada primero comprueba los bytes individualmente hasta que el puntero apunta al límite de alineación natural de 4 u 8 bytes delunsigned long. El estándar C dice que acceder a un puntero que no está alineado correctamente tiene un comportamiento indefinido , por lo que esto debe hacerse absolutamente para que el próximo truco sucio sea aún más sucio. (En la práctica, en algunas arquitecturas de CPU que no sean x86, fallará una palabra desalineada o una carga de doble palabra. C no es un lenguaje ensamblador portátil, pero este código lo está usando de esa manera). También es lo que hace posible leer más allá del final de un objeto sin riesgo de fallar en implementaciones donde la protección de memoria funciona en bloques alineados (por ejemplo, páginas de memoria virtual de 4 KB).Ahora viene la parte sucia: el código se rompe la promesa y lee 4 u 8 de 8 bits bytes a la vez (una
long int), y utiliza un truco poco con la adición sin firmar averiguar rápidamente si había alguna cero bytes dentro de los 4 u 8 bytes: utiliza un número especialmente diseñado para que el bit de transporte cambie los bits que captura una máscara de bits. En esencia, esto se resolvería si alguno de los 4 u 8 bytes en la máscara son ceros supuestamente más rápidos que lo que sería recorrer cada uno de estos bytes. Finalmente, hay un bucle al final para descubrir qué byte fue el primer cero, si lo hay, y devolver el resultado.El mayor problema es que en
sizeof (unsigned long) - 1el tiempo de espera desizeof (unsigned long)los casos será leer más allá del final de la cadena - sólo si el byte nulo está en el último byte de acceder (es decir, en ascendente hacia la izquierda el más significativo, y en big endian el menos significativo) , no accede a la matriz fuera de los límites!El código, aunque se usa para implementar
strlenen una biblioteca estándar de C, es un código incorrecto . Tiene varios aspectos definidos por la implementación e indefinidos y no debe usarse en ningún lugar en lugar del sistema provistostrlen. Cambié el nombre de la funciónthe_strlenaquí y agregué lo siguientemain:El búfer se dimensiona cuidadosamente para que pueda contener exactamente la
hello worldcadena y el terminador. Sin embargo, en mi procesador de 64 bitsunsigned longes de 8 bytes, por lo que el acceso a la última parte excedería este búfer.Si ahora compilo con
-fsanitize=undefinedy-fsanitize=addressejecuto el programa resultante, obtengo:Es decir, sucedieron cosas malas.
fuente
Ha habido muchas suposiciones (ligeramente o totalmente) erróneas en los comentarios sobre algunos detalles / antecedentes para esto.
Estás viendo la implementación optimizada de respaldo C optimizada de glibc. (Para ISA que no tienen una implementación de asm escrita a mano) . O una versión anterior de ese código, que todavía está en el árbol fuente de glibc. https://code.woboq.org/userspace/glibc/string/strlen.c.html es un navegador de códigos basado en el árbol glibc git actual. Aparentemente, todavía lo usan algunos objetivos de glibc convencionales, incluido MIPS. (Gracias @zwol).
En ISA populares como x86 y ARM, glibc usa asm escritos a mano
Por lo tanto, el incentivo para cambiar cualquier cosa sobre este código es menor de lo que piensas.
Este código de bithack ( https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord ) no es lo que realmente se ejecuta en su servidor / computadora de escritorio / computadora portátil / teléfono inteligente. Es mejor que un bucle ingenuo byte-a-a-time, pero incluso este bithack es bastante malo en comparación con el asm eficiente para CPU modernas (especialmente x86 donde AVX2 SIMD permite verificar 32 bytes con un par de instrucciones, permitiendo 32 a 64 bytes por reloj haga un ciclo en el bucle principal si los datos están calientes en la caché L1d en las CPU modernas con carga de vector de 2 / reloj y rendimiento de ALU, es decir, para cadenas de tamaño mediano donde la sobrecarga de inicio no domina).
glibc utiliza trucos de enlace dinámico para resolver
strlenuna versión óptima para su CPU, por lo que incluso dentro de x86 hay una versión SSE2 (vectores de 16 bytes, línea de base para x86-64) y una versión AVX2 (vectores de 32 bytes).x86 tiene una transferencia de datos eficiente entre registros vectoriales y de propósito general, lo que lo hace único (?) bueno para usar SIMD para acelerar funciones en cadenas de longitud implícita donde el control de bucle depende de los datos.
pcmpeqb/pmovmskbhace posible probar 16 bytes separados a la vez.glibc tiene una versión AArch64 como esa usando AdvSIMD , y una versión para CPU AArch64 donde los registros vector-> GP bloquean la canalización, por lo que en realidad usa este bithack . Pero utiliza los ceros de recuento para encontrar el byte-dentro del registro una vez que recibe un acierto, y aprovecha los eficientes accesos no alineados de AArch64 después de verificar el cruce de páginas.
También relacionado: ¿Por qué este código es 6.5 veces más lento con las optimizaciones habilitadas? tiene más detalles sobre lo que es rápido versus lento en x86 asm
strlencon un gran búfer y una implementación simple de asm que podría ser bueno para que gcc sepa cómo en línea. (Algunas versiones de gcc imprudentemente en línea,rep scasbque es muy lenta, o un bithack de 4 bytes a la vez como este. Por lo tanto, la receta en línea de GCC necesita actualización o desactivación).Asm no tiene "comportamiento indefinido" estilo C ; es seguro acceder a los bytes en la memoria como desee, y una carga alineada que incluya los bytes válidos no puede fallar. La protección de la memoria ocurre con granularidad de página alineada; los accesos alineados más estrechos que eso no pueden cruzar el límite de una página. ¿Es seguro leer más allá del final de un búfer dentro de la misma página en x86 y x64? El mismo razonamiento se aplica al código de máquina que este hack de C consigue que los compiladores creen para una implementación independiente y no en línea de esta función.
Cuando un compilador emite código para llamar a una función no en línea desconocida, debe suponer que la función modifica cualquiera / todas las variables globales y cualquier memoria a la que posiblemente tenga un puntero. es decir, todo excepto los locales que no han tenido su escape de dirección deben estar sincronizados en la memoria durante la llamada. Esto se aplica a las funciones escritas en asm, obviamente, pero también a las funciones de la biblioteca. Si no habilita la optimización del tiempo de enlace, incluso se aplica a unidades de traducción separadas (archivos fuente).
Por qué esto es seguro como parte de glibc pero no de otra manera.
El factor más importante es que esto
strlenno puede alinearse con nada más. No es seguro para eso; contiene UB de alias estricto (lectura dechardatos a través de ununsigned long*).char*se le permite alias cualquier otra cosa, pero lo contrario no es cierto .Esta es una función de biblioteca para una biblioteca compilada por adelantado (glibc). No se alineará con la optimización del tiempo de enlace en las personas que llaman. Esto significa que solo tiene que compilar un código de máquina seguro para una versión independiente de
strlen. No tiene que ser portátil / seguro C.La biblioteca GNU C solo tiene que compilarse con GCC. Aparentemente no es compatible compilarlo con clang o ICC, a pesar de que admiten extensiones GNU. GCC es un compilador anticipado que convierte un archivo fuente C en un archivo objeto de código de máquina. No es un intérprete, por lo que, a menos que esté en línea en el momento de la compilación, los bytes en la memoria son solo bytes en la memoria. es decir, UB de alias estricto no es peligroso cuando los accesos con diferentes tipos ocurren en diferentes funciones que no se alinean entre sí.
Recuerde que
strlenel comportamiento está definido por el estándar ISO C. Ese nombre de función específicamente es parte de la implementación. Los compiladores como GCC incluso tratan el nombre como una función incorporada a menos que lo use-fno-builtin-strlen, por lo questrlen("foo")puede ser una constante de tiempo de compilación3. La definición en la biblioteca solo se usa cuando gcc decide emitirle una llamada en lugar de incluir su propia receta o algo así.Cuando UB no es visible para el compilador en el momento de la compilación, obtienes un código de máquina sensato. El código de la máquina tiene que funcionar para el caso sin UB, e incluso si lo desea , el asm no puede detectar qué tipos utiliza la persona que llama para colocar los datos en la memoria señalada.
Glibc se compila en una biblioteca estática o dinámica independiente que no puede alinearse con la optimización del tiempo de enlace. Los scripts de compilación de glibc no crean bibliotecas estáticas "gordas" que contengan código máquina + representación interna Gcc GIMPLE para la optimización del tiempo de enlace cuando se incorporan a un programa. (es decir
libc.a, no participará en la-fltooptimización del tiempo de enlace en el programa principal). Construir glibc de esa manera sería potencialmente inseguro en los objetivos que realmente usan esto.c.De hecho, como comenta @zwol, LTO no se puede usar al construir glibc en sí , debido a un código "frágil" como este que podría romperse si fuera posible la alineación entre los archivos fuente de glibc. (Hay algunos usos internos de
strlen, por ejemplo, tal vez como parte de laprintfimplementación)Esto
strlenhace algunas suposiciones:CHAR_BITes múltiplo de 8 . Verdadero en todos los sistemas GNU. POSIX 2001 incluso garantizaCHAR_BIT == 8. (Esto parece seguro para sistemas conCHAR_BIT= 16o32, como algunos DSP; el bucle de prólogo no alineado siempre ejecutará 0 iteraciones sisizeof(long) = sizeof(char) = 1cada puntero siempre está alineado yp & sizeof(long)-1siempre es cero). Pero si tenía un conjunto de caracteres no ASCII donde los caracteres son 9 o 12 bits de ancho,0x8080...es el patrón incorrecto.unsigned longes de 4 u 8 bytes. O tal vez realmente funcione para cualquier tamaño deunsigned longhasta 8, y utiliza unassert()para verificar eso.Esos dos no son posibles UB, son simplemente no portabilidad para algunas implementaciones de C. Este código es (o fue) parte de la implementación de C en plataformas donde funciona, así que está bien.
El siguiente supuesto es potencial C UB:
0es UB; podría ser unachar[]matriz C que contiene,{1,2,0,3}por ejemplo)Ese último punto es lo que hace que sea seguro leer más allá del final de un objeto C aquí. Eso es bastante seguro incluso cuando se alinea con los compiladores actuales porque creo que actualmente no tratan que no se pueda alcanzar una ruta de ejecución. Pero de todos modos, el alias estricto ya es un éxito si alguna vez dejas esto en línea.
Entonces tendría problemas como la vieja
memcpymacro CPP insegura del kernel de Linux que usaba puntero-casting paraunsigned long( gcc, alias estricto e historias de terror ).Esto
strlense remonta a la época en la que podía salirse con la suya en general ; solía ser bastante seguro sin la advertencia "solo cuando no está en línea" antes de GCC3.UB que solo es visible cuando se miran a través de los límites de llamadas / ret no puede hacernos daño. (por ejemplo, llamar a esto en
char buf[]lugar de en una matriz deunsigned long[]conversión a aconst char*). Una vez que el código de la máquina se establece en piedra, solo se trata de bytes en la memoria. Una llamada de función no en línea tiene que suponer que la persona que llama lee cualquier / toda la memoria.Escribir esto de forma segura, sin alias estricto UB
El atributo de tipo GCC
may_aliasle da a un tipo el mismo tratamiento de alias-cualquier cosa quechar*. (Sugerido por @KonradBorowsk). Los encabezados GCC actualmente lo usan para tipos de vectores SIMD x86 como__m128ipara que siempre pueda hacerlo de manera segura_mm_loadu_si128( (__m128i*)foo ). (Consulte ¿Es `reinterpret_cast`ing entre el puntero de vector de hardware y el tipo correspondiente un comportamiento indefinido? Para obtener más detalles sobre lo que esto significa y lo que no significa).También puede usar
aligned(1)para expresar un tipo conalignof(T) = 1.typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;Es una forma portátil de expresar una carga de alias en ISO
memcpy, con la cual los compiladores modernos saben cómo alinearse como una sola instrucción de carga. p.ejEsto también funciona para cargas no alineadas porque
memcpyfunciona como si fuera porcharacceso a la vez. Pero en la práctica, los compiladores modernos entiendenmemcpymuy bien.El peligro aquí es que si GCC no sabe con certeza si
char_ptrestá alineado con palabras, no lo alineará en algunas plataformas que podrían no soportar cargas no alineadas en asm. por ejemplo, MIPS antes de MIPS64r6, o ARM anterior. Si recibió una llamada a la función realmemcpysolo para cargar una palabra (y dejarla en otra memoria), eso sería un desastre. A veces, GCC puede ver cuándo el código alinea un puntero. O después del ciclo de char-at-a-time que alcanza un límite ulong podría usarp = __builtin_assume_aligned(p, sizeof(unsigned long));Esto no evita la posible UB de leer más allá del objeto, pero con el CCG actual eso no es peligroso en la práctica.
Por qué es necesaria una fuente C optimizada a mano: los compiladores actuales no son lo suficientemente buenos
El asm optimizado a mano puede ser aún mejor cuando desea hasta el último rendimiento para una función de biblioteca estándar ampliamente utilizada. Especialmente para algo así
memcpy, pero tambiénstrlen. En este caso, no sería mucho más fácil usar C con intrínsecos x86 para aprovechar SSE2.Pero aquí solo estamos hablando de una versión ingenua vs. bithack C sin ninguna característica específica de ISA.
(Creo que podemos tomarlo como un hecho que
strlense usa lo suficiente como para hacer que funcione lo más rápido posible. Por lo tanto, la pregunta es si podemos obtener un código de máquina eficiente de una fuente más simple. No, no podemos).GCC y clang actuales no son capaces de auto-vectorizar bucles donde el recuento de iteraciones no se conoce antes de la primera iteración . (por ejemplo, tiene que ser posible verificar si el bucle ejecutará al menos 16 iteraciones antes de ejecutar la primera iteración). Por ejemplo, es posible autovectorizar memcpy (buffer de longitud explícita) pero no strcpy o strlen (cadena de longitud implícita), dada la corriente compiladores
Eso incluye bucles de búsqueda, o cualquier otro bucle con
if()breakun contador dependiente de datos .ICC (compilador de Intel para x86) puede vectorizar automáticamente algunos bucles de búsqueda, pero aún así hace ingenuo byte a la vez para una C simple / ingenua
strlencomo la libc de OpenBSD. ( Godbolt ) (De la respuesta de @ Peske ).Una libc optimizada a mano
strlenes necesaria para el rendimiento con los compiladores actuales . Ir a 1 byte a la vez (con desenrollar quizás 2 bytes por ciclo en CPU superescalares anchas) es patético cuando la memoria principal puede mantenerse con aproximadamente 8 bytes por ciclo, y el caché L1d puede entregar de 16 a 64 por ciclo. (2x cargas de 32 bytes por ciclo en las CPU x86 mainstream modernas desde Haswell y Ryzen. Sin contar AVX512 que puede reducir las velocidades de reloj solo por usar vectores de 512 bits; es por eso que glibc probablemente no tiene prisa por agregar una versión AVX512 . Aunque con vectores de 256 bits, AVX512VL + BW enmascarados comparar en una máscara yktest, okortestpodría hacerstrlenmás amigable Hyperthreading mediante la reducción de sus uops / iteración.)Estoy incluyendo no x86 aquí, esos son los "16 bytes". por ejemplo, la mayoría de las CPU AArch64 pueden hacer al menos eso, creo, y algunas ciertamente más. Y algunos tienen suficiente rendimiento de ejecución para
strlenmantenerse al día con ese ancho de banda de carga.Por supuesto, los programas que funcionan con cadenas grandes generalmente deben realizar un seguimiento de las longitudes para evitar tener que rehacer la búsqueda de la longitud de las cadenas C de longitud implícita muy a menudo. Pero el rendimiento de corta a media duración todavía se beneficia de las implementaciones escritas a mano, y estoy seguro de que algunos programas terminan usando strlen en cadenas de mediana longitud.
fuente
CHAR_BIT == 8es un requisito POSIX (como de la -2,001 rev; ver aquí ). (4) La implementación destrlenrespaldo de C se usa para algunas CPU compatibles, creo que la más común es MIPS.__attribute__((__may_alias__))atributo (esto no es portátil, pero debería estar bien para glibc).char*, pero todavía es UB leer / escribir uncharobjeto (por ejemplo, parte de achar[]) a través de along*. Regla de alias estricta y punteros 'char *'CHAR_BITdebe ser al menos 8 ( qv Anexo E de C11), por lo que al menos 7 bitscharno es algo de lo que deba preocuparse un abogado de idiomas. Esto fue motivado por el requisito, "Para los literales de cadena UTF − 8, los elementos de la matriz tienen tipochary se inicializan con los caracteres de la secuencia de caracteres multibyte, como se codifica en UTF − 8".Se explica en los comentarios en el archivo que vinculó:
y:
En C, es posible razonar en detalle sobre la eficiencia.
Es menos eficiente iterar a través de caracteres individuales que buscan un valor nulo que probar más de un byte a la vez, como lo hace este código.
La complejidad adicional proviene de la necesidad de garantizar que la cadena bajo prueba esté alineada en el lugar correcto para comenzar a probar más de un byte a la vez (a lo largo de un límite de palabra larga, como se describe en los comentarios), y de la necesidad de garantizar que las suposiciones acerca de los tamaños de los tipos de datos no se violan cuando se utiliza el código.
En la mayoría (pero no en todos) el desarrollo de software moderno, esta atención a los detalles de eficiencia no es necesaria, o no vale la pena el costo de la complejidad adicional del código.
Un lugar donde tiene sentido prestar atención a la eficiencia como esta es en las bibliotecas estándar, como el ejemplo que vinculó.
Si desea leer más sobre los límites de palabras, vea esta pregunta y esta excelente página de Wikipedia
fuente
Además de las excelentes respuestas aquí, quiero señalar que el código vinculado en la pregunta es para la implementación de GNU
strlen.La implementación de OpenBSD
strlenes muy similar al código propuesto en la pregunta. La complejidad de una implementación está determinada por el autor.EDITAR : El código de OpenBSD que vinculé anteriormente parece ser una implementación alternativa para ISA que no tienen su propia implementación de asm. Existen diferentes implementaciones
strlendependiendo de la arquitectura. El código para amd64strlen, por ejemplo, es asm. Similar a los comentarios / respuestas de PeterCordes que señalan que las implementaciones de GNU sin respaldo también son asm.fuente
s - strno está definido si el resultado no es representable enptrdiff_t.PTRDIFF_MAX. Pero todavía es posible tenermmapmás memoria que eso en Linux al menos (por ejemplo, en un proceso de 32 bits bajo un núcleo x86-64, podría mapear alrededor de 2.7GB contiguos antes de comenzar a tener fallas). IDK sobre OpenBSD; el núcleo podría hacer que sea imposible alcanzar esoreturnsin segfaulting o detenerse dentro del tamaño. Pero sí, pensarías que la codificación defensiva que evita la C UB teórica sería algo que OpenBSD querría hacer. Aunquestrlenno puede en línea y los compiladores reales solo lo compilarán en una resta.En resumen, esta es una optimización de rendimiento que la biblioteca estándar puede hacer al saber con qué compilador se compila: no debe escribir código como este, a menos que esté escribiendo una biblioteca estándar y pueda depender de un compilador específico. Específicamente, está procesando el número de bytes de alineación al mismo tiempo: 4 en plataformas de 32 bits, 8 en plataformas de 64 bits. Esto significa que puede ser 4 u 8 veces más rápido que la iteración de byte ingenua.
Para explicar cómo funciona esto, considere la siguiente imagen. Asuma aquí la plataforma de 32 bits (alineación de 4 bytes).
Digamos que la letra "H" de "¡Hola, mundo!" Se proporcionó una cadena como argumento para
strlen. Debido a que a la CPU le gusta tener cosas alineadas en la memoria (idealmenteaddress % sizeof(size_t) == 0), los bytes antes de la alineación se procesan byte a byte, utilizando el método lento.Luego, para cada fragmento del tamaño de la alineación, al calcularlo
(longbits - 0x01010101) & 0x80808080 != 0se verifica si alguno de los bytes dentro de un entero es cero. Este cálculo tiene un falso positivo cuando al menos uno de los bytes es mayor que0x80, pero la mayoría de las veces debería funcionar. Si ese no es el caso (ya que está en el área amarilla), la longitud aumenta con el tamaño de la alineación.Si alguno de los bytes dentro de un entero resulta ser cero (o
0x81), entonces la cadena se verifica byte por byte para determinar la posición de cero.Esto puede hacer un acceso fuera de límites, sin embargo, debido a que está dentro de una alineación, es más probable que no esté bien, las unidades de mapeo de memoria generalmente no tienen precisión de nivel de byte.
fuente
size_tNo se garantiza que esté alineado.Desea que el código sea correcto, fácil de mantener y rápido. Estos factores tienen diferente importancia:
"correcto" es absolutamente esencial.
"mantenible" depende de cuánto va a mantener el código: strlen ha sido una función de biblioteca Standard C durante más de 40 años. No va a cambiar La mantenibilidad es, por lo tanto, poco importante para esta función.
"Rápido": en muchas aplicaciones, strcpy, strlen, etc. utiliza una cantidad significativa del tiempo de ejecución. Para lograr la misma ganancia de velocidad general que esta complicada, pero no muy complicada, la implementación de strlen al mejorar el compilador requeriría esfuerzos heroicos.
Ser rápido tiene otra ventaja: cuando los programadores descubren que llamar a "strlen" es el método más rápido que pueden medir el número de bytes en una cadena, ya no se sienten tentados a escribir su propio código para hacer las cosas más rápido.
Entonces, para strlen, la velocidad es mucho más importante y la capacidad de mantenimiento es mucho menos importante que para la mayoría de los códigos que escribirás.
¿Por qué debe ser tan complicado? Digamos que tiene una cadena de 1,000 bytes. La implementación simple examinará 1,000 bytes. Una implementación actual probablemente examinaría palabras de 64 bits a la vez, lo que significa 125 palabras de 64 bits u ocho bytes. Incluso podría usar instrucciones vectoriales que examinen, digamos, 32 bytes a la vez, lo que sería aún más complicado e incluso más rápido. El uso de instrucciones vectoriales conduce a un código que es un poco más complicado pero bastante sencillo, verificar si uno de los ocho bytes en una palabra de 64 bits es cero requiere algunos trucos ingeniosos. Entonces, para cadenas medianas a largas, se puede esperar que este código sea aproximadamente cuatro veces más rápido. Para una función tan importante como strlen, vale la pena escribir una función más compleja.
PD. El código no es muy portátil. Pero es parte de la biblioteca Standard C, que es parte de la implementación, no necesita ser portátil.
PPS Alguien publicó un ejemplo en el que una herramienta de depuración se quejaba de acceder a bytes más allá del final de una cadena. Se puede diseñar una implementación que garantice lo siguiente: Si p es un puntero válido a un byte, entonces cualquier acceso a un byte en el mismo bloque alineado que sería un comportamiento indefinido de acuerdo con el estándar C, devolverá un valor no especificado.
PPPS Intel ha agregado instrucciones a sus procesadores posteriores que forman un bloque de construcción para la función strstr () (encontrar una subcadena en una cadena). Su descripción es alucinante, pero pueden hacer que esa función en particular sea probablemente 100 veces más rápida. (Básicamente, dada una matriz a que contiene "¡Hola, mundo!" Y una matriz b que comienza con 16 bytes "HelloHelloHelloH" y contiene más bytes, se da cuenta de que la cadena a no aparece en b antes de comenzar en el índice 15) .
fuente
Brevemente: verificar una cadena byte por byte será potencialmente lento en arquitecturas que pueden obtener grandes cantidades de datos a la vez.
Si la comprobación de la terminación nula se puede realizar en 32 o 64 bits, se reduce la cantidad de comprobaciones que debe realizar el compilador. Eso es lo que intenta hacer el código vinculado, con un sistema específico en mente. Hacen suposiciones sobre direccionamiento, alineación, uso de caché, configuraciones de compilador no estándar, etc.
Leer byte a byte como en su ejemplo sería un enfoque sensato en una CPU de 8 bits, o al escribir una biblioteca portátil escrita en el estándar C.
Mirar las bibliotecas estándar de C para obtener consejos sobre cómo escribir código rápido / bueno no es una buena idea, ya que no será portátil y dependerá de suposiciones no estándar o comportamientos mal definidos. Si es un principiante, leer dicho código probablemente será más dañino que educativo.
fuente
if()break. ICC puede auto-vectorizar tales bucles, pero IDK qué tan bien lo hace con un ingenuo strlen. Y sí, SSE2pcmpeqb/pmovmskbes muy bueno para strlen, probando 16 bytes a la vez. code.woboq.org/userspace/glibc/sysdeps/x86_64/strlen.S.html es la versión SSE2 de glibc. Vea también este Q&A .Una cosa importante que las otras respuestas no mencionan es que la FSF es muy cautelosa al garantizar que el código propietario no llegue a los proyectos GNU. En los Estándares de codificación de GNU en Referencia a programas propietarios , hay una advertencia sobre la organización de su implementación de manera que no se pueda confundir con el código propietario existente:
(El énfasis es mío).
fuente
strlen()es probable que las implementaciones "obvias" resulten similares o idénticas al código existente. Algo tan "loco" como la implementación de glibc no se puede rastrear así. Teniendo en cuenta la cantidad de disputas legales que hubo sobre las ¡rangeCheck11 líneas de código! - En la pelea de Google / Oracle, diría que la preocupación de la FSF estaba bien ubicada.