Optimizando código

En la JIK-partida de póker acabamos más interesados en resolver este problema que en la partida en si:
¿ Cuántos cortes perfectos hacen falta para que la baraja vuelva a su estado original ?
Un corte perfecto es un corte en el que todas las cartas se intercalan.

Finalmente *lio encontró una solución rápida y elegante, haciendo un código en C que resolvía el problema para barajas de N cartas, además de eso, ha trazado unos gráficos muy interesantes que muestran el número de iteraciones ("barajeos") en función del número de cartas:

Por mi lado, fije la baraja en 50000 cartas y busqué la forma de optimizar al máximo el código para que el algoritmo se ejecutase lo más rápido posible.

Mi algorimo original es el siguiente:

do {

/*Delay*/
for(i=0;i<MAX/5000;i++*MAX) for(j=0;j<MAX;j++*MAX);


for (i=0;i<half;i++){
deck2[2*i+1] = deck[i];
}

for (i=half;i<MAX;i++){
deck2[(i%half)+(i-half)] = deck[i];
}

for (i=0; i<MAX; i++) deck[i] = deck2[i];


} while(check(deck));

Sobre este algoritmo he creado 3 optimizaciones:

• Nivel 1: Se elimina la copia del final, donde restauramos el array deck
• Nivel 2: Además de lo anterior, se añade una cache para las operaciones "2*i+1" y "(i%half)+(i-half)", para no tener que calcularlas durante la ejecución.
• Nivel 3: Se elimina la función check, y se sustituye por un flag, comprobando en cada una de las mitades si el resultado asignado es correcto, esta optimización no aporta nada, de hecho retrasa incluso un poco sobre la segunda.

En un principio se ha compilado usando gcc y los resultados son los esperados 0>1>2=3, con lo que vemos que evitar copias en memoria es efectivo, al igual que aligerar carga al procesador.

Lo más interesante aparece cuando pedimos a gcc que optimice el código con -O1 -O2 -O3 -Os (optimización del tamaño). Los resultados son los siguientes:

	RAW (0)	No copy (1)	+ Cache (2)	+No check(3)
-O0	4121056	3794802	3406500	3411833
-O1	1297629	815846	1577955	1723155
-O2	980820	666561	1711097	1785242
-O3	879061	637885	1582850	1620995
-Os	1396125	1015367	1642606	1691794

Los números son tiempos en microsegundos (1s = 1000000us). Los resultados empiezan a cobrar interés cuando se introducen las optimizaciones. Vemos que de pronto no es nada rentable precalcular los índices y sustituirlos por accesos a memoria. Con el código optimizado gastamos menos tiempo si solo realizamos las operaciones que si accedemos a memoria para recuperar resultados. También se puede observar que la optimización s no conduce a gran cosa en relación con las demás.

En estos gráficos se ven mejor los resultados:

Este es el código original. Si alguien lee la entrada (improbable) y se le ocurre algo mejor, estaré encantado de recibir sus comentarios.