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

286

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?

Carreras de ligereza en órbita
fuente
2
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Samuel Liew
18
Para futuras referencias, el repositorio fuente oficial para GNU libc está en < sourceware.org/git/?p=glibc.git >. < sourceware.org/git/?p=glibc.git;a=blob;f=string/… > de hecho muestra un código similar al anterior; sin embargo, 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).
zwol
9
Votar para cerrar esto como principalmente basado en opiniones; "¿Realmente se necesita xxx en xxx?" es subjetivo a las opiniones de las personas.
SS Anne
2
@ JL2210: Buen punto, arreglé el título para capturar el espíritu de la pregunta en un título que no parece que se pregunte si se necesita rendimiento, sino por qué necesitamos estas optimizaciones para obtener el rendimiento.
Peter Cordes
9
@ JL2210 FWIW, el título original era "¿Por qué es tan complejo en C [sic!]", Y se cerró como "demasiado amplio", luego se volvió a abrir y luego se cerró como "principalmente basado en la opinión". Traté de arreglar esto (entrando en el fuego cruzado de "¡rompiste mi pregunta!" Y "¡Ustedes están abusando de sus poderes de edición!" Mientras tanto), pero en mi humilde opinión el problema mintió (y aún reside) en la premisa básica de la pregunta, lo cual era problemático ("este código es demasiado complejo para que yo lo entienda" no es adecuado para preguntas y respuestas; en mi opinión, es una solicitud de tutoría, no una respuesta). No lo volveré a tocar con un poste de 60 pies :)

Respuestas:

233

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 long es de 4 u 8 bytes
  • los bytes son 8 bits
  • se puede lanzar un puntero unsigned long longy nouintptr_t
  • se puede alinear el puntero simplemente comprobando que los 2 o 3 bits de orden más bajo son cero
  • uno puede acceder a una cadena como unsigned longs
  • 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;
}

(observe que tiene que ser un tipo compatible con size_t) con una versión en línea del compilador incorporado strlen, 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:

Descripción

  1. La strlenfunción calcula la longitud de la cadena apuntada por s.

Devoluciones

  1. La strlenfunción devuelve el número de caracteres que preceden al carácter nulo final.

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 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 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 del unsigned 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 de sizeof (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 provisto strlen. Cambié el nombre de la función the_strlenaquí y agregué lo 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 hello worldcadena y el terminador. Sin embargo, en mi procesador de 64 bits unsigned 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:

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

Antti Haapala
fuente
120
Re: "trucos y suposiciones de velocidad muy cuestionables", es decir, muy cuestionables en el código portátil . La biblioteca estándar está escrita para una combinación particular de compilador / hardware, con conocimiento del comportamiento real de las cosas que la definición del lenguaje deja como indefinidas. Sí, la mayoría de las personas no deberían escribir código como ese, pero en el contexto de la implementación de la biblioteca estándar no portátil no es inherentemente malo.
Pete Becker
44
De acuerdo, nunca escribas cosas como esta tú mismo. O casi nunca. La optimización prematura es la fuente de todo mal. (En este caso, en realidad podría estar motivado). Si termina haciendo muchas llamadas strlen () en la misma cadena muy larga, su aplicación quizás podría escribirse de manera diferente. Migra como ejemplo, guarda la longitud de cadena en una variable ya cuando se crea la cadena, y no necesita llamar a strlen () en absoluto.
ghellquist
65
@ghellquist: La optimización de una llamada de biblioteca de uso frecuente no es "optimización prematura".
jamesqf
77
@Antti Haapala: ¿Exactamente por qué crees que strlen debería ser O (1)? Y lo que tenemos aquí son varias implementaciones, todas las cuales son O (n), pero con diferentes multiplicadores constantes. Puede que no piense que eso importa, pero para algunos de nosotros una implementación de un algoritmo O (n) que hace su trabajo en microsegundos es mucho mejor que uno que lleva segundos, o incluso milisegundos, porque podría llamarse varios miles de millones de veces en el curso de un trabajo.
jamesqf
8
@PeteBecker: no solo eso, en el contexto de las bibliotecas estándar (aunque no tanto en este caso), escribir código no portátil puede ser la norma, ya que el propósito de una biblioteca estándar es proporcionar una interfaz estándar para cosas específicas de implementación.
PlasmaHH
148

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 de chardatos a través de un unsigned 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 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 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 , 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 printfimplementación)


Esto strlenhace algunas suposiciones:

  • CHAR_BITes 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= 16o 32, como algunos DSP; el bucle de prólogo no alineado siempre ejecutará 0 iteraciones si sizeof(long) = sizeof(char) = 1cada puntero siempre está alineado y p & 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.
  • (tal vez) unsigned longes de 4 u 8 bytes. O tal vez realmente funcione para cualquier tamaño de unsigned longhasta 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 primero 0es UB; podría ser una char[]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 memcpy macro CPP insegura del kernel de Linux que usaba puntero-casting para unsigned 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 de unsigned long[]conversión a a 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 GCCmay_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 __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).

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;

