Mémoire et performance

Un jeu dispose d'une image pour tout faire : 1/50 ou 1/60 de seconde. Et sa mémoire se compte en kilo-octets. Ce chapitre rassemble ce qu'il faut savoir pour écrire un programme rapide et économe, sur des processeurs aussi différents que le 6502, le Z80 et le 68000. Tous les chiffres ont été mesurés.

Le budget d'une image

Tout ce qu'un jeu fait pour une image (lire la manette, déplacer les personnages, tester les collisions, mettre à jour l'écran, jouer la musique) doit tenir dans le temps d'une image. Au-delà, le jeu ralentit.

Les cycles ne se comparent pas directement d'un processeur à l'autre : une instruction en prend 2 à 7 sur un 6502, 4 à 23 sur un Z80, 4 à plus de 100 sur un 68000. Ce qui compte, c'est la part de l'image que prend un calcul.

Mesurer avant d'optimiser

On optimise ce qui coûte, pas ce qu'on croit coûteux. La technique la plus simple, et la plus utilisée par les programmeurs de l'époque : changer la couleur de la bordure avant un calcul, et la remettre après. L'écran se dessine ligne par ligne pendant que le programme travaille : la hauteur de la bande colorée montre le temps passé.

// Mesurer avec la bordure : 20 divisions par 40 à chaque image (Commodore 64)
architecture commodore.c64;

addlib event.irq;
addlib vic.base;

unit {
    uint resultat;

    main() {
        vic.setBackgroundColor(vic.BLACK);
        while (1) {
            irq.waitFrame();                    // attendre le début d'une image
            vic.setBorderColor(vic.RED);        // la bordure en rouge pendant le calcul...
            for (uint i = 0; i < 20; i++) {
                .resultat = (i + 1000) / 40;
            }
            vic.setBorderColor(vic.BLACK);      // ... puis en noir
        }
    }

    interrupt -> irq {
    }
}

La même boucle, à un nombre près, prend presque toute l'image dans un cas, et une trentaine de lignes dans l'autre. Les sections suivantes expliquent pourquoi.

D'autres outils complètent la bordure :

• l'assembleur généré, asm/main.asm, montre ce que devient chaque ligne ;
• le rapport de compilation et le diagramme du projet de Simple8 IDE donnent la place occupée par chaque unit, en ROM, en RAM et en page zéro ;
• un débogueur d'émulateur (Geargrafx, VICE, Mesen…) compte les cycles entre deux points, grâce à la table des symboles, main.sym.

Choisir ses types selon le processeur

Au chapitre 3, la règle était : le plus petit type qui suffit. Elle est juste sur un 6502, mais chaque processeur a ses préférences. Voici le coût d'une addition, d'une multiplication et d'une division entre deux variables, mesuré sur les trois familles de processeurs, dans leurs propres unités.

6502 (C64, NES, PC Engine) : un vrai 8 bits

Le 6502 calcule 8 bits à la fois : chaque octet de plus coûte. Il ne sait ni multiplier ni diviser : ces opérations sont de petits programmes, et un ulong les rend 3 à 4 fois plus lentes. Préférez ubyte, puis uint ; réservez ulong aux grands nombres.

Z80 (Amstrad CPC, MSX, Master System) : un 8 bits qui aime le 16 bits

Surprise : sur Z80, un uint n'est pas plus lent qu'un ubyte, et même un peu plus rapide pour l'addition. Le Z80 a des paires de registres de 16 bits (HL, DE, BC) et une addition 16 bits (ADD HL,DE) : un ubyte, lui, doit d'abord être étendu. En revanche, il n'a rien pour 32 bits : un ulong coûte 6 à 8 fois plus. Sur Z80, uint est le type naturel ; ulong est à éviter dans les boucles. Le SM83 de la Game Boy, cousin du Z80, a lui aussi des paires de registres de 16 bits.

68000 (Mega Drive, Amiga) : un processeur 16/32 bits

Le 68000 a des registres de 32 bits : une addition coûte presque le même prix pour les trois tailles. On pourrait croire que long est alors le type naturel. Ce n'est pas le cas, pour deux raisons :

• ses instructions de multiplication et de division ne travaillent que sur 16 bits (MULU : 16 × 16 bits ; DIVU : 32 bits divisés par 16). Un ulong multiplié par un ulong demande plusieurs multiplications : 4,6 fois plus lent. La division est presque deux fois plus lente ;
• son bus de données fait 16 bits : lire ou écrire un long en mémoire demande deux accès au lieu d'un.

