Entretenido optimizando código para un ordenador retro

Vaya por delante que este post va a ser largo. Haz scroll  si quieres saber cuánto. Tengo muchas cosas en la cabeza que me apetece contar sobre esta batallita y eso implica extenderme. Vayamos al lío...

Llevo unos cuantos días, la última semana si no recuerdo mal, aprovechando mis ratitos de tiempo libre para optimizar el código de prueba de lo que podría llegar a ser un juego para un Commodore Amiga. La cuestión es que si esto lo estuviese haciendo para una máquina contemporánea, no habría necesitado pasar por todo lo que contaré a continuación. Simplemente, habría cogido la idea inicial, la habría plasmado en el algoritmo original que se me pasó por la cabeza y la habría ejecutado. Digamos que, en un i5 opr ejemplo, con varios cores a 2000MHz hubiese funcionado a la primera a bastante más de 50 FPSs. El problema es que si haces eso mismo y lo lanzas en un emulador  de Amiga con procesador Motorola 68030 a 50MHz y obtienes 30 FPS y además tu  intención es hacer que funcione dignamente en un 68000 a 7.1 MHz, tienes un problema y debes optimizar.

Un poco de contexto

En el mundillo retro dicen que los mejores juegos de Amiga, desde un punto de vista técnico al menos, deben hacerse en ensamblador. Yo pienso que es cierto, pero también que más vale programar decentemente en un lenguaje de alto nivel que mal en ensamblador. Doy por hecho que el segundo sería mi caso. Aprendí ensamblador del 68000 en la universidad pero lo tengo más que olvidado. Además, no sólo habría que ponerse al día de eso, también habría que empaparse de cómo funciona el hardware específico de un amiga (los llamados custom chips) y aprender a manejarlos en ensamblador. Todo esto ya me lo planteé el el año pasado y me lancé a hacer un primer juego en lenguaje Blitz Basic. Hay más opciones dependiendo de lo que uno se quiera complicar, incluso game makers como Red Pill, que es fantástico para aquellos que no sepan programar. Sin embargo,  creo que Blitz es una buena opción para los que quieran escribir código sin excesivas complicanciones. Es un lenguaje compilado, hecho específicamente para crear juegos a mediados de los 90 y que genera un código  bastante bien optimizado para la máquina. Además sólo se necesita aprender de una forma más superficial el hardware de la máquina ya que tiene instrucciones para manejar el Blitter, el Coper, etc.

La experiencia programando en Blitz Basic fue bastante buena pero con algún obstáculo debido a las limitaciones existentes. No voy a entrar en detalles respecto a eso para no aburrir, pero cuando acabé el juego ya tenia varias ideas de próximos proyectos y tenía claro que quería probar a hacerlo en C. Hay que decir que este lenguaje no tiene muy buena fama en Amiga. No hay constancia de muchos juegos programados con C en la época dorada de esta gama de ordenadores.Se supone que los compiladores de la época no generaban un código excesivamente bueno. Además, realmente era bastante normal programar en ensamblador por entonces. Por fortuna, ahora existen dos compiladores más o menos actualizados VBCC y GCC.

Hay otra cosa que debo aclarar también. Lo he dejado caer antes. Aprender a manejar el hardware del Amiga a bajo nivel requiere mucho tiempo, un esfuerzo que no quería afrontar. En Blitz Basic lo puedes esquivar gracias a las librerías existentes, oficiales y de terceros pero en C no conocía nada similar. Afortunadamente encontré un framework en desarrollo llamado ACE que viene a proporcionar una base bastante buena y con el que se ha creado (por parte de su desarrollador) algún juego que parece moverse lo suficientemente bien.

Lo que quiero hacer

Lo que tengo en mente hoy por hoy es hacer una prueba y comprobar el rendimiento que obtengo programándolo en C. Se trata de mover 20 pequeños cuadrados de colores de 2x2 píxeles que siguen una trayectoria cerrada de forma continua, o sea, un circuito. Para ello tengo un compilador cruzado en Linux y un emulador en el que corro los ejecutables que produce. Programar y/o probar en una máquina real a fecha de hoy es lago impensable, además, los emuladores de Amiga son muy fieles, o al menos lo bastante, como se verá mas tarde.

 

