strlen es una función bastante simple, y obviamente es O(n) para calcular. Sin embargo, he visto algunos enfoques que operan en más de un personaje a la vez . Vea el ejemplo 5 aquí o este enfoque aquí . La forma básica en que funcionan es reinterpretando el búfer char const* en un búfer uint32_t const* y luego verificando cuatro bytes a la vez.
Personalmente, mi reacción instintiva es que se trata de un error de segmento a la espera de que suceda, ya que podría desreferenciar hasta tres bytes fuera de la memoria válida. Sin embargo, esta solución parece mantenerse, y me parece curioso que algo tan obviamente roto haya resistido la prueba del tiempo.
Creo que esto comprende UB por dos razones:
( Tenga en cuenta que no hay un problema de creación de alias; uno podría pensar que uint32_t tiene un alias como un tipo incompatible, y el código después de strlen (como el código que podría cambiar la cadena) podría funcionar fuera de orden para strlen , pero resulta que ese char es una excepción explícita al alias estricto ).
Pero, ¿cuál es la probabilidad de que fracase en la práctica? Como mínimo, creo que debe haber un relleno de 3 bytes después de la sección de datos literales de cadena, malloc debe estar alineado en 4 bytes o más (en realidad, el caso en la mayoría de los sistemas), y malloc debe asignar 3 bytes adicionales. Hay otros criterios relacionados con el aliasing. Todo esto está bien para las implementaciones de compiladores, que crean sus propios entornos, pero ¿con qué frecuencia se cumplen estas condiciones en el hardware moderno para el código de usuario?
La técnica es válida y no la evitará si llama a nuestra biblioteca C strlen . Si esa biblioteca es, por ejemplo, una versión reciente de la biblioteca GNU C (al menos en ciertos objetivos), hace lo mismo.
La clave para que funcione es asegurarse de que el puntero esté alineado correctamente. Si el puntero está alineado, la operación leerá más allá del final de la cadena, pero no en una página adyacente. Si el byte de terminación nulo está dentro de una palabra del final de una página, se accederá a esa última palabra sin tocar la página siguiente.
Ciertamente no es un comportamiento bien definido en C, por lo que conlleva la carga de una validación cuidadosa cuando se transfiere de un compilador a otro. También activa falsos positivos de detectores de acceso fuera de límites como Valgrind.
Valgrind tuvo que ser reparado para evitar que Glibc hiciera esto. Sin los parches, obtiene errores molestos como este:
==13669== Invalid read of size 8 ==13669== at 0x411D6D7: __wcslen_sse2 (wcslen-sse2.S:59) ==13669== by 0x806923F: length_str (lib.c:2410) ==13669== by 0x807E61A: string_out_put_string (stream.c:997) ==13669== by 0x8075853: obj_pprint (lib.c:7103) ==13669== by 0x8084318: vformat (stream.c:2033) ==13669== by 0x8081599: format (stream.c:2100) ==13669== by 0x408F4D2: (below main) (libc-start.c:226) ==13669== Address 0x43bcaf8 is 56 bytes inside a block of size 60 alloc'd ==13669== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so) ==13669== by 0x8063C4F: chk_malloc (lib.c:1763) ==13669== by 0x806CD79: sub_str (lib.c:2653) ==13669== by 0x804A7E2: sysroot_helper (txr.c:233) ==13669== by 0x408F4D2: (below main) (libc-start.c:226) Glibc está usando instrucciones SSE para calcular wcslen ocho bytes a la vez (en lugar de cuatro, el ancho de wchar_t ). Al hacerlo, accede al desplazamiento 56 en un bloque de 60 bytes de ancho. Sin embargo, tenga en cuenta que este acceso nunca podría cruzar el límite de una página: la dirección es divisible por 8.
Si está trabajando en lenguaje ensamblador, no tiene que pensar dos veces en la técnica.
De hecho, la técnica se usa bastante en algunos códecs de audio optimizados con los que trabajo (apuntando a ARM), que presentan una gran cantidad de lenguaje ensamblador escrito a mano en el conjunto de instrucciones de Neon.
Lo noté cuando ejecuté Valgrind en el código que integraba estos códecs y me puse en contacto con el proveedor. Explicaron que era solo una técnica de optimización de bucle inofensiva; Revisé el lenguaje ensamblador y me convencí de que tenían razón.
(1) definitivamente puede suceder. No hay nada que le impida tomar el strlen de una cadena cerca del final de una página asignada, lo que podría resultar en un acceso más allá del final de la memoria asignada y un gran bloqueo. Como observa, esto podría mitigarse rellenando todas sus asignaciones, pero luego debe hacer que las bibliotecas hagan lo mismo. Peor aún, debe hacer arreglos para que el enlazador y el sistema operativo agreguen siempre este relleno (recuerde que el sistema operativo pasa argv[] en un búfer de memoria estática en alguna parte). La sobrecarga de hacer esto no vale la pena.
(2) definitivamente también sucede. Las versiones anteriores de los procesadores ARM generan abortos de datos en los accesos no alineados, lo que hace que su programa muera con un error de bus (o detiene la CPU si está ejecutando bare-metal), o fuerza una trampa muy costosa a través del kernel para manejar el acceso no alineado. Estos chips ARM anteriores todavía se usan ampliamente en teléfonos celulares y dispositivos integrados más antiguos. Los procesadores ARM posteriores sintetizan accesos de múltiples palabras para lidiar con accesos no alineados, pero esto dará como resultado un rendimiento general más lento ya que básicamente duplicará la cantidad de cargas de memoria que necesita hacer.
Muchos PIC actuales ("modernos") y microprocesadores incorporados carecen de la lógica para manejar accesos no alineados y pueden comportarse de manera impredecible o incluso sin sentido cuando se les dan direcciones no alineadas (personalmente he visto chips que simplemente enmascaran los bits inferiores, lo que daría información incorrecta). respuestas, y otros que solo darán resultados basura con accesos no alineados).
Por lo tanto, esto es ridículamente peligroso de usar en cualquier cosa que deba ser portátil de forma remota. Por favor, por favor, no utilice este código; utilice la libc strlen. Por lo general, será más rápido (optimizado para su plataforma correctamente) y hará que su código sea portátil. Lo último que desea es que su código se rompa sutil e inesperadamente en alguna situación (cadena cerca del final de una asignación) o en algún procesador nuevo.
Donald Knuth, una persona que escribió más de 3 volúmenes sobre algoritmos inteligentes, dijo: "La optimización prematura es la raíz de todos los males".
strlen() se usa mucho, por lo que realmente debería ser rápido. Basándose en el comentario de wildplasser, "Confiaría en la función de la biblioteca", ¿qué te hace pensar que la función de la biblioteca funciona byte a la vez? ¿O es lento?
El título puede dar a la gente la impresión de que el código que sugieres es más rápido que la biblioteca del sistema estándar strlen() , pero creo que lo que quieres decir es que es más rápido que un strlen() ingenuo que probablemente no se use de todos modos.
Compilé un programa simple en C y busqué en mi sistema de 64 bits que usa la función glibc de GNU. El código que vi era bastante sofisticado y parece bastante rápido en términos de trabajar con ancho de registro en lugar de byte a la vez. El código que vi para strlen () está escrito en lenguaje ensamblador, por lo que probablemente no haya instrucciones basura como las que podría obtener si se compilara en código C. Lo que vi fue rtld-strlen.S . Este código también desenrolla los bucles para reducir la sobrecarga en los bucles.
Antes de pensar que puede hacerlo mejor en strlen, debe mirar ese código, o el código correspondiente para su arquitectura particular, y registrar el tamaño.
Y si escribe su propio strlen, compare con la implementación existente.
Y obviamente, si usa el sistema strlen, probablemente sea correcto y no tenga que preocuparse por las referencias de memoria no válidas como resultado de una optimización en el código.