Se explica en los comentarios en el archivo que vinculó:

 27 /* Return the length of the null-terminated string STR. Scan for 28 the null terminator quickly by testing four bytes at a time. */

y:

 73 /* Instead of the traditional loop which tests each character, 74 we will test a longword at a time. The tricky part is testing 75 if *any of the four* bytes in the longword in question are zero. */

En C, es posible razonar en detalle sobre la eficiencia.

Es menos eficiente iterar a través de caracteres individuales buscando 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 sobre los tamaños de los tipos de datos no se violan cuando se usa 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 las palabras, consulteesta pregunta y esta excelente página de wikipedia.

También creo que esta respuesta anterior es una discusión mucho más clara y detallada.

No necesita y nunca debe escribir un código como ese, especialmente si no es un compilador de C / proveedor de biblioteca estándar. Es un código que se usa para implementar strlen con algunos trucos de velocidad y suposiciones muy cuestionables (que no se prueban con afirmaciones ni se mencionan en los comentarios):

• unsigned long es de 4 u 8 bytes
• los bytes son 8 bits
• un puntero se puede convertir a unsigned long long y no a uintptr_t
• uno puede alinear el puntero simplemente comprobando que los 2 o 3 bits de menor orden son cero
• uno puede acceder a una cadena como s unsigned long
• uno puede leer más allá del final de la matriz sin ningún efecto negativo.

Es más, un buen compilador podría incluso reemplazar el código escrito como

 size_t stupid_strlen(const char s[]) { size_t i; for (i=0; s[i] != '\0'; i++) ; return i; }

(tenga en cuenta que tiene que ser un tipo compatible con size_t ) con una versión en línea del compilador incorporado strlen , o vectorizar el código; pero es poco probable que un compilador pueda optimizar la versión compleja.

La función strlen se describe en C11 7.24.6.3 como:

Descripción

2. La función strlen calcula la longitud de la cadena a la que apunta s.

Devoluciones

3. La función strlen devuelve el número de caracteres que preceden al carácter nulo final.

Ahora, si la cadena a la que apunta s estaba 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 en

 char *str = "hello world"; // or char array[] = "hello world";

Entonces, realmente, la única forma en C totalmente portátil / compatible con los estándares para implementar esto correctamente es la forma en que está escrito en su pregunta , excepto por 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 demasiado pesada, aprovechar las suposiciones razonables o seguras conocidas no siempre es algo malo. Especialmente en el código que es parte de una implementación específica de C. Pero debe comprender el reglas antes de saber cómo/cuándo puedes doblarlas).

La implementación strlen vinculada primero verifica los bytes individualmente hasta que el puntero apunta al límite de alineación natural de 4 u 8 bytes del unsigned long . El estándar C dice que acceder a un puntero que no está correctamente alineado tiene un comportamiento indefinido , por lo que es absolutamente necesario hacerlo 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, una palabra desalineada o una carga de doble palabra fallará. C no es un lenguaje ensamblador portátil, pero este código lo usa 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 la memoria funciona en bloques alineados (por ejemplo, páginas de memoria virtual de 4kiB).

Ahora viene la parte sucia: el código rompe la promesa y lee 4 u 8 bytes de 8 bits a la vez (un long int ), y usa un pequeño truco con una adición sin firmar para averiguar rápidamente si había cero bytes dentro de esos 4 u 8 bytes: utiliza un número especialmente diseñado que haría que el bit de acarreo cambiara los bits capturados por una máscara de bits. En esencia, esto determinaría si alguno de los 4 u 8 bytes en la máscara son ceros supuestamente más rápido que recorrer cada uno de estos bytes. Finalmente, hay un bucle al final para averiguar qué byte fue el primer cero, si lo hay, y devolver el resultado.

