GitHub ha logrado optimizar significativamente el proceso de «case folding», una operación esencial en la indexación y búsqueda de texto. Este proceso es crucial para igualar cadenas de texto que solo se diferencian en el uso de mayúsculas o minúsculas, como ocurre con palabras como café y CAFÉ.
El motor de búsqueda de código de GitHub, Blackbird, que indexa más de 180 millones de repositorios, realiza el «case folding» sobre cada byte antes de extraer fragmentos y construir su índice. A gran escala, la velocidad de esta operación básica se vuelve crítica.
GitHub ha aplicado una estrategia inusual pero efectiva: eliminar una optimización en lugar de agregar una. Su enfoque anterior implicaba detenerse al encontrar un byte no ASCII, pero descubrieron que barrer todo el búfer sin interrupciones era más rápido. Han desarrollado un crate de Rust llamado «casefold» que encapsula este enfoque.
Una diferencia clave entre conversiones de texto, como el «case folding» y pasar a minúsculas, es que este último es sensible al contexto y al idioma, mientras que el primero es un proceso más simple y coherente.
En un esfuerzo por aumentar la eficiencia, el nuevo método de GitHub implementa una serie de técnicas para evitar bifurcaciones en el flujo de código, logrando que el proceso sea más veloz y funcionando casi a la velocidad del ancho de banda de la memoria.
Este avance se logra en parte gracias a la ausencia de bifurcaciones condicionadas y al uso de operaciones aritméticas byte a byte en lugar de decodificar caracteres completos. Este doble beneficio permite que el proceso se ejecute rápido y con un espacio de tabla reducido, manteniendo la memoria eficiente.
GitHub compartió esta innovación al público mediante un crate de Rust, brindando una oportunidad para que otros desarrolladores y empresas optimicen sus procesos de gestión de texto de manera similar.
vÃa: Github Open Source