En cuanto al objetivo, mi idea suele ser que funcione en mi Amiga 1200 con procesador 68030 (030 para los amigos) y ampliación de RAM, algo que era un estándar bastante extendido durante los últimos años de la época "no retro" de la plataforma. Sin embargo, ACE está pensado para la primera generación de Amigas, o sea el archiconocido Amiga 500. Por otro lado, es curioso porque los que ahora estamos activos (con máquinas reales) somos cada cual ligeramente fanáticos de algún tipo de máquina. Hay quien quiere usarla en su esencia y critica el uso de nuevos procesadores basados en FPGA, que es lo más top que puedes llegar a ponerle hoy en día a tu vieja máquina. Otro punto a favor es que si programas para el 500 llegarás a la práctica totalidad de los usuarios que existen, ya que con las posteriores debería haber retrocompatibilidad. En resumen, a fecha de hoy el reto es hacer una prueba en C que funcione bien en un 500.

Primeros pasos

Pues allá que me lancé. Me miré unos cuantos ejemplos de ACE y pasé unos días creando el armazón del programa y comprendiendo cómo manejar los gráficos. Creé el primer algoritmo sin pararme a pensar en nada, a lo que saliera. Se trataba de un bucle que en cada iteración calculaba a dónde se había movido cada cuadrado y lo pintaba. Pintar en este caso significa borrar la posición anterior y pintar en la nueva (o sea, son dos operaciones gráficas realmente). Lo lancé en el FS-UAE (el emulador) para una máquina 030. No había mucho más que eso, un fondo estático, una linea negra a modo de circuito, los puntos, un poco de texto que se actualizaba con el número de FPS y datos de cada uno de los cuadrados. No era gran cosa, esto tenía que volar...

¡Ops! Pues no, no volaba. El invento iba a unos 36 FPS. Ufff! Ahí no acababan las malas noticias. El 030 emulado era más rápido que el mío real y mi máquina ejecutaba la aplicación a 26 FPS. Como no tengo un 500 y emularlo no me resulta fácil, rebajé el procesador del emulador a un 020, que corre a 14MHz, en teoría el doble del 68000 del 500. En este caso me daba ¡16FPS! Los gráficos estaban casi parados y en la máquina objetivo sería aún peor.

Era el momento de reflexionar. La autoestima baja porque sólo quieres pintar 20 miserables cuadrados de 2x2 pixeles. Entonces recuerdas cosas que hace la gente y sólo puedes quitarte el sombrero. Por ejemplo, el año pasado salió un juego llamado Reshoot R. Desde mi punto de vista es brutal. Cuando veo algún vídeo, especialmente, me quedo bobo en un cierto momento en el que caen unos asteroides desde arriba. Los puedes acribillar con multitud de disparos, explotan, arrojan partículas o terminan cayendo al suelo y formando parte del paisaje mientras mueves tu nave y unos alienígenas en la parte de abajo se tambalean a la vez que te disparan. Y si eso parece asombroso la continuación del juego que saldrá este año ya es la bomba. En las preview de Reshoot Próxima 3 se observa triple scroll parallax, no sé cuántos meteoritos o enemigos moviéndose hacia a ti, decenas de disparos, chispas cuando los proyectiles alcanzan una roca... Es absolutamente brutal. Al menos, lo bueno de todo esta frustración era aprender a valorar el mérito de lo que veía.

 

Parándome a pensar.

En fin, lo positivo dentro de los malos resultados era que el algoritmo lo había pensado tan poco que debía haber muchas cosas mejorables. También es cierto que a penas tenía experiencia con ACE . Por ejemplo, ni si quiera hoy tengo ni idea de cómo usar sprites por hardware, lo que suele ser de bastante ayuda (se suele usar normalmente para pintar los proyectiles que se disparan sin consumir a penas CPU). En teoría sólo estoy usando el Blitter, que tiene sus limitaciones y no es muy rápido pintando. Era una pequeña maravilla a mediados de los 80 pero, años más tarde, a principios de los 90, ya no aportaba más que la propia CPU. Moraleja, como es lo que tengo que usar en un Amiga 500 hay que intentar reducir el número de blits que se hacen.