El mayor problema es que en sizeof (unsigned long) - 1 vez fuera de los casos de tamaño de sizeof (unsigned long) leerá más allá del final de la cadena - solo si el byte nulo está en el último byte accedido (es decir, en little-endian 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 strlen en una biblioteca estándar de C, es un código incorrecto . Tiene varios aspectos definidos e indefinidos de implementación y no debe usarse en ningún lugar en lugar del strlen proporcionado por el sistema. Cambié el nombre de la función a the_strlen aquí y agregué el siguiente main :

 int main(void) { char buf[12]; printf("%zu\n", the_strlen(fgets(buf, 12, stdin))); }

El búfer se dimensiona cuidadosamente para que pueda contener exactamente la cadena hello world y el terminador. Sin embargo, en mi procesador de 64 bits, el unsigned long es de 8 bytes, por lo que el acceso a la última parte excedería este búfer.

Si ahora compilo con -fsanitize=undefined y -fsanitize=address y ejecuto el programa resultante, obtengo:

 % ./a.out hello world ================================================================= ==8355==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffffe63a3f8 at pc 0x55fbec46ab6c bp 0x7ffffe63a350 sp 0x7ffffe63a340 READ of size 8 at 0x7ffffe63a3f8 thread T0 #0 0x55fbec46ab6b in the_strlen (.../a.out+0x1b6b) #1 0x55fbec46b139 in main (.../a.out+0x2139) #2 0x7f4f0848fb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96) #3 0x55fbec46a949 in _start (.../a.out+0x1949) Address 0x7ffffe63a3f8 is located in stack of thread T0 at offset 40 in frame #0 0x55fbec46b07c in main (.../a.out+0x207c) This frame has 1 object(s): [32, 44) 'buf' <== Memory access at offset 40 partially overflows this variable HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext (longjmp and C++ exceptions *are* supported) SUMMARY: AddressSanitizer: stack-buffer-overflow (.../a.out+0x1b6b) in the_strlen Shadow bytes around the buggy address: 0x10007fcbf420: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x10007fcbf430: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x10007fcbf440: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x10007fcbf450: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x10007fcbf460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 =>0x10007fcbf470: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00[04] 0x10007fcbf480: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x10007fcbf490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x10007fcbf4a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x10007fcbf4b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x10007fcbf4c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb ==8355==ABORTING

es decir, sucedieron cosas malas.

Brevemente: verificar una cadena byte por byte puede ser 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 por 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 C estándar.

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 se basará en suposiciones no estándar o en un comportamiento mal definido. Si es un principiante, leer dicho código probablemente sea más dañino que educativo.

Quiere que el código sea correcto, mantenible 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 estándar de C durante más de 40 años. No va a cambiar. Por lo tanto, la mantenibilidad es bastante poco importante para esta función.

"Rápido": en muchas aplicaciones, strcpy, strlen, etc. usan una cantidad significativa del tiempo de ejecución. Para lograr la misma ganancia de velocidad general que esta implementación complicada, pero no muy complicada, de strlen mediante la mejora del compilador, se necesitarían 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 la cantidad de bytes en una cadena, ya no tienen la tentación de 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 mantenibilidad mucho menos importante que para la mayoría del código que escribirá.

¿Por qué debe ser tan complicado? Digamos que tiene una cadena de 1000 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 inteligentes. 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 portable. Pero es parte de la biblioteca Standard C, que es parte de la implementación; no es necesario que sea portátil.

PPS. Alguien publicó un ejemplo en el que una herramienta de depuración se quejó 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, cualquier acceso a un byte en el mismo bloque alineado que tendría un comportamiento indefinido según el estándar C devolverá un valor no especificado.

PPP. 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) .

Además de las excelentes respuestas aquí, quiero señalar que el código vinculado en la pregunta es para la implementación de strlen de GNU.

La implementación de OpenBSD de strlen es muy similar al código propuesto en la pregunta. La complejidad de una implementación la determina el autor.

 ... #include <string.h> size_t strlen(const char *str) { const char *s; for (s = str; *s; ++s) ; return (s - str); } DEF_STRONG(strlen);

