Optimización de los ciclos

Denomino ciclos en este artículo a la sucesion de enteros que suelen comenzar por cero, aunque no es obligatoro, se van incrementando hasta llegar a un limite y vuelven a empezar por cero. Este tipo de ciclos es lo usual en las animaciones de sprites. Vamos a ver aqui como sencillamente se puede hacer más rápido la actualizacion.

Vamos a verlo todo con un ejemplo un poco estúpido1 pero significativo. Supongamos que la linea 1: es la actualizacion del frame, el limite de frames es de 4 imagenes y estan seran frm = [ 0 | 1 | 2 | 3 ]. La linea 1: parte de que nos salimos del ámbito de las imagenes. En la linea 2: comprobamos si nos fuimos por encima del limite, no comprobamos que se fuera por debajo porque nunca decrementamos solo incrementamos.

En la linea 3: hacemos el modulo entre el limite del valor del frame. Esto nos da cuanto nos pasamos del limite, si nos pasamos dos enteros, tendriamos que haber vuelto al cero y avanzar 2 enteros , frame 2. Esto es lo que hace el módulo.

Se puede ver el código en ensamblador lo costoso que puede ser el módulo.

1:frm=5; 
2:if(frm>=4) 
   
3:  frm=frm%4; 

mov dword ptr [ebp-30h],5
cmp dword ptr [ebp-30h],4
jl  main+129h (00401229)
mov edx,dword ptr [ebp-30h]
and edx,80000003h
jns main+126h (00401226)
dec edx
or  edx,0FCh
inc edx
mov dword ptr [ebp-30h],edx

Vamos a ver que pasa si sustituimos el modulo por el resto. La optimizacion viendo el código ensamblador es evidente. Y podemos hacer esto pero de forma limitada y por la siguiente razon.

Supongamos la recta entera dividida en dos intervalos contiguos de longitud la del limite [0,1,2,3] y [4,5,6,7]. Nosotros queremos estar en el primer intervalo y nos situan en el segundo. Si hacemos la resta por el valor de la longitud del intervalo nos situamos en la misma posición relativa del segundo intervalo en el primer intervalo2.

La limitación de esta versión es que solo funciona si siempre nos movemos por el primer y el segundo intervalo. Podemos asegurar que esto ocurrira si nunca incrementamos mas de la longitud del intervalo.

1:frm=5; 
2:if(frm>=4) 
   
3:   frm=frm-4;

mov dword ptr [ebp-30h],5
cmp dword ptr [ebp-30h],4
jl  main+13Fh (0040123f)
mov eax,dword ptr [ebp-30h]
sub eax,4
mov dword ptr [ebp-30h],eax

El tercer ejemplo, viendo el código en ensamblador, parece peor que el anterior. Pero pongo este ejemplo para los casos en que no se cumpla la restriccion de la anterior. Esto es más rápido que el primer caso ya que no realiza el salto del if. Se da el caso de que los saltos en algunas maquinas son más costosos de lo normal. Esto pasa porque en el salto se vacia el buffer de código y se vuelve a llenar. Por esto es desaconsejado abusar del if else y de otros saltos.

Este caso se puede hacer ya que se da la propiedad en el módulo que aplicado sobre un numero entre (0..limite) da el mismo número.

1:frm=5;
2:frm=frm%4;

mov dword ptr [ebp-30h],5
mov ecx,dword ptr [ebp-30h]
and ecx,80000003h
jns main+156h (00401256)
dec ecx
or  ecx,0FCh
inc ecx
mov dword ptr [ebp-30h],ecx

Se puede ampliar el ejemplo añadiendo un desplazamiento adicional para que no tenga que empezar obligatoriamente en cero el intervalo. Por ejemplo, para un intervalo [despl,despl+1,..,despl+limite] se haria de la siguiente forma:

1:const int superior=despl+limite;
2:frm++; 
3:if(frm>=superior) 
4:   frm=frm-limite;

O lo siguiente:

2:frm++; 
3:frm=(frm-despl)%limite + despl;

Espero que os sirva de algo, un saludo,

Luis Cabellos

1. Bueno muy estúpido

2. Esto es fácil verlo usando una regla y un lapicero para simular la longitud.

3. El código en ensamblador es el generado por Visual C++