¿Por qué el strlen de glibc necesita ser tan complicado para correr rápidamente?

optimization portability

Question

Estaba mirando el código strlen here 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 strlen en 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?

Answer 1

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 strlen es muy similar al código propuesto en la pregunta. La complejidad de una implementación está determinada por 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 OpenBSD que vinculé anteriormente parece ser una implementación alternativa para ISA que no tienen su propia implementación de asm. Existen diferentes implementaciones strlen dependiendo de la arquitectura. El código para amd64 strlen , por ejemplo, es asm. Similar a los comentarios / share PeterCordes que señalan que las implementaciones de GNU sin respaldo también son asm.

Answer 2

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

Answer 3

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

Answer 4

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 ingenua de bytes.

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 (idealmente address % 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 != 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 mayor que 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 se incrementa por el tamaño de 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.

Answer 5

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:

¡En ningún caso, consulte el código fuente de Unix para o durante su trabajo en GNU! (O a cualquier otro programa propietario).

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

Por ejemplo, las utilidades de Unix fueron generalmente optimizadas para minimizar el uso de memoria; si vas por velocidad , tu programa será muy diferente.

(El énfasis es mío).

Answer 6

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 es utilizado por 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 strlen a 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 único (?) bueno para usar SIMD para acelerar las funciones en cadenas de longitud implícita donde el control de bucle depende de los datos. pcmpeqb / pmovmskb hace 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 usa 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 para strlen con 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 rep scasb línea rep scasb que es muy lento, o un rep scasb 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 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 este strlen no puede strlen con nada más. No es seguro para eso; contiene UB de alias estricto (lectura de datos de caracteres a través de un unsigned long* ). char* puede alias cualquier otra cosa, pero lo contrario no es cierto .

Esta es una función de biblioteca para una biblioteca compilada antes de tiempo (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 adelantado 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 tiempo de 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 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 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 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 de gcc GIMPLE para la optimización del tiempo de enlace al integrarse 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 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 la implementación de printf )

Este strlen hace algunas suposiciones:

• CHAR_BIT es un múltiplo de 8 . Verdadero 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 no 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 utiliza un assert() 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:

• 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. (Verdadero en asm en todos los sistemas GNU, y en todas las CPU normales porque la protección de 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 el momento de la compilación. Sin alinear, 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[] 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 implica que una ruta de ejecución es inalcanzable. 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 antigua macro CPP de memcpy insegura del kernel de Linux que usaba la conversión de puntero a unsigned long ( gcc, alias estricto e historias de terror ).

Este strlen se remonta a la época en que se 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 mira a través de los límites de llamadas / ret no puede hacernos daño. (por ejemplo, invocar esto en un char buf[] lugar de en una matriz de unsigned long[] a un const 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_alias le da a un tipo el mismo tratamiento de alias-cualquier cosa que char* . (Sugerido por @KonradBorowsk). Los encabezados de GCC actualmente lo usan para tipos de vectores SIMD x86 como __m128i por lo que siempre puede hacer _mm_loadu_si128( (__m128i*)foo ) forma segura. (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).

strlen(const char *char_ptr)
{
typedef unsigned long __attribute__((may_alias)) aliasing_ulong;
aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;
for (;;) {
unsigned long ulong = *longword_ptr++; // can safely alias anything
...
}
}

También puede usar aligned(1) para expresar un tipo con alignof(T) = 1 .
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;

Una forma portátil de expresar una carga de alias en ISO es con memcpy , que los compiladores modernos saben cómo incorporar 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 por acceso char -a-a-time. Pero en la práctica, los compiladores modernos entienden muy bien la 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 antes de MIPS64r6, o ARM anterior. Si memcpy una llamada de función real a memcpy solo para cargar una palabra (y dejarla en otra memoria), 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 usar
p = __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 la última caída 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 ingenua vs. bithack C sin ninguna característica específica de ISA.

(Creo que podemos dar por strlen que strlen se usa lo suficiente como para que sea tan rápido como sea 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 un if()break dependiente de datos, así como un contador.

ICC (el 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 un strlen C simple / ingenuo como el que usa la libc de OpenBSD. ( Godbolt ) (De la respuesta de @ Peske ).

Un libc strlen optimizado a strlen es necesario 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. (2 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 los vectores de 256 bits, AVX512VL + BW enmascarado se compara en una máscara y ktest o kortest podría hacer que strlen más amigable con el hyperthreading al reducir su 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 un rendimiento de ejecución suficiente para que strlen pueda mantenerse 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.

Answer 7

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 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 about the sizes of the datatypes are not violated when the code is used.

En la mayoría (pero no en todo) el desarrollo de software moderno, esta atención al detalle de la 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

Answer 8

TL; DR no necesita y nunca debe escribir código como ese, especialmente si no es un compilador de C / proveedor de biblioteca estándar. Es un código utilizado para implementar strlen con algunos strlen y suposiciones de velocidad muy cuestionables:

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

Ademá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 simple llamada a strlen incorporado, pero es poco probable que note que el código más largo debería hacer lo mismo.

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, 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 conocidos no siempre es algo malo. Especialmente en el código que es 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 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 esto debe hacerse absolutamente para que el próximo truco sucio sea aún más sucio. (En la práctica, en alguna arquitectura de CPU que no sea 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 rompe la promesa y lee 4 u 8 bytes de 8 bits a la vez (un long int ), y usa un truco de bits con adición sin signo para averiguar rápidamente si había cero bytes dentro de esos 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 de lo que lo 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 los casos sizeof (unsigned long) - 1 veces fuera del 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 por la implementación e indefinidos y no debe usarse en ningún lugar en lugar del strlen proporcionado por el sistema. strlen nombre de la función a the_strlen aquí y agregué lo siguiente:

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

El búfer está dimensionado 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.