EDITAR : el código de OpenBSD que vinculé anteriormente parece ser una implementación alternativa para las ISA que no tienen su propia implementación de asm. Hay diferentes implementaciones de strlen dependiendo de la arquitectura. El código para amd64 strlen , por ejemplo, es asm. Similar a los comentarios/ respuesta de PeterCordes que señalan que las implementaciones de GNU sin respaldo también son asm.

En resumen, esta es una optimización del 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 bytes ingenua.

Para explicar cómo funciona esto, considere la siguiente imagen. Suponga aquí la plataforma de 32 bits (alineación de 4 bytes).

Digamos que la letra "H" de "Hello, world!" string se proporcionó como argumento para strlen . Debido a que a la CPU le gusta tener las cosas alineadas en la memoria (idealmente, address % sizeof(size_t) == 0 ), los bytes antes de la alineación se procesan byte por byte, utilizando un método lento.

Luego, para cada fragmento del tamaño de la alineación, calculando (longbits - 0x01010101) & 0x80808080 != 0 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 superior a 0x80 , pero la mayoría de las veces debería funcionar. Si ese no es el caso (como está en el área amarilla), la longitud aumenta según 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 los 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.

Ha habido muchas conjeturas (ligera o totalmente) incorrectas en los comentarios sobre algunos detalles / antecedentes de esto.

Está viendo la implementación optimizada de reserva de C optimizada de glibc. (Para ISA que no tienen una implementación asm escrita a mano) . O una versión antigua 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ódigo basado en el árbol git de glibc 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 escrito a mano

Entonces, el incentivo para cambiar cualquier cosa sobre este código es menor de lo que podría pensar.