Me surgieron unas cuantas ideas de mejora. Se pueden clasificar en dos bloques, las que mejorarían el rendimiento de las operaciones puramente lógicas y de calculo de posiciones (x, y) de los objetos del juego y las encaminadas a reducir el número de operaciones gráficas a completar al pintar la pantalla. Decidí dejar las segundas para el final y estrujarme la cabeza con mejoras de algoritmos para empezar. También se me ocurrió reflejarlo en una hoja de cálculo para poder tener la comparación registrada.

Manos a la obra... Lo que quería era alcanzar unos 60 FPS en un procesador 68020 emulado. ¿Por qué? Pues porque era una prueba y si continuo con el desarrollo en serio, tendré que meter más código, más interacciones y los FPS caerán. Si conseguía 60 en un 020 tal vez al final tenga 25 en un 68000. A continuación intentaré explicar paso a paso cada cosa de las que hice y las pondré en el mismo orden en el que las programé.

1. Recordando algoritmos de búsqueda.

En la aplicación de prueba se usa ordenación. Los cuadrados del programa se adelantan unos a otros porque llevan diferente velocidad, así que existe una lista en la que deben aparecer ordenados a modo de clasificación de una carrera. Para solucionar esto, viajé hasta mis tiempos de estudiante. Me vinieron a la mente tres algoritmos de ordenación Bluble Sort, Merge Sort y Quick Sort. Creía recordar que el mejor era el último así que en la primera versión había un Quick Sort para ordenar la lista. Pero un momento,,, ya hacía muchos años de eso, tal vez ya por entonces habrían otras opciones y hoy por hoy seguro que tenía que haber algo más avanzado. ¿Y si había algo mejor?

uase

Buscando en internet se puede ver que hay muchos algoritmos para ordenar elementos, muchos no los conocía. Me puse a mirar gráficas comparativas y... ¡vaya! había uno que bajaba bastante los tiempos del Quick Sort, el Counting Sort.  Me puse a implementarlo y sí que iba mejor pero, como se puede ver en la tabla de abajo, y para mi decepción, la cosa casi no mejoraba. En cualquier caso era un pequeño avance y llegó para quedarse.

2. Eliminando bucles interiores

Relacionado con la ordenación, resulta que tenía dos arrays con datos necesarios. Viendo el código que  se ejecutaba para mover cada cuadro, cantaba mucho un bucle que recorría uno de los arrays para encontrar el índice correspondiente en el otro array. Además, esto se ejecutaba 20 veces para cada frame a pintar. Esto es un clásico, un bucle dentro de otro bucle. Si el primer bucle se ejecuta 20 veces y el segundo puede llegar a 20, tendremos 400 iteraciones como resultado (como máximo). Tengo que decir en mi defensa que poner ese bucle ahí no me gustó desde el principio y me dejé un comentario como recordatorio para cambiarlo. La solución a esto fue meter un indice que diese la posición que se deseaba buscar en el otro array y eliminar así la necesidad de recorrerlo.

Un poco de código vale más que mil palabras. El original se correspondía con esto:

int j = 0;
while (positions[j].driver!=i){
    j++;
}

y se cambió por este otro:

int j = cars[i].position; 

El resultado fue el que se ve a continuación:

Sinceramente, me esperaba más de este cambio.  A parte de la decepción,  había una cosa curiosa que empezaba a manifestarse tras introducir esa mejora. Si os dais cuenta, en ambos casos el rendimiento en porcentaje se incrementa en mayor medida en la máquina más lenta. Mientras que en el 68030 se sigue casi como al principio, en el 68020 se ve un 104%, algo es algo.

 3. Eliminación de referencias de memoria

Esto me vino a la cabeza mientras estaba con otra cosa, mientras hacía otro de los cambios. Recordé haber leído sobre esto en algún foro de Blitz Basic meses atrás, lo que a su vez me refrescó otra de las enseñanzas básicas que recibí de estudiante. Resulta que cada referencia a la posición de un array, se traduce durante la ejecución en una búsqeda en memoria. Tener que hacerlo en algún momento es imprescindible, pero en algunas partes del código existían muchas referencias a un mismo elemento. Cuando eso ocurre, vale la pena usar una referencia para obtener el valor en una variable local, usarla todas las veces que haga falta y, al finalizar, usar otra referencia a esa posición de memoria para guardar un nuevo valor, en caso de que hayas alterado la variable y necesites almacenarlo.

 Por ejemplo, esta parte del código:

for (int i=0; i< NUMBER_OF_CARS; i++){
   counts[arr[i].nextPoint] = counts[arr[i].nextPoint] + 1;
}

Se cambia por esta otra y tendremos la mitad de accesos a memoria:

int np;
for (int i=0; i< NUMBER_OF_CARS; i++){
   np= arr[i].nextPoint;
   counts[np] = counts[np] + 1;
}

El resultado se mantiene en la línea del resto, un pequeño incremento en rendimiento que no era para tirar cohetes. Sin embargo, en este caso es  parece que empezaba a notarse algo. Aún así seguía muy lejos de los 60 FPS a los que quería llegar con el 68020.

4. Control del cambio de posición

Ahora iba a empezar a jugar con lo que se pinta en pantalla y lo que se deja de pintar. Esto debería tener influencia directa en las operaciones con el Blitter y comenzar a dar resultados más notables. Lo primero que se ocurrió fue no pintar todo el texto en cada frame. Usaría el propio ordenamiento para determinar cuando había un cambio de posición y por tanto era necesario actualizar el texto.

En cuanto al resultado... otro bajón, me esperaba mucho más en este caso. Además la lógica que añadí era demasiado agresiva y el texto no se actualiza siempre que es necesario, cuando lo corrija el beneficio se reducirá. Entonces empecé a dudar de poder llegar a los 60 FPS en el 020 pero sabía que las mejores ideas eran probablemente las últimas que pensaba aplicar.

5. Control del cambio de coordenada

Como contaba antes, los puntos se pintan en todos los fotogramas, sin distinción. Además la posición x,y se guarda como un valor real, por lo que se trata de coordenadas con decimales. Estos decimales no sirven de nada a la hora de pintar en pantalla. Creo recordar que en los amiga de última generación, o sea, última generación de entonces (chipset AGA) sí pero en un 500 el resultado de pintar un punto en (10.35, 4,23) es lo mismo que (10.77,4.15) y se pintará en (10,4). ¿Qué tal  si pintamos sólo cuando comprobemos que hay un cambio en x  o y? Pues que tendremos frames en los que no habrá que pintar algún que otro cuadrado, o lo que es lo mismo, dejaremos de tener que pintar siempre 20 objetos.

Parece que aquí se obtiene el primer cambio que realmente salta a la vista. Es curioso que en este caso mejoraba mucho más la máquina con 030. Seguía muy lejos de los 60 FPS planteados pero aún quedaban cosas por hacer.

 6. Eliminación de operaciones con decimales

Antes he dicho que las posiciones x e y se almacenaban como reales. Eso forzaba a hacer muchas operaciones con ellos y la realidad, en aquella época, era que prácticamente todos los Amiga se vendían sin FPU, o sea, sin unidad de coma flotante, es decir, si una unidad especializada del procesador para operar con decimales. Esto conlleva que operar con ellos se convierte en algo muy lento y, si podemos depender sólo de números enteros, todo nos irá mejor. El problema que tenía para lograr esta modificación era que, de alguna manera, tenía que seguir operando con x e y "con decimales" en los que poder registrar un avance menor de una unidad. La solución: multiplicar por 100 los valores de x e y para considerar las dos ultimas cifras como decimales. Ahora una coordenada se almacenaría como (1035,423) y en el momento de pintarla la dividiríamos por 100, por lo que seguiremos pintando en (10,4).

