XiliuxUna librería de criptografía tenía un cuello de botella que nadie podía ver en las pruebas: cifrar medio megabyte costaba cincuenta segundos. Todas las pruebas pasaban. Llevaban pasando meses.
El motivo es una trampa que se repite: una optimización correcta, bien documentada, que arregla la constante y no el orden — y cuyo comentario, por estar bien escrito, convence a quien lo lee de que el problema ya está resuelto.
Qué hacía el código
Quipu representa datos cifrados como una secuencia de símbolos. Para eso convierte todo el mensaje a un único número entero enorme y lo va dividiendo para sacar los dígitos, igual que uno pasa un número de base 10 a base 2 a mano.
El código no dividía de uno en uno. Tenía una optimización sensata: dividir por la mayor potencia de la base que cabe en una palabra de máquina, sacando nueve dígitos por pasada en vez de uno. El comentario que la explicaba empezaba diciendo que hacerlo de uno en uno sería cuadrático, y a continuación explicaba la mejora.
Todo cierto. Y aun así el resultado seguía siendo cuadrático: sacar nueve dígitos por pasada divide el trabajo entre nueve, no cambia cómo crece.
Esa frase —«hacerlo así sería cuadrático»— se lee en pasado, como si describiera el estado anterior. Describía el actual.
La medición, que es lo único que lo dice
| Tamaño | Tiempo | Factor al duplicar |
|---|---|---|
| 64 KiB | 0,79 s | — |
| 128 KiB | 3,16 s | ×4,0 |
| 256 KiB | 12,6 s | ×4,0 |
| 512 KiB | 50,7 s | ×4,0 |
Cuatro exacto, tres veces seguidas. Eso es cuadrático de libro: cada vez que la entrada se dobla, el tiempo se multiplica por cuatro. Extrapolando, diez megabytes habrían costado unas cinco horas y media.
Y aquí está lo importante: una prueba de corrección no ve nada de esto. Un algoritmo lento produce exactamente los mismos bytes que uno rápido. El banco seguía verde, y seguiría verde para siempre.
La solución tiene doscientos años
No hacía falta inventar nada. La conversión de base por divide y vencerás es un algoritmo clásico: en vez de arrancar dígitos por un extremo, se parte el número por la mitad —dividiéndolo por una potencia que tiene la mitad de los dígitos— y se repite sobre cada mitad. El árbol tiene tantos niveles como duplicaciones caben en el tamaño, y en cada nivel se paga una multiplicación grande en vez de miles de divisiones.
| Tamaño | Antes | Después | |
|---|---|---|---|
| 512 KiB | 50 698 ms | 457 ms | 111× |
| 10 MiB | ~5,6 h | 41,4 s | ~490× |
El factor al duplicar bajó de 4,00 a 2,82, que tampoco es un número caprichoso: es lo que sale de combinar el árbol con la multiplicación rápida de enteros grandes.
Lo que hay que comprobar ANTES de escribirlo
Y esto es lo que separa una mejora de una que empeora: divide y vencerás solo compensa si la división de enteros grandes de tu librería es subcuadrática.
Si la división es la escolar, partir por la mitad y recurrir sigue siendo cuadrático, y con peor constante que el bucle que querías sustituir. Habrías escrito un algoritmo más elegante, más difícil de leer y más lento.
La librería usada resultó traer división recursiva de Burnikel-Ziegler, así que compensa. Eso se comprueba antes de escribir la primera línea, no después de medir un resultado decepcionante.
Cómo se evita esto en el próximo repositorio
La pregunta que ahorra las cinco horas y media no es «¿esto está optimizado?» sino «¿el ORDEN cambió, o solo la constante?» — y se responde con dos tamaños y una división, no leyendo el código:
- si al doblar la entrada el tiempo se multiplica por ~2, es lineal;
- si por ~4, es cuadrático;
- si por ~2,8, hay un árbol y una multiplicación rápida detrás.
Cuesta un minuto. Y el resultado de esa medición merece quedarse como una prueba que falle si alguien vuelve a meter un bucle: una regresión de coste no la ve un banco de corrección, porque el código sigue dando la respuesta correcta — solo que tarda cinco horas.