Este código bithack ( https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord ) no es lo que realmente se ejecuta en su servidor/escritorio/portátil/smartphone. Es mejor que un bucle ingenuo de byte a la vez, pero incluso este bithack es bastante malo en comparación con el asm eficiente para las CPU modernas (especialmente x86 donde AVX2 SIMD permite verificar 32 bytes con un par de instrucciones, lo que permite de 32 a 64 bytes por reloj ciclo en el bucle principal si los datos están activos en la memoria 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 strlen en una 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 excepcionalmente (?) Bueno para usar SIMD para acelerar funciones en cadenas de longitud implícita donde el control de bucle depende de los datos. pcmpeqb / pmovmskb permite probar 16 bytes separados a la vez.

glibc tiene una versión AArch64 como esa que usa AdvSIMD , y una versión para CPU AArch64 donde los registros vector->GP detiene la canalización, por lo que en realidad usa este bithack . Pero utiliza el conteo de ceros a la izquierda para encontrar el byte dentro del registro una vez que recibe un acierto, y aprovecha los accesos no alineados eficientes 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 y lento en x86 asm para strlen con un búfer grande y una implementación de asm simple que podría ser buena para que gcc sepa cómo en línea. (Algunas versiones de gcc imprudentemente en línea rep scasb que es muy lento, o un bithack de 4 bytes a la vez como este. Por lo tanto, la receta en línea de GCC necesita actualizarse o desactivarse).

Asm no tiene un "comportamiento indefinido" al estilo C ; es seguro acceder a los bytes en la memoria como quieras, y una carga alineada que incluye cualquier byte válido no puede fallar. La protección de la memoria ocurre con la granularidad de página alineada; los accesos alineados más estrechos que eso no pueden cruzar un límite de 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 truco de C hace que los compiladores creen para una implementación independiente 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, tiene que asumir 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 cuya dirección no se ha escapado, debe estar sincronizado en la memoria durante la llamada. Esto se aplica a las funciones escritas en asm, obviamente, pero también a las funciones de biblioteca. Si no habilita la optimización del tiempo de enlace, incluso se aplica a unidades de traducción separadas (archivos de origen).

Por qué esto es seguro como parte de glibc pero no de otra manera.

El factor más importante es que este strlen no puede integrarse en nada más. No es seguro para eso; contiene UB de alias estricto (lectura de datos char a través de un unsigned long* ). char* puede crear un alias para cualquier otra cosa, pero lo contrario no es cierto .

Esta es una función de biblioteca para una biblioteca compilada con anticipación (glibc). No se alineará con la optimización del tiempo de enlace en las personas que llaman. Esto significa que solo tiene que compilar en 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 compilar con GCC. Aparentemente, no se admite compilarlo con clang o ICC, aunque admiten extensiones GNU. GCC es un compilador avanzado 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 se inserte en línea en el momento de la compilación, los bytes en la memoria son solo bytes en la memoria. es decir, el 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 el comportamiento de strlen 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 use -fno-builtin-strlen , por lo que strlen("foo") puede ser una constante de tiempo de compilación 3 . La definición en la biblioteca solo se usa cuando gcc decide emitir 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, obtiene 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 quisiera , no hay forma de que el asm detecte qué tipos usó la persona que llama para poner datos en la memoria apuntada.

Glibc se compila en una biblioteca estática o dinámica independiente que no puede estar en línea con la optimización del tiempo de enlace. Los scripts de compilación de glibc no crean bibliotecas estáticas "grandes" que contengan código de máquina + representación interna gcc GIMPLE para la optimización del tiempo de enlace cuando se insertan en un programa. (es decir, libc.a no participará en la optimización del tiempo de enlace -flto en el programa principal). Construir glibc de esa manera sería potencialmente inseguro en los objetivos que realmente usan este .c .

De hecho, como comenta @zwol, LTO no se puede usar al compilar glibc en sí , debido a un código "frágil" como este que podría romperse si fuera posible intercalar entre los archivos fuente de glibc. (Hay algunos usos internos de strlen , por ejemplo, tal vez como parte de la implementación de printf )

Este strlen hace algunas suposiciones:

• CHAR_BIT es un múltiplo de 8 . Cierto en todos los sistemas GNU. POSIX 2001 incluso garantiza CHAR_BIT == 8 . (Esto parece seguro para sistemas con CHAR_BIT= 16 o 32 , como algunos DSP; el bucle de prólogo no alineado siempre ejecutará 0 iteraciones si sizeof(long) = sizeof(char) = 1 porque cada puntero siempre está alineado y p & sizeof(long)-1 siempre es cero.) Pero si tenía un conjunto de caracteres que no son ASCII donde los caracteres tienen 9 o 12 bits de ancho, 0x8080... es el patrón incorrecto.
• (tal vez) unsigned long es de 4 u 8 bytes. O tal vez en realidad funcionaría para cualquier tamaño de unsigned long hasta 8, y usa una assert() para verificar eso.

Esos dos no son UB posibles, simplemente no son portátiles para algunas implementaciones de C. Este código es (o era) parte de la implementación de C en las plataformas donde funciona, así que está bien.

La siguiente suposición es C UB potencial:

• Una carga alineada que contiene bytes válidos no puede fallar y es segura siempre que ignore los bytes fuera del objeto que realmente desea. (Cierto en asm en todos los sistemas GNU y en todas las CPU normales porque la protección de la memoria ocurre con granularidad de página alineada. ¿Es seguro leer más allá del final de un búfer dentro de la misma página en x86 y x64? seguro en C cuando el UB no es visible en tiempo de compilación. Sin inline, este es el caso aquí. El compilador no puede probar que leer más allá del primer 0 es UB; podría ser una matriz C char[] 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 integra con los compiladores actuales porque creo que actualmente no tratan eso, lo que implica que una ruta de ejecución es inalcanzable. Pero de todos modos, el alias estricto ya es una maravilla si alguna vez deja esto en línea.

Entonces tendría problemas como la antigua macro memcpy CPP insegura del kernel de Linux que usaba la conversión de punteros a unsigned long ( gcc, strict-aliasing e historias de terror ). (Linux moderno compila con -fno-strict-aliasing en lugar de tener cuidado con los atributos may_alias ).

Este strlen se remonta a la era en la que podías salirte con la tuya en general ; solía ser bastante seguro antes de GCC3, incluso sin una advertencia de "solo cuando no está en línea".

UB que solo es visible cuando se mira a través de los límites de call/ret no nos puede hacer daño. (por ejemplo, llamando a esto en un char buf[] en lugar de en una matriz de unsigned long[] a un const char* ). Una vez que el código de máquina está escrito en piedra, solo se trata de bytes en la memoria. Una llamada de función no en línea tiene que asumir que la persona que llama lee cualquier/toda la memoria.

Escribiendo esto de forma segura, sin UB de alias estricto

El atributo de tipo GCC may_alias le da a un tipo el mismo tratamiento de alias-cualquier cosa que char* . (Sugerido por @KonradBorowsk). Los encabezados GCC actualmente lo usan para tipos de vectores SIMD x86 como __m128i , por lo que siempre puede hacer _mm_loadu_si128( (__m128i*)foo ) de manera segura. (Consulte ¿Es `reinterpret_cast`ing entre el puntero de vector SIMD de hardware y el tipo correspondiente un comportamiento indefinido? para obtener más detalles sobre lo que esto significa y lo que no significa).

 strlen(const char *char_ptr) { typedef unsigned long __attribute__((may_alias)) aliasing_ulong; // handle unaligned startup somehow, eg check for page crossing then check an unaligned word // else check single bytes until an alignment boundary. aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr; for (;;) { // alignment still required, but can safely alias anything including a char[] unsigned long ulong = *longword_ptr++; ... } }

Puede usar aligned(1) para expresar un tipo con alignof(T) = 1 .
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong; . Esto podría ser útil para la parte de inicio no alineada de strlen, si no solo hace char-a-la-vez hasta el primer límite de alineación. (El bucle principal debe estar alineado para que no se culpe si el terminador está justo antes de una página sin asignar).

Una forma portátil de expresar una carga de alias en ISO es con memcpy , que los compiladores modernos saben cómo en línea como una sola instrucción de carga. p.ej

 unsigned long longword; memcpy(&longword, char_ptr, sizeof(longword)); char_ptr += sizeof(longword);

Esto también funciona para cargas no alineadas porque memcpy funciona como si fuera un acceso char a la vez. Pero en la práctica, los compiladores modernos entienden muy bien memcpy .

El peligro aquí es que si GCC no sabe con certeza que char_ptr está alineado con palabras, no lo alineará en algunas plataformas que podrían no admitir cargas no alineadas en asm. por ejemplo, MIPS anterior a MIPS64r6 o ARM anterior. Si recibiera una llamada de función real a memcpy solo para cargar una palabra (y dejarla en otra memoria), sería un desastre. GCC a veces puede ver cuándo el código alinea un puntero. O después del bucle char-at-a-time que alcanza un límite largo que podría usar
p = __builtin_assume_aligned(p, sizeof(unsigned long));

Esto no evita la posible UB de lectura más allá del objeto, pero con el GCC 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 obtener hasta la última gota de rendimiento para una función de biblioteca estándar ampliamente utilizada. Especialmente para algo como memcpy , pero también strlen . 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 C ingenua frente a bithack sin ninguna característica específica de ISA.

(Creo que podemos dar por sentado que strlen se usa lo suficiente como para que sea importante hacerlo funcionar lo más rápido posible. Entonces, 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 número 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). compiladores.

Eso incluye bucles de búsqueda o cualquier otro bucle con un if()break dependiente de los datos, así como un contador.

ICC (compilador de Intel para x86) puede auto-vectorizar algunos bucles de búsqueda, pero aún así solo crea un asm de byte a la vez ingenuo para un C strlen simple/ingenuo como los usos de libc de OpenBSD. ( Golpe de Dios ). (De la respuesta de @Peske ).

Una libc strlen optimizada a mano es necesaria para el rendimiento con los compiladores actuales . Pasar de 1 byte a la vez (con desenrollar tal vez 2 bytes por ciclo en CPU superescalares anchas) es patético cuando la memoria principal puede mantenerse al día 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 convencionales modernas desde Haswell y Ryzen. Sin contar AVX512, que puede reducir las velocidades de reloj solo por usar vectores de 512 bits; razón por la cual glibc probablemente no tenga prisa por agregar una versión AVX512 Aunque con vectores de 256 bits, AVX512VL + BW enmascarado se compara con una máscara y ktest o kortest podría hacer que strlen sea más amigable con el hyperthreading al reducir sus uops/iteración).

Estoy incluyendo no x86 aquí, esos son los "16 bytes". por ejemplo, creo que la mayoría de las CPU AArch64 pueden hacer al menos eso, y algunas ciertamente más. Y algunos tienen suficiente rendimiento de ejecución para que strlen se mantenga al día con ese ancho de banda de carga.

Por supuesto, los programas que trabajan con cadenas largas deben realizar un seguimiento de las longitudes para evitar tener que volver a encontrar la longitud de las cadenas C de longitud implícita con mucha frecuencia. Pero el rendimiento de longitud corta a media aún se beneficia de las implementaciones escritas a mano, y estoy seguro de que algunos programas terminan usando strlen en cadenas de longitud media.

Una cosa importante que no se menciona en las otras respuestas es que la FSF es muy cautelosa al garantizar que el código propietario no se convierta en proyectos GNU. En los Estándares de codificación de GNU, en Referencia a programas propietarios , hay una advertencia sobre cómo organizar su implementación de manera que no se pueda confundir con el código propietario existente:

¡Bajo ninguna circunstancia haga referencia al código fuente de Unix para o durante su trabajo en GNU! (O a cualquier otro programa propietario).

Si tiene un vago recuerdo de las partes internas de un programa Unix, esto no significa absolutamente que no pueda escribir una imitación de él, pero intente organizar la imitación internamente en diferentes líneas, porque es probable que esto haga que los detalles de la versión de Unix es irrelevante y diferente a sus resultados.

Por ejemplo, las utilidades de Unix generalmente se optimizaron para minimizar el uso de memoria; si opta por la velocidad , su programa será muy diferente.

(Énfasis mío).

¿Por qué algo como lo siguiente no funcionaría igual de bien o mejor?

 // OP's code - what is needed to portably function correctly? unsigned long strlen(char s[]) { unsigned long i; for (i = 0; s[i] != '\0'; i++) continue; return i; }

El código de OP tiene errores funcionales.

Sin embargo, es bastante fácil de modificar.

Al escribir código portátil, se necesita cuidado para obtener primero la función correcta y luego buscar mejoras en el rendimiento.

Incluso el código muy simple y aparentemente correcto puede tener fallas funcionales .

Escribe

La longitud de una cadena está en el rango de size_t que puede diferir de unsigned long . Problema con la firma de la función ya que no coincide con size_t (*f)() = strlen . Problema con plataformas poco comunes donde ULONG_MAX < SIZE_MAX y la longitud de la cadena es enorme.

const

s debe ser const char * .

Complemento distinto de 2

(Esta preocupación afecta a una cantidad cada vez menor de procesadores hoy en día, por lo que en realidad solo es una preocupación pedante. El complemento de Non-2 probablemente se especificará en el próximo C (¿C23?)).

El s[i] != '\0' puede activarse en -0 cuando char está firmado y no es complemento a 2. No debería. str...() funciona como si se accediera a los caracteres como unsigned char .

Para todas las funciones de esta subcláusula, cada carácter se interpretará como si tuviera el tipo unsigned char (y, por lo tanto, todas las representaciones de objetos posibles son válidas y tienen un valor diferente).

Para reparar estos aspectos del código simple de OP

 size_t strlen(const char *s) { size_t i; for (i = 0; ((const unsigned char *)s)[i] != '\0'; i++) continue; return i; }

Ahora, armado con un mejor candidato strlen() portátil, busque compararlo con las alternativas "complicadas".