Sur 68000, int et uint sont les types naturels ; long se justifie quand la valeur dépasse 65 535, et pour les adresses (une ressource de la Mega Drive est une adresse sur 32 bits, chapitre 11). ubyte n'y fait rien gagner, et coûte parfois un peu plus, le temps d'être étendu.

En résumé

Dans tous les cas, les types non signés donnent le code le plus court quand la valeur ne peut pas être négative.

Les puissances de deux

Diviser par une puissance de deux (2, 4, 8, 16, 32…) revient à décaler les bits vers la droite (chapitre 3), et prendre le reste revient à garder les bits du bas. Simple8 le fait tout seul dès que le diviseur est une constante puissance de deux. Mesuré sur C64, avec un uint :

Diviser par 32 est 13 fois plus rapide que diviser par 40, et le reste par 32 ne coûte presque rien. D'où un conseil de conception : dimensionner en puissances de deux. Une carte de 64 colonnes plutôt que 60, des tableaux de 256 cases, des sprites de 16 × 16 pixels : les calculs d'indices deviennent gratuits.

La page zéro et fast

Sur 6502 : la page zéro

Le 6502 atteint plus vite les 256 premiers octets de la mémoire, la page zéro. fast y place une variable. Mais tout ne gagne pas autant :

Pour une variable ordinaire, la page zéro ne fait gagner qu'un cycle par accès. Pour un pointeur, elle divise presque le coût par deux : le 6502 ne lit par un pointeur que s'il est en page zéro, et un pointeur ordinaire doit y être recopié à chaque accès.

L'optimiseur s'en charge déjà

La page zéro est petite (206 octets disponibles sur C64, NES et PC Engine) et partagée avec les bibliothèques. L'optimiseur de Simple8 y range de lui-même les variables locales les plus utilisées dans les boucles, sans qu'on écrive fast. Dans ce programme, aucune variable n'est déclarée fast :

uint f(uint x) {
    uint a = x * 2;
    uint b = a + 1;
    return b;
}

Pourtant, la table des symboles montre Main_f_a en $20 et Main_f_b en $22 : en page zéro. Chaque variable déclarée fast est donc un octet que l'optimiseur ne pourra plus donner à une variable de boucle, souvent plus utile.

Selon le processeur

Vers la disparition de fast

fast est une indication donnée à la main, et elle n'a de sens que sur certains processeurs. L'optimiseur fait déjà mieux pour les variables locales : il mesure leur usage, et choisit lui-même. Les prochaines versions de Simple8 doivent étendre ce choix automatique à toutes les variables, et fast est appelé à disparaître. D'ici là, réservez-le à trois cas :

• un pointeur parcouru dans une boucle ;
• une variable lue à chaque image par une interruption ;
• une variable qu'un bloc _asm adresse en page zéro.

Économiser la mémoire

Quelques règles pour la ménager :

• const ne coûte pas de mémoire vive. Une constante, un tableau constant, une chaîne restent dans la ROM. Une table de 256 valeurs déclarée const économise 256 octets de RAM.
• Une valeur de départ coûte deux fois. ubyte t[100] = { … }; prend 100 octets de RAM, et 100 de ROM pour les valeurs que boot.asm y recopie au démarrage (chapitre 3). Si le tableau ne change jamais, faites-en un const.
• Chaque variable locale a sa propre place. Les locales de deux fonctions ne partagent pas la même mémoire, même si les fonctions ne s'exécutent jamais en même temps : un grand tableau local dans une fonction rarement appelée occupe la RAM en permanence.
• Les contextes partagent leur mémoire (chapitre 8) : les variables d'un niveau n'occupent la RAM que pendant ce niveau.
• Regarder la place prise : le diagramme du projet de Simple8 IDE donne, pour chaque unit, la ROM, la RAM et la page zéro utilisées.

Les recettes

À retenir

• Tout doit tenir dans une image : mesurez avec la bordure avant d'optimiser.
• Le bon type dépend du processeur : ubyte sur 6502, uint sur Z80, int / uint sur 68000 ; long coûte cher partout dans les multiplications et les divisions.
• Diviser ou prendre un reste par une puissance de deux est presque gratuit : dimensionnez en puissances de deux.
• fast ne sert vraiment que sur 6502, surtout pour les pointeurs ; l'optimiseur place déjà les variables les plus utilisées, et fast est appelé à disparaître.
• const ne coûte pas de RAM ; une valeur de départ coûte en RAM et en ROM.

À vous de jouer

1. Mesurez avec la bordure le coût d'une multiplication par 40, puis par 32.
   Voir la solutionMasquer la solution

   On reprend l'exemple et on ne change que la ligne du calcul : une multiplication au lieu d'une division. Pour que la bande soit bien visible, la boucle fait 100 tours au lieu de 20. Pour comparer, on compile trois versions : * 40, * 32, et la boucle seule (.resultat = i + 1000;), qui donne le coût de tout ce qui n'est pas la multiplication.

   main() {
       vic.setBackgroundColor(vic.BLACK);
       while (1) {
           irq.waitFrame();                    // attendre le début d'une image
           vic.setBorderColor(vic.RED);        // la bordure en rouge pendant le calcul...
           for (uint i = 0; i < 100; i++) {
               .resultat = (i + 1000) * 40;
           }
           vic.setBorderColor(vic.BLACK);      // ... puis en noir
       }
   }

   Mesuré dans l'émulateur du kit de test, entre les deux changements de couleur :

   Calcul dans la boucle (100 tours)	Cycles	Lignes d'écran	Par opération
   la boucle seule	4 954	78
   * 40	14 354	227	94 cycles
   * 32	11 154	177	62 cycles

   La multiplication par 32 (cinq décalages) reste la plus rapide, mais l'écart n'est que de 1,5 fois, loin du rapport de 13 entre les deux divisions. La raison : multiplier par une constante ne demande pas de routine. Dans asm/main.asm, Simple8 calcule 40 = 5 × 8 : deux décalages et une addition donnent i * 4 + i, puis trois décalages multiplient par 8. C'est la division qui coûte cher, pas la multiplication par une constante.

   

2. Diviser par 40 sert souvent à trouver la ligne d'une position de l'écran. Remplacez la division de l'exemple par une table de 25 valeurs (le début de chaque ligne), et comparez la hauteur des bandes.
   Voir la solutionMasquer la solution

   Dans un programme, diviser par 40 sert surtout à trouver la ligne d'une position de l'écran du C64 (40 colonnes, 25 lignes, positions de 0 à 999). On modifie donc l'exemple pour qu'il divise de vraies positions, de 0 à 950. La table de 25 valeurs contient le début de chaque ligne : 0, 40, 80… La ligne d'une position n est la dernière dont le début ne dépasse pas n.

   Parcourir la table depuis la ligne 0 marche, mais ne gagne presque rien : jusqu'à 24 comparaisons de uint, presque le prix de la division. L'astuce est de partir d'un point déjà proche : n >> 6, c'est-à-dire n / 64, ne coûte que des décalages et n'est jamais plus grand que n / 40. Il reste au plus 9 pas à faire. Le test r < 24 empêche de lire après la fin de la table.

   // le début de chaque ligne de l'écran : 0, 40, 80… (25 valeurs, en ROM)
   const uint DEBUT[] = { 0, 40, 80, 120, 160, 200, 240, 280, 320, 360, 400, 440, 480,
                          520, 560, 600, 640, 680, 720, 760, 800, 840, 880, 920, 960 };
   uint resultat;
   
   main() {
       vic.setBackgroundColor(vic.BLACK);
       while (1) {
           irq.waitFrame();                    // attendre le début d'une image
           vic.setBorderColor(vic.RED);        // la bordure en rouge pendant le calcul...
           uint n = 0;                         // une position de l'écran, de 0 à 999
           for (ubyte i = 0; i < 20; i++) {
               ubyte r = (ubyte)(n >> 6);      // n / 64 : jamais plus que la vraie ligne
               while (r < 24 && n >= .DEBUT[r + 1]) {
                   r++;                        // au plus 9 pas jusqu'à la bonne ligne
               }
               .resultat = r;                  // sa ligne, de 0 à 24
               n = n + 50;
           }
           vic.setBorderColor(vic.BLACK);      // ... puis en noir
       }
   }
   
   interrupt -> irq {
   }

   Mesuré pour 20 positions (le tour de boucle seul, sans calcul, prend 940 cycles) :

   Méthode	Cycles	Lignes d'écran
   n / 40	16 310	258
   la table, parcourue depuis 0	14 320	227
   la table, depuis n >> 6	7 294	115

   La bande est un peu plus de deux fois moins haute. Un programme de contrôle, qui compare la méthode à n / 40 pour les 1 000 positions de l'écran, trouve 0 différence. La leçon : une table remplace un calcul quand on sait où y lire. Une table de 1 000 valeurs, lue directement par LIGNE[n], serait encore plus rapide, mais coûterait 1 000 octets ; celle-ci n'en prend que 50.

   

