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.

---

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

---

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

---

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 :


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.

n	n²	n³	2n³	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.

---

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.

---

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.

---

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

---

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.

---

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.


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 :


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 :


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 :


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.

---

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.


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.


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) :


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


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 :


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 :


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 :


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.


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.


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.


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.


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.


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 :


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 :

• Documentation du SH4AL-DSP : jeu d'instructions, fonctionnement du processeur.
• Documentation du SH7724 et la bible : modules périphériques.

---

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 :


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 :


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.


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


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.

---

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!

---