Cómo GitHub logró case-folding a +45 GiB/s con Rust y aritmética de bytes

Introducción

El motor de búsqueda de código de GitHub, Blackbird, indexa más de 180 millones de repositorios con un total de 480 TB de código fuente. Cada byte de este corpus debe ser transformado a una forma canónica (case folding) antes de extraer n-gramas y construir el índice. Además, cada resultado potencial de una consulta requiere otra operación de case folding para localizar coincidencias. A esta escala, incluso optimizaciones marginales en una operación aparentemente simple tienen un impacto masivo en el rendimiento y los costos operativos.

El problema no es solo la velocidad: usar str::to_lowercase() de Rust (o equivalentes en otros lenguajes) introduce bugs sutiles de seguridad. El case folding para comparación no es lo mismo que el lowercase para display, y diferencias en caracteres como ß, İ o sigma final pueden llevar a falsos negativos o positivos en búsquedas. GitHub resolvió ambos problemas con una implementación personalizada en Rust, liberada como crate público casefold.

Qué ocurrió

GitHub desarrolló una función de case folding optimizada para su motor de búsqueda de código, logrando un rendimiento superior a 45 GiB/s en un único core de CPU. El avance clave fue contrario a la intuición: eliminar una optimización común (detener el procesamiento al encontrar el primer byte no-ASCII) y reemplazarla con un loop sin branches que procesa todo el buffer usando aritmética de bytes.

La implementación superó tanto a str::to_lowercase() de Rust como a librerías ICUNeon (basadas en ICU), incluso para datos ASCII puros. Para texto no-ASCII, el rendimiento se mantiene competitivo mientras garantiza corrección según el estándar Unicode. GitHub open-sourció el resultado como el crate casefold.

Impacto para DevOps / Infraestructura / Cloud / Seguridad

Para equipos de DevOps e infraestructura, este caso exemplifica cómo optimizaciones a nivel de CPU pueden reducir costos en sistemas a gran escala. Procesar 480 TB de código con la implementación anterior habría requerido días; con el nuevo algoritmo, el tiempo se reduce drásticamente. En cloud, donde el consumo de CPU se traduce directamente en dólares, este tipo de mejoras impactan directamente en la factura.

Desde la perspectiva de seguridad, el uso incorrecto de to_lowercase() para comparación case-insensitive es un riesgo subestimado. Por ejemplo:

• El carácter ß (eszet) lowerCasea a ß, pero su case folding es ss. Una búsqueda de SS no coincidiría con STRAßE si se usa lowercase.
• El character İ (I con punto) lowerCasea a i̇ (i followed by combining dot), pero su case folding es i. Una comparación con i fallaría.

Detalles técnicos

El problema con las implementaciones estándar

Rust’s str::to_lowercase() y similares tienen dos desventajas para este uso caso:

1. Semántica incorrecta: Realizan lowercase (para display), no case folding (para comparación). Por ejemplo:

   assert_eq!("ß".to_lowercase(), "ß"); // Lowercase
   assert_eq!("ß".to_casefold(), "ss");  // Case folding
   

1. Rendimiento: Usan allocations y iteradores, lo que agrega overhead.

La optimización clave: branch-free ASCII

El 95% del código fuente en GitHub es ASCII. Para estos bytes, el case folding es simple: convertir A-Z a a-z (restando 32), dejar los demás sin cambios. La implementación naive sería:

for &byte in bytes.iter() {
    if byte >= b'A' && byte <= b'Z' {
        byte + 32
    } else {
        byte
    }
}

GitHub descubrió que eliminar la condición y procesar todos los bytes con aritmética es más rápido:

// Versión simplificada del algoritmo ASCII
for byte in bytes.iter_mut() {
    *byte = *byte | 0x20 // Convierte A-Z a a-z, no afecta otros bytes
}

Esta versión usa un OR bitwise con 0x20 (32 en decimal), que:

• Convierte A (65) en a (97): 65 | 32 = 97
• Convierte Z (90) en z (122): 90 | 32 = 122
• Deja a (97) como a: 97 | 32 = 97
• Deja 0 (48) como 0: 48 | 32 = 48

El loop sin branches permite:

• Mejor predicción de branch (ningún branch mispredicted)
• Vectorización automática por el compilador (SIMD)
• Procesamiento de múltiples bytes por instrucción

Manejo de Unicode

Para bytes no-ASCII (valores > 127), el algoritmo verifica si el byte es parte de una secuencia UTF-8 válida y aplica el case folding según CaseFolding.txt. esta parte es más compleja y menos optimizable, pero representa solo el 5% del datos.

Benchmarks

En un AMD EPYC 7763 (2.6 GHz):

• casefold: 45.7 GiB/s para ASCII, 4.7 GiB/s para Unicode mixto
• str::to_lowercase(): 1.5 GiB/s para ASCII, 1.0 GiB/s para Unicode mixto
• ICU Neons: 2.6 GiB/s para ASCII, 2.0 GiB/s para Unicode mixto

El crate casefold incluye benchmarks reproducibles con cargo bench.

Qué deberían hacer los administradores y equipos técnicos

Evaluar el uso de case folding vs lowercase

• Usá case folding para: comparación de strings (búsquedas, autenticación, validación de inputs).
• Usá lowercase para: display (mostrar texto al usuario).
• Auditá tu código base para buscar usos incorrectos de to_lowercase() o toUppercase() en contextos de comparación. En Rust, podés usar cargo clippy con la lint unnecessary_to_owned (y luego revisar manualmente) para encontrar puntos suspiciosos.

Adoptar el crate casefold donde corresponda

Si implementás búsqueda de código, indexado de texto o cualquier sistema que requiera case folding de alto rendimiento:

1. Agregá el crate a tu Cargo.toml:

   [dependencies]
   casefold = "0.1.0"
   

1. Reemplazá las llamadas a to_lowercase() con casefold::Casefolded::fold():

   use casefold::Casefolded;

   let folded = Casefolded::fold("STRAßE");
   assert_eq!(folded, "strasse");
   

1. Benchmarkeá el antes y después. En datos ASCII-dominantes, esperá mejoras de 10x o más.

Optimizar hot paths

Si no podés adoptar el crate casefold (por ejemplo, en otro lenguaje), aplicá los principios:

• Para datos ASCII puros, usá aritmética de bytes (OR 0x20) en un loop sin branches.
• Asegurate de que el compilador pueda vectorizar el loop (evitá function calls dentro del loop, usá iteradores sobre slices).
• Perfilá con herramientas como perf para verificar que el código se ejecuta sin branch mispredictions.

Revisar dependencias

Si usás librerías de case folding (como ICU), evaluá si su rendimiento es adecuado para tu escala. En algunos casos, una implementación especializada para tu distribución de datos (como la de GitHub) puede justificar el esfuerzo de desarrollo.

Conclusión

El caso de GitHub demuestra cómo un problema aparentemente resuelto (case folding) puede esconder oportunidades significativas de optimización y riesgos de seguridad. Al cuestionar supuestos («detenerse temprano es siempre mejor»), usar conocimiento de bajo nivel (aritmética de bytes, predicción de branches) y priorizar la corrección sobre la conveniencia, el equipo logró un orden de magnitud de mejora en rendimiento sin sacrificar exactitud.

Para equipos que operan sistemas a gran escala, las lecciones son claras: perfilá los hot paths, cuestioná las optimizaciones convencionales y no subestimes el impacto de las operaciones «básicas». En seguridad, recordá que la semántica de Unicode matters: usar la operación incorrecta para case-insensitive comparison puede llevar a vulnerabilidades sutiles.

Fuentes

Don’t stop early: Case-folding source code at memory speed