Hace poco se dio a conocer una propuesta para el kernel de Linux, en la cual se propone incluir un conjunto de parches con una implementación optimizada de la función memchr() utilizada para buscar un carácter en una matriz.

La función memchr() escanea los n bytes iniciales del área de memoria apuntada por s para la primera instancia de c. Tanto c como los bytes del área de memoria a la que apunta s se interpretan como caracteres sin signo.

La propuesta promete ser más rápida para ubicar un carácter dentro de un bloque de memoria. En las pruebas realizadas por el desarrollador, la nueva implementación puede ser casi cuatro veces más rápida en búsquedas grandes

A diferencia de la versión anterior, que utilizaba una comparación byte por byte, la implementación propuesta se crea teniendo en cuenta el uso completo de los registros de la CPU de 64 y 32 bits. En lugar de bytes, la comparación se realiza mediante palabras de máquina, lo que permite comparar al menos 4 bytes a la vez.

Esta serie de parches optimizó «memchr()» y agregó una macro para
«memchr_inv()» para que ambas funciones puedan usarla para generar una máscara de bits.

La implementación original de «memchr()» se basa en la comparación de bytes,
que no utiliza completamente el registro de 64 o 32 bits en la CPU. Implementamos una
comparación por palabras para que se puedan comparar al menos 4 bytes al mismo
tiempo. El «memchr()» optimizado es casi 4 veces más rápido que el original
para cadenas largas. En Linux Kernel, encontramos que la longitud de la cadena
buscada por «memchr()» es de hasta 512 bytes en drivers/misc/lkdtm/heap.c.

Al buscar en cadenas grandes, la nueva versión resultó ser unas 4 veces más rápida que la anterior (por ejemplo, para cadenas de 1000 caracteres). Para cadenas pequeñas, la eficiencia de la nueva implementación no es tan significativa, pero sigue siendo mayor que la versión original.

Lo interesante de la nueva propuesta es la mejora para cadenas grandes, lo cual mejora bastante los tiempos. Cabe mencionar que en el kernel de Linux, el tamaño de las cadenas procesadas en memchr() alcanza los 512 bytes. En las pruebas realizadas la ganancia de rendimiento para cadenas de 512 bytes, en una situación en la que el carácter de búsqueda se encuentra al final de la cadena, es del 20 %.

Cabe mencionar que la versión original de memchr() se implementa con la técnica de comparación byte-wise, que no utiliza completamente los registros en la CPU 64 bits o 32 bits.

Usamos la comparación de toda la palabra para que 8 caracteres se puede comparar al mismo tiempo en la CPU. Este código se basa en la implementación de David Laight.

Creamos dos archivos para medir el rendimiento del primer archivo el cual contiene en promedio 10 caracteres por delante del carácter de destino. El segundo archivo contiene al menos 1000 caracteres delante del personaje objetivo.

Nuestra implementación de «memchr()» es ligeramente mejor en la primera prueba y casi 4 veces más rápido que el original implementación en la segunda prueba.

La prueba del kernel 5.18 con la nueva variante «memchr()» para arquitecturas de 32 y 64 bits no reveló ningún problema.

Qué sucede si p no está alineado con 8 (o 4 en objetivos de 32 bits) bytes? No todo los objetivos admiten cargas no alineadas (eficientes), ¿verdad?
 Creo que funciona si p no está alineado a 8 o 4 bytes. Digamos que la cadena es de 10 bytes. El bucle for aquí buscará el primero 8 bytes. Si el carácter de destino está en los últimos 2 bytes, el segundo para bucle lo encontrará. También funciona así en máquinas de 32 bits.

Aún no se ha evaluado la ganancia de rendimiento general de los subsistemas del kernel cuando se usa la variante «memchr()» optimizada, ni se ha analizado la conveniencia de reemplazar la implementación (la llamada a la función memchr() ocurre 129 veces en el código del kernel, incluso en el código de controladores y sistemas de archivos).

Finalmente si estás interesado en poder conocer más al respecto, puedes consultar los detalles en el siguiente enlace.