GitHub logró ejecutar la operación de plegado de mayúsculas y minúsculas, o Case Folding, a una velocidad superior a 45 gigabytes por segundo en un solo núcleo mediante el rediseño del bucle de software para que no se detuviera ante el primer byte no ASCII, sino que recorriera todo el búfer sin ramas de control dependientes de los datos. La empresa utiliza esta operación en el motor de búsqueda de código Blackbird, que indexa más de 180 millones de repositorios y más de 480 terabytes de código fuente.
Alexander Neubeck y Greg Orzell presentaron los detalles de este diseño en una entrada publicada en el blog de GitHub el 31 de julio de 2026. La entrada también anunció que el resultado estaría disponible en una biblioteca de Rust de código abierto llamada casefold.
El plegado de mayúsculas y minúsculas no consiste simplemente en convertir a minúsculas
Los motores de búsqueda y las herramientas que comparan textos necesitan una representación estándar que haga que las cadenas que difieren en el uso de mayúsculas y minúsculas sean iguales al compararlas. Esto aparece en las búsquedas, las expresiones regulares que no distinguen entre mayúsculas y minúsculas, y los nombres de usuario y de host.
Sin embargo, convertir el texto a minúsculas no produce el mismo resultado. La conversión a minúsculas puede depender del idioma y del contexto, como ocurre con la diferencia entre la forma de la sigma griega al final de una palabra y dentro de ella, o con las distintas reglas para la letra I en turco. En cambio, el plegado de mayúsculas y minúsculas está diseñado para la comparación, por lo que es independiente del idioma y del contexto. El resultado también difiere en casos como la letra alemana ß, la letra turca İ y la sigma griega final.
La biblioteca realiza un plegado simple uno a uno, conforme a los estados C y S del archivo CaseFolding.txt de la base de datos de caracteres Unicode. No ejecuta operaciones de plegado de múltiples caracteres, como convertir ß en ss, ni operaciones de plegado específicas del turco.
Eliminar la optimización que ralentizaba el bucle
Dado que el código fuente está compuesto en su mayor parte por caracteres ASCII, la ruta más rápida se centra en convertir las letras latinas mayúsculas de A a Z en minúsculas. El diseño intuitivo se detenía inmediatamente al encontrar un byte no ASCII y luego trasladaba el resto del texto a una ruta Unicode. Sin embargo, las pruebas realizadas en un procesador Apple M4 mostraron que este método no superaba aproximadamente los 3 gigabytes por segundo.
La causa principal eran las ramas de control dentro del bucle. En lugar de comprobar cada byte y detenerse pronto, el algoritmo reúne el bit más alto de todos los bytes en una sola variable y comprueba el resultado después de terminar el recorrido. La comprobación de si el byte se encuentra dentro del rango de las letras mayúsculas se realiza mediante aritmética: se resta el carácter A con envoltura y se compara el resultado con el número 26. Después se utiliza una máscara aritmética para establecer el quinto bit del byte, lo que convierte la letra mayúscula en minúscula sin una rama ni una escritura condicional.
Esta estructura permite al compilador LLVM generar instrucciones vectoriales que procesan 16 bytes cada vez mediante NEON en el Apple M4. El resultado supera los 45 gigabytes por segundo, acercándose al límite del ancho de banda de la memoria. Las mediciones de GitHub indican que eliminar la salida temprana fue el factor que permitió la vectorización; mantener la salida basada en los datos impide generar instrucciones vectoriales aunque el resto del bucle quede libre de ramas.
¿Por qué el recorrido combinado no siempre es más rápido?
GitHub probó una solución intermedia basada en comprobar el ASCII en bloques y luego convertir el prefijo ASCII. Este método lee los datos dos veces, pero alcanzó aproximadamente 23 gigabytes por segundo, mucho más rápido que el bucle ingenuo, y conservó la capacidad de detenerse en el primer bloque no ASCII.
En cambio, combinar la comprobación y la conversión en un solo bucle que opera sobre bloques de 16 bytes fue más lento: alcanzó aproximadamente 8,7 gigabytes por segundo, frente a los 23 gigabytes por segundo de la solución de dos pasadas. Según la entrada, una rama de salida temprana después de cada bloque impide que el compilador desenrolle el bucle o oculte la latencia entre la lectura, la comprobación, la conversión y la escritura. Por ello, dos bucles limpios y aptos para la vectorización superaron a un solo bucle que toca los datos menos veces, pero contiene una rama dependiente del contenido.
Reducir las asignaciones de memoria
La función simple_fold recibe una cadena String por propiedad, lo que le permite modificar su búfer y devolverlo directamente. Si el texto es completamente ASCII, se devuelve la misma memoria después de convertir las letras en el lugar, sin un segundo búfer ni copias adicionales.
Cuando hay caracteres no ASCII, el algoritmo no crea un búfer nuevo hasta llegar a un carácter cuya longitud o contenido cambie. La entrada explica que la mayoría de las operaciones de plegado conservan o reducen la longitud UTF-8, pero los caracteres U+023A y U+023E pueden aumentar cada uno de dos a tres bytes. Por ello, el algoritmo reserva una sola vez una capacidad máxima de aproximadamente 1,5 veces la longitud de entrada, en lugar de ampliar el búfer gradualmente y volver a copiar los datos.
También mueve los grupos de bytes que no han cambiado mediante copy_nonoverlapping, en lugar de copiarlos byte a byte. Mantiene algunos textos no latinos, como CJK, Hangul, Kana, árabe, hebreo y símbolos, en su asignación original cuando no contienen caracteres que requieran plegado.
Procesar Unicode en el espacio de bytes
Unicode 16.0 contiene 1484 operaciones de plegado simple, pero GitHub comprimió su tabla a 1776 bytes aprovechando la concentración de caracteres plegables en páginas de 64 puntos de código. Para comprobar si un carácter necesita plegarse, el algoritmo utiliza un mapa de bits; si el bit correspondiente no está activado, el carácter se descarta inmediatamente sin decodificar UTF-8 ni buscarlo en una tabla hash.
Dentro de las páginas que contienen operaciones de plegado, el algoritmo almacena rangos contiguos en lugar de un registro separado para cada punto de código. Los rangos se describen mediante un inicio, un final, un paso y una diferencia, lo que reduce unas 1484 operaciones a 238 rangos distribuidos en 59 páginas. También utiliza una comparación paralela sobre ocho claves a la vez para determinar el rango adecuado.
Después de encontrar el rango, los caracteres plegados se calculan sumando bytes a nivel de UTF-8 con una constante específica del rango, en lugar de decodificar el carácter a un punto de código y volver a codificarlo. Esto permite gestionar los cambios de longitud, como convertir U+212A, el símbolo del kelvin, de tres bytes a la letra k de un byte, o convertir U+023A en un carácter de tres bytes.
Este método supone que la entrada es UTF-8 válido y está en forma reducida, una propiedad garantizada por los tipos String y str de Rust. En cambio, los datos sin procesar procedentes de otras fuentes deben validarse o normalizarse antes de utilizar estos cálculos.
El resultado y los límites de las mediciones
En el caso común de ASCII, la velocidad de la biblioteca supera los 45 gigabytes por segundo, más de un 50 % superior a la de la función no exactamente equivalente str::to_lowercase, según las mediciones incluidas en la entrada. En los peores casos de entrada, en los que la mayoría de los caracteres necesitan plegarse, las soluciones basadas en cálculos en el espacio de bytes fueron aproximadamente dos veces más rápidas que la ruta optimizada de decodificación y recodificación de UTF-8.
GitHub confirma que las cifras y los porcentajes de comparación son orientativos y no se pueden trasladar literalmente entre procesadores, porque dependen de la vectorización automática, SWAR, los cálculos de bytes en orden little-endian, además del ancho de banda de la memoria y la arquitectura del procesador. La entrada resume la idea en dos principios: recorrer completamente la ruta común sin ramas y ejecutar la ruta poco frecuente específica de Unicode en el espacio de bytes, en lugar de decodificar y volver a codificar los caracteres.