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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// Cabecera principal de CPCtelera // Para este ejemplo, se utiliza CPCtelera 1.4.2 #include <cpctelera.h> //------------------------------------------------------- // Declaración de estructura para almacenar una entidad // 7 bytes que incluyen posición, energía, // estado y puntero al sprite //------------------------------------------------------- typedef struct { u8 x, y; u16 energy; u8* sprite; u8 state; } TEntity; //------------------------------------------------------- // Constantes y variables globales //------------------------------------------------------- // Constante: Energías para nuestras 10 entidades const u16 energies[10] = { 1000, 600, 900, 1100, 600, 750, 1200, 900, 500, 880 }; // Constante: Datos de los píxeles de un sprite para poder pintarlo en pantalla const u8 sprite1[10] = { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF }; // Variable: Array de entidades (todo inicializado a 0 por defecto) TEntity entities[10]; //------------------------------------------------------- // Programa principal // Simula la inicialización del array de entidades // utilizando un bucle con código para asignar los valores //------------------------------------------------------- void main() { u8 i, j = 10; // Recorre todas las entidades y asigna los // valores iniciales una por una for(i=0; i < 10; i++) { --j; entities[i].energy = energies[j]; entities[i].state = 2; entities[i].x = 10; entities[i].y = 10; entities[i].sprite = sprite1; } // Bloquearse para siempre while(1); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | ;src/main.c:50: void main() { ; --------------------------------- ; Function main ; --------------------------------- _main:: push ix ; Código para manejar la PILA al entrar a la funcion main ld ix,#0 add ix,sp push af push af ;src/main.c:55: for(i=0; i < 10; i++) { ld -4 (ix), #0x0a ; Guardamos 10 (0x0A) en (IX-4) { Variable j } ld -3 (ix), #0x00 ; Guardamos 0 (0x00) en (IX-3) { Variable i } 00105$: ;src/main.c:56: --j; dec -4 (ix) ; Decrementamos la variable j (IX-4) ;src/main.c:57: entities[i].energy = energies[j]; ld c,-3 (ix) ; C = variable i ld b,#0x00 ; B = 0 ld l, c ; / HL = BC { variable i en 16 bits } ld h, b ; \ add hl, hl ; / add hl, bc ; | HL = HL * 10 add hl, hl ; | Cada elemento del array son 10 bytes add hl, bc ; \ Así que hay que ir hasta entities + i * 10 ld bc,#_entities ; BC = Dirección donde empieza entities add hl,bc ; HL = HL + BC { entities + i * 10 } ld c, l ; / BC = HL { Salvamos en BC una copia ld b, h ; \ de la dirección de este elemento i } ld hl, #0x0002 ; / HL += 2 { 2 bytes más adelante de donde empieza add hl,bc ; \ este elemento, está almacenado su 'energy' } ld -2 (ix), l ; / Salvamos esta dirección de memoria (HL) ld -1 (ix), h ; \ en las posiciones (IX-1) e (IX-2) de memoria ld l, -4 (ix) ; L = (IX-4) = valor de la variable j ld h, #0x00 ; H = 0, así que HL = valor de variable j en 16 bits add hl, hl ; HL *= 2 { Cada elemento de energies es 2 bytes } ld de, #_energies ; DE = Dirección de memoria de energies add hl, de ; HL += DE { energies + 2*j, para llegar al elemento j } ld e, (hl) ; / Guardamos DE en energies[j] en memoria inc hl ; | DE = energies[j] { es de 16 bits } ld d, (hl) ; \ ld l,-2 (ix) ; / HL Vuelve a apuntar a entities[i].energy ld h,-1 (ix) ; \ { lo habíamos salvado antes en (IX-1) (IX-2) } ld (hl), e ; / inc hl ; | Almacenamos DE { energies[j] } ld (hl), d ; \ donde apunta HL { entities[i].energy } ;src/main.c:58: entities[i].state = 2; ld hl, #0x0006 ; HL = 6 { Distancia de entities[i] hasta state } add hl, bc ; HL += BC { HL = entities[i] + 6 } ; Recordemos que BC conserva la dirección de entities + 10*i ld (hl), #0x02 ; Almacenamos el 2 en (HL) { entities[i].state } ;src/main.c:59: entities[i].x = 10; ld a, #0x0a ; A = 10 { 0x0A } ld (bc), a ; BC apunta a x, porque es el primer campo de entities, ; así que guardar a en (BC) es entities[i].x = 10 ;src/main.c:60: entities[i].y = 10; ld l, c ; / HL = BC { HL apunta a entities[i].x } ld h, b ; \ inc hl ; HL += 1 { Apunta al byte siguiente, que es entities[i].y } ld (hl), #0x0a ; Almacenamos un 10 { 0x0A } en (HL) { entities[i]. y } ;src/main.c:61: entities[i].sprite = sprite1; ld hl, #0x0004 ; HL = 4 { Distancia de entities[i] a su campo sprite } add hl, bc ; HL += BC { entities[i] + 4, HL apunta a entities[i].sprite } ld (hl), #<(_sprite1) ; Guardamos el byte bajo de (_sprite) en (HL) { entities[i].sprite } inc hl ; HL++ { Apuntamos al siguiente byte, el byte alto del sprite } ld (hl), #>(_sprite1) ; Guardamos el byte alto de (_sprite) ;src/main.c:55: for(i=0; i < 10; i++) { inc -3 (ix) ; i++ { Recordemos que i está guardada en (IX-3) } ld a, -3 (ix) ; A = Variable i sub a, #0x0a ; A - 10 { Para comprobar si vale 10 } jr C,00105$ ; Mientras A != 0 { i != 10 } saltar al comienzo del bucle ;src/main.c:65: while(1); 00103$: jr 00103$ ; Bucle infinito |
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).
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.
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.
1 2 3 4 5 6 7 8 9 | // Versión anterior (Acceso desordenado) for(i=0; i < 10; i++) { --j; entities[i].energy = energies[j]; entities[i].state = 2; entities[i].x = 10; entities[i].y = 10; entities[i].sprite = sprite1; } |
1 2 3 4 5 6 7 8 9 | // Nueva versión (Acceso ordenado) for(i=0; i < 10; i++) { --j; entities[i].x = 10; entities[i].y = 10; entities[i].energy = energies[j]; entities[i].sprite = sprite1; entities[i].state = 2; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | ;src/main.c:50: void main() { ; --------------------------------- ; Function main ; --------------------------------- _main:: push ix ld ix,#0 add ix,sp dec sp ;src/main.c:55: for(i=0; i < 10; i++) { ld -1 (ix), #0x0a ld c, #0x00 00105$: ;src/main.c:56: --j; dec -1 (ix) ;src/main.c:57: entities[i].x = 10; ld b,#0x00 ld l, c ld h, b add hl, hl add hl, bc add hl, hl add hl, bc ex de,hl ld hl, #_entities add hl,de ex de,hl ld a, #0x0a ld (de), a ;src/main.c:58: entities[i].y = 10; ld l, e ld h, d inc hl ld (hl), #0x0a ;src/main.c:59: entities[i].energy = energies[j]; push de pop iy inc iy inc iy ld l, -1 (ix) ld h, #0x00 add hl, hl ld a, #<(_energies) add a, l ld l, a ld a, #>(_energies) adc a, h ld h, a ld a, (hl) inc hl ld b, (hl) ld 0 (iy), a ld 1 (iy), b ;src/main.c:60: entities[i].sprite = sprite1; ld hl, #0x0004 add hl, de ld (hl), #<(_sprite1) inc hl ld (hl), #>(_sprite1) ;src/main.c:61: entities[i].state = 2; ld hl, #0x0006 add hl, de ld (hl), #0x02 ;src/main.c:55: for(i=0; i < 10; i++) { inc c ld a, c sub a, #0x0a jr C,00105$ ;src/main.c:65: while(1); 00103$: jr 00103$ |
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.
1 2 3 4 5 6 7 8 9 10 | // Versión anterior, accediendo al array a través de // índice (i) con cálculos asociados for(i=0; i < 10; i++) { --j; entities[i].x = 10; entities[i].y = 10; entities[i].energy = energies[j]; entities[i].sprite = sprite1; entities[i].state = 2; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | // Nueva versión usando un puntero para ir recorriendo // los elementos del array, sumando 1 TEntity cada vez // El puntero e, apunta al inicio del vector entities TEntity* e = entities; for(i=0; i < 10; i++) { --j; e->x = 10; e->y = 10; e->energy = energies[j]; e->sprite = sprite1; e->state = 2; // Sumar +1 TEntity al puntero (+7 bytes) ++e; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | _main:: ;src/main.c:54: TEntity* e = entities; ld bc, #_entities+0 ;src/main.c:55: for(i=0; i < 10; i++) { ld de,#0x0a0a 00107$: ;src/main.c:56: --j; dec d ;src/main.c:57: e->x = 10; ld a, #0x0a ld (bc), a ;src/main.c:58: e->y = 10; ld l, c ld h, b inc hl ld (hl), #0x0a ;src/main.c:59: e->energy = energies[j]; push bc pop iy inc iy inc iy ld l, d ld h, #0x00 add hl, hl ld a, #<(_energies) add a, l ld l, a ld a, #>(_energies) adc a, h ld h, a ld a, (hl) inc hl ld h, (hl) ld 0 (iy), a ld 1 (iy), h ;src/main.c:60: e->sprite = sprite1; ld hl, #0x0004 add hl, bc ld (hl), #<(_sprite1) inc hl ld (hl), #>(_sprite1) ;src/main.c:61: e->state = 2; ld hl, #0x0006 add hl, bc ld (hl), #0x02 ;src/main.c:62: ++e; // Sumar 1 TEntity al puntero (7 bytes) ld hl, #0x0007 add hl,bc ld c, l ld b, h ld l, e dec l ;src/main.c:55: for(i=0; i < 10; i++) { ld a,l ld e,a or a, a jr NZ,00107$ ;src/main.c:66: while(1); 00103$: jr 00103$ |
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 j
. j
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
.
1 2 3 4 5 6 7 8 9 10 11 12 13 | // Versión anterior usando *e como puntero // para evitar los cálculos de entities[i] u8 i, j = 10; TEntity* e = entities; for(i=0; i < 10; i++) { --j; e->x = 10; e->y = 10; e->energy = energies[j]; e->sprite = sprite1; e->state = 2; ++e; // Sumar 1 TEntity al puntero (7 bytes) } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | // Nueva versión // Usamos *e para acceder a entities // y *ene para acceder a energies eliminando // la variable j y el coste de energies[j] TEntity* e = entities; u16* ene = energies + 9; // Para eliminar la necesidad de la variable i // Usamos el propio puntero *e para saber cuando // hemos terminado: cuando apunte a la primera // posición fuera de array, es decir entities + 10 // (No olvidemos que +10 = +10*TEntity = +70 bytes) while(e != (entities + 10)) { e->x = 10; e->y = 10; e->energy = *ene; e->sprite = sprite1; e->state = 2; ++e; // Sumar +1 TEntity al puntero (+7 bytes) --ene; // Restar -1 u16 al puntero (-2 bytes) } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | ;src/main.c:50: void main() { ; --------------------------------- ; Function main ; --------------------------------- _main:: ;src/main.c:68: TEntity* e = entities; ld bc, #_entities ;src/main.c:69: u16* ene = energies + 10; ld de, #_energies+20 ;src/main.c:76: while(e != (entities + 10)) { 00101$: ld a, c sub a, #<((_entities + 0x0046)) jr NZ,00122$ ld a, b sub a, #>((_entities + 0x0046)) jr Z,00105$ 00122$: ;src/main.c:77: e->x = 10; ld a, #0x0a ld (bc), a ;src/main.c:78: e->y = 10; ld l, c ld h, b inc hl ld (hl), #0x0a ;src/main.c:79: --ene; dec de dec de ;src/main.c:80: e->energy = *ene; push bc pop iy inc iy inc iy ld l, e ld h, d ld a, (hl) inc hl ld h, (hl) ld 0 (iy), a ld 1 (iy), h ;src/main.c:81: e->sprite = sprite1; ld hl, #0x0004 add hl, bc ld (hl), #<(_sprite1) inc hl ld (hl), #>(_sprite1) ;src/main.c:82: e->state = 2; ld hl, #0x0006 add hl, bc ld (hl), #0x02 ;src/main.c:83: ++e; // Sumar +1 TEntity al puntero (+7 bytes) ld hl, #0x0007 add hl,bc ld c, l ld b, h jr 00101$ ;src/main.c:88: while(1); 00105$: jr 00105$ |
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.