Mémoire cache et optimisation du code

Une bonne optimisation consiste à diminuer la quantité d'octets utilisés pour le padding, et éventuellement de le faire disparaître. Comme on le verra plus tard, il existe différentes méthodes pour éliminer ce padding, quel que soit le langage de programmation utilisé.

Pour le moment, nous allons nous limiter à aborder un conseil valable pour le C et le C++. Dans ces langages, on peut éviter de gaspiller de la mémoire inutilement en faisant attention à l'ordre de déclaration de nos variables. Par exemple, si on reprend le tableau du dessus, on peut gagner quatre octets facilement. Il suffit de déclarer la structure comme ceci :

typedef struct Exemple
{
    unsigned int entier_long;
    short entier_court ;
    char lettre;
} Exemple;

Si on regarde bien, cette structure donnerait ceci en mémoire :

Ce qui prend seulement huit octets au lieu de douze. Certains octets de padding ont été éliminés. Moralité : programmeurs, si vous voulez économiser de la mémoire, faites gaffe à bien gérer l'alignement en mémoire ! Essayez toujours de déclarer vos variables de façon à remplir un mot intégralement ou le plus possible.

Une bonne heuristique consiste à déclarer les données dans la structure de la plus grande à la plus petite : les données qui prennent le plus d'octets doivent être placées en tout début de structure, tandis que les plus légères doivent être placées en toute fin. Mais cela ne marche que si les données ont une taille qui est une puissance de deux : avec des données de trois ou sept octets, cela ne peut pas marcher.

Il faut noter que dans certains cas, il peut être avantageux d'ajouter du padding, histoire d'éviter certaines formes assez spéciales de cache miss (ces conflicts miss pour ceux qui connaissent). Mais cela ne fonctionne que dans des circonstances particulières, sur certains types de caches particuliers : les caches direct mapped et N-way Asociative. Je n'en parlerai pas tout de suite, mais je reviendrai dessus plus tard.

D'ordinaire, les programmeurs ont tendance à rassembler plusieurs structures dans des tableaux (ils peuvent aussi utiliser d'autres structures de données selon leurs besoins, mais passons).

Cependant, toutes les données d'une structure ne sont pas utiles en même temps et vous n'avez pas toujours besoin de tous les champs : seule une partie des champs est accédée et modifiée, tandis que certains champs sont laissés intacts. Certains champs de la structure sont fréquemment accédés ensemble, tandis que d'autres champs sont assez peu utiles.

Avec un tableau de structures, tous les champs d'une structure sont chargés dans le cache, même ceux qui sont inutiles. Pour éviter cela, on peut utiliser la technique du Hot/cold spilting. Celle-ci consiste à séparer les données fréquemment utilisées des données peu fréquemment utilisées dans des structures séparées. La première structure contiendra les données les plus fréquemment utilisées, ainsi qu'un pointeur vers l'autre structure. Cette autre structure contiendra les champs restants, peu fréquemment utilisés, et éventuellement un pointeur vers la première structure.

Avec cette technique, le parcours d'un tableau de structures ne chargera que la structure qui contient les données les plus fréquemment utilisées. Les autres données ne seront chargées que si le besoin s'en fait sentir, en passant par l'intermédiaire de la première structure.

Cependant, il existe une autre organisation, qui donne de meilleurs résultats du point de vue de la mémoire cache, et qui est systématiquement conseillée dans les guides d'optimisations publiés par Intel et AMD : utiliser des structures de tableaux en lieu et place de tableaux de structures.

Il faut toutefois préciser quelque chose sur cette différence entre SoA (Structure of Array) et AoS (Array of Structure) : la méthode SoA ne donne de bons résultats que pour des données qui sont suffisamment volumineuses. Plus précisément, si le tableau tout entier arrive à tenir dans la mémoire cache de niveau L1/L2, l'amélioration ne sera pas spectaculaire, et vous risquez même d'obtenir une baisse de performances dans certains cas. Par contre, si la taille du tableau est supérieure, vous obtiendrez systématiquement un gain.