3. Compilez le même programme pour C64 et pour Amstrad CPC, en ubyte puis en uint, et comparez le code de asm/main.asm.
   Voir la solutionMasquer la solution

   Un programme court suffit, pourvu qu'il additionne, compare et incrémente. On le compile quatre fois, en changeant seulement l'architecture et le type (ubyte ici) :

   architecture commodore.c64;
   
   unit {
       ubyte total;
   
       main() {
           for (ubyte i = 0; i < 10; i++) {
               .total = .total + i;
           }
       }
   }

   Voici la fonction main de asm/main.asm dans chaque cas (les lignes ; [Main:L8] rappellent la ligne du programme).

   Sur Commodore 64, en ubyte

   ; [Main:L7] Main_main__FOR_1_i = #0
           LDA #<0
           STA Main_main__FOR_1_i
   
   ; === Loop: _FOR_1 ===
   _FOR_1_start:
   ; Loop condition: Main_main__FOR_1_i < #10
           CMP #<10
           BCS _FOR_1_end
   _loop1:
   
   ; [Main:L8] t0 = Main.total + Main_main__FOR_1_i
           LDA Main_total
           CLC
           ADC Main_main__FOR_1_i
           STA Main_total
   
   ; [Main:L8] Main.total = t0
   
   ; Loop increment: Main_main__FOR_1_i++
           INC Main_main__FOR_1_i
   ; Loop end: _FOR_1
           LDA Main_main__FOR_1_i
           CMP #<10
           BCC _loop1
   _FOR_1_end:

   Sur Commodore 64, en uint

   ; [Main:L7] Main_main__FOR_1_i = #0
           LDA #<0
           STA Main_main__FOR_1_i
           STA Main_main__FOR_1_i+1
   
   ; === Loop: _FOR_1 ===
   _FOR_1_start:
   ; Loop condition: Main_main__FOR_1_i < #10
           LDA Main_main__FOR_1_i+1
           CMP #>10
           BCC _FOR_1_cond_ok
           BEQ _FOR_1_cond_ok_skip1
           JMP _FOR_1_end
   _FOR_1_cond_ok_skip1:
           LDA Main_main__FOR_1_i
           CMP #<10
           BCC _FOR_1_cond_ok
           JMP _FOR_1_end
   _FOR_1_cond_ok:
   
   ; [Main:L8] t0 = Main.total + Main_main__FOR_1_i
           LDA Main_total
           CLC
           ADC Main_main__FOR_1_i
           STA Main_total
           LDA Main_total+1
           ADC Main_main__FOR_1_i+1
   
   ; [Main:L8] Main.total = t0
           STA Main_total+1
   
   ; Loop increment: Main_main__FOR_1_i++
           INC Main_main__FOR_1_i
           BNE _FOR_1_incr_skip
           INC Main_main__FOR_1_i+1
   _FOR_1_incr_skip:
   ; Loop end: _FOR_1
           JMP _FOR_1_start
   _FOR_1_end:

   Sur 6502, tout double : l'addition se fait en deux fois, octet bas puis octet haut (le second ADC ajoute la retenue du premier) ; la comparaison avec 10 teste d'abord l'octet haut, puis l'octet bas ; l'incrémentation doit propager la retenue (INC, BNE, INC).

   Sur Amstrad CPC, en ubyte

   ; [Main:L7] Main_main__FOR_1_i = #0
           LD A,0
           LD (Main_main__FOR_1_i),A
   
   _FOR_1_start:
   ; Loop condition: Main_main__FOR_1_i < #10
           LD A,10
           LD B,A
           LD A,(Main_main__FOR_1_i)
           CP B
           JP NC,_FOR_1_end
   
   ; [Main:L8] t0 = Main.total + Main_main__FOR_1_i
           LD A,(Main_total)
           LD L,A
           LD H,0
           LD A,(Main_main__FOR_1_i)
           LD E,A
           LD D,0
           ADD HL,DE
           LD (t0),HL
   
   ; [Main:L8] Main.total = t0
           LD A,(t0)
           LD (Main_total),A
   
   ; Loop increment: Main_main__FOR_1_i++
           LD HL,Main_main__FOR_1_i
           INC (HL)
           JP _FOR_1_start
   _FOR_1_end:

   Sur Amstrad CPC, en uint

   ; [Main:L7] Main_main__FOR_1_i = #0
           LD A,0
           LD (Main_main__FOR_1_i),A
           LD A,0
           LD (Main_main__FOR_1_i+1),A
   
   _FOR_1_start:
   ; Loop condition: Main_main__FOR_1_i < #10
           LD HL,(Main_main__FOR_1_i)
           LD DE,10
           OR A
           SBC HL,DE
           JP NC,_FOR_1_end
   
   ; [Main:L8] t0 = Main.total + Main_main__FOR_1_i
           LD HL,(Main_total)
           LD DE,(Main_main__FOR_1_i)
           ADD HL,DE
           LD (t0),HL
   
   ; [Main:L8] Main.total = t0
           LD HL,(t0)
           LD (Main_total),HL
   
   ; Loop increment: Main_main__FOR_1_i++
           LD HL,(Main_main__FOR_1_i)
           INC HL
           LD (Main_main__FOR_1_i),HL
           JP _FOR_1_start
   _FOR_1_end:

   Sur Z80, c'est l'inverse pour l'addition : en uint, elle tient en trois instructions (LD HL, LD DE, ADD HL,DE) ; en ubyte, chaque valeur doit d'abord être étendue à 16 bits (LD H,0, LD D,0) avant la même ADD HL,DE, puis le résultat est ramené à un octet. La comparaison et l'incrémentation, elles, restent plus courtes en ubyte (CP, INC (HL)).

   Mesuré dans les émulateurs du kit de test (le programme moins un programme vide), et en taille du code de main :

   	C64, ubyte	C64, uint	CPC, ubyte	CPC, uint
   Temps des 10 tours	281 cycles	584 cycles	1 884 états	2 602 états
   Taille de main	25 octets	52 octets	44 octets	49 octets

   Sur C64, passer en uint double le temps et la taille. Sur CPC, la taille ne change presque pas, et l'addition elle-même devient plus simple ; dans cette boucle, la comparaison et l'incrémentation d'un compteur 16 bits rendent pourtant l'ensemble 1,4 fois plus lent. Le Z80 n'a pas de préférence aussi nette que le 6502 : il faut regarder le code.

