Costes ocultos en arrays de estructuras en C

Este artículo es el número 2 de 2 de la serie Programación Avanzada en C

Continuamos nuestra serie abordando los costes ocultos al usar arrays de estructuras en C en Amstrad CPC. Las posiciones en memoria son relativas al inicio de los arrays, y el compilador produce código para calcular dónde está cada elemento. Las estructuras funcionan similar: cada miembro está a una distancia en bytes del inicio de la estructura. Trabajamos sobre un ejemplo en CPCtelera que vamos optimizando progresivamente. Primero entendemos cómo son estos cálculos y el código que el compilador genera para realizarlos. Vemos las limitadas posibilidades que tiene el compilador para optimizar, debido a los pocos registros del procesador Z80. Finalmente, le vamos facilitando la vida, simplificando los cálculos y ganando bytes y tiempo de CPU con sencillos cambios en el código.

Nuestro ejemplo simula una sencilla estructura de datos para almacenar entidades de un videojuego cualquiera. Nuestras entidades cuentan con posición x e y, energía, un estado y un sprite para dibujarse. Declaramos la estructura de entidad y creamos un array para almacenar 10 entidades. Como cada entidad nos ocupa 7 bytes, nuestro array inicialmente ocupará 70 bytes. Sin embargo, lo que más nos preocupa no es lo que ocupan las entidades, sino lo que ocupa el código que utilizaremos para inicializar los valores de estas entidades. Es muy habitual utilizar algún tipo de bucle o función que vaya dando un valor a cada uno de los miembros de la estructura. Eso es lo que simulamos en nuestro código siguiente:

El coste oculto de los arrays

Hemos añadido el código generado por el compilador SDCC 3.6.8 comentando detalladamente lo que hace cada parte en ensamblador. Ahí se puede ver los costes ocultos de nuestro código en C. El primer coste viene del acceso a un array. Para entenderlo, veamos la figura 1. Creamos un array E con 5 elementos de tamaño u8 (1 byte cada uno). Eso pone nuestros 5 elementos consecutivos en memoria, a partir de la posición 100 (por ejemplo).

Figura 1: Esquema de memoria para un array

Si queremos acceder a alguna posición de este array, por ejemplo E[3], esa es la posición 100 + 3 = 103.  Si la posición es un valor constante como E[3] no hay ningún cálculo que hacer, ya sabemos que es la 103. Pero la cosa cambia si accedemos a E[i], usando una variable. Como i puede ser 1, 2 o 4, por ejemplo, no queda más remedio que calcular la posición a la que queremos acceder en el momento de hacerlo. Por eso el compilador genera código como el de nuestro ejemplo, en el que suma a la posición inicial del array un desplazamiento para llegar a donde comienza el elemento i que queremos.

Este coste es más grande conforme el procesador tiene menos recursos para poder hacer el cálculo. En procesadores modernos hay muchos registros e instrucciones específicamente diseñadas para estos cálculos. Sin embargo, nuestro Z80 está mucho más limitado, y eso hace que genere tantas instrucciones como hemos visto antes.

La cosa se complica con las estructuras

El segundo coste oculto que hay en nuestro código es la estructura de datos TEntity. Las estructuras de datos también se almacenan juntas y siguen una lógica parecida a la de los arrays. La diferencia es que en un array todos sus elementos son iguales (y ocupan lo mismo), mientras que en una estructura no. En este caso, la figura 2 nos muestra cómo quedaría nuestra estructura TEntity en memoria.
Figura 2: Ejemplo de layout de memoria de una estructura en C
La estructura ocupa 7 bytes en total: x (1 byte), y (1 byte), energy (2 bytes), sprite (2 bytes), state (1 byte). Como muestra la figura, estos bytes se almacenan consecutivos en memoria, igual que en el caso del array. Lo que cambia es que algunos bytes forman parejas para los números de 16 bits (como energy) o para los punteros (como sprite). Por este motivo, y para verlo más claro, hemos añadido la fila de contenido en hexadecimal, que es un reflejo de lo que realmente contendría la memoria. El número 1023 es 03FF en hexadecimal, y 482 es 01E2, y ambos se almacenan invertidos en memoria porque así es el formato del Z80, conocido como little-endian.

Una vez más, si hacemos accesos directos a una estructura como por ejemplo P.x = 5; la posición de memoria es conocida y constante. Pero si lo hacemos a través de variables, como punteros o elementos de un array, introducimos un nuevo cálculo: hay que sumar a la posición P el desplazamiento del campo de la estructura al que accedemos. Y no hay más remedio que hacer ese cálculo con código, si el acceso es variable. Esto está sucediendo en nuestro ejemplo anterior, cuando asignamos valores a los elementos de TEntity dentro de entidades[i].