Reprenons cette structure d'exemple, et créons un tableau de 1 500 000 de ces structures :

typedef struct Exemple
{
    unsigned int entier_long;
    char lettre;
} Exemple;

Exemple tableau[1500000] ;

Si l'on crée un tableau de 1 500 000 structures de type « Exemple », le compilateur va automatiquement insérer du padding dans chaque structure. Ce qui fait que le char d'une structure sera séparé du int de la structure suivante par du padding, qui prendra inutilement de la mémoire cache.

À la place, il est recommandé de ne pas utiliser un tableau, mais plusieurs : un par champ de la structure. Dans l'exemple du dessus, on devrait utiliser deux tableaux de 1 500 000 éléments : un tableau qui stocke les int de chaque structure et un autre pour les char.

typedef struct Tableau_Exemple
{
    unsigned * tableau_entiers ;
    char * tableau_lettre;
} Tableau_Exemple;

En faisant cela, les int sont alignés en mémoire sans qu'il y ait besoin de padding, et c'est la même chose pour les char : le padding disparaît.

De plus, quand vous parcourez une structure, vous n'avez pas toujours besoin de tous les champs : seule une partie des champs est accédée et modifiée, tandis que certains champs sont laissés intacts. Avec un tableau de structures, tous les champs d'une structure sont chargés dans le cache. Mais ce n'est pas le cas avec une structure de tableaux : seuls les tableaux des champs utiles sont parcourus, pas les autres. L'économie en cache et en bande passante mémoire est donc appréciable.

Sous certaines conditions, il vaut donc mieux utiliser plusieurs tableaux regroupés dans une seule structure, avec un tableau pour chaque champ de la structure. Les conditions pour cela sont simples :

• un faible nombre de champs doivent être visités lors du parcours des tableaux ;
• la taille du tableau doit être suffisante pour dépasser la taille du cache ;
• les accès au tableau doivent être des accès séquentiels.

Cette technique permet d'économiser de la mémoire et donne de bons résultats, quel que soit le cache, ou les algorithmes de prefetch utilisés par le processeur. Les gains peuvent être assez impressionnants : on peut doubler, voire tripler la vitesse de votre code source.

Cette technique peut aussi s'appliquer aux tableaux multidimensionnels et aux matrices, même si le gain est clairement moindre.