4. Cherchez dans le diagramme du projet de l'IDE l'unit qui prend le plus de RAM, et réduisez-la avec const.
   Voir la solutionMasquer la solution

   Le diagramme du projet affiche, pour chaque unit, ce que le compilateur écrit dans asm/main_units.json : ROM, RAM et page zéro. On peut donc faire l'exercice dans l'IDE, ou en lisant ce fichier. Les exemples du cours déclarent déjà leurs tables en const ; voici un petit programme qui ne le fait pas : une unit Niveau avec une carte de 8 lignes de 32 cases, et deux petites tables pour la dessiner.

   // Niveau.s8u : une carte de 8 lignes de 32 cases
   unit Niveau {
       ubyte carte[256] = {
           1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
           1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
           1,0,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,0,1,
           1,0,0,0,0,0,0,0,0,0,0,3,3,3,3,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,1,
           1,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,1,
           1,0,2,2,2,2,0,0,0,0,0,3,3,3,3,3,3,3,3,3,3,0,0,0,0,0,2,2,2,2,0,1,
           1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
           1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
       };
       ubyte couleurs[4] = { 0, 14, 7, 2 };        // vide, mur, bonus, piège
       ubyte dessins[4] = { ' ', '#', '*', '+' };

   Le diagramme (et main_units.json) donne, pour Niveau : "rom": 355, "ram": 264. C'est l'unit qui prend le plus de RAM, de loin : Main n'en prend aucune. Les 264 octets sont les trois tableaux (256 + 4 + 4). Ils ont une valeur de départ, donc ils existent deux fois : en RAM, et dans le programme, d'où boot.asm les recopie au démarrage.

   Or dessiner() ne fait que lire ces tableaux. On les déclare donc const, avec un nom en majuscules comme les autres constantes du cours, et la taille entre crochets n'est plus nécessaire :

   unit Niveau {
       const ubyte CARTE[] = {
           1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
           // …
           1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
       };
       const ubyte COULEURS[] = { 0, 14, 7, 2 };        // vide, mur, bonus, piège
       const ubyte DESSINS[] = { ' ', '#', '*', '+' };
   
       void dessiner() {
           uint n = 0;
           for (ubyte y = 0; y < 8; y++) {
               vic.setCursor(4, (ubyte)(y + 8));
               for (ubyte x = 0; x < 32; x++) {
                   ubyte c = .CARTE[n];
                   vic.setFontColor(.COULEURS[c]);
                   vic.putChar(.DESSINS[c]);
                   n++;
               }
           }
       }
   }

   Résultat : "rom": 355, "ram": 0. Les 264 octets de RAM sont libérés, la ROM ne change pas (les valeurs y étaient déjà), et le fichier main.prg perd même 18 octets : la table de recopie du démarrage n'a plus rien à recopier. L'écran est identique au pixel près (captures de VICE comparées).

   Si un jour le jeu doit modifier la carte (une brique cassée, par exemple), elle ne peut plus être const. On garde alors la carte d'origine en const, et on ne met en RAM que ce qui change, comme Jeu.briques au chapitre 14.