Eliminando los costes: mejorando la salida del compilador

Ahora que sabemos todo esto, sólo resta pasar a la acción. Lo primero que podemos hacer para facilitar la tarea al compilador es acceder a los elementos de la estructura en orden. Como sabemos que están seguidos en memoria, si los inicializamos en ese orden favorecemos que el compilador pueda guardar la dirección base de la estructura en un registro y lo vaya incrementando para pasar de un campo al siguiente. Así minimizamos los cálculos que tiene que hacer, y su necesidad de ir guardando en memoria las direcciones que calcula.

Sólo con este cambio, en este ejemplo se ganan 8 bytes compilando con SDCC 3.6.8 (En el vídeo se gana algo más al usar una versión anterior del compilador). Puede no parecer mucho, pero el cambio es importante. Si nos fijamos en el ensamblador generado podemos ver muchos cambios. Además de 8 bytes menos de código, también hace menor uso de variables locales en memoria (sólo accede a IX-1, cuando antes llegaba a IX-4). Además, al evitar estos accesos a memoria, el código generado será más rápido que el anterior. Por otra parte, al estar el código más compacto y ordenado, permite que añadamos más cosas con menor coste.

La siguiente mejora consiste en gestionar manualmente el acceso a los elementos del array usando un puntero. En lugar de obligar al compilador a hacer el cálculo asociado a entities[i], lo que hacemos es utilizar una variable puntero que guarde la dirección de comienzo del array entities, e ir sumando 1 TEntity (7 bytes) cada vez que queramos acceder al siguiente elemento. De esta forma obligamos al compilador a tener guardada la posición del TEntity que estamos manejando y a no recalcular cada vez que avanzamos i: basta con la suma de +7 bytes.

Esta mejora hace el código generado 24 bytes más pequeño. Es una mejora muy relevante, teniendo en cuenta que el tamaño total de nuestro código es ahora de tan sólo 73 bytes. Con estos 2 ahorros hemos pasado de 105 a 73 bytes, lo que es un -30%. Además, al igual que antes, la calidad del código generado es mejor. No hay uso de memoria en la pila para variables locales: todas caben en los registros del procesador (otro byte que ahorramos más los accesos). Esto hace nuestro código mucho más rápido, pequeño y eficiente.

Pero todavía podemos mejorar más. Nos sigue quedando un código generado bastante largo por el acceso a energies[j]. Siguiendo la lógica anterior, podemos cambiarlo accediendo mediante otro puntero. Como se ve en el vídeo, aunque este cambio parece obvio, aplicado aisladamente no produce la mejora esperada. A veces, las combinaciones que el compilador puede hacer con los registros del Z80 se complican cuando usamos varios punteros. Sin embargo, el cambio sí es efectivo si nos fijamos en otro detalle: usando los punteros, no necesitamos las variables i y jj queda sustituida  por el nuevo puntero, mientras que i sólo la estamos usando para contar. Pero no nos hace falta contar porque el puntero e lo estamos avanzando en cada iteración, por lo que nos puede hacer de contador. Sólo tenemos que parar cuando e apunte fuera del array. Como el último elemento está en entities + 9 , cuando e == entities + 10 habremos terminado. Así podemos ahorrarnos la variable i.

Estos últimos cambios reducen el código 4 bytes más, dejándolo en 69 bytes. Tenemos, por tanto, una ganancia total de 36 bytes (-35%), sin contar el menor uso de memoria de la pila (otros 4 bytes) y un código más rápido y limpio. No hay más que comparar los ensambladores generados por la opción inicial y esta última para ver los grandes cambios.

Pese a todo, aún hay formas de hacer este código más compacto y rápido. Se deja como ejercicio al lector buscar esas formas. El objetivo de este artículo eran estas optimizaciones en concreto y, sobre todo, la forma de pensar respecto al compilador y al lenguaje C para entender mejor cómo manejarlo.

Resumen final

Utilizando un sencillo ejemplo hemos mostrado lo importante que es la forma de programar para conseguir un mejor rendimiento, tanto en espacio como en tiempo. Debemos conocer los costes ocultos de las estructuras de datos que utilizamos y cómo todo esto es manejado a bajo nivel por el compilador. Sabiendo esto podemos programar mucho mejor.

Las técnicas utilizadas para mejorar nuestro código han sido las siguientes:

  • - Conocer los costes de acceso a arrays y estructuras de datos.
  • - Acceder a los campos de las estructuras en órden.
  • - Utilizar punteros para evitar los cálculos de acceso a los arrays y estructuras.
  • - Usar los punteros y direcciones de memoria para contar, eliminando las variables contador innecesarias.

Esperamos que toda esta información os sea de utilidad para hacer grandes videojuegos que todos disfrutemos.

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.