On peut aussi citer le fait que, pour des raisons relativement techniques (liées à l'associativité du cache), il est préférable de regrouper des tableaux unidimensionnels séparés dans un seul tableau multidimensionnel. Ainsi, on peut transformer une structure de tableaux en un seul tableau multidimensionnel sans problèmes.

Mais évidemment, cela ne marche pas toujours : il faut que les données soient de même type. À défaut, certains n'hésiteront pas à contourner cette contrainte en utilisant des unions, mais je ne conseille pas cette pratique.

Dans la majorité des langages objet, ces tableaux qui contiennent des objets (des types non primitifs) sont soit simplement des tableaux de références, soit des tableaux de pointeurs (oui, j'ai dit pointeur, et si ça ne vous plaît pas, c'est le même tarif). En conséquence, les objets ne sont pas absolument pas consécutifs en mémoire.

Selon quelques études faites sur le sujet, c'est une des raisons qui font que le Java est plus lent que le C. Il y a sûrement moyen d'éviter cela, en utilisant les constructions du langage, mais je ne les connais malheureusement pas.

Cependant, il existe des situations où utiliser des tableaux de pointeurs donne un avantage certain en matière de performances : cela permet de ne pas dupliquer des données. Prenons un tableau de structures, ces structures étant assez grosses. Il arrive parfois que certaines structures soient identiques : la même structure est présente plusieurs fois dans le tableau, à des indices différents. Dans ce cas, il vaudrait mieux n'utiliser qu'un seul exemplaire de cette structure, pour diminuer l'occupation de la mémoire.

Dans ce cas, les tableaux de pointeurs permettent d'éviter de tels doublons. Il suffit d'utiliser un tableau de structures dans lequel les structures ne sont présentes qu'en un seul exemplaire (sans doublons), et un second tableau de pointeurs. Le tableau de pointeurs sert à effectuer la correspondance indice → pointeur vers la structure demandée. À partir de ce pointeur, on peut alors accéder à la structure voulue. Cette organisation est ce qu'on appelle un vecteur de Liffe.

Ces vecteurs de Liffe permettent donc de diminuer l'occupation de la mémoire, en évitant les doublons. L'avantage est clair en matière de cache. De plus, le premier accès à une structure va charger celle-ci en cache : les accès suivants à cette structure peuvent être améliorés si jamais la donnée est encore en cache lors de ceux-ci. Avec un tableau de structures, chaque accès à une structure va charger celle-ci depuis la mémoire.

Cette technique peut aussi s'appliquer aux tableaux multidimensionnels et aux matrices : on obtient alors des matrices creuses.

Prenons le tableau à deux dimensions suivant :

Comme vous le voyez, il s'agit d'un tableau d'entiers, à deux dimensions, comprenant trois lignes et trois colonnes.

Dans certains langages, comme le C, le C++ ou le FORTRAN, toutes les données du tableau sont stockées les unes à côté des autres en mémoire. En clair, les données stockées dans un tableau à plusieurs dimensions sont rassemblées dans un tableau à une seule dimension : les lignes ou les colonnes d'un tableau multidimensionnel sont stockées les unes à la suite des autres.

Ceci dit, il nous reste un petit détail à régler. Si je prends le tableau ci-dessus, je peux parfaitement stocker celui-ci dans un seul tableau, mais de deux façons différentes. Je peux tout stocker dans un tableau en mettant les colonnes les unes après les autres.

C'est cette solution qui est utilisée dans des langages de programmation comme FORTRAN, mais ce n'est pas le cas en C. En C, nos tableaux sont stockés ligne par ligne.

La morale, c'est que l'on observera de grosses différences de performances suivant que l'on parcoure un tableau ligne par ligne ou colonne par colonne. En C, le parcours ligne par ligne sera nettement plus rapide, vu que les lignes sont placées les unes après les autres, on accédera à des données consécutives en mémoire : le parcours se résumera en un simple parcours de tableau unidimensionnel. Par contre, le parcours colonne par colonne ne permettra pas d'accéder à des données consécutives : deux colonnes consécutives ne se suivent pas en mémoire, et les performances seront désastreuses.

Un bon exemple est celui de la multiplication de deux matrices. Lors du calcul de A fois B, la matrice A est parcourue ligne par ligne tandis que l'autre l'est colonne par colonne. Dans ces conditions, il vaut mieux faire en sorte que la matrice A soit stockée ligne par ligne, tandis que l'autre l'est colonne par colonne. Donc, avec un algorithme de calcul adapté pour obtenir le bon résultat, on peut obtenir des gains de performances.

Il faut noter que, comme pour les tableaux unidimensionnels, les performances ne seront pas les mêmes entre une structure de tableaux multidimensionnels comparée à un tableau multidimensionnel de structures.

Si la majorité des langages se basent sur un stockage ligne par ligne ou colonne par colonne, des chercheurs ont inventé des matrices qui ne se basent pas sur ce genre de principes. Il existe de nombreuses organisations, comme les matrices de Morton. Évidemment, les algorithmes qui manipulent ces matrices doivent être adaptés pour tenir compte de l'ordre des données en mémoire. Le principe est de découper les matrices en sous-matrices et de stocker celles-ci en mémoire les unes à la suite des autres.

L'astuce qui se cache derrière ces matrices est celle qui est à l'origine de tous les algorithmes optimisés pour le cache. Ces algorithmes sont des algorithmes de type diviser pour régner récursifs : ils décomposent un problème en sous-problèmes identiques, mais qui agissent sur une portion de la donnée originale. Au lieu de traiter toute la donnée d'un coup, on la traite partie par partie avant de fusionner les résultats obtenus avec chaque portion de la donnée.

L'astuce, c'est qu'une donnée complète (ici, la matrice complète) ne tient pas totalement dans le cache, ce qui est la cause de nombreux cache miss. Par contre, une sous-donnée peut tenir complètement dans le cache, ce qui rend son traitement particulièrement rapide. Dans notre exemple, une matrice complète a peu de chances de tenir dans le cache, alors qu'une sous-matrice peut.

Évidemment, ces algorithmes donnent de meilleurs résultats si les données sont organisées de manière à faciliter l'implémentation de ces algorithmes. Par exemple, un algorithme de recherche dichotomique doit agir sur un tableau trié, de même qu'un algorithme de multiplication de matrice récursif, qui agit sous-matrice par sous-matrice, gagne clairement à avoir des matrices explicitement découpées en sous-matrices. Et c'est le but des organisations de matrice qui vont suivre.

Commençons par les matrices 4D. Avec ces structures de données, la matrice à stocker est découpée en sous-matrices rectangulaires, de hauteur M et de largeur N. Ces sous-matrices sont stockées comme une matrice normale, soit ligne par ligne, soit colonne par colonne. Ces sous-matrices sont placées les unes à la suite des autres en mémoire.

Là encore, il y a deux possibilités pour le stockage des sous-matrices : en ligne ou en colonne.

Les sous-matrices doivent avoir une taille optimale pour obtenir les meilleures performances. Dans les faits, chaque sous-matrice doit tenir dans le cache du processeur, et doit voir sa taille varier suivant la quantité de données qui peuvent être stockées dans une ligne de cache. Or, cette taille n'est pas connue et dépend de nombreux paramètres, qui dépendent de l'ordinateur. On peut donc optimiser la taille des matrices pour un ordinateur en particulier, mais sans obtenir un résultat optimal sur toutes les architectures.

Les matrices de Morton permettent de résoudre ce problème. Dans celles-ci, la matrice est découpée en quatre sous-matrices de même largeur et longueur. Elles sont stockées dans cet ordre dans la mémoire :

• d'abord la matrice en haut à gauche ;
• puis celle en haut à droite ;
• puis celle en bas à gauche ;
• puis celle en bas à droite.

Puis, chaque sous-matrice subit le même sort et la même procédure est appliquée de manière récursive. On arrête lorsque la matrice obtenue ne contient qu'un seul élément.

On peut trouver d'autres organisations, comme dans les matrices de Hilbert (basées sur la courbe de Hilbert) ou de Gray-Morton, qui se différencient par l'ordre de stockage des sous-matrices.

Cette organisation récursive est clairement un atout qui permet de ne pas avoir à se soucier de la taille optimale des sous-matrices : quelle que soit la taille du cache, on trouvera forcément une sous-matrice qui aura la taille adéquate.

Dans ces conditions, linéariser les listes chaînées est une bonne chose. Et cela peut être fait de plusieurs manières.

Dans certains langages, comme le LISP, les listes sont implémentées en utilisant ce qu'on appelle le CDR coding. Mais cette méthode n'est clairement pas facile à utiliser dans des langages non fonctionnels (il vaut mieux avoir des listes immuables avec ce CDR coding).

Une seconde solution, nettement plus utilisable, consiste à mémoriser plusieurs éléments par nœud dans la liste. En clair : la liste chaînée est transformée en une liste de tableaux, chaque tableau correspondant à un nœud de la liste. On obtient alors une unrolled linked list.

Dans la majorité des implémentations, chaque nœud de la liste a une taille finie : tous les tableaux ont la même taille, qui est généralement celle d'une ligne de cache. Seulement, il n'est pas obligatoire que les tableaux soient totalement remplis.

À chaque nœud, on doit donc non seulement stocker le tableau et le pointeur vers le nœud suivant, mais aussi le nombre de cases du tableau qui contiennent quelque chose.

L'accès à un élément bien précis dans la liste demande donc de tenir compte du nombre d'éléments présents dans un tableau, ce qui complique le code de parcours d'une telle liste. L'insertion et la suppression d'un élément sont aussi nettement plus compliquées pour les mêmes raisons. Reste à implémenter tout cela.

Une autre solution consiste à remplacer les listes par ce que l'on appelle un Packed Memory Array. Il s'agit d'un tableau dans lequel on laisse des « trous » entre deux éléments successifs : cela permet de supporter des insertions et suppressions de données relativement rapides.

Des versions améliorées ont été proposées dans les articles suivants :

• An Adaptative Packed Memory Array ;
• Partially Deamortized Packed-Memory Array.

Commençons par le plus simple : les arbres binaires (non triés, pour commencer). Ceux-ci peuvent être implémentés avec un simple tableau, réduisant la dispersion des données en mémoire, et éliminant les pointeurs (qui pompent de la mémoire et nuisent à un alignement correct des nœuds de l'arbre en mémoire). Sur le principe, il suffit de faire comme ceci :

Autant dire que cette implémentation est idéale pour les parcours en largeur, qui se réduisent en une simple boucle qui parcourt le tableau dans l'ordre séquentiel. Avec l'implémentation usuelle, on se retrouve avec un cache miss pour chaque nœud de l'arbre : la complexité en défauts de cache est donc en O(n). Alors qu'avec l'implémentation sous forme de tableau, le nombre de cache miss tombe à zéro sur du matériel moderne.

Pour les parcours en profondeur, cette organisation permet de diminuer le nombre de cache miss, mais il ne faut pas trop en attendre : cela permet de diminuer la quantité de cache miss d'un facteur constant.

Il existe une autre solution pour stocker les arbres binaires avec un tableau : utiliser ce que l'on appelle le layout de Van Emde Boas. Avec lui, l'arbre est toujours stocké en mémoire dans un tableau, mais la répartition des données dans le tableau est différente : l'arbre est découpé en sous-arbres, de manière récursive.

Le principe consiste à décomposer l'arbre en sous-arbres, qui sont eux-mêmes décomposés en sous-arbres et ainsi de suite. Ainsi, il arrivera un moment où un sous-arbre pourra tenir tout seul dans le cache (ou dans une ligne de cache). C'est encore le principe du diviser pour régner récursif, appliqué aux structures de données. Reste à voir comment appliquer ce principe aux arbres binaires de recherche.

Prenons un arbre contenant N éléments, qui est de hauteur H. On supposera que la hauteur est une puissance de deux (si ce n'est pas le cas, prendre la puissance de deux supérieure). L'idée est de couper l'arbre à mi-hauteur en deux morceaux. Le premier morceau est celui qui contient la racine, de hauteur H/2, qui contient kitxmlcodeinlinelatexdvp\sqrt{N}finkitxmlcodeinlinelatexdvp nœuds. L'autre morceau est composé de kitxmlcodeinlinelatexdvp2^{H/2}finkitxmlcodeinlinelatexdvp sous-arbres : chaque feuille du premier sous-arbre sert de racine à chacun de ces sous-arbres.

Tous les sous-arbres sont alors mémorisés les uns à la suite des autres dans le tableau :

• d'abord on place le sous-arbre qui contient la racine ;
• puis on place successivement chacun des sous-arbres du second morceau, en partant de gauche à droite.

Chacun de ces sous-arbres est décomposé en suivant le même principe, récursivement. Le découpage s'arrête une fois que l'on obtient un arbre de taille 1.