¡Vaya! con esta modificación se conseguía doblar los resultados iniciales para un 020. Subidón de moral al fin. y aún quedaba lo mejor, pero ya era el último cartucho.

 7. Escalado de velocidad

Esto no era realmente una optimización, en realidad se trataba de corregir un error de concepto inicial, una cosa muy obvia en la que no había caído al principio. Resulta que estaba intentando representar un movimiento a una velocidad mucho más rápida de la necesaria. Me explico, a 25 FPS los cuadrados tardaban en recorrer más o menos 5 segundos el segmente recto de la parte inferior del circuito, y una vuelta completa debía rondar el medio minuto(esto último nunca lo llegué a medir) . Pues bien, comparando con el circuito representado, el segmento inferior (la recta de meta) debería recorrerse en 10-11 segundos. Entonces, estaba lanzando el doble de las operaciones necesarias en cada frame. ¿Cómo podía aproximarme a la realidad cuando esté funcionando a 25 FPS?

Midiendo el segmento, resultaba tener 100 píxeles de longitud. Tenía que recorrerlo en 10 segundos, por tanto 10 píxeles en cada segundo. Como en cada segundo quiero pintar 25 veces la pantalla, se debía fijar la velocidad de avance en 0.4 píxeles por frame. De ese número se desprende que se reducirían a menos de la mitad de las operaciones a realizar.

¡Estupendo! Esto se había notado realmente. Los FPS se habían multiplicado más de 3.5 veces en un 020... Pero no llegaban a 53.

Conclusiones

Pues fue todo, al menos la primera batería de cosas que se me ocurrieron. Siendo objetivo, me quedé a las puertas de conseguir lo que quería. Sólo alcancé los 52 FPS en el 020. Tal vez te preguntes cómo quedó la cosa en mi 1200 real. No lo medí para cada caso porque es mucho menos cómodo pero, tras todos los cambios, se quedó en 96 FPS.  Creo que voy a continuar con el desarrollo pero con un ojo puesto en ver como cae el rendimiento. Todo el código nuevo que añada hará que vayan cayendo los FPS pero espero que se me sigan ocurriendo cosas que puedan ir contrarrestando este efecto.

Otra aspecto que pienso, es que si esto lo hubiese hecho para una máquina contemporánea, que en mi caso sería un portátil con Linux y SDL para programarlo, me hubiese ido bien a la primera. Ese código fuente de baja calidad me hubiese dado FPS de sobra para lanzarme a continuar con la idea. Sólo me habría visto forzado a realizar el ultimo cambio para adaptar la velocidad a la escala del circuito. De acuerdo, esto fue lo que más subió el rendimiento pero no es realmente una optimización. En el paso anterior, acumulando todas las mejoras, había doblado la cantidad de FPS en un 020. Todo eso lo habría perdido ya que no me habría tenido que preocupar en optimizar. Puede que esto no parezca importante, pero imagina que se tratase del código de un servicio de internet con miles de usuarios accediendo a el. Un servicio mal optimizado como ese, generaría mucha más carga de CPU que la necesaria, lo que implica más CPUs, más máquinas virtuales para dar ese servicio de forma adecuada, más temperatura en cada procesador y por tanto en la sala donde se encuentren los servidores, más consumo energético... Ahora ya no parece tanta broma ¿verdad? Hay muchas empresas que realmente dedican un gran esfuerzo a optimizar su código viendo lo que esto significa. Sin embargo, también en muchos casos se descuida este aspecto, se adoptan frameworks de programación que son capas y más capas de software que facilitan mucho el trabajo a costa de tener un código más torpe. Tal vez por ello deberíamos pararnos de vez en cuando a programar algo para una maquina de hace treinta años, aprenderíamos cosas, o las recordaríamos, las incluiríamos en nuestros proyectos profesionales y los haríamos mejores. Ya se de algún programador que afirma directamente esto cuando se le pregunta. Programar para una máquina retro le hace producir un código de mayor calidad en su trabajo. Y por cierto, tambíén hay algún profesor que en su asignatura pone a sus alumnos a programar en viejas máquinas como un Amstrad CPC.