[C/ASM] Optimiser au cycle près : la référence
Posté le 20/06/2021 22:24
J'adore programmer des add-ins, je pense que ça ne vous aura pas échappé. Le sujet est très large, mais s'il y a une problématique spécifique que je considère ma «spécialité», c'est d'exploiter toutes les astuces logicielles et matérielles pour améliorer les performances.
Ce topic est une référence de techniques d'optimisation d'add-ins, de tous les styles et niveaux. Ce post contient un index de tous les sujets qui me paraissent utiles (sauf ceux que j'ai oubliés), et j'écrirai des bouts au gré des opportunités et des découvertes.
Le sujet étant large, je ne m'attarderai pas sur les notions générales de C/assembleur dans un premier temps. Cela dit, seules les catégories «Bas niveau» risquent d'être un peu rudes ; en cas de doute, demandez dans les commentaires
Tutoriels qui vous aideront à comprendre les concepts :
La référence de l'optimisation au cycle près
Identifier les besoins d'optimisation
Il est très tentant, mais inutile, d'optimiser du code qui ne limite pas les performances du programme. Identifier les parties critiques et les liens faibles qui monopolisent les ressources est toujours la première étape.
Optimisations algorithmiques
On ne peut pas sous-estimer l'importance des optimisations algorithmiques. En un sens, l'algorithmique est la science de calculer ce qu'on veut avec la bonne
méthode, indépendamment de l'implémentation. Avec l'exception du dessin sur Graph 90+E et des programmes très intensifs en calcul, l'immense majorité des améliorations du
code sont des fourmis au pied de la montagne de l'algorithmique.
Optimisations de calcul et d'implémentation
Vous allez voir que nos chères calculatrices ne sont pas si bien équipées pour calculer que ça.
Optimisations sur la mémoire
En général, plus vous progressez en C, plus vous regardez la mémoire de près. Je vais jusqu'à dire que la mémoire est
le concept fondamental et omniprésent qui guide l'implémentation de tout programme en C (avec bien sûr l'algorithmique qui guide la conception). Sur la calculatrice, c'est encore plus vrai, et de toutes les optimisations de code très peu concurrenceront une gestion supérieure de la mémoire.
Optimisations sur le code assembleur
C'est dans le boucles critiques, exécutées plusieurs millions de fois par seconde, où chaque cycle compte, que ce topic trouve son nom. Vous avez optimisé les algos, les méthodes de calcul, conçu le programme avec la meilleure distribution possible de la mémoire, et maintenant vous voulez écrire en assembleur la version la plus rapide possible. Voilà comment.
Citer : Posté le 07/03/2024 01:31 | #
Ça fait bien longtemps que je n'ai pas posté sur cette référence (rien en 2023 !), donc voici un petit freebie que j'ai rédigé entre les talks à CGO/CC'24.
Je n'ai pas de plans immédiats de conclure cette série (ça apparaîtra dans ma signature à un moment), mais je trouvais ça dommage de ne pas entretenir au moins un peu ce topic.
Enjoy!
Citer : Posté le 07/03/2024 01:31 | #
Benchmark de toutes les méthodes d'accès par région (Programmation générale — ★☆☆)
Dans les techniques précédentes, on a discuté de l'importance de la mémoire et des grandes variations qui existent entre différents types d'accès à différentes mémoires. Le but de cette technique est d'établir un benchmark pour quantifier ces différences et en déduire des intuitions sur la bonne façon d'utiliser la mémoire. En clair, on veut connaître le débit d'accès aux différentes mémoires pour savoir lesquelles vont plus ou moins vite.
Chiffres donnés pour :
Code de test pour mesurer la vitesse
Mesurer les performances de la mémoire est assez facile dans l'absolu ; on fait juste plein d'accès et on mesure le temps que ça prend. Il faut prendre soin de tester différentes configurations : avec/sans cache, accès linéaires/aléatoires, etc. mais rien de très surprenant. Cette technique est basée sur une implémentation dans gintclt, que je vais suivre plus ou moins directement : voyez src/perf/memory.c et src/perf/memory.S pour les détails.
Bien sûr, il n'y a pas juste un chiffre avec un débit pour chaque zone de mémoire : les vitesses sont différentes en lecture et en écriture, pour des accès séquentiels et aléatoires, et pour différentes tailles d'accès. Il y a donc pas mal de situations à étudier. Je raconterai en quoi elles sont intéressantes au fur et à mesure, mais voici déjà la liste complète des accès qu'on va tester (L18).
Accès à une région mémoire
Accès à deux régions mémoire
Tous les tests ne sont pas applicables pour toutes les régions. Par exemple, la ROM est en lecture seule, la mémoire SPU ne supporte que les accès de 4 octets, et les zones virtualisées ne peuvent pas être manipulées directement par le DMA. Mais c'est la liste complète.
Pour faire ces tests il faut, comme d'habitude, éliminer un maximum d'interférences. Ici, on veut mesurer la vitesse d'accès à la mémoire et donc il faut que notre fonction de test elle soit bel et bien limitée par les accès mémoire. L'idéal pour ça c'est d'écrire une boucle bien serrée en assembleur. Sur le processeur SuperH, quand il n'y a pas de branches/sauts le plus efficace est de faire une boucle DSP, qui ressemble à ça :
ldre 2f # fin de la boucle au label "2:"
ldrc rN # nombre de tours (rN ≤ 4096)
1: insn_1
insn_2
...
2: insn_N
J'en ai déjà parlé un peu dans la technique Mesurer au cycle près mais c'est l'occasion de détailler un peu plus. Si on réfléchit un peu à ce qu'une boucle est en pratique, c'est juste un bout de code qu'on exécute encore et encore jusqu'à ce qu'une condition devienne fausse. En principe il n'y a aucune raison qui empêche le matériel de boucler puisque c'est juste un saut vers l'arrière. La difficulté c'est que la condition de la boucle doit être calculée et ça c'est quelque chose qui peut être très compliqué, donc il faut que le logiciel s'en charge.
Mais bon, même s'il existe des boucles avec des conditions compliquées il y a aussi plein de boucles avec des conditions simples. Par exemple il y a plein de boucles for qui exécutent juste le même code un nombre fixe de fois. Et ça, le matériel pourrait le gérer ! Il suffirait d'avoir un compteur matériel (nombre de tours restant) et d'indiquer où la boucle commence et se termine. Comme ça, chaque fois qu'on arrive à la fin de la boucle, si le compteur est supérieur à 0, le CPU saute au début de la boucle, sinon il continue tout droit et sort de la boucle.
C'est exactement ce que le code ci-dessus fait. Les instructions ldrs et ldre annoncent quelles sont la première et la dernière instruction de la boucle ("s" et "e" signifient "start" et "end"). Les paramètres 1f et 2f sont juste des labels spécifiques à l'assembleur GCC désignant le prochain "1:" et le prochain "2:" respectivement. Ensuite ldrc ("c" signifie "count") indique combien de tours on veut faire, via un registre rN. Et hop, une fois ces instructions exécutées les rN prochaines exécutions de l'instruction qui suit le label "2:" se termineront pas un saut vers l'arrière au label "1:".
Ce mécanisme est décrit plus en détail dans le manuel du SH4AL-DSP, section 6.3.2 (attention à ne pas confondre avec 6.3.1 qui est un mécanisme similaire, mais plus vieux et moins pratique à utiliser). Pour notre application, il y a une seule limitation qui nous embête, c'est qu'on ne peut faire que 4096 tours maximum. Pour la mémoire on en voudrait un peu plus. Du coup memory.S commence par définir une paire de macros PROLOGUE() et EPILOGUE() (L1) à laquelle on spécifie le nombre de tours qu'on veut, et qui exécute la boucle DSP autant de fois que nécessaire pour atteindre le bon total.
Avec cette base, les différentes fonctions de test ne sont pas trop difficiles à implémenter. Par exemple, la lecture séquentielle par accès de 4 octets est la suivante :
_mem_read32:
shlr2 r5
PRELUDE(r5)
1: 2: mov.l @r4+, r0
EPILOGUE(r5)
Les autres fonctions de memory.S sont toutes du même style. Le reste est dans la fonction benchmark() (L155) qui lance tous les benchmarks appropriés sur une zone mémoire donnée.
Régions mémoire à tester
La prochaine question est quelles sont les régions à tester ? Ça peut sembler évident : on prend juste la liste de toutes les régions. En gros c'est ça, mais il y a quelques subtilités qu'on a envie de prendre en compte.
Sur la ROM et la RAM, qui sont grandes, le comportement de la mémoire va changer selon si on travaille avec une petite ou une grande quantité de données. Cette différence est causée par l'existence du cache, dont on a discuté dans les techniques précédentes. Comme le cache fait 32 ko, je prends une petite zone de 2 ko (garantie de tenir dans le cache) et une grande zone de 64 ko (clairement plus grande). Et naturellement, si le cache a un impact, enlever le cache aura aussi un impact. On va donc tester les accès à la ROM et à la RAM à la fois à travers le cache et en contournant le cache. Et pendant qu'on y est, on va aussi tester avec et sans le MMU, puisque la traduction d'adresse n'est peut-être pas gratuite.
Sur la mémoire DSP (la XRAM et la YRAM sur-puce), il faut savoir qu'elles font toutes les deux 8 ko mais sont en réalité coupées en deux « pages » de 4 ko et il y a un délai quand on passe d'une page à l'autre. Du coup on va en profiter pour comparer des lectures/écritures dans une seule page à des lectures/écritures qui alternent entre les pages.
Du coup, ça nous donne la liste suivante (L86) :
Et du coup, plus qu'à lancer le code et tabuler les résultats, let's go !
Les chiffres complets sont disponibles dans la référence technique sur la bible. Tous ne sont pas transcendants et il y a surtout une poignée de règles dont il est important de se souvenir quand on programme. Du coup dans cette technique je vais me concentrer sur ces résultats-là.
La RAM : magique en lecture, terrible en écriture
Pour ce tableau comme pour chacun des autres, chaque colonne indique un type de mémoire. L'adresse donnée est indicative et permet de déduire la zone, la présence potentielle du cache, et la présence potentielle du MMU. La taille indiquée est celle du buffer dans laquelle le test est fait (à comparer avec la taille du cache, 32 ko), pas la taille totale de la zone.
séquentielle
séquentielle
Posons déjà un cadre avec la RAM. Les chiffres donnés ici sont sur Graph 90+E, au niveau d'overclock par défaut soit 118 MHz sur le CPU. Ça veut dire qu'une boucle d'accès 8-bit peut lire au plus 118 Mo/s, une boucle d'accès 16-bit 236 Mo/s et une boucle d'accès 32-bit 472 Mo/s, si jamais les accès se font tous en 1 cycle. Bien sûr, ce n'est jamais parfaitement atteint, mais je note
Sur la RAM, ce maximum est atteint quand on fait des accès séquentiels avec cache sur une petite zone de 2 ko (première colonne). La raison est que la région de 2 ko tient dans le cache, donc après la première passe un peu lente qui charge les données dans le cache, les 15 passes suivantes obtiennent juste toutes leurs réponses en un seul cycle. Donc les données chaudes en RAM sont accessibles à la vitesse maximale du CPU aussi longtemps qu'elles sont dans le cache, ce qui est parfait ! Ça veut dire qu'on a accès à jusqu'à 32 ko de données
Si le cache n'était pas là, les résultats seraient très différents (troisième colonne). Le cache aide parce qu'il charge des lignes de cache d'un coup (32 octets), ce qui lui permet à la fois de répondre au mov en cours mais aussi à plein de mov qui suivent. Évidemment, ça permet de faire beaucoup moins d'aller-retours avec la mémoire. Quand on fait des accès hors-cache, il faut contacter la mémoire à chaque mov, ce qui coûte beaucoup plus cher. Là on tombe à une vitesse risible qui varie entre 4 et 15 Mo/s selon la taille des accès. Donc on est clairement sur un truc à éviter à tout prix pour des gros volumes, ce que je note
De façon générale le programme ne fait jamais d'accès hors cache donc la troisième colonne n'est pas vraiment un danger. Par contre, ce qui peut se passer c'est que si on lit beaucoup de données on ne pourra pas tout avoir dans le cache et donc on a un juste milieu, noté dans la deuxième colonne. En RAM, on bloque à environ 40 Mo/s, ce qui est pas top. Malheureusement il n'y rien qu'on puisse vraiment faire parce que y'a pas de région plus rapide avec une taille raisonnable. Mais donc on sait qu'il faut rester dans le cache le plus possible.
Le vrai problème c'est l'écriture. On est limités à 29 Mo/s dans le meilleur cas où on fait que des accès 4 octets, et sinon c'est encore moins ! Les accélérateurs du CPU (cache et write queue) sont quasiment inutiles dans ce cas : non pas qu'ils marchent mal, mais contrairement à la lecture pour laquelle après une passe tout se passe en cache, les donées écrites doivent _toujours_ aller jusqu'à la RAM, et la puce RAM est juste super lente en écriture. Le cache et la write queue améliorent la vitesse en groupant les écritures ensemble, mais rapidement il faut envoyer le groupe à la RAM et là c'est la catastrophe. Donc toute écriture de grandes quantités de données en RAM est immédiatement critique.
Pour contexte, la lenteur d'écriture en RAM est la raison pour laquelle Azur existe et marche si bien. Le simple fait de remplir la VRAM (écrire 396×224×2 = 177 ko) prend 6.1 ms avec des accès 4 octets, et comme généralement on affiche plutôt pixel par pixel ce serait avec des accès 2 octets, soit de l'ordre de 10.6 ms. Le CPU peut calculer durant les accès mémoire donc ça ne veut pas juste ajouter le temps de calcul à ce chiffre, mais c'est quand même problématique dans le budget de frame de 30 ms. Par comparaison, dans la mémoire on-chip ça prendrait 400/800 ms avec des accès de 4/2 octets. En prenant un peu de recul, on voit que 177 ko par frame ça fait 5.3 Mo/s à écrire, ce qui fait du rendu l'une des activités les plus intenses en écriture, donc c'est pas étonnant que ce soit une cible facile.
Le DMA n'est pas super utile parce qu'il maximise aussi à 39 Mo/s. Je ne sais pas trop pourquoi c'est plus lent à ce point sur les petites zones (27 Mo/s) vu que le nombre de répétitions est quand même pas énorme. Utiliser le DMA peut quand même être utile parce qu'on peut calculer durant le DMA, mais ça ne marche bien que si le calcul ne fait vraiment aucun accès RAM, donc il faut mettre la pile et les données du calcul ailleurs, ce qui est clairement une optimisation avancée.
Conclusions :
La mémoire on-chip : perfection à petites doses
séquentielle
séquentielle
alternée
Sans surprise, la mémoire on-chip propose des performances exceptionnelles. La mémoire du DSP intégré (XRAM et YRAM) peut lire et écrire à pleine vitesse, 420 Mo/s, ce qui contourne complètement les problèmes d'écriture en RAM pour les tâches qui génèrent beaucoup de données temporaires.
En revanche, la XRAM et la YRAM ont une subtilité. Elles sont formées de deux pages de 4 ko chacune, et les lectures répondent en 1 cycle seulement si on accède toujours à la même page. Quand on passe d'une page à l'autre, la réponse prend 2 cycles. Dans le test ci-dessus, la « lecture alternée » est faite de façon à changer de page à chaque lecture, et on peut voir que ça divise la vitesse de lecture par 2 : c'est donc un cas à surveiller. Bien sûr l'alternance stricte est un pire cas qui ne se produira probablement pas en pratique, mais on peut avoir des niveaux intermédiaires de stalling avec des images, par exemple. Dans ce cas il peut être plus performant de laisser les images en RAM, parce que le cache n'a pas ce problème, en plus d'être plus grand (32 ko) et plus flexible.
L'ILRAM (Instruction-Local RAM) est prévue pour mettre du code, pas des données : ses performances ne sont pas donc pas brillantes. (Le SH-4 a habituellement une mémoire symétrique pour les données, l'OLRAM ou Operand-Local RAM, mais sur notre modèle elle est remplacée par la XRAM et la YRAM). L'ILRAM a quand même des performances décentes, mais vue sa petite taille il est plus naturel d'utiliser la RAM quand c'est possible.
La PRAM0 est spéciale, comme d'habitude — on se rappelle qu'elle ne supporte que les accès 32-bit, comme discuté dans la cartographique. Ses performances sont inférieures à celles de la RAM même dans le pire cas en écriture, et elle est complètement hors cache. Mais ses usages sont de toute façon limités à des situations exceptionnelles dans lesquelles la performance est secondaire, donc je ne pense pas qu'il y ait de recommandations particulières à suivre ici.
Toutes ces mémoires sont plus lentes avec le DMA qu'avec le CPU, à cause de leur placement plus éloigné qu'on a exploré dans la technique La cartographie du SH4AL-DSP et du SH7305. Il n'est pas du tout naturel pour le DMA de rentrer dans le CPU (ou dans le SPU) pour aller chercher les données. Même si on pouvait calculer durant les accès DMA, l'écart est tellement abyssal que ça n'en vaut pas la peine (limite avec PRAM0, et encore). Le mémo est juste de ne jamais utiliser le DMA sur ces zones.
Conclusions :
La ROM : difficile mais globalement sous-exploitée
séquentielle
Avec tout ça on pourrait s'attendre à ce que la ROM soit désastreuse. En fait c'est pas trop mal, et on pourrait s'en servir plus que ce qu'on fait actuellement si on y va intelligemment. La difficulté principale c'est que les performances ne sont pas très consistantes et pour l'instant je ne sais pas encore pourquoi.
Déjà, le plus important (et ce qui rend la ROM potable) c'est que le cache est actif sur les accès à la ROM. Donc quand on prend une petite région comme dans la première colonne, le cache s'en sort très bien et on arrive quasiment à la vitesse maximale. La vitesse 8-bit n'est pas aussi rapide qu'on pourrait l'espérer, mais je n'ai aucune idée de pourquoi c'est le cas dans ce test.
Les accès qui ne bénéficient pas bien du cache tombent immédiatement à la vitesse réelle de la puce ROM. Dans le cas d'une lecture séquentielle longue (ici 64 ko), le cache aide dans la limite de chaque ligne de cache, mais on passe quand même notre temps à attendre que la ROM réponde. La vitesse maximale de la ROM quand l'unité de transfert est une ligne de cache (32 octets) est de 9 Mo/s, et au moins grâce à l'effet « uniformisant » du cache on l'atteint peu importe la taille des accès.
Si on se met en accès complètement hors cache (ce qui comme pour la RAM n'a pas de sens sauf s'il y a des conditions vraiment particulières), on récupère 1, 2 ou 4 octets par accès au lieu de 32, et évidemment les performances souffrent en conséquence, et on tombe à une ridicule poignée de Mo/s. À éviter à tout prix.
La partie qui m'étonne, et je l'ai notée sur la troisième colonne, et que apparemment le choix des accès via P0 ou P1 a un effet sur la vitesse de lecture pour les accès 4 octets. Dans la première colonne, on accède à la ROM via l'adresse 00300000 qui est gérée par le MMU et redirige quelque part en ROM. Dans la troisième colonne, on accède direct à 80000000. Et là, pour une raison qui m'échappe complètement la vitesse de lecture en 32-bit prend un gros coup et devient plus lente que les lectures 16-bit. L'idée que le 16-bit soit supérieur n'est pas totalement étrange car la ROM est connectée au BSC via un bus de 16 bits, mais je n'ai aucune idée de pourquoi le MMU ferait une différence.
Ce n'est pas le seul mystère autour de la ROM. Dans CGDoom, les accès 16-bit pour la recherche des fichiers dans la ROM sont plus rapides que les accès 4 octets. La table montre que c'est le cas pour les accès avec le cache, mais c'est ici le cas avec les accès sans cache. Et la raison pour laquelle CGDoom utilise des accès sans cache, c'est que somehow c'est quand même plus rapide dans ce cas.
Mais si on met ces faits étonnants à part, on peut au moins tirer quelques idées générales.
Conclusions :
Conclusion
La mémoire étant l'un des éléments cruciaux dans l'optimisation fine des programmes, il est important de connaître ses mémoires et leurs caractéristiques. Sur une platefore traditionnelle (e.g. PC), il n'y a que la RAM et chaque machine est différente ; ce qui optimise sur une peut déteriorer sur l'autre, et il n'y a pas de recette parfaite générale. Mais sur la calculatrice, avec toutes ses mémoires embarquées et où toutes les machines sont essentiellement identiques, la recherche de performances peut aller beaucoup plus loin. Optimiser la mémoire avec des accès en un cycle nous débloque la possibilité d'optimiser le code en lui-même, par un choix intelligent des instructions et une exploitation fine de CPU.