Cincuenta segundos para medio megabyte: la optimización que arreglaba la constante y no el orden

Una 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

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.

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.