Es una forma portátil de expresar una carga de alias en ISOmemcpy , con la cual los compiladores modernos saben cómo alinearse 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 memcpyfunciona como si fuera por characceso a la vez. Pero en la práctica, los compiladores modernos entienden memcpymuy 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 real memcpysolo 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 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 el último rendimiento para una función de biblioteca estándar ampliamente utilizada. Especialmente para algo así 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 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 y ktest, o kortestpodría hacer strlenmá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.

Peter Cordes
fuente
12
Algunas notas: (1) Actualmente no es posible compilar glibc en sí con ningún compilador que no sea GCC. (2) Actualmente no es posible compilar glibc por sí mismo con las optimizaciones de tiempo de enlace habilitadas, debido precisamente a este tipo de casos, en los que el compilador verá UB si se permite la incorporación. (3) CHAR_BIT == 8es un requisito POSIX (como de la -2,001 rev; ver aquí ). (4) La implementación de strlenrespaldo de C se usa para algunas CPU compatibles, creo que la más común es MIPS.
zwol
1
Curiosamente, el UB de alias estricto podría repararse haciendo uso del __attribute__((__may_alias__))atributo (esto no es portátil, pero debería estar bien para glibc).
Konrad Borowski
1
@SebastianRedl: puede leer / escribir cualquier objeto a través de a char*, pero todavía es UB leer / escribir un char objeto (por ejemplo, parte de a char[]) a través de a long*. Regla de alias estricta y punteros 'char *'
Peter Cordes
1
Los estándares C y C ++ dicen que CHAR_BITdebe ser al menos 8 ( qv Anexo E de C11), por lo que al menos 7 bits charno 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 tipo chary se inicializan con los caracteres de la secuencia de caracteres multibyte, como se codifica en UTF − 8".
Davislor
2
Parece que este análisis es una buena base para proponer un parche que haga que el código sea más robusto frente a las optimizaciones actualmente deshabilitadas, además de dar una respuesta increíble.
Deduplicador
61

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

Timothy Jones
fuente
39

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

Peschke
fuente
55
Eso hace una muy buena ilustración de los diferentes valores que se optimizan en OpenBSD vs GNU tools.
Jason
11
Es la implementación de respaldo portátil de glibc . Todas las principales ISA tienen implementaciones de asm escritas a mano en glibc, utilizando SIMD cuando ayuda (por ejemplo, en x86). Ver code.woboq.org/userspace/glibc/sysdeps/x86_64/multiarch/… y code.woboq.org/userspace/glibc/sysdeps/aarch64/multiarch/…
Peter Cordes
44
¡Incluso la versión OpenBSD tiene una falla que el original evita! El comportamiento de s - strno está definido si el resultado no es representable en ptrdiff_t.
Antti Haapala
1
@AnttiHaapala: en GNU C, el tamaño máximo del objeto es PTRDIFF_MAX. Pero todavía es posible tener mmapmá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 eso returnsin 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. Aunque strlenno puede en línea y los compiladores reales solo lo compilarán en una resta.
Peter Cordes
2
@PeterCordes exactamente. Lo mismo en OpenBSD, por ejemplo, ensamblado i386: cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/arch/i386/string/…
dchest
34

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 (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 != 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 que 0x80, 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.

Konrad Borowski
fuente
Esta implementación es parte de glibc. El sistema GNU protege la memoria con granularidad de página. Entonces, sí, una carga alineada que incluye bytes válidos es segura.
Peter Cordes
size_tNo se garantiza que esté alineado.
SS Anne
32

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

gnasher729
fuente
O ... Si descubro que estoy haciendo mucho procesamiento basado en cadenas y hay un cuello de botella, probablemente implemente mi propia versión de Pascal Strings en lugar de mejorar strlen ...
Baldrickk
1
Nadie le pide que mejore strlen. Pero hacerlo lo suficientemente bueno evita tonterías como las personas que implementan sus propias cadenas.
gnasher729
24

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.

Lundin
fuente
1
Por supuesto, es muy probable que el optimizador desenrolle o vectorice automáticamente este bucle, y el pretratador puede detectar trivialmente este patrón de acceso. Sería necesario probar si estos trucos realmente importan en los procesadores modernos. Si se puede ganar, probablemente esté usando instrucciones vectoriales.
russbishop
66
@russbishop: Eso esperarías, pero no. GCC y clang son completamente incapaces de auto-vectorizar bucles donde el recuento de iteraciones no se conoce antes de la primera iteración. Eso incluye bucles de búsqueda o cualquier otro bucle con datos dependientes if()break. ICC puede auto-vectorizar tales bucles, pero IDK qué tan bien lo hace con un ingenuo strlen. Y sí, SSE2 pcmpeqb/ 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 .
Peter Cordes
Oof, eso es desafortunado. Por lo general, soy muy anti-UB pero, como usted señala, las cadenas C requieren la lectura de fin de búfer técnicamente UB para permitir incluso la vectorización. Creo que lo mismo se aplica a ARM64 ya que requiere alineación.
ruso obispo
-6

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

Jack Kelly
fuente
55
¿Cómo responde esto a la pregunta?
SS Anne
1
La pregunta en OP era "¿no funcionaría mejor este código más simple?", Y esa es una pregunta que no siempre se decide por mérito técnico. Para un proyecto como GNU, evitar las trampas legales es una parte importante del código que "funciona mejor", y 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.
Jack Kelly el