Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » [C/ASM] Optimiser au cycle près : la référence
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

[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.

  • Les forces et les limites de l'optimisation dans le compilateur (Programmation générale — ★★☆)
  • Travailler avec de l'assembleur SuperH, idiomes classiques (Programmation générale — ★☆☆)
  • Exécution simultanée d'instructions : le pipeline (Bas niveau — ★★★)
  • Exécution simultanée d'instructions : l'architecture superscalaire (Bas niveau — ★★☆)
  • Accès mémoire : délais, alignement, conflits (Bas niveau — ★★☆)
  • Dépendances de données et ordonnancement des instructions (Bas niveau — ★★☆)
  • Déroulement et entrelacement de boucles (Bas niveau — ★★★)
  • Détournements du jeu d'instructions parallèle du DSP (Bas niveau — ★★☆)



Dark storm Hors ligne Labélisateur Points: 11634 Défis: 176 Message

Citer : Posté le 30/06/2021 17:10 | #


Ceci étant dit, typiquement sur la division par 10 l'opti de passer par des templates est grosso-modo équivalente à l'opti de la call-table ? Ou du moins c'est pas si horrible de faire un / 10 dans un bout de code que ce que tu laissais imaginer au début.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 30/06/2021 18:32 | #


Je suis pas sûr que call-table soit ce que tu penses ; c'est pas parce qu'un diviseur est petit que tu peux avoir le résultat de la division de toutes les entrées possibles dans une table.

Maintenant je suis surpris de voir que GCC le génère effectivement comme ça (ie. une multiplication au lieu d'une division) sur un programme que je viens de tester... contrairement à mes essais précédents. Je sais pas comment expliquer la différence. o_o

Well, tu as ta réponse à ta question précédente du coup. ¯\_(ツ)_/¯
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Dark storm Hors ligne Labélisateur Points: 11634 Défis: 176 Message

Citer : Posté le 30/06/2021 21:50 | #


Je suis pas sûr que call-table soit ce que tu penses ; c'est pas parce qu'un diviseur est petit que tu peux avoir le résultat de la division de toutes les entrées possibles dans une table

Non, mais tu peux avoir les constantes x dans une table, et soit appliquer l'algo optimisé si le diviseur est référencé dans la table, soit faire du call-div1 si il n'est pas dedans. En tout cas c'est comme ça que j'ai compris l'extrait de doc.

Ajouté le 30/06/2021 à 22:26 :
Du coup je suis allé fouiner dans le dépôt de GCC, j'ai trouvé des trucs intéressants, de type :

un snippet pour générer ce qui a l'air d'être une table des x
le résultat

J'ai pas l'impression que ce soit exactement l'opti que tu présente, mais en tout cas c'est définitivement mieux que faire une division classique. Même si faire un bout de code custom reste plus fiable pour les raisons que tu expliquais
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 30/06/2021 22:35 | #


Hmm si ça ressemble, ok ok. Dans l'ensemble j'ai clairement sous-estimé/pas réussi à observer le job que GCC fait de ce côté-là, tu as bien fait de creuser. Effectivement c'est cool d'avoir la garantie, mais du coup c'est moins rentable de maintenir le code manuel en C si c'est pas critique.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 07/07/2021 12:56 | #


Introduction à la complexité (Algorithmique — ★☆☆)

De toutes les optimisations que vous pouvez faire, la plupart du temps les optimisations algorithmiques sont les plus poussées. En général, quand on a un algorithme il n'y a pas énormément de façons différentes de le coder ; la structure du code (conditions, boucles, etc.) et déjà fixée ; et ce qu'on va voir avec la «complexité» c'est que le nombre d'opérations à faire l'est aussi dans une certaine mesure.

Le but de la complexité algorithmique c'est donc de quantifier le nombre d'opérations à faire pour exécuter un algorithme.

(Si vous savez qu'une multiplication de matrices prend O(n³) et un tri rapide O(n·log n), ce message ne vous apprendra rien.)

Qu'est-ce qu'une opération exactement ?

Quand on fait de la complexité algorithmique, on regarde un algorithme écrit en pseudo-code, comme par exemple cet algorithme qui calcule l'accumulation de 3 matrices de n lignes et n colonnes :

Accumulation de matrices : C = C + A×B
• A,B,C: double[n][n]

Pour i=1 à n:
  Pour j=1 à n:
    cumul <- 0
    Pour k=1 à n:
      cumul <- cumul + A[i][k] × B[k][j]
    C[i][j] <- C[i][j] + cumul

On aimerait pouvoir déterminer combien de temps cet algorithme va prendre, et comme le processeur va à une vitesse à peu près fixe on s'intéresse à combien d'opérations il prend.

Mais du coup, qu'est-ce qui compte comme une opération ? Les additions et multiplications d'accord, mais est-ce que incrémenter i et j ça compte ? Est-ce que les affectations comme cumul <- 0 ça compte ?

La réponse est : on compte les opérations les plus lentes. Par exemple sur la calculatrice, les opérations en point flottant sur les double sont très lentes, dans le genre 300 à 400 fois plus lentes que les opérations sur les entiers. Ce qu'on fait donc c'est qu'on néglige les accès aux matrices, les opérations sur i et j, et on ne compte que les additions et les multiplications de double.

Selon les cas, ce choix peut varier. Par exemple, il y a des simulations physiques qui multiplient des matrices tellement gigantesques qu'elles ne passent pas dans la RAM d'un ordinateur moderne. On est alors obligés de les lire sur le disque dur, ce qui est extrêmement lent (bien plus que les opérations sur les double). Dans ce cas-là, les accès aux matrices comme A[i][k] sont les points les plus sensibles parce que chaque accès au disque dur prend beaucoup de temps, et donc c'est ça qu'on compte.

Ici, je vais compter les opérations arithmétiques parce que c'est le plus classique. Cependant, sur la calculatrice les accès mémoire sont parfois plus limitants ; quelques exemples seront donnés dans la section sur la mémoire. Une bonne connaissance de ce qui se passe sur le matériel permet de faire des analyses algorithmiques plus pertinentes.

Le paramètre pour la complexité

Vous aurez remarqué quand dans mon exemple, j'ai dit que les matrices sont de taille n×n sans dire quelle est la valeur de n. C'est parce qu'en complexité ça ne nous intéresse pas vraiment de savoir combien d'opérations il faut pour multiplier des matrices 10×10. Non, on veut savoir combien d'opérations il faut pour multiplier des matrices de n'importe quelle taille (qu'on note n×n) et ensuite voir ce qui se passe quand n devient grand.

C'est parce que le but de la complexité c'est de trouver des algorithmes robustes qui vont être rapides même quand il faut multiplier des matrices géantes, quand il faut trier des listes gigantesques ou quand il faut chercher un chemin entre un PNJ et le joueur dans une map immense.

En ne spécifiant pas la valeur de n, on se prépare à calculer une complexité qui donnera le nombre d'opérations en fonction de n, ce qui nous permettra de comparer n=10, n=100, n=1000, et de voir si l'algorithme reste rapide quand le sujet devient grand ou s'il devient catastrophiquement lent.

Si votre programme ne multiplie que des matrices de 3×3 alors la complexité ne vous aidera pas à l'optimiser. Mais si vous multipliez des matrices de 20×20, ou 50×50, ou 100×100, alors là la complexité peut vous dire comment il faut faire le calcul pour que ça aille vite.

En général, on étudie un seul paramètre qui est la taille du problème (la taille des matrices, la taille des tableaux, le nombre de cases sur la map, etc). Comme pour tout il y a des exceptions, mais on choisit souvent la taille parce que c'est ça qui influence le plus le nombre d'opérations à faire.

Avec tous ces détails bien mis en place, on peut calculer la complexité de l'algorithme d'accumulation de matrices que j'ai présenté ci-dessus.

Accumulation de matrices carrées : 2n³ + n²

Pour rappel, on compte les opérations sur les double. Il y a une multiplication et une addition dans cumul + A[i][k] × B[k][j], et une addition dans C[i][j] + cumul. La question qui est importante ici, c'est donc «combien de fois est-ce qu'on exécute ces deux lignes ?».

La première est dans une boucle k=1...n et est donc exécutée n fois. Mais la boucle elle-même est exécutée n fois (pour j=1...n) et cette boucle encore est exécutée n fois (pour i=1...n). La ligne est donc exécutée n×n×n = n³ fois, et comme il y a deux opérations sur les double (une addition et une multiplication), ça donne un total de 2n³.

La deuxième ligne est dans la boucle j=1...n, qui est elle-même dans la boucle i=1...n, et donc elle est exécutée n² fois, pour un total de n² opérations (puisqu'il n'y a qu'une addition sur la ligne).

Le nombre d'opérations en point flottant dans cet algorithme est donc T(n) = 2n³ + n². (On dit T pour le temps de calcul, par habitude.)

L'influence énorme de la complexité dans le temps de calcul

Dans le tableau ci-dessous j'ai résumé les valeurs de n², n³, et 2n³ et T(n) pour différentes valeurs de n.

n2n³T(n) = 2n³+n²
5 25 125 250 275
10 100 1000 2000 2100
250 62500 15.625 millions 31.25 millions 31.31 millions
4'000 16 millions 64 milliards 128 milliards 128.02 milliards
10'000 100 millions 1 billion 2 billions 2.0001 billions

La première chose à voir, c'est que ça grandit très vite ! Il est évident qu'avec cette méthode accumuler des matrices de 250×250 ça passe encore, 4000x4000 c'est faisable avec un bon ordinateur, mais 10000x10000 c'est même pas envisageable sans un super-ordinateur.

On peut comparer ça avec un algorithme de tri, pour se donner une idée. Une matrice de 10000x10000 possède 100 millions d'éléments ; peut-on trier 100 millions d'éléments ? Oui, et c'est même assez facile, ça prend environ n·log₂ n = 2.5 milliards de comparaisons de double. C'est beaucoup bien sûr, mais c'est réaliste rien qu'avec mon ordinateur portable.

La morale c'est que dans quasiment tous les cas, la complexité de l'algorithme domine complètement le temps de calcul quand on prend des objets très grands. Ici j'ai pris des objets vraiment grands avec des millions de nombres, mais si votre jeu a une map de 100x100 = 10000 tiles vous verrez déjà des grandes différences de performance entre les algorithmes lents qui une complexité élevée, et les algorithmes intelligents qui ont une complexité plus faible.

Complexité asymptotique et notation grand O : O(n³)

À propos de dominer, vous remarquerez que dans le 2n³+n² c'est clairement le n³ qui fait tout le boulot ; dès que n est assez grand la contribution de n² au nombre total d'opérations est assez négligeable. De la même façon, le facteur 2 a de moins en moins d'importance.

Pour cette raison, les algorithmiciens utilisent une notation spéciale pour simplifier les formules. On parle d'une notation asymptotique, ce qui veut dire qu'elle s'intéresse uniquement à ce qui se passe quand n devient grand (asymptotique = «au voisinage de l'infini» si vous êtes prêt·es à simplifier un peu).

Cette notation s'écrit avec un O majuscule (prononcé «grand O»). La définition est la suivante :

On dit que T(n) = O(f(n)) si à partir d'une certaine valeur de n, T(n) ≤ C × f(n) pour une constante fixée C.

Décortiquons doucement cette définition. «À partir d'une certaine valeur de n» concrétise le fait qu'on ne s'intéresse qu'au comportement quand n devient grand. Si la complexité qu'on a déterminée ne marche pas pour n=0 ou n=1, on s'en moque. On veut juste quelle marche pour n≥2, ou n≥10, ou n≥100. (Évidemment si elle ne marche que pour n ≥ 1 million le résultat sera inutile, mais techniquement c'est acceptable aussi.)

T(n) ≤ C × f(n) ça veut dire qu'à une constante C près, T(n) est plus petit que f(n). Autrement dit, que f(n) indique une borne sur le nombre d'opérations, à ×2 près, ou à ×3 fois, ou à ×1000 près.

Par exemple, on peut dire que T(n) = O(n³) : en effet, T(n) = 2n³ + n² ≤ 3 × n³ dès que n ≥ 0. En revanche, on ne peut pas dire que T(n) = O(n) puisque peu importe la constante C qu'on choisit, il y a des grandes valeurs de n pour lesquelles T(n) > C × n.

Attention, O() n'est pas une fonction, c'est une notation. (Les gens vraiment rigoureux seront contents de savoir qu'il y a une définition propre : O(f) c'est l'ensemble de toutes les fonctions qui valident la propriété par rapport à f, et on écrit T ∈ O(f), ou dans notre cas, T ∈ O(n ↦ n³). Mais il faut vraiment aller chercher des mathématiciens pour raisonner comme ça.)

Pour résumer, on dit que la complexité de cet algorithme est O(n³) (prononcé «un grand O de n³») pour mettre en avant le fait que le nombre d'opérations est très proche de n³ quand n est grand, en ignorant les petits facteurs qui sont négligeables à côté. Moralement, le temps de calcul est «de l'ordre de grandeur de n³».

Comment ça marche en pratique ?

Souvent, les problèmes qu'on veut résoudre dans un programme sont déjà étudiés (produits de matrices, tris de tableaux, recherches de chemin sur une map pour ne citer que les exemples que j'ai déjà mentionnés). Le processus de réflexion pour le développeur du programme est donc à peu près comme ça :

  1. Déterminer si le calcul qu'on veut faire correspond à un problème classique (souvent oui), et lequel.
  2. Consulter les différents algorithmes disponibles pour ce problème.
  3. Comparer la difficulté d'implémentation, la complexité, le quantité de mémoire nécessaires, et d'autres facteurs pertinents dans le code en général.
  4. Implémenter un ou plusieurs algorithmes prometteurs, et valider que le temps d'exécution correspond aux attentes.

Typiquement si vous voulez trier un tableau vous utilisez par exemple un tri rapide en O(n·log n), ça se code en 20-30 lignes en C ; vous n'avez pas besoin de l'inventer (le copier/coller de Wikipédia marche très bien), et ça ira souvent 10-15 fois plus vite qu'un tri naïf comme un tri bulle en O(n²).

Ou bien pour une recherche de chemin entre un PNJ et le joueur sur la map, vous modélisez la map comme un graphe et vous implémentez soit un parcours en largeur, soit un Dijkstra, soit un A*... parfois d'autres algorithmes sont plus appropriés, comme Floyd-Warshall si vous avez énormément de chemins à calculer, ou Bellman-Ford si le map change par petites touches ; etc etc.

Il n'est pas nécessaire de connaître tous ces algorithmes pour écrire des programmes optimisés. Mais il est important de savoir que la complexité d'un algorithme peut influencer énormément le temps d'exécution d'un programme, et de pouvoir reconnaître quand un amélioration de d'algorithme est plus rentable qu'optimiser le code.

N'oubliez pas que si vous optimisez le code aux petits oignons mais que vous devez ensuite changer d'algorithme parce que celui que vous utilisez est super lent, toute l'optimisation sera perdue. Idéalement on veut choisir les bons algos en premier, ensuite les coder, et ensuite optimiser ce code.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 18/07/2021 19:27 | #


Accès aux mémoires, bus, et compromis taille/vitesse (Bas niveau — ★☆☆)

Le microprocesseur SH7305 qui est au cœur de la calculatrice est un ordinateur relativement moderne, dans le sens où ses préoccupations en termes de performances sont similaires à celles des processeurs plus avancés qu'on trouve communément dans nos ordinateurs (par exemple x64/amd64) ou appareils mobiles (par exemple arm/aarch64).

À l'époque (aujourd'hui révolue) où les processeurs et les mémoires étaient alignés sur la même horloge, un programme passait un cycle pour faire une addition et un cycle aussi pour lire un octet dans la mémoire. Aujourd'hui, cet équilibre n'est plus du tout vérifié, mais ces deux types d'opérations continuent de dominer l'occupation des programmes.

Un programme donna sera donc limité selon les moments soit par la vitesse de calcul du processeur soit par sa capacité à accéder rapidement la mémoire.

La différence est significative : par exemple, un programme qui fait de très nombreux accès à la VRAM pour dessiner des objets à des positions éloignées de l'écran imposera une charge maximale sur les accès mémoire. À l'inverse, un programme qui calcule les points d'une fractale de Mandelbrot ne fait que du calcul et sera exclusivement limité par l'ordre et la quantité des opérations arithmétiques. Il est crucial de savoir ce qui limite chaque programme pour optimiser où il faut.

(Précision : sur un ordinateur la VRAM est de la mémoire sur le GPU, mais pour nous c'est juste un tableau de pixels dans la RAM. Si je parle de VRAM c'est donc juste une variable qui est dans la RAM principale et qui est trop grosse pour aller dans les mémoires plus petites.)

La différence est aussi subtile, car une simulation du jeu de la vie pourra se trouver à la fois limitée par le calcul (puisque le calcul de l'état de chaque cellule à la génération suivante demande une addition de 8 termes et des comparaisons, entre autres) et par les accès mémoire (puisque ce calcul nécessite l'information des 8 cellules qui l'entourent, qu'il faut aller lire en mémoire). Une analyse fine est parfois requise.

Dans cette technique du guide d'optimisation, je m'intéresse à la mémoire ; les calculs seront plutôt abordés dans les optimisations sur le code assembleur.

Mécanisme des accès mémoires et bus

Pour bien comprendre l'impact des accès mémoire sur les performances, il est important de voir comment ils se déroulent en termes matériels.

La connexion entre le processeur et les différents modules qui l'entourent (dont les mémoires, mais aussi tous les modules périphériques entre autres) se fait par l'intermédiaire d'un bus. Un bus est un peu une route sur laquelle les informations circulent entre différents composants électroniques.

Dans l'idée, c'est juste un fil qui relie tous les composants ; dès que quelqu'un écrit un 0 ou un 1 dedans, tout le monde reçoit la valeur. On y ajoute un mécanisme pour éviter que deux personnes écrivent en même temps, on attribue des «adresses» pour que chaque composant puisse identifier les messages qui lui sont destinés et ignorer les autres, on met plusieurs fils pour pouvoir écrire plusieurs bits simultanément, et c'est à peu près tout (mais je ne suis pas spécialiste ici, ne me citez pas sur le sujet).

Lorsque le processeur exécute une instruction d'accès mémoire, il écrit sur le bus l'adresse à laquelle il veut accéder, la taille de l'accès (1, 2 ou 4 octets), si l'accès est une lecture ou une écriture, et, si c'est une écriture, la valeur à écrire. La mémoire, qui «écoute» sur le bus, reçoit l'information et traite la demande ; si c'est une lecture elle va chercher la valeur et l'écrit sur le bus en réponse, si c'est une écriture elle sauvegarde la valeur fournie par le processeur. Dans les deux cas la mémoire indique via le bus à quel moment elle a terminé.

Il y a plusieurs éléments importants ici en termes de performance ; le principal c'est qu'il n'y a pas de contrainte sur le temps de traitement de l'accès. Le processeur «attend» jusqu'à ce que la mémoire indique qu'elle a fini, et donc différentes mémoires qui ont différents mécanismes électroniques peuvent mettre des temps différents (et elles le font).

Le bus a aussi un rôle à jouer. Comme le bus est utilisé pour passer des messages entre plusieurs composants, et qu'une seule personne peut écrire dessus à la fois, il peut y avoir des délais pour cause d'embouteillages. Parfois, l'optimisation est une affaire de faire passer les bons messages sur les bons bus pour éviter les collisions.

L'éternel équilibre entre taille et vitesse

La mémoire parfaite est une mémoire à la fois très grande et très rapide. La nature faisant bien les choses, il est clair d'emblée qu'une mémoire à la fois très grande et très rapide ne peut donc pas exister.

Il y a beaucoup de raisons pour ça, mais la plus simple est que plus il y a d'octets dans la mémoire plus il y a de travail à faire pour identifier le petit composant électronique qui contient la donnée. Tout comme plus une bibliothèque est grande, plus il y a de travail à faire pour identifier un livre spécifique, même si les livres sont numérotés de façon parfaite. Les octets de mémoire, comme les livres, occupent physiquement de la place ; plus il y en a plus le circuit est grand, et plus le signal électrique met longtemps à le traverser.

Par conséquent, une mémoire qui est plus grande est nécessairement plus lente (à autre facteurs égaux), et de la même façon une mémoire plus rapide est nécessairement plus petite.

Cette dichotomie est omniprésente, et pour compenser ses effets chaque ordinateur a souvent beaucoup de mémoires de différentes tailles (et de vitesses inversement proportionnelles).

Par exemple, sur un ordinateur portable moyen comme le mien, un accès à la RAM prend beaucoup plus qu'un cycle d'horloge du processeur. Pour compenser ce problème, on a inventé le cache ; une mémoire intermédiaire située entre le processeur et la RAM, plus petite que la RAM mais aussi plus rapide, qui contient une copie des données auxquelles on a accédé récemment. Si on utilise les mêmes données plusieurs fois de suite le cache répond à la place de la RAM, ce qui va beaucoup plus vite, sinon il accède à la RAM comme avant.

Le cache améliore tellement les performances que les ordinateurs en ont aujourd'hui trois niveaux, chacun plus gros mais plus lent que le précédent. La calculatrice a aussi un cache, quoiqu'un seul niveau, ce qui suffit car la mémoire n'est pas aussi lente que sur un PC (principalement parce qu'elle n'est pas aussi grosse !).

L'échelle des mémoires est assez longue ; les plus petites sont les registres du processeur, les plus grandes sont les disques durs et autres périphériques externes, avec toute une palette d'intermédiaires. Il est donc important de savoir à qui on s'adresse dans un programme pour contrôler les performances.

Structure du SH4AL-DSP et du SH7305

Le processeur qu'on a est un SH4AL-DSP. Malheureusement, sa documentation ne contient pas de diagramme montrant la structure du bus et des composants. À la place, en voici une que j'ai prise dans celle du SH-4A (page 30), qui est relativement proche.


Ce diagramme n'est pas aussi compliqué qu'il en a l'air de loin, on peut le déchiffrer ensemble. Chaque ligne représente une connexion physique, et des formes épaisses sont utilisées pour indiquer que les connexions sont larges (plusieurs bits en parallèle).

La partie "SH-4A core" en pointillés représente le processeur. Physiquement, cette région est sur une unique puce au milieu du circuit. Le reste c'est les parties du MPU (pour nous, le SH7305) qui sont autour. Il y a trois bus dans le processeur :
  • Le bus d'instructions ;
  • Le bus d'opérandes ;
  • Et le bus interne cache/RAM.

Et il y a deux bus à l'extérieur :
  • Le SuperHyway (littéralement l'autoroute) ;
  • Et le bus périphérique.

Bus d'instructions et bus d'opérandes

Ces deux bus sont les plus proches du processeur et aussi les plus rapides. Ils sont tous les deux reliés soit aux mémoires très proches (ILRAM ou cache par exemple) soit aux modules qui permettent d'accéder aux mémoires plus éloignées (typiquement le MMU).

Le bus d'instructions est utilisé pour lire le code dans les mémoires très proches, et le bus d'opérandes est utilisé pour lire et écrire les données : variables, tableaux, et autres opérandes d'instructions. Séparer les deux est utile parce qu'on fait souvent les deux à la fois et parce que les programmes se comportement très différemment vis-à-vis des deux.

Deux cas simples sont l'ILRAM (Instruction Local RAM) et l'OLRAM (Operand Local RAM). La première est dédiée au stockage d'instructions et est connectée au bus d'instructions, la seconde est dédiées au stockage d'opérandes et est connectée au bus d'opérandes. (Sur le SH4-AL DSP l'OLRAM est remplacée par autre chose de similaire.) La vitesse de ces bus et mémoires est illustrée par la documentation concernant les accès en instructions à la mémoire IL :

Instruction fetch access from the CPU is performed directly via the instruction bus for a given virtual address. In the case of successive accesses to the same page of IL memory and as long as no page conflict occurs, the access takes one cycle.

Du code placé en mémoire IL peut donc être lu en un seul cycle, ce qui est le meilleur résultat possible. On notera quand même que la mémoire IL est divisée en «pages» de 4 ko et que la garantie d'un cycle n'est valide que tant qu'on reste sur la même page. Nous on n'a qu'une page de toute façon (l'ILRAM fait 4 ko en tout) mais on retrouvera ce genre de contraintes sur d'autres exemples.

Vous remarquerez que la vitesse d'accès n'est pas la même si on accède à la mémoire IL par une opérande :

Operand access from the CPU and access from the FPU are performed via the cache/RAM internal bus. Access via the cache/RAM internal bus takes more than one cycle.

Eh bien tout de suite ça passe par le bus interne cache/RAM, qui est plus lent, donc ça prend plus d'un cycle. Vous voyez déjà que différents types d'accès à la même mémoire peuvent passer par différents bus et donc prendre différentes durées.

Sur le SH4-AL DSP, on n'a pas de FPU à côté du CPU, mais on a un DSP. Ce DSP a deux zones de mémoire dédiées, la XRAM et la YRAM, qui sont toutes les deux reliées au DSP par des bus dédiés de 16 bits, le bus X et le bus Y. Ça il y en a un schéma dans la doc du SH4AL-DSP (page 177).


Vous pouvez voir que le bloc "DSP unit" est relié aux mémoires X et Y par ces deux bus dédiés. Ils font chacun 16 bits, si bien que le DSP peut lire 16 bits de mémoire X et 16 bits de mémoire Y en même temps. (Il peut aussi lire 32 bits d'une seule parce que chacun des deux bus peut accéder aux deux mémoires, même si le schéma ne le montre pas.) Les accès par les bus X et Y se font en un seul cycle.

Cela dit, le DSP n'est pas pratique à utiliser pour des raisons que j'explorerai dans une autre technique, donc on préfère accéder à la mémoire X et Y par le CPU. Pour ça, il faut utiliser le bus d'opérandes que vous pouvez voir représenter à droite du diagramme (ou le bus d'instructions qui lui n'est pas représenté). Par chance, les accès à la mémoire X et Y par ces deux bus prennent aussi 1 seul cycle, donc le CPU bénéficie des mêmes performances remarquables que le DSP.

Voilà qui conclut à peu près le tour des mémoires très proches. Il y aussi les caches, mais on ne peut pas contrôler directement ce qu'il y a dedans, ils sont associatifs donc non triviaux à utiliser efficacement, et ça méritera une technique complète qui suivra certainement un autre jour.

Le bus interne cache/RAM

Le bus interne cache/RAM est, comme son nom l'indique, le bus avec lequel le processeur interface avec le cache et la RAM (toute la mémoire "principale" donc). Le cache, qui est séparé en un cache d'instructions et un cache d'opérandes (parce que le code et les données ne sont pas du tout traitées pareil par le programme donc on gagne à gérer les deux caches différemment), est accessible directement pas les bus d'instructions et d'opérandes quand le CPU demande un accès, et reçoit les données en provenance de la RAM par le bus interne cache/RAM quand les données demandées ne sont pas immédiatement disponibles.

La RAM à proprement parler, et la ROM (OS + mémoire de stockage) aussi d'ailleurs, sont derrière le BSC (Bus State Controller), donc l'accès ne s'arrête pas au bus interne cache/RAM, il continue encore (et vous commencez peut-être à voir pourquoi les accès à la VRAM sont lents).

Il n'y a pas grand-chose de très intéressant à accéder par ce bus ; vous noterez que les accès en opérandes/instructions aux mémoires IL/OL (les accès pour lesquels ces mémoires ne sont pas conçues, donc) passent par le bus interne cache/RAM comme je l'ai illustré précédemment, donc sont plus lents.

Le point le plus important concernant ce bus est le MMU. Le MMU est le composant qui traduit les adresses virtuelles en adresses physiques quand on accède à la mémoire par une adresse virtuelle dans P0 (à savoir, en gros, la ROM ou le segment de données) ou P3 (qui ne contient rien sur la calculatrice). Ça veut dire que si vous mappiez l'ILRAM dans P0 par exemple vous perdriez la vitesse d'accès. Pour les mémoires qui sont hors du processeur et qui doivent passer par le bus interne cache/RAM dans tous les cas, utiliser les adresses physiques est quand même utile puisque ça économise le temps de décodage par le MMU, mais je ne sais pas quel est l'ordre de grandeur.

Le SuperHyway et le bus périphérique

Les modules hors du processeur sont reliés par le SuperHyway où on trouve notamment le BSC, qui donne accès à la RAM principale et à la ROM (qui ne sont même pas dans le SH7305 mais encore à l'extérieur), et le contrôleur DMA.

Vous pouvez voir ici en pleine action la dichotomie taille/vitesse dont je parlais tout à l'heure. Un accès à la RAM principale (comme le dessin dans la VRAM) passe d'abord par le bus d'opérandes, puis optionnellement le MMU, puis le bus interne cache/RAM, puis le SuperHyway, puis le BSC, un bus externe, et ensuite seulement il atteint la RAM, avant de refaire le même chemin en sens inverse. Ce sera toujours beaucoup plus long qu'un accès parfait d'un cycle à la mémoire X par le bus d'opérandes, pour des raisons évidentes.

Le DMA est un cas intéressant. On s'en sert souvent pour copier des données de la RAM à la RAM, ou de la RAM à l'écran, ou de l'ILRAM à la RAM dans quelques cas (comme la fonction dma_memset() de gint). Le DMA est derrière le SuperHyway, donc il est raisonnablement bien placé pour accéder à la RAM et à l'écran, mais il est moins bien placé que le processeur pour accéder aux mémoires rapides comme les mémoires IL, X ou Y. C'est pour cette raison par exemple que copier de la mémoire X vers la mémoire Y va beaucoup plus vite par le CPU mais copier de la RAM vers la RAM va beaucoup plus vite par le DMA. (On explorera en détail les débits dans une autre technique, sinon celle-ci ne se terminera jamais. x3)

Le bus périphérique n'est pas très intéressant, il mène aux modules périphériques, mais comme on n'y accède jamais très souvent ce n'est pas un problème pour les performances.

Paramètres d'horloges, overclock

Comme à peu près tous les composants, les bus sont cadencés par des horloges. Et qui dit horloge dit paramétrage de la fréquence (voire overclock) avec le CPG (Clock Pulse Generator, le module qui gère les horloges). Je ne détaille pas, mais on retrouve principalement ces horloges pour contrôler les bus :

  • : Horloge du CPU (et des trois bus qui sont dedans)
  • : Horloge du bus SuperHyway (et du DBSC)
  • : Horloge du BSC (donc accès RAM, ROM) et des modules périphériques sur le SuperHyway
  • : Horloge du bus périphérique et des modules qui sont dessus

Il y en a d'autres, y compris certaines qui servent à cadencer des périphériques externes. (Je n'ai pas encore trouvé d'horloge qui permette d'overclock spécifiquement l'écran, mais peut-être que ça arrivera.)

En général elles sont toutes overclockées en même temps, vous pouvez regarder par exemple les paramètrages par défaut de Ptune3 pour vous donner une idée. Il y a aussi pas mal de contraintes, par exemple la fréquence de Iϕ doit être un multiple de celle de Sϕ, Sϕ ne peut être égale qu'à Bϕ ou à 2Bϕ, et d'autres du même style (voyez la documentation du SH7724, 17.5.2 pour les détails).

Voilà qui devrait vous donner une bonne idée des enjeux. L'usage de mémoires proches et rapides est très bénéfique voire inégalable, surtout lorsque la mémoire est de loin le facteur limitant (ce qui est le cas dans le dessin en général). Dans une autre technique je ferai une cartographique complète des zones de mémoire et de leurs tailles, ce qui permettra ensuite de discuter des différentes méthodes d'accès (CPU, DSP, DMA, instructions vs opérandes, caches) et de leurs vitesses au cas-par-cas.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 18/07/2021 21:42 | #


Interlude : éléments d'analyse asymptotique (Maths — ★★★)

Quand j'ai écrit la technique Introduction à la complexité on m'a demandé des détails sur la notation O() et ce que ça veut dire exactement donc je prends ce moment pour en parler. Ça c'est des maths uniquement et ça n'a aucun lien direct avec l'optimisation des programmes, n'hésitez pas à survoler ou sauter le post

Le domaine dont ces outils sont tirés s'appelle l'analyse asymptotique. C'est le domaine où on étudie des fonctions à la limite, soit vers l'infini soit vers des points finis (typiquement 0). Le but est de caractériser le comportement des fonctions au voisinage du point limite, en ignorant ce qui se passe ailleurs, et notamment de calculer des formes simplifiées qui sont «équivalentes» (pour une certaine définition très précise d'équivalence) à la fonction originale.

Pour toute cette technique, on se donne un point limite a qui est soit un réel soit un infini. Comme le sujet général c'est la complexité par défaut je prendrai comme limite +∞, mais je mentionnerai aussi parfois le cas 0 (pour lequel les relations sont assez différentes). Je suppose aussi que toutes les fonctions sont strictement positives (ie. à valeurs dans ℝ⁺*) pour simplifier les définitions.

Pour info, c'est du cours du Maths sup. en gros (mais je le ressors de tête parce que je l'ai pas avec moi pour vérifier xD).

Domination et petit o

Une première idée qu'on veut formaliser c'est le fait que certaines fonctions grandissent plus vite que d'autres (... au voisinage de +∞, en 0 ce serait diminuent en général). Cette relation de «domination» va par exemple permettre de se concentrer sur un seul terme dans une complexités et d'ignorer les autres. Typiquement dans 2n³+n² le terme 2n³ domine le terme n² en +∞, et le terme n² domine le terme 2n³ en 0.

On dit que f domine g au voisinage de a si: lim(x→a) g(x)/f(x) = 0.

Très concrètement la domination on la représente par un quotient. Si le quotient g/f tend vers 0, f domine g. Quand f peut s'annuler c'est plus casse-pieds à définir, mais l'idée reste la même.

Comme on utilise souvent cette relation, on définit l'ensemble o_a(f) (prononcé « petit o en a de f ») qui inclut toutes les fonctions dominées par f.

o_a(f) = { g | lim(x→a) g(x)/f(x) = 0 }.

Et c'est là qu'on trouve une ribambelle de raccourcis de notation plus ou moins douteux :
  • On écrit o(f) sans spécifier a quand c'est clair dans le contexte. Ça ok.
  • On écrit souvent o(2n³) au lieu de o(n ↦ 2n³) ou o(f(x)) au lieu de o(f). Pas hyper propre mais passable.
  • On écrit g = o(f) au lieu de g ∈ o(f). Ça c'est extrêmement répandu et aussi extrêmement trompeur.

La raison évidemment pour laquelle utiliser le signe d'égalité est manipulateur, c'est que c'est pas une relation d'équivalence. Déjà o(f) = g ça n'a aucun sens, et puis on peut avoir g = o(f) et h = o(f) sans avoir g = h (y'a qu'à prendre g(x) = x² et h(x) = x dans l'exemple précédent).

Néanmoins, on voit couramment des trucs comme T(n) = 2n³+n² = O(2n³) = O(n³), ce qui sert juste à donner différentes approximations successives, ce qu'on écrirait d'une façon plus rigoureuse T(n) = 2n³+n² ; T ∈ O(n ↦ 2n³) ⊆ O(n ↦ n³). (On verra dans un instant ce que veut dire O(), mais la définition est similaire et le raccourci est le même.)

Attention donc aux raccourcis, en cas de doutes il faut bien se rappeler que o(f) est un ensemble, et à partir de là on arrive généralement à s'y retrouver.

Équivalents

Une des grandes idées de l'analyse asymptotique est de trouver des équivalents. Et par équivalent, on entend quelque chose qui se rapproche de la fonction dans un ratio de 1 (et rien d'autre).

On dit que f est équivalent à g au voisinage de a, et on écrit f ~_a g, si: lim(x→a) f(x)/g(x) = 1.

Par exemple, au voisinage de l'infini on a 2n³+n² ~ 2n³ parce que le terme en n² ne contribue qu'à une proportion négligeable du total. (Vous noterez que j'emploie les mêmes raccourcis que précédemment : termes libres. vs fonctions, et omettre la valeur de a.)

Attention par contre, 2n³ ≁ n³ (puisque le rapport est 2). On a (x+1)⁵ ~ x⁵, mais en revanche e^(x+1) ≁ e^x (le rapport est e). Là on commence à voir la différence entre les polynômes (qui sont assez réguliers et se moquent de petits décalages) et les exponentielles (qui sont très sensibles). Plus tard ça explique pourquoi on choisit d'avoir P et EXPTIME comme classes de complexité.

Notez que la définition rigoureuse c'est f ~_a g si f-g ∈ o_a(f), autrement dit la différence est négligeable devant le total. Ça évite les problèmes de division mais ça revient au même dans le cas des fonctions strictement positives.

L'analyse asymptotique aime beaucoup les équivalents et souvent on essaie d'en établir. Parfois c'est assez tordu, par exemple on peut définir une suite de façon implicite du style «soit u_n la valeur x telle que de f(n,x)=0» et ensuite déterminer un équivalent de u_n en l'infini. Ça revient à estimer où se trouvent les racines de f(n,·) en fonction de n, ce qui est déjà assez musclé. D'ailleurs j'ai du mal avec ce genre de choses, heureusement en informatique (typiquement en complexité) on se trimballe presque exclusivement des fonctions explicitement définies. x)

Bornes supérieures et O()

Un autre outil très important pour les bornes supérieures est O() (« grand O »). Le principe est similaire à o(), sauf que cette fois on ne veut pas dominer, on veut juste une borne supérieure à une constante près. Cette définition est très utile même pour les fonctions qui s'annulent, donc en général on déroule la limite pour avoir une forme plus générale. Comme la limite s'écrit différemment en +∞ et pour un réel je vous donne la version +∞.

On dit que f ∈ O_+∞(g) s'il existe M∈ℝ et C>0 tels que ∀ x≥M, f(x) ≤ C·g(x).

Je pense que la définition est relativement explicite, mais à défaut ça dit que g est une borne supérieure de f à une constante C près et au voisinage de +∞ (on ne chercher pas à savoir ce qui se passe pour x<M).

Conceptuellement, c'est un peu comme si le quotient f(x)/g(x) était borné par une constante à l'infini. Mais attention ce n'est pas la définition et il n'y a pas besoin que le quotient ait une limite pour avoir un O(). Le but de cette remarque est simplement de montrer la relation entre ces trois outils (pour des fonctions à valeurs strictement positives) :

  • Si f(x)/g(x) tend vers 0, on a un petit o.
  • Si f(x)/g(x) tend vers 1, on a un équivalent.
  • Si f(x) est borné par un multiple constant de g(x), on a un grand O.

Notez que O() c'est vraiment que la borne supérieure, je peux prendre n'importe quel algorithme et dire que sa complexité est O(2^(n!^n)), ça ne sert juste à rien. En informatique on écrit O() et on prouve bien la propriété de O() mais on cherche toujours à trouver la plus petite borne possible. Par exemple c'est techniquement correct de dire que le produit matriciel est O(n⁴), mais si vous mettez ça au partiel je vous garantis que vous n'aurez pas les points sur la question. x3

Notez que pour pas mal de problèmes on ne sait juste pas quelle est la meilleure complexité qu'on peut obtenir avec un algorithme. Rien que pour le produit matriciel par exemple, il y a des algos plus malins que l'algo naïf (comme celui de Strassen) qui font O(n^2.807), il y a des algos super tordus qui O(n^2.373) mais que personne n'utilise, et on ne sait pas jusqu'où on peut descendre à part le fait qu'on ne peut pas descendre plus bas que O(n²).

Autres notations parfois utiles

On écrit f = Ω(g) si g = o(f).

On écrit f = Θ(g) si f = O(g) et g = O(f) ; notez que du coup, g = Θ(f) aussi. Ça revient à dire que f est coincé entre 2 multiples constants de g, ce qui est une sorte d'équivalent à facteur constant près (et inversement). Ce que je disais plus haut c'est qu'en général en complexité algorithmique on essaie d'obtenir des Θ(), ce qui indique que la borne est optimale. Cela dit même quand on les atteint en général on écrit O() et on ajoute à côté « la borne est optimale », parce que la notation est assez rare (et que parfois la condition d'optimalité est légèrement différente).

Propriétés intéressantes et quelques développements limités

J'y vais un peu rapidement ici parce qu'il y a beaucoup de choses à explorer (toute une théorie, en fait) et je peux pas faire un cours complet d'analyse asymptotique. :x

Les o() et les O() peuvent être additionnés et soustraits. Par exemple, 2n³ = O(n³) et n² = O(n³) donc 2n³ + n² = O(n³). C'est aussi des trucs transitifs, typiquement si f = o(g) et g = o(h), alors f = o(h)... pareil avec O(). La multiplication marche aussi sans problème. Dans l'idée votre intuition de ce que «domination» et «borne supérieure» veulent dire se traduit assez bien par des propriétés sur les o() et O(), il n'y a pas fondamentalement de piège (à part celui de croire qu'il y a des propriétés suffisamment évidentes pour qu'on n'ait pas besoin de les prouver :P).

L'équivalence est une relation d'équivalence (oui c'est bien nommé !).

Les équivalents ça se multiplie et divise très bien et sans piège (à part si la fonction quotient s'annule). Par contre, additionner ou soustraire des équivalents est un crime capital passable de -4 sur n'importe quelle copie de prépa et aussi la source #2 de frustration du prof de sup' sur ce chapitre (la source #1 étant les gens qui balancent des équivalents sur tout et n'importe quoi en se disant «bwarf, c'est presque la même fonction donc c'est probablement ~équivalent~»).

Tout ça se raccroche beaucoup au développements limités. Pour vous donner une petite idée de la puissance de l'analyse asymptotique, prenons un exemple. Vous savez peut-être que sin(x)/x se rapproche beaucoup de 1-x²/6 au voisinage de 0. On peut quantifier à quel point en calculant un développement limité de sin(x)/x en 0 (c'est une série de MacLaurin/Taylor que vous connaissez probablement) :

sin(x)/x = 1 - x²/6 + x⁴/24 - x⁶/720 + ...

Le premier terme (à savoir 1) est un équivalent, et ensuite à chaque fois que vous coupez la séquence vous avec un o(). Par exemple sin(x)/x = 1 + o(1) ou bien sin(x)/x = 1 - x²/6 + o(x²). Vous pouvez prendre le nombre de termes qui vous arrange, vous aurez à chaque fois une approximation de sin(x)/x avec plus ou moins de précision.

Pour comparer avec notre seconde fonction 1 - x²/6 je peux prendre aussi un développement limité en 0, mais comme c'est un polynôme c'est juste lui-même. Donc là aussi l'équivalent c'est 1, et on peut écrire 1 - x²/6 = 1 + o(1) ; je peux continuer aussi avec le second terme mais à ce moment-là ce ne sera plus une approximation donc le o() disparaîtra.

Maintenant on peut déterminer à quel point les deux fonctions sont proches en 0 en soustrayant les développement limités (que je coupe à l'ordre 4 parce que je veux qu'un seul terme) :

sin(x)/x - (1-x²/6) = x⁴/24 + o(x⁴)

Et voilà un équivalent de la différence : au voisinage de 0, sin(x)/x et 1 - x²/6 se rapprochent à la vitesse de x⁴/24. Bon courage pour trouver ce résultat autrement !

Vous voyez bien d'ailleurs que ce n'est pas la différence des équivalents (qui est 1 - 1 = 0). Faire cette soustraction c'est comme faire la différence des développements limités mais avec un seul terme, ce qui ne donne rien d'utile :

sin(x)/x = 1 + o(1)
1 - x²/6 = 1 + o(1)
sin(x)/x - (1-x²/6) = (1 + o(1)) - (1 + o(1)) = o(1)

Je cache un peu des règles de «calcul sur les o()» qui sont juste des raccourcis supplémentaires sur la notation ensembliste. Mais vous pouvez voir que le résultat qu'on a c'est que la différence est o(1), ce qui est techniquement correct mais pas assez précis pour sortir un équivalent (pour ça il faut aller à l'ordre 4).

Voilà donc quelques éléments d'analyse asymptotique et un exemple jouet de ce qu'on peut faire avec.

Ne vous inquiétez pas si cette dernière partie vous a complètement échappé, c'est plus destiné aux étudiants qui ont eu un cours dessus. Un seul post de ce style n'est pas suffisant pour introduire autant de notions de façon digeste.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 19/07/2021 22:10 | #


Concepts généraux et bons benchmarks (Programmation générale — ★☆☆)

Optimiser un programme est une activité un peu ambiguë ; ça peut être crucialement utile mais aussi une perte complète de temps, selon ce qu'on optimise et comment on le fait. Dans l'ensemble c'est aussi une activité chronophage, d'où l'intérêt d'optimiser intelligemment et surtout là où ça frappe le plus fort. Avoir un programme optimisé c'est cool, ne pas avoir de programme parce qu'on a plus le temps de le finir c'est moins cool.

Avoir un objectif bien défini

Il est utile d'avoir un cahier des charges pour savoir où on va. Parfois on veut juste que le jeu atteigne 30 FPS, parfois on veut que le jeu soit assez rapide pour pouvoir enregistrer une vidéo du gameplay par USB sans le ralentir, parfois on veut que la simulation calcule 400 générations par seconde, et parfois on veut carrément avoir le code le plus rapide possible pour un challenge personnel.

Avoir une idée préliminaire de ce qui appartient au domaine du possible est utile pour se fixer des objectifs réalistes. Ça demande un peu d'expérience, mais par exemple je pense que si vous voulez un jeu en 3D classique à 10 FPS en pleine résolution sur Graph 90+E vous allez apprendre des choses sympa et vous amuser, si vous le voulez à 30 FPS vous allez suer, et si vous le voulez à 60 FPS vous allez échouer. En cas de doute, visez l'objectif modeste, ce sera plus fun.

Une autre idée utile, même si ça ça déborde un peu sur la gestion des projets de façon générale, c'est d'avoir une idée du temps qu'on veut y passer. C'est dur à estimer au début d'un projet (ça dépend à la fois des possibilités techniques et de votre expérience), mais après quelques heures de travail on sent en général si on s'attaque à un truc simple ou monstrueux, et on peut ajuster les ambitions en conséquence.

Identifier les parties du code qui ont besoin d'attention

On ne peut pas optimiser tout le code d'un programme à la fois, et de toute façon la plupart du code n'a pas besoin d'attention spécifique. Pour ménager le temps (et les nerfs), il est utile d'avoir une portée claire et raisonnable, ce qui nécessite de savoir ce qu'on veut optimiser et pourquoi on le fait.

Pour ça, il n'y a pas de meilleur outil que celui qui identifie quelle partie du programme consomme le plus de ressources.

Honnêtement, même avec toute l'expérience du monde, il n'y a pas de bonne raison d'optimiser des morceaux de programme avant d'avoir vérifié que c'est bien les morceaux qui prennent le plus du temps.

Dans un jeu par exemple, on prendra un soin considérable à mesurer le temps d'exécution du rendu de chaque frame, du traitement des entrées, et de la simulation physique ; à collecter des statistiques sur plusieurs frames pour observer les variations ; et à sous-diviser les parties qui prennent le plus de temps en mesures plus fines pour voir où se trouvent précisément les lenteurs.

De façon générale, si vous avez une partie qui prend un temps considérable par rapport aux autres, concentrez-vous dessus. Découpez la mesure en morceaux correspondant aux sous-fonctions de cette partie, et comparez les sous-mesures. S'il y en a une qui prend la majorité du temps, concentrez-vous dessus et oubliez les autres. Plus vous pouvez descendre bas comme ça et mieux vous serez, parce que ça veut dire qu'une petite partie du code prend une majorité du temps. Et on aime ça parce que plus la partie qu'on regarde est petite plus c'est facile à optimiser.

À l'inverse, si vous avez différentes parties indépendantes qui prennent toutes des temps similaires, vous aurez plus de mal à optimiser le programme parce que chaque transformation localisée n'affectera qu'une petite proportion du temps total.

Attention donc à optimiser avant d'avoir mesuré. Ça rejoint la célèbre maxime de Donald Knuth: "Premature optimization is the root of all evils" (l'optimisation prématurée est l'origine de tous les maux), qui avertit des problèmes qui attendent ceux qui programment un code «optimisé» avant d'avoir codé une version naïve. Notamment le risque de passer beaucoup d'efforts à pré-optimiser du code qui n'est pas du tout limitant, et le travail supplémentaire nécessaire pour gérer le code optimisé qui est souvent plus complexe que la version naïve (et donc plus facile à écrire de travers, buggé, etc).

Avoir une idée des ordres de grandeur

Dans les add-ins, beaucoup de choses peuvent être mesurées avec une grande précision. (On peut même mesurer le nombre exact de cycles processeur qu'une séquence d'instructions prend en la répétant un peu !) Par conséquent, on connaît des ordres de grandeur à toutes les échelles, et c'est très utile de voir comment les cycles presque-instantanés se transforment en microsecondes puis en millisecondes puis en secondes parfaitement tangibles pour les utilisateurs.

Voilà quelques ordres de grandeur classiques mais utiles à avoir en tête :

  • Un jeu qui tourne à 60 FPS dispose de 17 ms pour simuler et produire chaque frame.
  • Un jeu qui tourne à 30 FPS dispose de 33 ms pour simuler et produire chaque frame.
  • De façon générale le cerveau humain perçoit un effet d'instantanéité/fluidité quand la boucle de feedback entre l'action (par exemple la pression d'une touche) et le résultat (par exemple la mise à jour de l'écran) prend moins de 100 ms, et de préférence moins de 50 ms.
  • En général une seconde c'est la mesure de performance sur laquelle on définit un objectif (en FPS ou générations de simulation ou autre) ; une milliseconde c'est une partie du budget pour chaque frame/génération ; et une microseconde c'est 50-100 cycles d'horloge.

Voilà quelques ordres de grandeur pour les Graph mono :

  • Le processeur tourne à 58 MHz (Graph 35+E II) ou 29 MHz (autres modèles), donc il y a 58 ou 29 cycles par microseconde.
  • L'écran est aussi rapide que le proco, dupdate() prend environ 1 ms ou 2.5 ms (même distinction entre les modèles). On peut atteindre 400-500 FPS avec un peu d'effort, mais de toute façon l'écran ne s'actualise qu'à 64 Hz, donc ça ne sert à rien d'aller au-delà, il vaut mieux essayer d'être précisément synchronisé.
  • La VRAM fait 1024 octets et peut être couverte en 256 accès mémoire de 4 octets chacun, ce qui est très rapide.
  • Par conséquent, la puissance de calcul est souvent le principal limiteur, et l'overlock a beaucoup d'effet.
  • Il y a environ 96 ko de RAM très facilement accessible (un peu plus sur Graph 35+E II), et dans les 500 ko si on va chercher toutes les options y compris les plus casse-pieds.

La conclusion c'est que la Graph mono est une plateforme très chill en termes d'optimisation, sauf si on fait vraiment des choix défavorables (genre coller des nombres en point flottant partout). Je pense qu'on peut aisément écrire des jeux et atteindre le maximum absolu de 64 FPS sans jamais rien optimiser pourvu que ce soit fait dans les règles de l'art. La 3D est une exception évidemment (la 3D est toujours une exception).

Et voilà d'autres ordres de grandeur pour le modèle où l'optimisation est le plus souvent nécessaire, la Graph 90+E :

  • Le processeur tourne à 117 MHz (par défaut), donc il y a 117 cycles par microseconde.
  • dupdate() ou Bdisp_PutDisp_DD() prend 11.0 ms (!!).
  • La VRAM fait 177 ko et peut être couverte en 44'000 accès mémoire de 4 octets chacun, ce qui en plus d'être lent nécessite d'être mis dans la RAM principale, ce qui n'aide pas à accélérer les choses.
  • Modifier à la main tous les pixels (396×224) prend environ 6.1 ms.
  • Afficher une image depuis la ROM en plein écran dépend du format de l'image, plus l'image prend de la place en ROM plus c'est lent. Pour du 16-bit complet compter environ 25 ms, pour du 8-bit indexé 20 ms, pour du 4-bit indexé 15 ms.
  • Clairement le dessin est extrêmement limitant pour à peu près tout le monde, sauf les programmes vraiment orientés calcul genre les fractales de Mandelbrot ou automates cellulaires.
  • L'overclock a de l'effet mais moins que sur Graph mono parce que la RAM et l'écran ne sont pas overclockées autant que le processeur.
  • Il y a environ 1 Mo de RAM très facilement accessible, et dans les 1.5 Mo si on va chercher toutes les options y compris les plus casse-pieds. Là-dedans, il y a environ 20 ko de mémoire réellement rapide, plus 32 ko de cache de données (associatif !).
  • Pour la plupart des applications, 30 FPS c'est un objectif sérieux (et c'est fluide pourvu qu'il n'y ait pas de tearing), 60 FPS c'est inutilement dur/limitant, et plus de 90 FPS c'est purement impossible avec les méthodes d'affichage classique.

Imaginons par exemple que je veux coder un RPG en plein écran sur Graph 90+E. À chaque frame, je dois afficher la map, qui couvre tout l'écran, à partir d'un tileset. Je suis quelque part entre 6.1 ms et 15 ms, sachant que le tileset est plus petit en mémoire qu'une image plein écran ; disons 10 ms. À ça on ajoute 11 ms pour rafraîchir l'écran, ce qui donne un total de 21 ms. Je sais donc déjà, avant d'avoir touché le moindre code, que mon jeu ne dépassera pas un plafond absolu de 50 FPS sauf à faire des choses non-orthodoxes. Mettons que je vise 30 FPS avec 30 simulations par seconde, ça me laisse 12 ms pour faire tout le dessin hors map, la simulation physique, et les IA (entre autres). Et là on rentre immédiatement dans le vif du sujet (spoiler: si les ennemis font du pathfinding sur une map de 200x200 avec un algo tout nul ça ne passera pas x3).

Mesurer souvent et rigoureusement

J'ai une théorie que dans les problèmes techniques et compliqués on se perd beaucoup plus vite parce qu'on n'arrive pas à organiser et analyser ce qu'on fait que par la complexité réelle des problèmes.

Pour ce qui est de l'optimisation, la réponse à beaucoup de choses est de mesurer plus, plus souvent, et plus rigoureusement. Dans mon expérience si la réponse n'est pas là, alors c'est soit un bug dans le programme soit un comportement du matériel qui était inconnu jusque-là.

Les yeux ne sont pas un bon instrument de mesure pour déterminer si le programme va plus vite ou pas. La RTC c'est potable mais c'est pas précis. Je ne vois aucune excuse pour ne pas utiliser le TMU pour mesurer les performances, surtout qu'on peut le faire sur tous les SDK : fx-9860G SDK, PrizmSDK, fxSDK sans problèmes particuliers. Pour le dernier, il y a même une bibliothèque qui automatise tout ça, libprof.

Comme la paire fxSDK/gint est la plateforme la plus courante sur Planète Casio, voilà un résumé express du cas d'usage le plus trivial le plus trivial de libprof. Le header est <libprof.h>, on initialise avec prof_init() et on nettoie avec prof_quit() :

#include <libprof.h>

int main(void)
{
    prof_init();
    /* .... */
    prof_quit();
    return 0;
}

Et pour savoir combien de temps un bout de code prend, prof_exec() :

uint32_t temps_rendu = prof_exec({
    dclear(C_WHITE);
    dimage(player_x, player_y, &image_player);
    dupdate();
});

temps_rendu; // = 2145 µs (exemple fictif)

Croyez-moi, vous ne regretterez jamais d'avoir codé ça en 3 minutes et d'avoir soudain des vrais chiffres à améliorer sur votre projet. De façon générale, vous ne regretterez pas de programmer les mesures du temps d'exécution dans votre programme parce que c'est à la fois très rapide à coder et extrêmement utile.

Je détaillerai les possibilités de mesure et de visualisation dans une autre technique, mais ça vous donne un avant-goût.

Quand vous envisagez d'optimiser quelque chose, prenez vraiment 30 minutes pour mesurer dans le détail ce qui prend du temps. Non seulement ça vous guidera pour optimiser les parties utiles, mais en plus ça vous aidera à former une intuition de ce qui peut poser des problèmes de performance et pourquoi.

Une fois que vous avez identifié le problème et la solution à atteindre, continuez de mesurer votre nouveau code à différentes étapes pour vérifier que la solution se conforme à vos attentes. On peut assez facilement avoir des surprises, et à la fin c'est toujours les chiffres qui ont raison.

Conclusion

Avoir les bonnes compétences et la bonne expérience technique permet certainement de rendre des programmes beaucoup plus rapides, mais avoir la bonne méthodologie permet de le faire avec beaucoup moins d'efforts de développement. Ne négligez pas d'y revenir de temps en temps, je promets que vous ne le regretterez pas.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Dark storm Hors ligne Labélisateur Points: 11634 Défis: 176 Message

Citer : Posté le 20/07/2021 20:56 | #


Excellent tout ça !

Je me permets de faire un petit aparté sur la complexité des algorithmes (#183646). Je ne garantis pas tout de suite l'exactitude de ce que je raconte, je mettrais à jour si il y a des trucs à corriger.

Problèmes NP-complets et solutions approximatives

Comme expliqué par Lephe, la grande majorité des problèmes auxquels vous allez être confrontés ont déjà été théorisés. Le tout étant de trouver quel(s) algorithme(s) connu(s) correspond(ent) au-dit problème . Si je prends l'exemple des tris, un tri bulle en O(n²) sera bien évidemment moins efficace dans le cas général qu'un tri rapide en O(n⋅log n). Donc si je compte trier la distance à la caméra d'un nuage de points de quelques centaines voire milliers d'éléments, j'ai tout intérêt à utiliser le meilleur algorithme à disposition.

Là où est l'os, c'est que tous les problèmes n'ont pas forcément un algorithme exact efficace. Si l'on prend par exemple le problème du voyageur de commerce, il faut nécessairement (n-1)!/2 opérations pour trouver la solution exacte. On est sur une complexité de O(n!). Pour rappel, la factorielle est une fonction qui croit très rapidement. Si 10! = 3 628 800, 100! ≈ 10¹⁵⁷. Autant dire qu'il n'est pas envisageable de résoudre exactement le problème pour une liste de villes qui dépasse la douzaine.

Dans ce cas il ne faut pas chercher à résoudre exactement le problème, mais trouver une solution suffisante. Un algorithme qui donne une solution approximative en un temps très court sera très probablement plus intéressant à utiliser que l'algorithme exact, qui en pratique sera inutilisable parce que vous n'allez pas attendre (littéralement) quelques milliers d'années qu'il vous retourne la solution.

Ces problèmes sont dit NP-complets. C'est à dire qu'on ne sait pas trouver la solution exacte en temps polynomial, que ce soit O(n²), O(n⁴) ou même O(n⁴⁹²⁷). Pour être très précis, NP signifie que l'on sait vérifier une solution en temps polynomial et complet veut dire que c'est le problème le plus difficile de sa classe (ie, de même complexité).

Bref, revenons à nos moutons, concrets. Je vais digresser un peu et prendre un exemple moins subtil mais beaucoup plus parlant, celui de la recherche d'un chemin dans un graphe. En anglais on parle de pathfinding. Il existe beaucoup d'algorithmes différents, mais je m'attarderais sur deux en particulier. Si l'algorithme de Dijkstra est exact, il est beaucoup moins rapide que l'A* (prononcez A-star), qui lui est bien, mais sans garantie que le résultat soit le meilleur possible.

Il est évident que choisir celui qui est le plus adapté sera primordial. Pour une IA qui ne laisse aucune chance au joueur, Dijkstra sera sûrement un bon choix, alors que A* sera sûrement préférable pour guider une horde de 143 zombies qui se dirigent vers le joueur à tout allure. On se fiche probablement que les zombies prennent exactement le meilleur chemin. Si ils prennent un chemin qui va vers le joueur, si possible sans faire le tour de la carte, ce sera déjà très bien.

La conclusion à cet addendum est que vous pouvez très bien, pour un problème donné, choisir d'utiliser une solution approximative : elle sera très probablement beaucoup plus rapide à calculer que la solution exacte. Dans certains cas, cela peut vous permettre de gagner quelques précieux FPS au détriment de la non-garantie d'être parfait. Comme d'habitude, l'optimisation est un jeu d'équilibre et de compromis.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 20/07/2021 21:05 | #


Merci ! C'est tout à fait exact, les algorithmes d'approximation sont très utiles. Quand ils sont formalisés en général on a une garantie, qui ressemble à «cet algorithme calcule un chemin qui est au plus 2 fois plus long que le chemin le plus court». Mais même quand ils ne sont pas formalisés et qu'il n'y a pas de garantie ça peut être très utile.

Deux petites corrections :
  • NP ⊆ EXPTIME donc le voyageur de commerce a des solutions en temps exponentiel, qui même si pas rapide, reste bien plus rapide que Θ(n!).
  • Tous les problèmes difficiles ne sont pas NP-complets ; il y en a des (beaucoup) plus difficiles, par exemple TQBF qui est PSPACE-complet (même si techniquement pas prouvé hors de NP), ou décider si une machine de Turing s'arrête en moins de k étapes, qui est EXPTIME-complet. Certains comme le problème de l'arrêt sont carrément indécidables, et il y en a d'autres qui sont «encore plus indécidables».
  • Mais c'est vrai que la plupart des problèmes de tous les jours sont dans NP donc les pires sont NP-complets.

Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Dark storm Hors ligne Labélisateur Points: 11634 Défis: 176 Message

Citer : Posté le 20/07/2021 21:42 | #


J'en profite pour caler ici un exemple concret, le Sprite Optimizer. Les lignes à dessiner que calcule l'outil ne sont pas forcément les plus optimales, mais dans la majorité des cas la solution est suffisante pour le but recherché.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 20/07/2021 21:47 | #


Très bon exemple ! Soit dit en passant je n'avais pas réussi à trouver de preuve directe que le problème dans le cas du Super DrawStat (où le lever de crayon a un coût) est NP-complet, mais je serais pas surpris qu'il le soit.

Le problème dans le cas de Multi DrawStat est un cas particulier de Set Cover, qui est NP-complet... mais qui a une approximation polynomiale qui donne un nombre de lignes au plus ln(n)+1 fois l'optimal (où n est le nombre d'ensembles). Les notions se retrouvent comme tu peux le voir
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 20/07/2021 22:24 | #


Exploiter efficacement les caches (Programmation générale — ★☆☆)

Parmi les mémoires rapides du SH4AL-DSP (celui de la calculatrice en tous cas) auxquelles on peut accéder en un cycle, on a 8 ko de mémoire X, 8 ko de mémoire Y, 4 ko de mémoire IL, et un peu de mémoire RS qui est utilisée par l'OS pour des choses très importantes et à laquelle on ne touche donc pas en général. (X, Y, IL et RS sont juste les noms de ces mémoires, pas des «types» différents.)

Ce total est assez faible et même plus faible que la taille du cache : 32 ko pour le cache d'opérandes (et 32 ko aussi pour le cache d'instructions, mais ça c'est moins important en général). Ça veut dire qu'utiliser correctement le cache peut maximiser le nombre d'accès à un cycle (ou presque) pour des données de jusqu'à 32 ko dans la RAM principale, quand tout va pour le mieux.

Fonctionnement d'un cache simple

Le cache est un composant invisible pour le programme. Il sert d'intermédiaire durant tous les accès entre le CPU et la RAM, et accélère les accès quand c'est possible, mais n'affecte pas le comportement du programme.

Il faut bien voir qu'on ne peut pas contrôler ce qu'il y a dans le cache. Les contenus sont gérés automatiquement par un algorithme de remplacement, et même si on peut tout à fait faire des accès mémoire de façon à charger certaines données qu'on vise dans le cache, on ne peut pas écrire dans le cache comme on écrit dans les mémoires internes (X, Y, IL par exemple).

L'algorithme en question est assez simple :
  • Au début, le cache est vide.
  • Lors d'un accès en lecture, si les données sont dans le cache, il les renvoie. Sinon il charge les données de la RAM vers le cache et ensuite les renvoie. (Le cache note les données mais aussi leur adresse en RAM pour les retrouver plus tard.)
  • Lors d'un accès en écriture c'est à peu près pareil, mais il y a un paramètre pour choisir si on écrit immédiatement dans la RAM (write-through) ou uniquement dans le cache (copy-back). J'y reviendrai.
  • Quand on charge des données de la RAM vers le cache, s'il y a un emplacement libre «compatible» pour ces données elle est utilisée, sinon l'emplacement «compatible» qui est resté inutilisé le plus longtemps est expulsé et ses contenus sont recopiés dans la RAM.

Vous noterez que les données que vous demandez ne sont chargées qu'à un emplacement «compatible». La raison pour ça est simple : si le cache fait 8 ko et que vous demandez une adresse spécifique, le cache ne peut pas comparer toutes les 8000 adresses à la votre pour savoir s'il a les données. Il doit répondre en un cycle ! (Le choix de 8 ko comme exemple est important ; le cache réel de 32 ko est un peu différent, j'en parle dans la section suivante.)

Ce problème est éliminé de deux façons. D'abord les données ne sont pas chargées par octets mais par blocs qu'on appelle des lignes de cache. Sur le SH4AL-DSP, les lignes de cache font 32 octets, et alignées à des adresses multiples de 32. Par exemple (en supposant que les adresses dans la RAM commencent à 0 pour simplifier), 0x40-0x5f c'est une ligne de cache. Si vous accéder à l'adresse 0x54, le cache va charger toute la ligne 0x40-0x5f. Si vous accédez ensuite à 0x64, le cache va charger la ligne suivante 0x60-0x7f même si les deux adresses concernées sont distantes de moins de 32 octets.

Cela dit, quand vous demandez à accéder à une adresse, le cache de 8 ko ne peut pas faire 256 comparaisons pour savoir si la ligne est chargée, c'est toujours trop long. Donc en fait le cache est agencé pour que chaque ligne ne puisse être chargé qu'à un seul emplacement, à partir des bits de l'adresse.

Voilà comment ça se passe : dans une adresse de ligne de 32 bits, les 5 bits du bas sont forcément à 0 parce que l'adresse est multiple de 32. Les 8 bits suivants indiquent lequel des 256 emplacements peut contenir la ligne.

0x08103a40 = 0000 1000 0001 0000 001[1 1100 010][0 0000] → emplacement 1110 0010 = 226

Ça c'est très pratique pour le cache parce que quand vous demandez d'accéder à une adresse dans la RAM, il efface les 5 bits du bas pour trouver l'adresse de la ligne, il extrait les 8 bits suivants pour obtenir le numéro de l'emplacement, et ensuite il regarde si cet emplacement contient ou non la donnée que vous demandez. Si oui, il la renvoie. S'il est vide, il charge la donnée par un accès à la RAM. Sinon, il expulse la donnée présente et la remplace par la donnée que vous demandez par un accès à la RAM.

Vous noterez par conséquent que si vous accédez à 0x08103a40 puis à 0x08105a40, il y a une collision et donc l'accès à la deuxième ligne expulse la première ligne du cache, même si le cache est absolument vide partout ailleurs !!

Un cache simple de ce type est donc approprié pour charger un gros bloc continu, mais très mauvais si on accède à plusieurs zones à la fois parce que les collisions sont très difficiles à éviter. Le seul moyen de s'assurer que les adresses qu'on utilise n'ont pas de collisions, c'est d'avoir un seul bloc continu. (Cela dit, très souvent on utilise toujours la pile et la région des variables globales en même temps que les gros buffers de données, ce qui rend ce travail difficile.)

Les caches associatifs

Le cache associatif mitige les problèmes du cache simple en ajoutant plusieurs «voies». Essentiellement chaque voie est une copie du cache simple que j'ai présenté plus haut. Dans le SH4AL-DSP, il y a 4 voies de faisant chacune 8 ko (256 lignes de 32 octets), pour un total de 32 ko.

Avoir 4 voies signifie que chaque ligne de RAM peut maintenant être chargée à 4 emplacements différents. Ça donne aussi au cache 4 comparaisons à faire à chaque accès mémoire, mais ça reste assez raisonnable pour tenir en un cycle.

Avoir plusieurs voies donne aussi le choix de quel emplacement expulser quand aucun n'est libre pour charger une nouvelle ligne dans le cache. L'algorithme optimal, bien sûr, c'est d'expulser la ligne qui sera nécessaire la plus tard dans le futur. Mais ça, le proco ne le connaît pas. À la place, il expulse celle qui est restée inutilisée le plus longtemps possible. Cet algorithme s'appelle LRU (least recently used) et on peut prouver qu'il est pas mal par rapport à l'optimal.

Avec ça, vous pouvez comprendre quasiment tous les éléments dans la description des caches dans la documentation du SH4AL-DSP :


Accès favorables au cache et prefetching

Le cache associatif à 4 voies résout en partie le problème des collisions entre les accès au sujet du programme (par exemple un buffer de données de calcul ou de données graphiques) et les accès à des objets plus ou moins aléatoires comme la pile ou le segment de données.

Par exemple, dans la mesure où la pile est assez locale et occupe généralement une seule voie, vous pouvez accéder sans problème à un buffer de 8, 16 ou 24 ko puisque qu'il y aura assez de voies pour couvrir le buffer entier en plus des quelques accès à la pile.

Cependant, l'histoire ne s'arrête pas là. Si vous faites simplement une lecture ou une écriture linéaire du buffer, vous n'allez pas gagner énormément de temps. La raison c'est qu'à chaque fois que vous allez changer de ligne, le premier accès paiera le tarif complet d'un aller-retour vers la RAM pour charger la ligne, et ensuite seuls 7 accès (en supposant que tous les accès font 4 octets) seront réellement accélérés.

Pour cette raison, le cache dispose d'une opération dite de pré-chargement (prefetch). Le principe est d'indiquer à l'avance qu'on prépare un accès à une ligne, comme ça le cache charge la ligne pendant qu'on fait autre chose et au moment ou l'accès annoncé se présente tout est déjà dans le cache.

Le prefetching ne fait pas de la magie, surtout dans le cas d'une lecture linéaire, parce qu'il me semble que charger une ligne de cache prend plus de 8 cycles de toute façon donc même en saturant la RAM on ne peut pas lire un buffer de 8 ko en entier en un cycle par accès. Mais si on reste plus longtemps sur chaque ligne ça peut être assez utile.

Pour ce qui est des écritures, il y a deux modes : write-through (WT) où les écritures sont systématiquement faites dans la RAM ; et copy-back (CB) où les écritures sont faites uniquement dans le cache et le résultat est sauvegardé dans la RAM quand la ligne est expulsée (ce qu'on peut demander à la main avec une instruction dédiée).

Pour les performances, copy-back est bien évidemment mieux. Mais ça pose le problème que les données ne sont pas réellement écrites dans la RAM, donc si quelqu'un va lire la RAM sans passer par le cache il aura un résultat pas à jour. Et si vous regardez la cartographie des bus du processeur, vous pouvez identifier des accès de ce type ; par exemple le DMA ignore le cache, donc une écriture dans la RAM sur une page en copy-back qui est toujours dans le cache est invisible pour le DMA. Ce problème dit de cohérence des mémoires est une des raisons pour laquelle les caches sont un sujet compliqué ; nous on n'a qu'un cache donc c'est raisonnablement simple, mais dans les processeurs multi-coeurs ça peut vite devenir un enfer.

Avec ça, je pense avoir fait le tour des éléments importants. Je ne vous donne pas ici de recette pour utiliser le cache efficacement, à part utiliser des buffers pas trop gros de façon très linéaire, parce que je n'en connais pas. Mais au moins vous devriez avoir toutes les informations pour étudier l'usage du cache au cas-par-cas dans vos programmes.

Dans l'ensemble, bien utiliser le cache dans un programme est relativement compliqué et demande pas mal d'attention aux détails. Personnellement, je préfère utiliser en priorité les mémoires rapides (X, Y, IL) et utiliser le cache en dernier ressort.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 14/10/2021 14:23 | #


Juste un message rapide pour signaler que je suis toujours sur ce topic. Prochaine technique, les structures de données
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 14/10/2021 17:31 | #


Structures de données (Algorithmique — ★★☆)

Lecture complémentaire utile : tutoriel sur les structures de données de Louloux

La notion de «structure de donnée» s'intéresse à la façon dont les données sont organisées dans un programme. Avoir une bonne organisation permet d'accéder aux bonnes informations rapidement, et ainsi peut aider dramatiquement les performances.

Dans certains programmes, le choix d'une structure de données intelligente est l'élément majeur autour duquel toutes les performances tournent. Par exemple, dans le premier DOOM une structure de données bien choisie appelée "binary space partition" est au centre des performances du moteur 3D (en plus de la forme bien choisie des murs verticaux).

Les structures de données ont toutes le même aspect extérieur ; elles ont chacune :

  • Un certain modèle de données (séquence ; ensemble ; dictionnaire ; pile ; file de priorité ; ...).
  • Une certaine façon de stocker les données dans la mémoire.
  • Des algorithmes pour accéder aux données.
  • Et souvent des algorithmes pour modifier les données.

Ce qui change c'est la complexité de chaque opération. Par exemple, un tableau et une liste chaînée sont deux structures de données permettant de représenter des séquences. Avec un tableau, on peut accéder immédiatement à n'importe quel élément, mais si on veut en insérer ou supprimer ça prend un temps très long. Avec une liste chaînée, accéder à un élément quelconque prend beaucoup de temps, mais les insertions et suppressions sont immédiates. Selon les besoins du programme, on choisira l'une ou l'autre pour utiliser le plus possible des opérations rapides.

Cette technique donne un tour d'horizon des modèles de données classiques et de quelques structures de données classiques, et fait partie de la boîte à outils des algorithmiciens. Les programmeurs n'ont pas besoin de toute connaître, mais certaines structures sont vraiment fondamentales et sont détaillées ici. Pour d'autres, je renvoie vers les articles techniques de Wikipédia pour l'implémentation ; le plus important est de savoir qu'elles existent (et idéalement, quand les utiliser).

Pour toutes les structures, on note n le nombre d'éléments (la taille/longueur) de la structure. La durée que prend chaque opération est une complexité exprimée en fonction de n ; comme souvent, on voit savoir si les opérations prennent longtemps quand la structure de données devient grande. Si cette idée est nouvelle pour vous, je vous invite à lire la technique Introduction à la complexité. J'utiliserai la notation O().

Séquences (ordonnées)

Une séquence (ou séquence ordonnée) est un modèle de données très simple. C'est juste une liste d'éléments stockés dans un certain ordre. Il y a un premier élément, un second, un troisième... et ainsi de suite jusqu'au dernier. Les éléments peuvent avoir n'importe quelle valeur.

Dans une séquence, on s'intéresse principalement aux opérations suivantes :
  • Accéder à un élément par son numéro (sa position) ;
  • Accéder aux éléments qui précédent, suivent, etc. ;
  • Insérer ou supprimer des éléments au début, au milieu ou à la fin de la séquence.

Les deux structures de données les plus classiques pour stocker des séquences sont les tableaux et les listes chaînées.

Tableaux (arrays)

Dans un tableau, tous les éléments sont écrits les uns à la suite des autres dans la mémoire. Si vous n'êtes pas familier·ère avec la mémoire, consultez le Tutoriel du Mercredi #19 pour les détails. Essentiellement, la mémoire est une très longue liste d'emplacements numérotés, et on peut lire ou modifier la donnée de n'importe quel emplacement à partir de son numéro (adresse) en temps constant.

Le principe du tableau est très similaire. Le premier élément est à une certaine adresse p, le second est à l'adresse p+1, le troisième à p+2, et le dernier à p+n-1 (où n est la longueur de la séquence). De cette façon, il suffit de connaître p pour pouvoir accéder à n'importe quel élément (par le biais d'une addition et d'un accès mémoire).

En C, c'est exactement ce qu'il se passe. Dans l'exemple ci-dessous, je crée un tableau array de 16 caractères. L'adresse du premier caractère est p, celle du second est p+1, et ainsi de suite.

char array[16];
&array[0]; // = une certaine adresse p
&array[1]; // = p+1
&array[2]; // = p+2
...
&array[15]; // = p+15

Si vous écrivez array tout seul c'est pareil que &array[0] ; vous obtenez p. (Les lecteurs les plus avisés ne seront donc pas surpris de savoir que array[i] est défini comme *(array+i), ce qui permet d'écrire de façon curieuse, mais parfaitement valide, i[array] au lieu de array[i].)

Comme mentionné précédemment, chaque accès à un tableau prend un temps constant, c'est-à-dire que ça prend toujours la même durée peu importe la taille du tableau ; on écrit O(1). C'est parfait parce qu'on ne peut pas faire plus rapide que ça, si on pouvait on aimerait bien avoir toutes les opérations en O(1) (spoiler : on ne peut pas, mais c'est beau de rêver !).

Pour les insertions et suppressions, c'est plus difficile. Un tableau ne peut pas avoir de vides, donc si on retire un élément tous les éléments qui suivent doivent être décalés pour combler le vide. De même, si on veut insérer un élément il faut d'abord décaler tous les éléments qui suivent pour faire de la place.


Cet effet est pire quand on modifie près du début de tableau ; dans ce cas, le nombre d'éléments à déplacer est proche de n et donc la complexité est O(n).

Pour résumer la complexité du tableau :
Accès à un élément par son numéro : O(1)
Insertion et suppression : O(n)

Vous remarquerez donc que les tableaux sont pratiques quand les données ont une taille fixe (ou un taille maximale), mais plus difficiles à utiliser quand les données changent beaucoup de taille ou les éléments de position. En plus redimensionner un tableau en C pose aussi quelques difficultés.

Listes chaînées (linked lists)

Dans une liste chaînée, tous les élément sont séparés dans la mémoire, et on les relie par des chaînes de pointeurs, chaque élément pointant vers son successeur pour former la séquence. Cette fois-ci, il n'y a pas de relations entre les adresses, donc pas moyen de savoir rapidement où est chaque élément, la seule option est de partir du début et de suivre la chaîne.


En C, ça se passe avec une structure qui contient un pointeur (souvent appelé «next») vers l'élément suivant, comme ceci :

struct node {
    int value; // tout ce qu'on veut comme données
    struct node *next;
};

Ce qu'on perd en organisation mémoire du fait que les éléments sont séparés, on le gagne en flexibilité pour organiser la liste, parce que maintenant on peut faire et défaire des liens à loisir. Par exemple, pour supprimer un élément, il suffit que son prédécesseur le snobe et se mette à pointer vers son successeur (comme illustré ci-dessous). De la même façon, pour insérer un nouvel élément il suffit de modifier le lien du prédécesseur.


Ces opérations très efficaces sont particulièrement utiles quand on veut toujours modifier au même endroit (par exemple une pile ne modifie que le premier élément).

Il y a pas mal de variantes, dont la liste doublement chaînée, qui est similaire mais où chaque élément a deux pointeurs : un vers son successeur et un vers son prédécesseur. Ça permet de parcourir la liste dans les deux sens (parce qu'avec une liste simplement chaînée impossible de trouver le prédécesseur d'un élément !).

Pour résumer la complexité de la liste chaînée :
Accès à un élément par sa position : O(n)
Insertion et suppression à un endroit connu : O(1)


Piles et files

Piles (stacks)

Une pile est un type de séquence spécial qui ne possède que trois opérations :
  • Ajouter un élément au sommet de la pile ;
  • Retirer l'élément qui est au somemt de la pile (optionnellement, le regarder sans le retirer).


On dit aussi «FILO» pour "First In, Last Out" puisque le premier élément ajouté à la pile est le dernier élément supprimé. Ces restrictions signifient qu'on peut faire moins de choses avec une pile qu'avec une séquence, mais en échange on peut mieux optimiser une pile.

Par exemple, si on fait une pile avec une liste chaînée, toutes les opérations sont en temps constant puisqu'il suffit de modifier les liens des premiers éléments pour en ajouter et en supprimer.
Accès, empilement et dépilement : O(1)

Le plus souvent on utilise une pile pour garder la trace d'un traitement en cours, par exemple l'exécution d'une fonction. Chaque élément de la pile est un traitement (une fonction en train de tourner), et chaque empilement représente le début d'un sous-traitement (par exemple l'appel d'une sous-fonction). La clé pour que ça marche c'est que la sous-fonction doit se terminer en premier (avant la fonction qui l'a appelée), ce qui garantit qu'on retire toujours l'élément au somment de la pile.

C'est d'ailleurs sur une pile que sont stockées les informations sur les appels de fonctions en cours dans un programme (en particulier les variables locales)

Files (queues)

Une file est aussi un type de séquence spécial, où on ajoute et retire à deux bouts différents. Les opérations sont :
  • Ajouter un élément à la fin de la file ;
  • Retirer l'élément au début de la file (optionnellement, le regarder sans le retirer).

C'est littéralement une file d'attente. On dit aussi «FIFO» pour "First In, First Out" puisque le premier élément qui entre est aussi le premier qui sort.


Il y a plusieurs façons de programmer une file (pour être précis : il y a plusieurs structures de données qui ont ce modèle), le plus évident étant une liste doublement chaînée. On peut aussi utiliser deux listes simplement chaînées (une pour les arrivées, une pour les départs), un tableau circulaire (quand la taille est limitée), et bien d'autres méthodes...

Là aussi les attentes c'est que les opérations sont en temps constant.
Accès, enfilement et défilement : O(1)

Il y a là aussi plein de situations où une file est utile, mais c'est assez intuitif parce que tout le monde s'imagine bien une file d'attente. Essentiellement une file est utile si vous voulez traiter les tâches dans le même ordre que vous les découvrez ; la file sert juste à vous souvenir des tâches en attente entre leur découverte et leur traitement.


Arbres

Il y a beaucoup de choses à dire sur les arbres, bien trop pour tenir dans une seule section. Les arbres font partie des structures de données les plus polyvalentes, avec des centaines de variations qui font des choses différentes.

Fondamentalement, un arbre fonctionne comme un liste chaînée : les éléments sont séparés et reliés par des pointeurs. Mais chaque élément peut avoir plusieurs voisins, et ils sont hiérarchisés.


Ici j'ai représenté un arbre avec sa racine A, dont les enfants sont B et C ; chacun d'eux a encore des enfants, D, E et F. Certains noeuds (éléments) ont deux enfants, d'autres en ont un seul, d'autres n'en ont pas du tout (ceux-là on les appelle des feuilles). Par contre chaque élément n'a qu'un parent, c'est le plus important.

Usuellement, soit les noeuds de l'arbre soit les feuilles contiennent les élément de la structure. Un arbre peut représenter une séquence (par exemple en lisant chaque étage de gauche à droite : A B C D E F G H, ou en lisant chaque sous-arbre dans l'ordre : A B D G H E C F), une file de priorité (voir la mention des tas vers la fin), des ensembles ou des dictionnaires (voir la section suivante), et bien d'autres données utiles.

La force d'un arbre c'est que comme il est hiérarchisé on peut le parcourir de haut en bas très vite. L'arbre d'exemple ci-dessus a une hauteur de 4 même s'il contient 8 éléments. Les valeurs sont souvent arrangées de sorte que les accès ou modifications des données ne nécessitent que des allers-retours de haut en bas sans consulter tous les éléments, ce qui est un gain très important.

Je n'ai pas la place de rentrer dans tous les détails, mais je peux montrer au moins un exemple. Un cas très classique d'arbre est un arbre binaire, où chaque noeud a soit 2 enfants soit pas d'enfants du tout. On aime bien les arbres binaires quand ils sont complets, c'est-à-dire que toutes les feuilles sont au même niveau. Vous pouvez en voir un exemple ci-dessous ; le fait que l'arbre est complet se voit au « fond plat ».


Les arbres de cette forme sont extrêmement utiles parce que quand la hauteur est n le nombre de noeuds est environ 2^n. Mis dans l'autre sens, ça veut dire que si on a 2^n éléments à manipuler et qu'on peut les organiser dans un arbre binaire complet, ça donne un arbre de hauteur n. Les opérations qui se font uniquement dans la hauteur sont donc extrêmenent rapides ! Pour donner quelques ordre de grandeur : 1000 éléments = 10 étages ; 1 million d'éléments = 20 étages ; 1 milliard d'éléments = 30 étages. 30 étages c'est rien !

Arbres de recherche équilibrés (self-balancing search trees)

Et il se trouve qu'il y a une situation particulière dans laquelle on peut utiliser un arbre binaire complet : pour représenter une séquence triée de valeurs. L'idée est relativement facile : dans chaque noeud vous avez une valeur, avec la contrainte suivante : tous les noeuds dans l'enfant gauche ont des valeurs plus petites, et tous les noeuds dans l'enfant droit ont des valeurs plus grandes. On appelle ça un arbre de recherche, et mon dernier exemple ci-dessus en est un (la séquence étant 11 13 15 17 22 24 28).

On peut voir ensemble pourquoi cette structure est si utile. Imaginons que je veux déterminer si 25 est dans la séquence. Rien qu'en regardant la première valeur 17, je sais que si 25 existe alors il est dans la partie droite de l'arbre, et donc j'ai éliminé d'un coup la moitié des éléments de ma recherche. Je peux ensuite recommencer avec l'enfant droit, voir 24, et de nouveau éliminer un des deux enfants entièrement. Le résultat c'est qu'à chaque étage de l'arbre il suffit de regarder une seule valeur, et donc le temps de recherche dépend de la hauteur de l'arbre et plus du nombre d'éléments.

On a vu tout à l'heure que pour 2^n éléments la hauteur est n, ce qui nous donne une complexité en O(log n).
Recherche d'éléments : O(log n)
Insertion et suppression : O(log n)

Je ne rentre pas non plus dans les détails, mais on peut ajouter ou retirer des éléments sans casser la contrainte sur les valeurs. Les méthodes les plus classiques pour faire ça donnent les arbres rouge-noir et les arbres AVL.


Ensembles et dictionnaires

Un ensemble (set) est un groupe de valeurs sans ordre particulier. Par exemple, en Python :

a_set = { 78, 35, 44, -3, 21}

Les opérations sur un ensemble sont :
  • Tester si une valeur est présente dans l'ensemble ;
  • Ajouter ou retirer des valeurs.

En général on arrive à se débrouiller pour trouver un moyen de comparer les valeurs, ce qui permet de représenter l'ensemble comme une séquence triée de valeurs, et de l'implémenter avec un arbre de recherche. De cette façon toutes les opérations ont une complexité O(log n), ce qui est très effiace (c'est quasiment O(1) en pratique).

Un dictionnaire (dictionary, map, associative array...) est un groupe d'associations entre une clé et une valeur. Vous les connaissez sans doute mieux en Python :

couleurs = {
  "rouge": (255,0,0),
  "vert":  (0,255,0),
  "bleu":  (0,0,255),
}

Les opérations sur un dictionnaire permettent de maintenir et modifier ces associations :
  • Tester si une clé est présente ;
  • Si une clé est présente, obtenir la valeur associée ;
  • Ajouter ou supprimer des associations.

Là encore, on arrive à se débrouiller pour trouver un moyen de comparer les clés, et donc le dictionnaire devient essentiellement un ensemble de clés... et on l'implémente avec un arbre de recherche (en notant à la fois les clés et les valeurs dans les noeuds). De cette façon les opérations sont aussi toutes en O(log n), ce qui est très impressionnant pour une structure « complexe » comme celle-ci.

Les dictionnaires sont aussi appelés maps dans un certain nombre de langages, puisque map signifie (entre autres) associer en anglais.


Autres structures dignes d'intérêt

Si vous avez encore des neurones vivants, vous trouverez de quoi les occuper avec les quelques structures suivantes. :P

Une file de priorité est une file dans laquelle les éléments ont une priorité et peuvent donc prendre la place des éléments précédents. C'est très utile pour organiser des tâches à accomplir. En pratique ce n'est pas du tout codé comme une file, mais plutôt avec un tas.

Un tas donc, justement, est un arbre où on stocke des valeurs auxquelles on veut accéder dans un ordre croissant. La valeur la plus faible est au sommet de l'arbre, avec la contrainte que tout noeud doit avoir une valeur plus petite que ses enfants. Les données sont donc assez ordonnées pour qu'on puisse les tirer dans l'ordre croissant, mais assez peu ordonnées pour qu'on puisse en ajouter et retirer facilement. Ça donne d'ailleurs une méthode de tri très naturelle, le tri par tas.

Un graphe est une structure de données où les éléments, les noeuds, sont reliés entre eux par des arêtes. Contrairement à un arbre il n'y a pas de hiérarchie, de parents ou d'enfants, tous les noeuds sont en vrac. Les graphes permettent classiquement de représenter des réseaux (de routes, de personnes...) mais aussi une myriade d'autres problèmes (par exemple les dépendances de tâches parallèles, pour en citer un au hasard), et donnent lieu à un pan entier de l'informatique appelé la théorie des graphes qui est assez vaste pour y passer une carrière entière.

Une table de hachage est un objet fascinant qui fait appel à de la magie noire mathématique (souvent aléatoire) pour faire des ensembles et dictionnaires avec des opérations en temps constant. Le principe est relativement facile à comprendre mais c'est très difficile à manipuler rigoureusement.

Les multi-ensembles (page en anglais) sont des ensembles où une même valeur peut apparaître plusieurs fois ; de la même façon, les multi-dictionnaires (page en anglais) sont des dictionnaires où une même clé peut être utilisée plusieurs fois.

Un quadtree est un type d'arbre très amusant qui permet de partitionner les cartes 2D dans les jeux vidéo pour avoir des cartes très grandes sans prendre des gros coûts en performances. (En 3D il y a aussi les octrees).

Et bien sûr, il serait criminel de ne pas terminer sur la partition binaire de l'espace (BSP) utilisée dans DOOM et qui servait d'introduction à cette technique.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 18/10/2021 16:29 | #


La cartographie du SH4AL-DSP et du SH7305 (Bas niveau — ★★☆)

Le but de cette technique est d'établir une carte des outils de calculs et régions de mémoire du SH4AL-DSP (le processeur) et SH7305 (le MPU entier). La mémoire est la considération principale en termes d'optimisation ici, mais il faut aussi prendre en compte qui y accède. Dans la technique Accès aux mémoires, bus, et compromis taille/vitesse, j'ai présenté le diagramme à blocs du SH-4A où on peut voir la hiérarchie des bus et les différents chemins d'accès aux mémoires.

Dans cette technique, on va détailler la carte de l'espace virtuelle avec les propriétés de chaque zone, les régions qui permettent d'accéder aux mémoires, et les modules matériels impliqués dans leur utilisation. C'est un mélange entre le document listant les régions sur la bible et une amélioration de la partie du TDM 19 sur la mémoire virtuelle.

L'espace d'adressage physique

Le SH7305 a deux espaces d'adressage : l'espace physique dont les adresses font 29 bits et est minimalement configurable au niveau matériel pour gérer différents types de puces RAM/ROM, et l'espace virtuel dont les adresses font 32 bits et qui peut être configuré logiciellement à loisir pour agencer les mémoires de toutes les façons utiles (ce qui dans l'OS de CASIO sert presque uniquement à lancer des add-ins).

Il est facile de confondre les deux, parce qu'il y a deux parties non-configurables de l'espace virtuel qui sont en bijection avec l'espace physique, et dans plusieurs cas (comme avec le DMA) on passe tantôt des adresses physiques, tantôt des adresses virtuelles.

L'espace physique, adressé de 0x00000000 à 0x1fffffff, est principalement géré par le Bus State Controller (BSC) qui le divise en régions. Le BSC est responsable des échanges avec les puces de RAM/ROM qui sont à l'extérieur du MPU, selon plusieurs standards : Burst ROM synchrone et asynchrone, SRAM, DRAM, etc. Il découple l'espace physique en plusieurs régions numérotées de Area 0 à Area 7, chacune ayant ses propres contraintes de protocole, taille, et configuration. (Pour plus de détails, voir la documentation du SH7724, §14.3 - le BSC du SH7305 est peut-être différent mais les concepts sont les mêmes).

Pour nous, il n'y a pas grand-chose à savoir, à part que :
  • 0x00000000 (Area 0) contient la ROM, sur tous les modèles de Graph.
  • 0x08000000 contient la RAM sur tous les modèles de Graph sauf la Graph 90+E.
  • 0x0c000000 contient la RAM sur Graph 90+E.
  • Area 7 contient des registres périphériques du SH7305.

Le CPU ne peut pas accéder à l'espace physique ; au mieux il peut utiliser des adresses virtuelles qui ont une correspondence directe avec la mémoire physique. Le seul périphérique pour lequel j'ai vu passer un driver et qui utilise des adresses physiques est le DMA. D'un côté c'est anecodtique, de l'autre vous allez voir que du coup le DMA n'a pas accès au code et données de l'add-in. (Soit dit en passant, le DMA utilise des adresses virtuelles pour désigner les zones de mémoire internes au CPU qui ne sont pas gérées par le BSC.)

Pour éviter les confusions, dans la suite toutes les adresses seront virtuelles sauf mention contraire.

L'espace d'adressage virtuel

L'espace d'adressage virtuel de 32 bits est celui dans lequel on vit et nage en permanence quand on écrit des add-ins. Tous les pointeurs dans les programmes contiennent des adresses virtuelles entre 0x00000000 et 0xffffffff. Bien sûr, il n'y a pas 4 Go de mémoire dans la calculatrice, et il y a beaucoup de découpages impliqués.

Le premier découpage est la séparation de l'espace virtuel en cinq sous-espaces : P0, P1, P2, P3, P4.

  • P0 est entièrement contrôlé par le MMU, c'est le seul espace accessible en mode non-privilégié du processeur.
  • P1 est en bijection avec l'espace physique, auquel il accède à travers le cache.
  • P2 est en bijection avec l'espace physique aussi, mais contourne le cache.
  • P3 est contrôlé par le MMU, c'est un équivalent direct de P0 mais à usage exclusif du noyau.
  • P4 contient les zones mémoires qui sont dans le CPU, les registres périphériques, et plein de petites données.

Je vous mets la carte complète ci-dessous pour visualiser dès maintenant mais la plupart des points sont détaillés ensuite.


On peut tout de suite présenter P1 et P2. Ces deux sous-espaces sont en bijection avec la mémoire physique dans le sens où un accès à l'adresse x dans P1 ou P2 est équivalent à un accès à l'adresse physique x & 0x1fffffff (on garde les 29 bits du bas). C'est une particularité du SH7305 d'ailleurs, sur un ordinateur moderne ce genre de choses n'est pas possible ; il faut utiliser la pagination pour y accéder à la façon de P0 (détaillée dans la section suivante).

La différence entre P1 et P2 est l'usage du cache. Pour les accès à P1 le cache enregistre les données lues et écrites, ce qui permet de bénéficier de performances supplémentaires. Par exemple l'immense majorité du code et des variables de l'OS sont référencées par des adresses dans P1, sans quoi la calculatrice irait drastiquement moins vite.

Les accès à P2 sont utile dans quelques cas, essentiellement tous ceux où on peut avoir des problèmes de cohérence de cache. Un premier cas c'est si on partage l'accès avec un autre module qui lui n'a pas accès au cache. Pour prendre un exemple tout à fait au hasard, dont je parle purement théoriquement parce que'il ne s'est absolument jamais produit dans mon propre code, si le DMA accède à la RAM pour lire des données graphiques, vous vous retrouvez avec la situation suivante.


On se rappelle dans ce diagramme que le CPU accède à la RAM en passant d'abord par le bus d'opérandes, puis par le cache d'opérandes et le bus interne cache/RAM, ensuite par le SuperHyway et le BSC. Le DMA lui, passe par le bus périphérique puis le SuperHyway et aussi le BSC.

Imaginez donc, par un hasard complètement fortuit et fictif, que les données écrites par le CPU soient encore dans le cache au moment où le DMA fait son accès à la RAM... pouf, on n'a n'importe quoi à l'écran.

Parmi les autres cas utiles, il y a des situations plus exotiques comme du code auto-modifiant ou le reset de la calculatrice (pour lequel on saute à 0xa0000000 pour être sûr d'atteindre le bootcode et pas des bêtises dans le cache). Pendant que je suis sur le code auto-modifiant, vous noterez que les pages autour de 00300000 sont configurées telle façon qu'on peut y écrire et le cache retient les écritures ; mais bien sûr la ROM est lecture-seule donc l'écriture ne persiste que jusqu'au moment indéterminé où le cache éjecte la ligne modifiée. Encore un truc fourbe auquel il faut faire attention.

Virtualisation par le MMU : pagination

Les zones P0 et P3 sont virtualisées. Ça veut dire qu'initialement elles ne pointent nulle part ; si on tente d'y accéder, comme aucune mémoire n'est liée, on a une erreur sur le CPU. Pour les utiliser il faut configurer le MMU (Memory Management Unit) pour créer des associations (mappings) vers la mémoire physique. L'unité d'association s'appelle une page ; le MMU propose différentes tailles de page, celles utilisées par l'OS sont 4 kio et 64 kio.

Par exemple, lorsqu'un add-in s'exécute, l'OS configure le MMU pour que l'adresse 00300000 soit associée à une addresse physique dans la ROM où se trouve le fichier g1a/g3a. De même, l'adresse 08100000 est associée à une adresse physique dans la RAM où se trouve un zone réservée au segment de données et à la pile de l'add-in.

Les associations de pages sont stockées dans une table matérielle appelée TLB pour Translation Look-Aside Buffer, ce qui donne son nom à la fameuse "TLB error" qui se produit quand vous accédez à une adresse qui n'est associée à rien. Notez que les TLB error se produisent uniquement pour les adresses dans P0 et P3. Il n'y pas de concept d'accès « dans le vide » dans P1, P2 et P4 : si vous faites un accès hors des zones de mémoire vous allez récupérer une valeur, ce sera juste n'importe quoi (et votre programme continuera joyeusement de s'exécuter avec ce n'importe quoi dans ses registres).

Chaque page est munie d'une certaine configuration détaillant si elle peut être utilisée par un processus non-privilégié, si le cache est actif et selon quelle règle (write-through/write-back), et (ce qui aurait été utile si l'OS de CASIO avait une notion de processus) à quel processus elle appartient (chaque processus ne peut voir que les pages qui lui appartiennent, ce qui permet sur un système multi-processus de présenter une version différente de P0 à chaque processus).

Le MMU est un composant indispensable de tout système informatique moderne pour une série de raisons.

  • Abstraction : sur PC en particulier, on ne veut pas utiliser la mémoire physique parce que sa structure est différente sur quasiment toutes les machines, sa taille varie beaucoup, et elle peut même avoir des trous.
  • Chargement des programmes : la plupart du temps, les programmes ont besoin de savoir quelle sera leur adresse à l'exécution dès l'édition des liens. On peut l'éviter, mais ça a un petit coût en performances et un gros coût en complexité (demandez à Yatis). On ne peut pas savoir à l'avance où ils vont arriver dans la ROM (dans la mémoire de stockage), donc on a besoin du MMU pour garantir que le code sera toujours accessible à l'adresse 00300000.
  • Fragmentation des programmes : le fichier g1a/g3a est fragmenté (coupé en morceaux) dans la mémoire de stockage, on ne peut donc de toute façon pas y accéder directement en ROM. On a besoin du MMU pour associer les pages successives à partir de 00300000 aux fragments correspondants dans la ROM et ainsi donner l'illusion de continuité.
  • Sécurité : dans un OS sérieux, la mémoire du noyau n'appartient qu'au noyau et les processus n'ont pas le droit d'y accéder. On a besoin de P0 pour pouvoir donner accès de la mémoire aux processus sans pour autant leur permettre d'accéder à P1 ou P2. (Les processus, qui utilisent le mode non-privilégié du processeur, ne peuvent pas accéder à P1-P4.)
  • Espaces d'adressage privés : tous les programmes veulent savoir à l'avance à quelle adresse leur code sera chargé et tous les programes veulent utiliser la même adresse. On a besoin du MMU pour que chaque processus puisse avoir sa propre "version" de P0 où il est chargé à 00300000 sans gêner les autres processus qui sont aussi chargés à 00300000 dans leur propre version.

Dans l'OS, à part le code de l'add-in à 00300000 et le segment de données à 08100000, il n'y a qu'une seule autre page : une page associant l'adresse virtuelle 00000000 à l'adresse physique 00000000 (qui est le bootcode). Cette page ne sert à rien à part une seule chose : faire en sorte qu'un accès à NULL (qui est un pointeur de valeur 0) renvoie une valeur au lieu de planter avec une TLB error (équivalent d'une segfault sur le PC). Je vous laisse imaginer le nombre de bugs passés inaperçus à cause de ça (je soupçonne que ce soit le but d'ailleurs).

Adresse et taille de la RAM/ROM

Pour la ROM, c'est assez simple ; 4 Mo sur toutes les mono sauf 8 Mo pour la Graph 35+E II, et 32 Mo pour la Prizm et la Graph 90+E.

Pour la RAM, il y a des très vieux modèles avec 256 kio, mais avant même de passer au SH4 les modèles ont commencé à avoir 512 kio (tout en n'en utilisant que la moitié, ce qui donne 256 kio de mémoire gratuite sur pas mal de machines). La Graph 35+E II est le seul modèle monochrome à utiliser les 512 kio entièrement. Quant à la Prizm il y a 2 Mo, et la Graph 90+E a 8 Mo.

Pour une certaine raison, la Graph 90+E est le seul modèle dont la RAM n'est pas à l'adresse physique 08000000 mais 0c000000, ce qui correspond à une autre zone du BSC (peut-être qu'ils ont changé de type de RAM). Pour la plupart des add-ins Prizm c'est la seule source d'incompatibilité parce que l'adresse de la VRAM est hardcodée, et utiliser le syscall à la place les rend compatibles. L'émulateur Graph 90+E utilise l'adresse de la Prizm, histoire que ce soit pas trop facile.

Sur la Graph 90+E, comme sur les modèles mono avec 512 kio dont seulement la moitié est utilisée, l'usage de la nouvelle puce RAM de 8 Mo pose des questions. Il est évident que l'OS Prizm n'a pas beaucoup changé et ne déborde pas vraiment sur les 6 Mo passés ac200000. Dans mes tests, j'ai trouvé sur cette région d'abord 3 Mo de zéros puis 3 Mo de données non identifiées et assez aléatoire. Je n'ai observé aucun changement sur ces 6 Mo après des transferts USB, optimisations de la mémoire de stockage, RESETs, lancements d'add-ins et usages normaux des applications. CGDoom détecte les zéros et utilise environ 3 Mo. Un des noyaux de Yatis utilise les 6 Mo entièrement. A priori ça ne pose pas de problème, mais c'est empirique et surtout de futures versions de l'OS pourraient s'étendre.

Mémoires on-chip (ILRAM, XRAM, YRAM)

Les mémoires "on-chip" sont celles situées dans le CPU. Elles comprennent l'ILRAM, la XRAM et la YRAM. Il y a aussi la mémoire RS, mais elle est assez pette et contient du code critique de l'OS, donc je préfère ne pas y toucher. Notez juste que la mémoire RS a un traitement particulier par rapport aux états de sommeil/veille du processeur et que le code de redémarrage de la calto après un SHIFT+OFF est dans la mémoire RS.

La propriété incontournable de ces mémoires c'est qu'elles répondent toutes en 1 cycle dans les conditions favorables. Quand les accès mémoire sont limitants, que la RAM est saturée ou que le cache est sous pression, les mémoires on-chip délivrent souvent des gros boosts de peformance.

L'ILRAM (Instruction Local RAM) est une zone de 4 kio conçue pour contenir du code. Un accès par le bus d'instructions se fait en un seul cycle, ce qui est pratique pour garantir un accès parfait sans penser au cache d'instructions. En pratique ça ne fait pas beaucoup de différences par rapport à mettre le code dans la ROM ou la RAM, parce que le cache d'instructions est très performant et pas énormément sollicité (par rapport aux cache de données en tous cas). Cela dit, utiliser l'ILRAM élimine un peu de variations et j'ai trouvé dans les tests de mesure au-cycle-près de gintctl que c'était idéal pour de la très haute précision.

Même si l'ILRAM est pensée pour contenir du code, elle est pertinente pour les données aussi, soit pour éviter quelques accès RAM soit pour mieux répartir les échanges sur le bus. Par exemple la fonction dma_memset() de gint (particulièrement utilisée pour dclear()) fait une copie DMA de l'ILRAM vers la RAM. L'avantage évident de ne pas utiliser la RAM comme entrée c'est de libérer du trafic pour le BSC. TSWilliamson raconte aussi avoir parfois gagné 40% de performances en mettant la pile de son programme dans l'ILRAM, ce qui est très malin. Si la RAM n'est pas critique cependant, ça ne fait aucune différence notable.

La XRAM et la YRAM sont deux régions associées au DSP qui accompagne le CPU dans le SH4AL-DSP. Traditionnellement un DSP (Digital Signal Processor) est un coprocesseur indépendant du CPU, mais pour nous c'est plus une extension du jeu d'instructions avec ces deux zones mémoire on-chip supplémentaires de 8 kio chacune.

Une des grandes gimmicks du DSP est qu'il peut manipuler la XRAM et la YRAM en même temps. Spécifiquement, il a deux bus de 16 bits qui y mènent, ce qui lui permet de faire un accès de 16 bits à chaque, ou bien un accès de 32 bits à une, (plus un calcul), en un seul cycle. Ça a son utilité de temps en temps (j'en reparlerai), mais la façon vraiment simple d'utiliser ces mémoires consiste juste à y accéder avec le CPU, puisque les accès par le CPU prennent aussi 1 cycle.

En pratique, la XRAM et la YRAM sont la première chose à laquelle je pense quand je soupçonne que les accès mémoire limitent les performances d'un programme. Comme ni l'OS ni gint ne les utilise, on peut faire des tests très facilement en remplaçant juste un pointeur bien choisi par (void *)0xe5008fff pour voir si la vitesse s'améliore. C'est juste des buffers gratuis de 8 kio de mémoire accessible en un cycle ; les usages sont illimités.

Voici un résumé rapide de ces zones.

NomDébutFinTailleRégionCache
ILRAMe5200000e5200fff4 kioP4Non
XRAMe5007000e5008fff8 kioP4Non
YRAMe5017000e5018fff8 kioP4Non
RSfd800000fd8007ff2 kioP4Non

Soit dit en passant le moteur d'affichage de TLT repose sur un usage malin de la XRAM/YRAM pour mettre des données graphiques et communiquer plus vite avec l'écran.

Mémoires du SPU2 (PRAM0/1, XRAM0/1, YRAM0/1)

Là on rentre dans les choses vraiment bizarres. Je vous laisse ici la documentation détaillée de ces zones et j'en fais un résumé très rapide, parce que les applications sont plus limitées. Voyez aussi ce topic de recherche sur le sujet.

Le SH7724 comporte un module périphérique appelé SPU2 (Sound Processing Unit 2) qui permet du traitement du son vers des sorties numériques à l'aide de deux DSP : DSP0 et DSP1. Contrairement au DSP intégré au SH4AL-DSP et qui est une extension du CPU, les DSP du SPU2 sont des vrais coprocesseurs avec chacun leur code, une horloge indépendante, des cycles indépendants, et des mémoires supplémentaires appelées PRAM0/1, XRAM0/1, et YRAM0/1.

Long story short, sur le SH7305 on ne sait pas si les DSP existent, mais la RAM est bel est bien là. Cependant, elle est conçue spécifiquement pour ces DSP et donc elle a pas mal de particularités :

  • PRAM0 et PRAM1 forment une seule unité de stockage de 160 kio qu'on peut répartir entre les deux zones.
  • XRAM0 et XRAM1 forment une seule unité de stockage de 168 kio qu'on peut répartir entre les deux zones.
  • PRAM0/1, XRAM0/1 et YRAM0/1 ne supportent que les accès de 32 bits.
  • Sur chaque accès de 32 bits, XRAM0/1 et YRAM0/1 ne contiennent que 24 bits de données.

Par défaut, la mémoire de PRAM0/1 est tout dans PRAM0 et celle de XRAM0/1 est tout dans XRAM0, donc PRAM1 et XRAM1 sont vides en pratique. Et bien entendu XRAM0, YRAM0 et YRAM1 ne font que trois quarts de leur taille apparente puisqu'un octet sur quatre ne contient pas de données.

Il est relativement facile d'utiliser PRAM0 pour stocker des tableaux pourvu que les accès fassent 32 bits. Mais les autres régions sont trop particulières pour s'y prêter aisément, donc je ne vais pas trop m'étendre dessus. Il y a en théorie un contrôleur DMA qui est capable de compacter/décompacter le format "24 bits tous les 32 bits", mais je n'ai pas encore essayé d'implémenter de driver.

Voici un résumé pour les plus aventureux. Pour information, ça fait 434 kio de RAM en plus, ce qui est bienvenu mais pas autant que les 8 Mo de la Graph 90+E. Les accès, qui sont fatalement hors-cache, sont aussi un peu plus lents que la RAM classique.

NomDébutTaille apparenteTaille réelleRégionCache
PRAM0fe200000160 kio160 kioP4Non
XRAM0fe240000224 kio168 kioP4Non
YRAM0fe28000064 kio48 kioP4Non
PRAM1fe300000160 kio0 kioP4Non
XRAM1fe340000224 kio0 kioP4Non
YRAM1fe38000064 kio48 kioP4Non

Usage du DMA

De façon générale, le DMA est très fort pour copier dans la RAM et la ROM. Pour toutes les zones de mémoire qui sont gérées par le BSC, il faut donner des adresses physiques, ce qui veut dire qu'il est impossible d'accéder de façon continue à des données dans la ROM. Par exemple on ne peut pas trivialement copier une grande image de la ROM vers la VRAM puisque l'image n'est pas stockées de façon continue dans le système de fichiers.

Pour toutes les autres zones, dont les accès se font hors BSC, le DMA prend des adresses virtuelles (pour la mémoire on-chip il doit aller vers le CPU, pour le DSP il doit aller sur le bus périphérique). Dans tous les cas la performance est très discutable voire aisément battue par des méthodes manuelles sur le processeur.

On verra les débits exacts dans une autre technique mais c'est l'idée générale.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 19/10/2021 13:03 | #


Travailler avec de l'assembleur SuperH, idiomes classiques (Programmation générale — ★☆☆)

La première chose à voir sur ce sujet est le tutoriel d'initiation à l'assembleur de Ziqumu. Tout est très important dedans, sauf le décodage manuel des instructions qui est assez fastidieux. Pour cette technique je suppose que vous avez les concepts généraux en tête, l'idée c'est de donner les éléments nécessaires pour pouvoir facilement tester et analyser du code assembleur mondain.

Compiler du code assembleur

Je parle ici uniquement de la toolchain GCC ; pour le fx-9860G SDK il y a une syntaxe différente. Les fichiers assembleur ont l'extension .s (assembleur pur) ou .S (assembleur avec le préprocesseur C). Le second est utile pour #include des en-têtes C ; bien sûr les prototypes, définitions de structures, etc. n'ont rien à faire dans un fichier assembleur, par contre on peut récupérer les définition de macros pour interfacer avec du C sans hardcoder les constantes.

Pour compiler :

  • Avec un Makefile, soit sh-elf-gcc -c $< -o $@ -Wa,--dsp soit directement avec as, sh-elf-as -c $< -o $@ --dsp. Je vous conseille gcc surtout si vous utilisez le préprocesseur, parce que as n'a pas les options qui permettent de récupérer après le passage du préproco les dépendances envers les headers inclus, qui sont nécessaires pour garantir une compilation incrémentale correcte.

  • Avec CMake, ajoutez simplement LANGUAGES ASM dans le project() et les fichiers assembleur dans les sources des libs/exécutables.

Obtenir le code assemblé et le code C compilé

binutils fournit des outils assez forts pour tout ce qui est introspection dans le code assembleur, celui qui nous intéresse ici est objdump. La plupart du temps, vous avez tout intérêt à faire du désassemblage sur des ELF. Le fxSDK les crée automatiquement dans build-{fx,cg}/<nom_du_projet>, mais vous pouvez en obtenir avec n'importe quel système de build ; il faut juste s'assurer que le linker script spécifie OUTPUT_FORMAT(elf32-sh) et appeler objcopy à la main dans le système de compilation pour obtenir ensuite le binaire plat duquel on génère le g1a/g3a.

L'option -h d'objdump est d'utilité générale et montre la liste des sections avec les adresses correspondantes, c'est une vue large sur l'ensemble du programme.

% sh-elf-objdump -h build-cg/gintctl

build-cg/gintctl:     file format elf32-sh

Sections:
Idx Name          Size      VMA       LMA       File off  Algn
  0 .text         0001b838  00300000  00300000  00000180  2**5
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  1 .rodata       00028928  0031bbb0  0031bbb0  0001bd30  2**2
                  CONTENTS, ALLOC, LOAD, READONLY, DATA
  2 .gint.drivers 00000210  0031b9a0  0031b9a0  0001bb20  2**2
                  CONTENTS, ALLOC, LOAD, DATA
  3 .gint.blocks  00000160  0031b840  0031b840  0001b9c0  2**4
                  CONTENTS, ALLOC, LOAD, READONLY, CODE
  4 .bss          000016f0  08101400  08101400  00047880  2**2
                  ALLOC
  5 .data         00000cd0  08102af0  003444d8  00044670  2**2
                  CONTENTS, ALLOC, LOAD, DATA
  6 .data.4       00000000  081037c0  081037c0  00047880  2**0
                  CONTENTS, ALLOC, LOAD, DATA
  7 .ilram        00000cc0  e5200000  003451a8  00045380  2**5
                  CONTENTS, ALLOC, LOAD, CODE
  8 .xram         00001000  e5007000  00345e68  00046080  2**5
                  CONTENTS, ALLOC, LOAD, DATA
  9 .yram         00000800  e5017000  00346e68  00047080  2**5
                  CONTENTS, ALLOC, LOAD, DATA
10 .gint.bss     00000200  081037c0  081037c0  000478c0  2**2
                  ALLOC
11 .debug_frame  00000ee0  00000000  00000000  00047880  2**2
                  CONTENTS, READONLY, DEBUGGING, OCTETS
12 .debug_loclists 00003297  00000000  00000000  00048760  2**0
                  CONTENTS, READONLY, DEBUGGING, OCTETS
13 .debug_rnglists 00000669  00000000  00000000  0004b9f7  2**0
                  CONTENTS, READONLY, DEBUGGING, OCTETS

L'option -d est ce qui fait vraiment le désassemblage. Personnellement je déssasemble souvent tout le fichier puis je le parcours avec less pour chercher les adresses qui m'intéressent (particulièrement quand je debug des System ERROR), mais vous pouvez aussi utiliser -j pour désassembler une section en particulier.

% sh-elf-objdump -d build-cg/gintctl | less

build-cg/gintctl:     file format elf32-sh


Disassembly of section .text:

00300000 <_start>:
  300000: 2f 86         mov.l r8,@-r15
  300002: 2f 96         mov.l r9,@-r15
  300004: 4f 22         sts.l pr,@-r15
  300006: d1 34         mov.l 3000d8 <_start+0xd8>,r1 ! 3107a4 <_hw_detect>
  300008: 7f f8         add #-8,r15
  30000a: 2f 42         mov.l r4,@r15
  30000c: 41 0b         jsr @r1
  30000e: 1f 51         mov.l r5,@(4,r15)
  300010: d1 32         mov.l 3000dc <_start+0xdc>,r1 ! 310ae4 <_regcpy>
  300012: d6 33         mov.l 3000e0 <_start+0xe0>,r6 ! 8102af0 <_menu_libs>
  300014: d5 33         mov.l 3000e4 <_start+0xe4>,r5 ! cd0 <_sdata>
  300016: d4 34         mov.l 3000e8 <_start+0xe8>,r4 ! 3444d8 <_ldata>
  300018: 41 0b         jsr @r1
...

Notez qu'en désassemblant vous perdez les noms des labels, des constantes, des macros ; les commentaires ; et toutes les marques de formatage qui structurent le code. Donc ça vaudra jamais la source en termes de lisibilité.

Si vous devez absolument désassembler un binaire (ie. l'OS) :

% sh-elf-objdump -b binary -m sh4-nofpu -D $FILE

Quand j'ai des données aléatoires que je soupçonne être du code, j'utilise une fonction de ce style :

shdis() {
  echo "$@" | xxd -r -p > /tmp/shdis.bin
  sh-elf-objdump -b binary -m sh4-nofpu -D /tmp/shdis.bin | tail -n +7
}

% shdis e307 e510
00000000 <.data>:
   0: e3 07         mov #7,r3
   2: e5 10         mov #16,r5

Pendant que je suis sur ce sujet, vous pouvez faire générer au linker une carte de toutes les variables et fonctions dans l'exécutable avec l'option -Map=<FICHIER>. Dans le fxSDK, vous l'obtenez dans build-{fx,cg}/map avec :

target_compile_options(<la cible> PRIVATE -Wl,-Map=map)

Pour les autres systèmes de build c'est pareil, n'oubliez pas le -Wl pour que l'option arrive à ld et pas gcc.

Écrire et exposer des fonctions assembleur

Comme vous l'avez vu dans le tutoriel de Ziqumu, en assembleur on se trimballe des labels et des sauts partout. Les labels ne sont pas anodins, ce sont (pour la plupart) des symboles : ils marquent la position de noms (variables ou fonctions) dans le code. De fait, pour écrire une fonction en assembleur, il suffit de créer un symbole et de le rendre public :

.global _ma_fonction
.type _ma_fonction, @function

_ma_fonction:
        rts
        nop

Plus simple que ça, on n'a pas - cette fonction ne fait rien et return immédiatement. Notez que toutes les variables et fonctions C ont leur nom automatiquement préfixé d'un underscore par le compilateur, donc si on veut utiliser ma_fonction() en C il faut appeler le symbole _ma_fonction en assembleur. Si le symbole ne commence pas par un underscore alors il est complètement inaccessible depuis du code C.

Comme il y a des symboles partout en assembleur, y compris pour les tests, conditions, boucles, accès aux variables globales, etc. par défaut ils sont privés. La directive .global indique de rentre le symbole global. Notez qu'il n'y a pas de type affixé à la fonction, c'est seulement côté C qu'on va lui en donner un. Si le type donné en C ne correspond pas au comportement de la fonction, c'est de notre faute, et là on ne peut pas inclure l'en-tête pour que le compilateur fasse la vérification automatiquement, il faut gérer à la main.

La directive .type indique que le symbole _ma_fonction est une fonction. C'est pas obligatoire, ça aide pour le debugging je crois. (Je l'oublie presque tout le temps.)

Voilà comment on appelerait cette fonction :

extern void ma_fonction(void);
ma_fonction();

La documentation

Vous n'y échapperez pas, toutes les informations importantes sont dedans.

Vous trouverez les détails du jeu d'instructions et des fonctionnalités du processeur dans la documentation du SH4AL-DSP.

Vous trouverez des informations à peu près correctes sur la majorité des modules périphériques du SH7305 dans la documentation du SH7724, et quelques autres bouts sur la bible.

Prenez l'habitude de chercher tout ce qui vous échappe dans le manuel voire de lire des descriptions d'instructions au hasard pour vous familiariser avec les aspects plus obscurs.

Conventions d'appel

Toutes les fonctions partagent les mêmes registres, donc il y a des conventions à suivre pour que tout le monde s'entende. Spécifiquement :

  • Registres caller-saved : les registres r0 à r7 sont caller-saved. Si l'appelant en a besoin, il les sauvegarde ailleurs avant de vous appeler. Votre fonction peut les utiliser sans restriction. Si vous appelez une sous-fonction, vous récupérerez des valeurs quelconques dans ces registres donc vous devez aussi les sauvegarder ailleurs si vous en avez besoin après coup.

  • Registres callee-saved : les registres r8 à r15 sont callee-saved. Votre appelant peut avoir des valeurs importantes dedans et il doit les récupérer après l'appel. Si vous voulez les utiliser il faut les sauvegarder (typiquement sur la pile). Si vous appelez une sous-fonction les valeurs dans ces registres seront préservées par la sous-fonction.

  • Arguments : les premiers arguments (de 32 bits chacun ou moins) sont passés dans les registres r4, r5, r6 et r7. S'il y en plus, ils sont poussés sur la pile dans l'ordre inverse de l'appel (ie. @r15 est le 5ème, @(4,r15) est le 6ème, etc). Si les arguments font plus de 32 bits, c'est plus compliqué ; mais souvent les valeurs de 64 bits (entiers 64 bits et double) sont passées sur deux registres consécutifs, sinon c'est sur la pile.

  • Valeur de retour : la valeur de retour (de 32 bits) est passée dans r0. Je sais que GCC aime mettre les valeurs de retour de 64 bits dans r0 et r1, mais je ne sais pas à quel point c'est général.

  • Registre pr : le registre pr indique où retourner quand la fonction termine. Il est utilisé implicitement quand vous faites un sous-appel de fonction avec jsr ou bsr, et il est callee-saved, donc vous devez le sauvegarder si vous utilisez des sous-fonctions.

Voilà un exemple de fonction pour démontrer ces usages.

# void *memzero(void *dst, size_t size) {
#    return memset(dst, 0x00, size);
# }

.global _memzero

# r4: dst
# r5: size
_memzero:
        # On sauvegarde pr sur la pile pour appeler memset
        sts.l   pr, @-r15

        # Chargement de l'adresse de memset. On peut utiliser r1 sans demander
        mov.l   .memset, r1

        # On déplace size vers le troisième argument
        mov     r5, r6

        # Appel de la fonction; le deuxième argument de memset est 0x00
        jsr     @r1
        mov     #0, r5

        # Désormais r4, r5, r6 sont quelconques, on sait uniquement que
        # r0 contient la valeur de retour de memset()

        # Restauration de pr
        lds.l   @r15+, pr

        # memset a mis sa valeur de retour dans r0 ; on la garde
        rts
        nop

.memset:
        .long   _memset

La raison pour laquelle on utilise sts.l et lds.l au lieu de mov.l est cosmétique ; l'instruction s'appelle comme ça parce que pr est catégorisé de façon méta comme un "registre système".

Je reviendrai sur la façon dont on a chargé l'adresse de memset() ainsi que la raison pour laquelle mov #0, r5 est après jsr @r1 et pas avant.

Notez que la convention pour le passage des listes d'arguments variables (va_list) varie entre GCC et le compilateur du SDK qui est notamment utilisé pour l'OS et fxlib, donc si les fonctions comme sprintf() de fxlib ne marchent pas sans l'option -mrenesas qui utilise l'ABI de Renesas.

Charger des constantes, variables globales et fonctions

Toutes les instructions SuperH font 16 bits, et "mov #imm, rn" n'en accorde que 8 à la valeur, donc elle ne peut être utilisée que pour charger des valeurs signées entre -128 et 127.

Pour aller plus loin, il faut utiliser le mode "mov @(disp,pc), rn" où @(disp,pc) représente une donnée à une certaine distance (disp) de l'instruction actuelle (pc). Mais bien sûr personne n'a envie de calculer la distance entre une constante qui à la fin du code et l'instruction qui l'utilise, donc on met un label et l'assembleur se débrouille.

_return_0xc0ffee:
        mov.l   .value, r0
        rts
        nop

.align 4
.value:
        .long   0xc0ffee

Le point dans le nom du symbole .value est une convention qui indique que c'est un label interne invisible de l'extérieur. Le .align 4 aligne l'adresse actuelle à 4 octets, parce qu'un long ne peut être que sur une adresse multiple de 4. Les instructions assembleur font 2 octets chacune donc cet alignment peut être cassé selon la longueur de la fonction qui précède.

Vous pouvez aussi charger avec mov.w une valeur de 16 bits stockée avec .word ; attention il y a une extension de signe et pas une extension nulle. Bien sûr dans ce cas pas besoin d'aligner.

Comme vous avez pu le voir dans l'exemple précédent, si après .long on met le nom d'un symbole, alors à l'édition des liens ce nom sera remplacé par l'adresse assignée au symbole. J'ai bien dit l'adresse, ce qui veut dire que pour une variable globale on a l'adresse de la variable, pas sa valeur.

# En C: int counter;

_get_counter:
        mov.l   .counter_address, r0 # = &counter
        rts
        mov.l   @r0, r0 # = counter

.align 4
.counter_address:
        .long   _counter

Delay slots

Les delay slots sont un mécanisme d'optimisation consistant à delay les sauts d'une instruction. Le problème vient du pipeline (dont je reparlerai plus tard), qui fait que plusieurs instructions sont exécutées en même temps. Avec le pipeline, une instruction démarre souvent avant que les instructions précédentes ne soient finies.

Ça pose un problème pour les sauts parce que la cible du saut ne peut en général pas être déterminée avant que les instructions précédentes ne soient finies, puiqu'elles calculent cette cible (par exemple ici je pourrais modifier pr juste avant rts, ou charger r1 juste avant jmp).

Quitte à être forcé d'attendre la terminaison des instructions précédentes, le SuperH propose donc d'exécuter une instruction de plus pendant cette attente ; cette instruction est écrite après celle de saut et s'appelle un delay slot.

Les delay slots sont soumis à une pléthore de règles, et il y a beaucoup de choses qu'on ne peut pas faire dans un delay slot. On ne peut pas mettre une instruction de saut, évidemment, mais on ne peut pas non plus mettre une instruction qui affecte PC ou en dépend, parce que durant l'exécution du delay slot PC est en train d'être mis à jour pour réaliser le saut.

Tout ce qui utilise @(disp,pc) par exemple est illégal dans un delay slot, donc les mov.l pour charger des constantes ça ne passe. mova non plus. Recharger pr depuis la pile ne marche pas non plus après rts, non que ce soit illégal comme delay slot, mais parce que le rts utilisera la valeur de pr précédente.

# INCORRECT:
rts
lds.l   @r15+, pr

Je vous invite à repasser les exemples ci-dessus pour observer les différents delay slots de jsr et rts.

Appels terminaux

Quand une fonction est appelée, pr contient l'adresse de retour. Si le corps d'une fonction se termine par un appel terminal (ie. elle appelle une sous-fonction et soit ignore soit transfère le résultat), alors une optimisation de l'appel terminal peut être faite.

Prenons par exemple la fonction memzero() définie plus haut.

void *memzero(void *dst, size_t size) {
   return memset(dst, 0x00, size);
}

L'appel à memset() est terminal. Plutôt que de faire un appel de sous-routine, on peut donc y sauter directement. Comme on ne fait pas un appel de sous-routine, pr n'est pas mis à jour donc l'adresse dans memzero() où on était avant l'appel est perdue. Mais ce n'est pas grave ; quand memset() finira (par rts) l'exécution reprendra à pr, c'est-à-dire directement à la fonction qui a appelé memzero().

De cette façon, on élimine un appel de fonction et un peu de gestion de pr. Le code ressemblerait à ceci :

.global _memzero

_memzero:
        mov.l   .memset, r1
        mov     r5, r6
        jmp     @r1
        mov     #0, r5

.memset:
        .long   _memset

Comme c'est memset qui revient à notre appelant, on n'a pas besoin de rts. La fonction memzero() se termine dès le jmp.

Les théoriciens fous verront dans cette technique une lueur de programmation par continuations, ce qui est absolument correct.

La documentation

Avec ça vous devriez être assez averti·e pour vous exercer. Je conseille d'écrire quelques fonctions sur les chaînes de caractères (strlen(), strcpy(), etc) à titre d'exercice. Pour toute le reste, la documentation est la constante :


Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 06/12/2021 16:29 | #


Mesurer et visualiser les performances (Programmation générale — ★☆☆)

Donc vous avez un programme, et vous voulez identifier les parties qui prennent le plus de temps. Naturellement vous allez vouloir mesurer et visualiser les performances du code, de préférence :

  • De façon automatique : plus il faut travailler pour avoir des chiffres moins on va en collecter. Le but ici c'est d'avoir des informations tout le temps en faisant absolument rien pour ne pas rater un morceau important par manque de mesure.

  • De façon comparée : il est rare qu'il y ait un et un seul bottleneck ; souvent on veut savoir si une fonction prend «la majorité du temps de rendu» ou bien «plus de temps que le pathfinding» pour décider qui optimiser.

  • De façon permanente : une fois que le code pour acquérir les chiffres est écrit, on veut qu'il reste en place pour surveiller que les performances ne se dégradent pas à chaque nouvelle fonctionnalité.

  • De façon réactive : on ne veut pas non plus passer notre temps à surveiller les chiffres des perfs, donc c'est pertinent de simplement avoir un avertissement si on passe en-dessous de 15 FPS, ou quelque chose du même style.

Cette technique s'appuie sur libprof, qui existe pour répondre spécifiquement à ces besoins. Pour les devs hors-gint, il y a une implémentation compatible avec le PrizmSDK dans CGDoom (libprof.h, libprof.c). Les instructions d'installation/utilisation sont dans le README.

Avant que libprof existe, les mesures de performance étaient le plus souvent soit au jugé soit avec la RTC (qui offre une oscillation à 128 Hz), rien de proprement exploitable pour optimiser un jeu et encore moins pour optimiser «au cycle près» des séquences critiques de code assembleur. Le but de cette technique est de montrer qu'on peut faire bien mieux.

Mesures ponctuelles

La méthode de mesure la plus simple consiste à ponctuellement chronométrer une section de code. Ça se fait aisément avec prof_exec(), qui prend en paramètre «du code» et renvoie la durée en microsecondes.

uint32_t dclear_time = prof_exec({
    dclear(C_WHITE);
});

dclear_time; // = 2600 µs

C'est un bon début surtout quand on ne sait pas encore ce qui prend le plus de temps. Cela dit, ça ne passe pas très bien à l'échelle : on ne peut pas mettre beaucoup de code (c'est une macro et le préproco n'aime pas les virgules mal placées dans les arguments d'une macro), ça ne mesure qu'une fois, et c'est pas très élégant d'en mettre partout.

En plus de ça, même si on peut mettre un prof_exec() à l'endroit critique et optimiser jusqu'à réduire le temps de façon satisfaisante, ce n'est pas vraiment suffisant. Pour que l'optimisation soit solide il faut ensuite pouvoir surveiller que les performances sont maintenues. Histoire que si on fait une erreur catastrophique qui réduit la vitesse de 20% au moment où on introduit une nouvelle fonctionnalité, ça ne passe pas inaperçu.

Pour ça, il faut continuer de chronométrer le code après l'avoir optimisé ; il faut donc avoir une structure plus propre et un moyen d'acquérir/tester/visualiser les mesures même quand on sera passés sur autre chose.

Mesures systématiques

prof_exec() est une macro qui revient, une fois l'exemple ci-dessus développé, à la séquence suivante :

prof_t perf = prof_make();
prof_enter(perf);
dclear(C_WHITE);
prof_leave(perf);
uint32_t dclear_time = prof_time(perf);

La quasi-totalité des fonctions de la bibliothèque est là :
  • Les objets de type prof_t sont des chronomètres avec un compteur de temps.
  • prof_enter() démarre le chrono et prof_leave() le met en pause.
  • prof_time() renvoie la durée chronométrée en microsecondes (à l'arrêt uniquement !).

Ce qu'on ne voit pas avec prof_exec(), c'est qu'on peut entrer et sortir du même compteur autant fois qu'on le veut, ce qui permet facilement de compter ensemble des fonctions très éloignées pourvu que les deux aient accès au compteur. On peut aussi compter le temps total passé dans une fonction sur plusieurs appels :

static prof_t perf_mafonction = prof_make();

void mafonction(void)
{
    prof_enter(perf_mafonction);
    /* ... */
    prof_leave(perf_mafonction);
}

Notez que le compteur interne à l'objet prof_t n'a de sens que lorsque le compteur est arrêté ; lorsqu'il compte la valeur a une autre signification. Il est donc crucial que chaque prof_start() soit accompagné d'exactement un prof_end(). Ça semble évident d'ici mais c'est quand on s'y attend le moins que ça nous tombe dessus :

void mafonction(void)
{
    prof_enter(perf_mafonction);

    if(...) {
        return; /* oops! */
    }

    prof_leave(perf_mafonction);
}

Notes sur les fonctions récursives. Les compteurs traquent le niveau de récursion. Si mafonction() est récursive alors le temps passé dans les sous-appels ne comptera qu'une fois (au titre de l'appel le plus externe). Donc la récursivité ne pose aucune difficulté si ce n'est que tous les appels doivent utiliser le même compteur (qui ne peut donc pas être local).

Si toutefois on sait qu'une fonction n'est pas récursive on peut utiliser prof_enter_norec() et prof_leave_norec() qui ignorent le niveau de récursion, ce qui est un poil plus rapide. (L'impact du chronométrage est largement en-dessous de 1 µs de toute façon en général.)

Profilage

Idéalement on aimerait pouvoir faire du profilage, dans le sens où on enregistrerait les moments où on entre et sort de chaque contexte (chronomètre) pour ensuite visualiser les résultats sous la forme d'une frise chronologique.

Pour l'instant ce n'est pas possible surtout parce qu'il faut mettre les données temporelles quelque part. Dans l'exemple précédent le temps passé est accumulé, mais dans un profileur complet il faut noter les dates d'entrée et sortie aussi.

Ça devrait être possible de faire une visualisation par USB, ou de générer un fichier pour gprof(1) puisqu'on a les ELF des add-ins disponibles sur l'ordinateur. Les données pourraient aussi être accumulées dans un grand buffer, surtout sur la Graph 90+E où il y a plusieurs Mo de RAM.

Structurer les mesures pour maintenir la performance

Comme mentionné dans l'introduction, il ne suffit pas vraiment de mesurer les performances une fois puis d'oublier le code concerné. Avec le temps, tout ou partie du code peut changer, ou bien les sous-fonctions ou structures de données peuvent changer, impactant la performance de différentes façons difficiles à prévoir.

C'est principalement pour cette raison qu'on veut avoir des informations sur les performances de façon permanente et de façon réactive ; comme ça on peut détecter les régressions et les détecter avec un minimum d'efforts.

Pour que la collecte des mesures soit permanente il faut qu'elle soit intégrée à l'API. Il n'y a pas besoin de faire compliqué, personnellement le plus souvent je déclare juste quelques variables globales en lecture-écriture et de quoi réinitialiser les compteurs. Par exemple, dans le pipeline de rendu d'un moteur, j'ai cette interface :

//---
// Performance indicators
//
// The following performance counters are run through by the rendering module
// in most stages of the rendering process. The module updates them but doesn't
// use them, so they are safe to write to and reset when they're not running.
//---

/* This counter runs during command generation and queue operations. */
extern prof_t azrp_perf_cmdgen;

/* This counter runs during the command sorting step. */
extern prof_t azrp_perf_sort;

/* This counter runs during shader executions in arzp_render_fragments(). */
extern prof_t azrp_perf_shaders;

/* This counter runs during CPU transfers to the R61524 display. */
extern prof_t azrp_perf_r61524;

/* This counter runs during the whole azrp_update() operation; it is the sum of
   sort, shaders, r61524, plus some logic overhead. */
extern prof_t azrp_perf_render;

/* azrp_perf_clear(): Clear all performance counters
   Generally you want to do this before azrp_update(). */
void azrp_perf_clear(void);

Ensuite, il faut qu'une partie du programme collecte les informations et les affiche, de sorte que vous, en tant que testeur, puissiez observer les indicateurs. Une partie du processus doit être automatique (le fait de collecter les mesures des bibliothèques, les combiner, calculer le nombre de FPS, etc.) et une partie doit être manuelle (le fait de lire le compteur de FPS ou de consulter l'écran de debug des performances par exemple).

Pour que ça marche les deux parties doivent se rejoindrent au milieu ; d'un côté, plus on automatise et plus il est facile de rester au taquet (ie. lire le compteur de FPS ne coûte rien et est déjà utile en cas de régression significative) ; de l'autre, plus on fait d'actions manuelles et plus on a la possibilité consulter et comparer différentes informations et de voir des détails fins. Il y a plein de façons de procéder, évidemment.

Personnellement je pense qu'avoir un compteur de FPS et un écran de debug avec un camembert ou une autre visualisation comparée des principaux bottleneck est de bon goût si on veut éviter que l'optimisation durement acquise ne s'effrite avec les modifications et la maintenance.

Quelques options de visualisation

Il y a pas mal d'options pour afficher les résultats, mais notez que le choix d'une bonne visualisation peut être toute une science. Si vous programmez quelque chose de durable, je conseille de mettre quelques couleurs et autres indices visuels quand les données collectées deviennent nombreuses, histoire que les tendances générales se voient d'un coup d'oeil.

Dans les cas vraiment extrêmes certaines visualisations comme une heat map ou une treemap peuvent être pertinentes.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 06/12/2021 21:04 | #


Mesurer au cycle près (Bas niveau — ★★★)

Mesurer le code au cycle près est utile quand on veut optimiser une boucle serrée d'assembleur. À cause de la complexité du pipeline et de l'exécution superscalaire, à laquelle s'ajoute des détails d'implémentation du CPU qui ne sont pas communiqués dans la documentation, il est généralement difficile de prédire exactement le temps que va prendre une séquence d'instructions. Mais on peut quand même le mesurer.

J'ai développé cette technique pour pouvoir étudier expérimentalement le pipeline et plus précisément les délais qu'on peut avoir entre plusieurs opérations sur les mêmes données. Mon implémentation est disponible dans gintctl (src/perf/cpu.c et src/perf/cpu.S) et cette technique est essentiellement une explication de ces deux fichiers.

La précision exacte des mesures

L'idée originale derrière libprof a toujours été de mesurer au cycle près. Ce qu'on voit assez rapidement quand on regarde la documentation c'est que l'horloge sur laquelle le timer compte est essentiellement aussi rapide que l'horloge du CPU. Les timers matériels s'approchent donc vraiment finement de pouvoir mesurer les instructions individuellement, et on n'a somme toute pas grand-chose à ajouter pour y parvenir.

La première chose à faire est de déterminer exactement le rapport entre la fréquence de comptage du timer et la fréquence d'exécution d'instructions du CPU. On peut trouver cette information dans la configuration du CPG, qui nous donne tous les paramètres nécessaires pour déduire en MHz la fréquence de l'horloge Iϕ (celle qui cadence les cycles du processeur) et celle de Pϕ (sur la base de laquelle le timer compte).

Les détails sont dans le manuel SH7724, section 17 ; mais si on regarde un screenshot de Ftune/Ptune on peut avoir l'information directement.


Les valeurs IFC et PFC indiquent de combien l'horloge source commune (celle qui sort de PLL) est divisée pour obtenir Iϕ et Pϕ. Sur les deux modèles, le rapport est de 4, donc Pϕ fait un cycle d'horloge pour 4 cycles de Iϕ.

Ce n'est pas tout cependant, parce que le timer ne compte pas exactement sur Pϕ. Il y a cinq options, qui sont détaillées dans le manuel SH7724, au tout début de la section 20 :

Manuel SH7724 a écrit :
Allows selection among five counter input clocks: Pϕ/4, Pϕ/16, Pϕ/64, Pϕ/256, and Pϕ/1024

Donc le décompte le plus rapide qu'on peut avoir est Pϕ/4 (que libprof sélectionne automatiquement), ce qui signifie que le timer compte une unité pour 16 cycles processeur.

Répétition du code

Clairemement, une mesure à 16 cycles près n'est pas suffisante pour identifier les instructions individuellement. Pour ça on va s'appuyer sur le plus vieux mécanisme de mesure de performances : répéter. Dans gintctl, je répète chaque section de code entre 256 et 4096 fois, selon le temps estimé pour la boucle (puis elle est longue moins il y a besoin de répéter). Du coup, soudainement le timer a une résolution qui varie entre 1/16 et 1/256 instruction, ce qui est largement suffisant pour conclure à l'unité près.

Je noterai juste que l'effet d'initialisation habituel de libprof s'applique ; je ne sais pas quelle est la cause exacte, mais la première mesure est toujours plus lente. Je pense que c'est à cause de l'accès au code via le cache, mais ce n'est pas certain. Jetez toujours la première mesure, les suivantes sont toutes consistantes.

Donc maintenant le jeu ça va consister à étudier attentivement le processus de mesure et le code pour s'assurer qu'aucune partie de ce qu'on exécute ne vient perturber la mesure. Spécifiquement, je vais parler des points suivants :
  • Le temps entre le démarrage du timer et le lancement du code à mesurer ;
  • Le mécanisme par lequel on fait boucler le test ;
  • Les accès au code et aux données durant l'exécution de la boucle.

Durée d'initialisation

La majorité de l'incertitude dans une mesure avec libprof (outre le premier run) se trouve dans la durée entre le démarrage du timer et le début du code testé, plus (symétriquement) la durée entre la fin du code testé et l'arrêt du timer.

Généralement on ignore complètement cet effet parce que libprof donne ses mesures en microsecondes et que ça compte pour moins d'une miroseconde (pour rappel, 1 µs ça fait entre 30 et 120 cycles CPU selon le modèle, sans overclock).

Ici, on utilise directement la mesure brute, et donc on peut voir la variation : généralement ça dévie d'une ou deux unités, c'est-à-dire que le temps mesuré pour une boucle qui se répète 1024 fois c'est une mutiple de 1024 plus 16 ou 32 cycles. On est très loin d'un niveau de bruit qui affecterait les conclusions, surtout quand on voit la consistance.

Boucle instantanée du DSP

J'ai dit qu'on faisait répéter le code plusieurs centaines ou milliers de fois, mais pour que la mesure soit correcte il faut encore que le coût de gestion de la boucle n'alourdisse pas le programme. Mettons par exemple que je compte naïvement le temps que ça prend de faire 2 nop, avec 1024 itérations :

        mov     #4, r0
        shll8   r0

1:      nop
        nop
        dt      r0   # oups!
        bf      1b   # oups!

On se retrouve dans la boucle avec beaucoup plus que 2 nop puisqu'on paie en plus une instruction ALU (dt) pour compter le nombre de tours et un saut (bf) qui impose en plus un cycle de latence dans le pipeline (qu'on pourrait matérialiser avec le delay slot).

Il y a différentes façons d'attaquer ce problème ; on pourrait mesurer le prix que ce dt/bf prend tout seul, le soustraire à la mesure finale, l'optimiser pour réduire l'impact, mais ultimement ce ne serait jamais aussi satisfaisant que d'utiliser la boucle instantanée du DSP.

        mov     #4, r0
        shll8   r0
        ldrs    1f
        ldre    2f
        ldrc    r0
        nop

1:      nop
2:      nop

Le mécanisme est un peu complexe et je vous laisse la liberté de le découvrir dans le manuel du SH4AL-DSP, section 6.3.2. Si vous voulez le tester dans un add-in n'oubliez pas d'activer le bit DSP dans SR (gint le fait automatiquement).

Essentiellement, on indique par ldrs quelle est la première instruction de la boucle, par ldre quelle est la dernière (ça peut être la même), et par ldrc combien de fois on veut faire la boucle. Ensuite l'exécution continue, et chaque fois que le CPU croise le label de fin (ici 2:), l'exécution continue non pas à l'instruction suivante mais au label de début (ici 1:) en décrémentant le nombre d'itérations restantes (qui est stocké dans SR et est limité à 4096). Quand le nombre d'itérations tombe à 0 le mécanisme s'arrête.

En bref, c'est une boucle for intégrée directement au CPU et pour laquelle on ne paie absolument rien ; l'exécution est aussi rapide que si le double nop était répété 1024 fois d'affilée (et même un peu plus puisqu'on bénéficie de la localité du cache d'instructions).

Vérifier que cette boucle ne coûte rien est la première chose que j'ai mesurée. On sait que la durée de ce double nop est 1 cycle (c'est là tout le principe de l'exécution superscalaire), et compte tenu des déviations discutées ci-dessus il est très facile de voir que ce code-là prend 1024 cycles.

On notera quand même une différence avec la boucle déroulée ; l'exécution superscalaire ne passe pas la frontière de la boucle, ie. si on met un seul nop il ne peut pas s'exécuter deux fois en même temps. En gros il ne faut pas espérer compter les demi-cycles.

Accès au code et aux données

Il y a un bon nombre de facteurs qui influencent la vitesse d'exécution du code. Ici, on s'intéresse au CPU lui-même, son pipeline, son architecture superscalaire, et le flot interne des données qui impose différentes latences pour différentes séquences d'opérations.

Il faut donc veiller à ne pas être perturbé par d'autres délais, et je pense en particulier aux accès mémoire.

Pour que les accès de lecture du code soient toujours consistants, je mets le code à tester dans l'ILRAM ; ainsi les lectures prennent toujours un cycle. Pour être honnête je ne suis pas sûr que ce soit nécessaire étant donné que le cache d'instructions fait des merveilles, mais on ne sait jamais.

Pour que les accès aux données ne soient pas limitants (ie. si on va lire une donnée en RAM sur une ligne qui n'est pas dans le cache, c'est immédiatement un désastre !), je fais les lectures dans la XRAM et la YRAM. Les deux sont assez petites (8 kio), mais ça n'empêche pas de faire quelques centaines/milliers de tours (surtout quand on veut juste faire un accès mémoire et qu'on n'a pas besoin de modifier de données).

Et enfin, il reste un facteur que j'ai observé mais donc je ne comprends pas exactement l'influence. Le code de la boucle doit être 4-aligné, sinon le temps d'exécution varie assez violemment. Sur SH3 ça ne me surprendrait pas parce que le processeur lit les instructions par paires quand il passe sur des adresses 4-alignées, et donc ne lit rien un cycle sur deux. Mais je croyais que cet effet n'existait plus sur SH4.

Dans tous les cas, dans le code du test il faut donc faire bien attention à coller .align 4 avant la fonction et à s'assurer que le PROLOGUE() contient un nombre pair d'instructions (ce qui est le cas).

/* EX/EX -> 2 cycles /i */
.align 4
_perf_cpu_EX_EX:
        PROLOGUE(1024)
1:      add     #0, r0
2:      add     #0, r1
        EPILOGUE()

Et c'est essentiellement tout ce qui est nécessaire pour mettre en oeuvre et exploiter des mesures au cycle près.

Exemple de résultats obtenus par cette méthode

Voilà ce que ça donne une fois lancé dans gintctl. Vous pouvez trouver les sources de chaque test sur le dépôt ; pour illustrer cette technique il suffit de voir les variations sur le nombre de cycles. "CPI" est le nombre de cycles par itération (ie. la durée du corps de boucle), "Cycles" est la mesure brute du nombre de cycles CPU (toujours un multiple de 16 à cause de la granularité du timer), et "Iter" est le nombre d'itérations.




Voilà donc comment on peut déterminer combien de cycles d'attente il y a entre le chargement mémoire d'un registre et le moment où on peut envoyer ce registre dans l'ALU : il faut attendre un cycle entier (la dépendance RAW LS/EX prend 3 cycles en tout). Compte tenu du parallélisme superscalaire, ça veut dire qu'on peut caser jusqu'à 3 instructions entre la lecture et l'usage dans l'ALU (une en parallèle de la lecture, deux durant le cycle d'attente).

Je reviendrai sur ce genre de détails lugubres dans les techniques poussées d'assembleur ; pour cette technique je pense que j'ai fait le tour.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

Citer : Posté le 02/12/2022 14:47 | #


Optimisations des copies et écritures avec le DMA (Programmation générale — ★★☆)

Comme on a pu le voir dans d'autres techniques comme Accès aux mémoires, bus, et compromis taille/vitesse, les accès mémoire sont des opérations assez complexes, et si on accède à des puces mémoire qui sont physiquement éloignées du processeur les accès peuvent être assez longs.

L'exemple le plus évident de ça est le buffer de pixels dans lequel on dessine (appelé VRAM mais c'est juste une variable pas une puce de mémoire), puisqu'il est situé dans la RAM centrale qui est relativement distante, est très grand donc requiert beaucoup d'accès, et (on verra pourquoi) ne bénéficie pas beaucoup du cache.

Le DMA (ou plus précisément DMAC, Direct Memory Access Controller) est un module matériel qui peut aider à mitiger ce problème en automatisant des accès mémoire pour nous. Essentiellement le travail du DMA ressemble à :

  1. Lire une donnée dans une mémoire source ;
  2. Écrire cette donnée dans une mémoire cible ;
  3. Possiblement incrémenter le pointeur source et/ou le pointeur cible ;
  4. Recommencer.

Le rôle habituel d'un DMA, dans un ordinateur classique, est de copier des données entre différents périphériques ; par exemple, entre le contrôlleur USB et la RAM (pour recevoir des données envoyées par USB) ou entre la RAM et le GPU (pour envoyer des textures au GPU).

Sur la calculatrice, l'idée générale est la même, mais comme tout est dimensionné différemment, les cas d'usage seront différents. Par exemple, pour communiquer par USB, ce sera parfois plus rapide d'utiliser le CPU parce que les buffers sont petits ; ou alors, le DMA peut être assez rapide pour copier de la RAM vers la RAM, ce qui n'est pas rentable sur PC. Les benchmarks mémoire détailleront les vitesses de transfert.

Le «D» de DMA, qui signifie Direct, est important. Si on regarde le diagramme à blocs du SH-4A, on voit assez aisément que le CPU (en haut à gauche) et le DMA (qui n'est pas visible mais branché sur le bus périphérique en bas à droite) sont diamétralement opposés :


Si vous vous souvenez de ce qu'on disait dans la cartographie mémoire du SH4AL-DSP, vous remarquerez que le chemin entre le DMA et la RAM (derrière le BSC en passant par le SuperHyway) ne passe pas par le MMU et pas par le cache. Seuls les accès en provenance du CPU y passent. Ça veut dire que :

  • Le DMA ne connaît pas les adresses virtuelles.
  • Les accès mémoire par le DMA posent un problème de synchronisation de caches.

Je propose de commencer par là parce que c'est des problèmes qu'il vaut mieux connaître avant de se lancer (c'est casse-pieds à debugger), et après on pourra passer aux détails pratiques.

Le DMA est un périphérique d'adressage physique

Donc le DMA, lorsqu'il accède à la mémoire, ne voit pas le MMU. Même lorsqu'il accède aux mémoires internes du CPU (ILRAM, XRAM, YRAM) d'ailleurs, puisque le MMU ne traduit que de l'intérieur du CPU vers l'extérieur. Il y a deux régions de mémoire auxquelles on accède habituellement par des adresses virtuelles dans un add-in, et c'est le code et le segment de données.

Le segment de données. C'est la région à l'adresse 0x08100000 où l'OS donne de la RAM pour exécuter le programme (8 kio sur SH3, 32 kio sur Graph SH4 mono, 512 kio sur Graph 90+E). Il y a pas mal de données dans ce buffer, mais les seules qui utilisent l'adresse virtuelle sont les variables globales.

La raison de ce fait est plus claire dès qu'on s'intéresse à pourquoi cette zone est virtualisée. Le buffer derrière 0x08100000 est continu, c'est juste un bloc de RAM. La raison pour laquelle il est virtualisé c'est parce que son adresse physique change d'une version de l'OS à l'autre (par exemple quand le buffer a grandi entre SH3 et SH4), et le virtualiser permet de le présenter à une adresse fixe aux add-ins malgré ces déplacements.

Ça veut dire en particulier qu'une fois l'add-in démarré on peut tout à fait se permettre de consulter le MMU pour déterminer l'adresse physique associée et l'utiliser directement. C'est ce que fait la fonction mmu_uram() de gint. Les variables globales sont les seules données dans ce buffer dont l'adresse est choisie avant le début de l'exécution (spécifiquement à l'édition des liens) et qui doivent donc utiliser l'adresse 0x08100000.

Voilà ce qu'on y trouve d'autre. Il y a la pile à la fin (sauf sur SH3), mais c'est l'OS qui initialise l'adresse de la pile juste avant de lancer l'add-in, donc il peut mettre directement l'adresse physique, qu'il connaît. Il y a aussi la VBR, où gint stocke ses gestionnaires d'interruptions, mais pour des raisons architecturales la VBR ne peut pas utiliser une adresse virtuelle donc gint utilise mmu_uram() pour obtenir l'adresse physique. Et tout ce qui reste est fourni à malloc(), mais là aussi gint utilise l'adresse physique puisqu'on l'a sous la main.

La conclusion c'est que le DMA peut accéder au segment de données, mais seulement quand l'adresse physique est utilisée, ce qui n'est pas le cas pour une variable globale. Si vous voulez utiliser le DMA sur une variable globale (ce qui n'a vraiment de sens que sur Graph 90+E parce que les Graph mono la région n'est pas assez grande pour qu'utiliser le DMA ne soit rentable), il faudra d'abord traduire l'adresse virtuelle en adresse physique et purger le cache (voir plus bas).

Le code et données constantes. Pour le code, c'est plus simple. Le code est virtualisé à l'adresse 0x00300000. Sa source, c'est le fichier g1a/g3a dans la mémoire de stockage. La virtualisation permet de présenter le fichier (dont la position exacte dans la mémoire de stockage varie beaucoup) à une adresse fixe. Mais surtout, elle permet de le présenter en un seul morceau alors que dans la mémoire de stockage il est fragmenté.

Tout comme le segment de données, on peut consulter le MMU pour savoir où le code est dans la mémoire de stockage (en ROM). Mais comme il est fragmenté, on ne peut avoir que des petits bouts. Il est donc impossible d'aller lire des données dans le fichier d'add-in avec le DMA (par exemple une image convertie avec fxconv) parce que le DMA ne fait que des lectures continues et que l'image n'est fondamentalement pas continue.

Donc sauf à se casser pas mal la tête, le DMA ne peut pas lire le code ou les données constantes de l'add-in.

Le DMA contourne les caches

L'autre aspect des accès mémoire avec le DMA qu'on peut voir en regardant le diagramme en blocs du SH-4A c'est que son chemin d'accès à la mémoire (souvent la RAM et la ROM via le BSC) ne passe pas par le cache, ce qui peut poser un problème de cohérence.

N'oubliez pas que quand vous écrivez dans la mémoire, par défaut le cache "retient" l'écriture dans le sens où il modifie la donnée en interne mais il ne transmet pas l'ordre à la RAM. C'est seulement quand la page de cache où vous avez écrit se fait sortir au profit d'une autre que l'écriture est réalisée pour de vrai.

(Ce mode de fonctionnement d'un cache s'appelle Write-Back ou Copy-Back. Il y a un autre mode appelé Write-Through où les écritures sont toujours transmises instantanément. En général ça réduit beaucoup les performances puisque chaque écriture fait un accès RAM, alors que le cache pourrait les combiner intelligement. Ironiquement, sur la calculatrice ça ne va pas plus vite, les écritures dans la RAM principale ayant la même vitesse en Copy-Back, en Write-Through, et même sans cache du tout. On a donc les inconvénients du Write-Back sans les avantages du Write-Back.)

Comme il est difficile de prévoir combien de temps une page va rester dans le cache avant de se faire remplacer, il est difficile de savoir si la RAM a vraiment reçu l'ordre d'écriture. C'est important parce que le DMA, qui contourne le cache, peut tout à fait aller lire dans la RAM des données que le programme a modifié mais qui ne sont encore pas encore à jour dans la RAM parce que le cache retient l'écriture ! C'est la raison pour laquelle historiquement gint accède à la VRAM par P2 (ie. en contournant le cache). Si on laisse le cache actif, les opérations DMA comme dupdate() présenteront des glitchs visuels partout où le cache retient des écritures.

Il y a deux solutions possibles à ce problème : purger le cache, c'est-à-dire forcer les écritures en attente à se faire, ou bien ignorer entièrement le cache. Dans le cas de la VRAM comme on ne fait quasiment que des écritures et que le cache ne les accélère pas ; on peut donc l'ignorer (et éviter de le purger indirectement à chaque frame). Pour un buffer de données dans lequel on fait des lectures, le cache reste important donc il vaut mieux purger. On verra comment faire juste après les transferts ci-dessous.

Utilisation basique du DMA : dma_memset() et dma_memcpy()

Les cas d'utilisation les plus faciles du DMA sont via deux fonctions de <gint/mpu.h> : dma_memset() et dma_memcpy(). Ces deux fonctions sont analogues à memset() et memcpy(), excepté que :

  • La source et la destination doivent être accessibles au DMA (ie. pas virtualisés) ;
  • La source et la destination doivent être alignées à 32 octets ;
  • La taille doit être un multiple de 32 octets ;
  • Pour dma_memset() le motif de remplissage est 4 octets au lieu d'un seul octet.

Les 32 octets viennent des tailles de transfert possibles du DMA ; le plus grand transfert unitaire configurable (et donc généralement le plus rapide) est de 32 octets. On peut faire plus fin en détaillant les appels (voir ci-dessous).

L'intérêt principal de dma_memset() et dma_memcpy() est de manipuler de gros buffers en RAM qu'il serait plus lent d'utiliser via le CPU même avec le cache. Les écritures sont particulièrement lentes en RAM (le benchmark mémoire détaillera, mais sur la Graph 90+E on est sur du 400 Mo/s en lecture, 29 Mo/s en écriture) et donc les remplissages sont sensibles. L'exemple canonique de dma_memset() est donc naturellement dclear() sur Graph 90.

On peut aussi s'en servir en VRAM ; par exemple, le fond du jeu dans Duet utilise des carrés en rotation qui sont assez lents à générer ; pour maintenir des performances décentes, seule une ligne de carrés est dessinée ; le reste est ensuite dupliqué avec dma_memcpy().

Utilisation détaillée de dma_transfer_*()

gint fournit trois fonctions plus précises pour contrôler les transferts avec le DMA. Les trois fonctions utilisent le DMA de la même façon, mais diffèrent dans la méthode d'attente de la fin du transfert :

  • dma_transfer_async() effectue un transfert asynchrone. Elle donne l'ordre au DMA de transférer, puis retourne immédiatement. Le DMA effectue ensuite le transfert en tâche de fond pendant que le programme continue de s'exécuter. La fonction a un callback en argument (un gint_call_t) qu'elle appelle une fois le transfert fini, ce que le DMA lui communique via une interruption.
  • dma_transfer_sync() effectue un transfert synchrone ; elle démarre comme dma_transfer_async(), sauf qu'elle attend l'interruption indiquant la fin du transfert. De cette façon le transfert est forcément fini quand la fonction retourne, et donc il n'y a pas de callback.
  • dma_transfer_atomic() effectue aussi un transfert synchrone, mais sans interruption. Elle attend la fin du transfert en surveillant activement les registres du DMA. C'est utile si on n'a pas le contrôle des interruptions ou qu'on est dans un gestionnaire d'interruption (eg. un callback de timer).

Les paramètres des transferts sont les suivants :

  • Le canal DMA à utiliser (channel). Le numéro 1 est toujours disponible pour l'utilisater (dma_memset() et dma_memcpy() l'utilisent notamment).
  • La taille des transferts unitaires (size) et leur nombre (blocks). Le nombre d'octets transféré est donc size*blocks. Généralement à la fois la source et la destination doivent être alignées à size octets.
  • L'adresse source (src) ainsi que le mode d'incrémentation de cette adresse durant le transfert (src_mode). On peut incrémenter, decrémenter, ou rester sur place (ce qui est utile pour les périphériques comme l'écran ou l'USB).
  • L'adresse de destination (dst) et son mode d'incrémentation (dst_mode).

À ceci s'ajoute la fonction dma_transfer_wait() qui sert à attendre l'un fin d'un transfert démarré avec dma_transfer_async().

Par exemple, dma_memcpy() revient au code suivant (en ignorant les détails de la mémoire SPU) :

void *dma_memcpy(void *dst, void const *src, size_t size)
{
    dma_transfer_sync(1, DMA_32B, size >> 5, src, DMA_INC, dst, DMA_INC);
    return dst;
}

Purger le cache

Comme discuté précédemment, si la mémoire à faire manipuler par le DMA est accessible par le cache, alors il est possible que le cache retienne des écritures précédentes. Dans ce cas, il faut purger le cache avant de lancer le DMA. Cette opération se fait individuellement par ligne de cache (32 octets) avec l'instruction ocbp.

Pour purger le buffer buf de taille size du cache, on pourra donc écrire :

for(void *p = buf; p <= (void *)buf + size; p += 32) {
    __asm__("ocbp @%0" :: "r"(p));
}

Cela ne génère pas le code le plus véloce possible mais c'est un bon point de départ. (gint fournira certainement une fonction équivalente dans le futur.)
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24261 Défis: 170 Message

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!
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 43 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd