La mémoire cache est un composant majeur des processeurs et sa mauvaise utilisation peut entraîner une baisse importante des performances d’un programme. Nous allons voir dans cet article quelques astuces pour mesurer les performances liées aux caches et éviter certains écueils.
Avec l’augmentation de la puissance des processeurs, l’accès aux données stockées en mémoire devient de plus en plus un goulot d’étranglement. Plusieurs techniques sont mises en œuvre par les fabricants de processeurs pour accélérer cet accès et éviter de perdre des cycles CPU à attendre les données. La première d’entre elles est l’ajout de mémoires caches rapides. Le premier CPU Intel disposant d’une mémoire cache intégrée au processeur était le 486 (1989). Parmi les autres techniques, on peut citer l’exécution dans le désordre (« out-of-order execution »), introduite sur les CPU Intel avec le Pentium Pro (1995), qui permet de masquer en partie la latence mémoire, et les systèmes de prélecture (« cache prefetching ») qui ont été introduits chez Intel sur les Pentium 3/4 (2000/2001) et qui permettent d’anticiper les futurs accès à la mémoire.
1. Architecture des caches d’un CPU
Sur un processeur moderne, la mémoire cache est typiquement organisée en 3 niveaux, du plus performant au moins performant (et du plus petit au plus gros) : L1, L2 et L3. Le cache L1 est lui-même divisé en deux parties : L1i pour le cache des instructions et L1d pour le cache des données. En général, chaque cœur du processeur dispose de son propre cache L1 et L2 (le cache L2 est parfois partagé entre plusieurs cœurs sur les processeurs économiques), mais le cache L3, de plus grosse capacité, est commun à tous les cœurs. Le cache L3 est aussi appelé parfois LLC pour « Last-Level Cache » ou « Longest-Latency Cache ».
À noter qu’il existe un dernier cache appelé TLB (« Translation Lookaside Buffer ») qui contient des correspondances entre adresses virtuelles et adresses physiques afin d’accélérer les accès mémoire.
Comparés aux accès à la mémoire centrale, les accès aux caches sont beaucoup plus rapides, d’un à deux ordres de grandeur, mais ces mémoires rapides sont aussi beaucoup plus chères, leur taille étant le résultat d’un compromis coût / efficacité. Optimiser le « cache hit » (probabilité d’accéder à la donnée voulue depuis un cache plutôt que depuis la mémoire) va donc permettre d'accroître très fortement la performance d’un programme.
Le mot « cache » est aussi utilisé au niveau du système d’exploitation pour parler de structures de données permettant d’enregistrer temporairement certaines données en vue d’un accès ultérieur plus rapide. Ces données sont stockées en mémoire centrale et sont utilisées en particulier pour accélérer les accès à des périphériques comme les disques durs, beaucoup plus lents que la mémoire de l’ordinateur.
2. Mesure des temps d’accès
Il est possible de faire une mesure relativement précise de la vitesse des différents caches et de la mémoire centrale avec lmbench, qui s’installe facilement sous Debian :
Le paquet lmbench est dans la section « non-free » de l’archive Debian, car son code est sous licence GPLv2, mais avec deux clauses restrictives complémentaires qui font que Debian ne le considère pas comme un logiciel libre. Il faut donc penser à rajouter la section « non-free » dans les lignes du fichier /etc/apt/sources.list (elle n’y est pas présente par défaut).
Lmbench dispose de plusieurs outils, dont lat_mem_rd que nous allons utiliser ici et qui est un benchmark de lecture mémoire. Son principe est le suivant : on met en mémoire un tableau d’une certaine taille et on mesure le temps de lecture de ces données. Si le tableau est suffisamment petit pour tenir dans le cache L1d, nous allons avoir un temps de lecture cohérent de la vitesse de lecture du cache L1d. Si le tableau est trop grand pour tenir dans le cache L1d, mais est plus petit que le cache L2, nous allons avoir un temps de lecture principalement dépendant de la vitesse de lecture du cache L2. Pareil pour le cache L3, et si le tableau est trop gros pour tenir dans les caches, alors on aura principalement des accès à la mémoire centrale.
Le petit script Python suivant permet d’automatiser le lancement de lat_mem_rd et de tracer les résultats sous la forme d’un graphique, avec en surimpression les tailles des différents caches. Il faut installer la bibliothèque matplotlib pour le tracé du graphique :
Le programme lat_mem_rd prend en argument la taille maximale (en Mo) du tableau de données, ainsi que le pas de lecture à l’intérieur de ce tableau (en octets). L’option -t ajoute de l’aléa dans l’ordre de lecture, ce qui permet de mettre en défaut les systèmes de prélecture du processeur (« hardware prefetchers », voir [1] pour plus d’informations sur ce mécanisme). La commande taskset est utilisée pour forcer l’exécution du benchmark uniquement sur le premier cœur (numéro 0) du processeur. Sans cela, l’ordonnanceur du système d’exploitation pourrait déplacer le programme sur différents cœurs au cours de son exécution, ce qui fausserait les résultats (les caches L1 et L2 étant spécifiques à chaque cœur). Sur la figure 2, nous avons tracé les résultats obtenus par le benchmark lat_mem_rd avec et sans l’option -t.
Les lignes rouges verticales indiquent les tailles des différents caches. On observe plusieurs « plateaux » qui correspondent à la vitesse de lecture des différentes mémoires (cache L1d, cache L2, cache L3 et mémoire DDR). La latence de lecture est bien plus faible (pour les caches L2 et L3, mais surtout pour la mémoire DDR) quand on lit les données avec un pas constant. En effet, ce pattern de lecture est détecté par le processeur et celui-ci anticipe les prochaines lectures en stockant les données correspondantes dans le cache L1d (ou L2, en fonction du « prefetcher » mis en œuvre). En revanche, dans le cas d’une lecture aléatoire, la prélecture ne fonctionne pas et on peut mesurer la « vraie » durée d’accès à la mémoire.
3. Les pièges à éviter
On peut penser que le cache, c’est magique, et qu’il suffit d’en avoir (plein) pour accélérer les traitements. Nous allons voir qu’il existe malheureusement certains pièges à éviter pour ne pas perdre tout l’intérêt de ces mémoires rapides.
Les exemples de code suivants sont compilés sans activer les optimisations du compilateur. En effet, s’agissant d’exemples très simples à vocation didactique, les problèmes qu’ils tentent d’illustrer sont facilement contournables par les techniques d’optimisation du compilateur. Ce ne serait cependant plus le cas sur des cas réels plus complexes.
3.1 Optimisation du « cache-hit »
Le petit programme suivant va permettre d’illustrer l’impact d’une mauvaise utilisation du cache. On crée deux gros tableaux représentant des matrices (donc des objets avec 2 dimensions, un nombre de lignes et un nombre de colonnes). Ces tableaux sont initialisés avec des valeurs dans une première section avec une double boucle for (sur les lignes et sur les colonnes), puis on effectue une multiplication terme à terme qui est cumulée dans la variable result. Cette variable est ensuite utilisée comme code de retour du programme, ceci afin d’éviter une optimisation du compilateur qui pourrait supprimer la quasi-totalité du code si celui-ci n’avait aucun effet de bord.
On compile, puis on lance le programme avec time pour mesurer son temps d’exécution :
Modifions maintenant le programme en intervertissant les boucles : au lieu de boucler d’abord sur les lignes, puis sur les colonnes, nous allons maintenant d’abord boucler sur les colonnes, puis sur les lignes. D’un point de vue mathématique, le nouveau programme est totalement équivalent au précédent. Et pourtant, le temps d’exécution est totalement différent :
Le temps d’exécution a été multiplié par quatre ! Que s’est-il passé ? Dans la première version du programme, le tableau est lu dans le sens de la mémoire. Ainsi, quand le programme va vouloir lire une première case du tableau, c’est en fait l’équivalent de toute une ligne de cache qui va être lue en mémoire et stockée dans le cache. La taille d’une ligne de cache est généralement de 64 octets. On peut le vérifier avec la commande suivante :
Lors de la lecture des cases suivantes du tableau, celles-ci seront donc le plus souvent directement lues dans le cache. En revanche, dans la seconde version du programme, la lecture se fait par sauts dans la mémoire, et donc la donnée recherchée n’est jamais dans le cache, obligeant à effectuer des lectures en RAM très lentes.
Pour s’en convaincre et mesurer plus finement le pourcentage de réussite et d’échec du cache (« cache hit » et « cache miss »), nous allons utiliser l’outil perf [2]. Il s’installe de la façon suivante :
Cet outil permet de mesurer un grand nombre d’événements, que l’on peut lister avec la commande suivante :
Nous allons ici utiliser perf pour mesurer le pourcentage d’échecs du cache via les événements cache-misses (nombre d’accès mémoire qui n’ont pas pu être servis par le cache) et cache-references (nombre total de tentatives d’accès mémoire via le cache).
Le résultat est sans appel : on passe d’un « cache-miss » d’environ 9,5 % (donc un « cache hit » de 90,5 %) pour la première version à un « cache-miss » de 82,5 % (donc un « cache hit » de 17,5 %) pour la seconde.
Les résultats précédents ont été obtenus avec un processeur Intel Core i5-2520M, assez ancien. Sur un processeur plus récent, les résultats peuvent être totalement différents, voire même contre-intuitifs, avec un « cache hit » plus important pour le code le plus lent. En effet, les compteurs matériels utilisés par perf n’ont pas toujours la même sémantique d’un processeur à l’autre. Par exemple, les accès de certains prefetchers peuvent être comptabilisés ou non, selon le processeur. La documentation d’Intel [3] reste vague sur le sujet. Par exemple, la documentation du compteur « Last Level Cache Misses » indique : « This event counts each cache miss condition for references to the last level on-die cache. The event count may include speculation and cache line fills due to the first-level cache hardware prefetcher, but may exclude cache line fills due to other hardware-prefetchers. Because cache hierarchy, cache sizes and other implementation-specific characteristics; value comparison to estimate performance differences is not recommended. »
3.2 Faux partage
Le « faux partage » (ou « false sharing » en anglais) est une situation, dans un contexte avec plusieurs threads, qui va engendrer une forte dégradation des performances, de façon similaire à l’utilisation d’une variable partagée entre 2 threads. Le problème est illustré dans la figure 3.
Le thread0 écrit une donnée qui se trouve dans une ligne de cache, provoquant l’invalidation de cette ligne de cache pour tous les cœurs du processeur. Le thread1, qui se contentait de lire une donnée qui était « à côté » dans la même ligne de cache, va devoir recharger toute la ligne de cache depuis la mémoire centrale, alors que ce n’était pas nécessaire, provoquant une forte baisse de performance.
Nous allons illustrer ce problème avec le programme suivant. Il s’agit ici de sommer tous les éléments d’un gros tableau à deux dimensions (non initialisé, ça n’a pas d’importance dans cet exemple). Afin d’accélérer le traitement, le programme utilise plusieurs threads qui vont chacun faire la somme des éléments d’une partie des lignes du tableau, et stocker cette somme partielle dans une variable dédiée pour chaque thread. La somme finale est obtenue en sommant ces sommes partielles, et elle sert de code de retour du programme afin que le compilateur n’optimise pas en supprimant du code « inutile ».
La gestion du multithreading est très simple et utilise les annotations du standard OpenMP (sujet déjà traité dans GLMF, voir [4] et [5]). La boucle for de plus haut niveau est ainsi parallélisée sur un certain nombre de threads (en fonction de la valeur de NB_THREADS). Chaque thread utilise une case dédiée du tableau results pour stocker son résultat intermédiaire, le numéro de la case du tableau étant déterminé grâce à la fonction omp_get_thread_num() qui renvoie le numéro du thread en cours.
Le programme se compile avec la commande suivante :
La figure 4 montre le temps d’exécution en fonction du nombre de threads (courbe bleue). L’augmentation du nombre de threads n’a quasiment aucun impact sur le temps d’exécution, alors que l’algorithme semble totalement parallélisable et sans aucune contention. Le phénomène de « false sharing » se produit en fait sur le tableau results contenant les résultats intermédiaires. À chaque fois qu’un des threads modifie son résultat intermédiaire, toute la ligne de cache contenant cette donnée ainsi que les données adjacentes est invalidée. Ainsi, lorsqu’un autre thread essaye d’accéder à son résultat intermédiaire pour lecture puis modification, cette donnée n’est plus considérée comme étant valide dans le cache (alors que pourtant elle l’est), et la ligne de cache doit être rechargée depuis la RAM.
Sur un cas trivial comme celui-ci, la solution la plus simple pour éviter ce problème serait de tout simplement utiliser une variable locale à chaque thread pour le calcul des sommes partielles. C’est d’ailleurs une solution équivalente à celle utilisée par le compilateur quand on active les optimisations sur cet exemple (on peut vérifier cela avec la commande gcc -S -masm=intel -fverbose-asm -O3 false_sharing.c), puisque celui-ci utilise un registre du processeur pour faire l’accumulation au niveau de chaque thread et n’écrit que la valeur finale dans le tableau results, à la fin du bloc de code parallélisé. Dans un cas plus général et plus complexe, il n’est souvent pas possible d’utiliser des variables locales à chaque thread. Dans ce cas, il faut faire en sorte que les données utilisées par chaque thread ne se trouvent pas dans la même ligne de cache que les données utilisées par un autre thread. Pour cela, il suffit de rajouter l’équivalent d’une ligne de cache (64 octets) entre elles. Dans le cas précédent, on pourrait par exemple changer le tableau de flottants results en un tableau de structures qui incluraient une zone de bourrage.
Avec cette modification, on obtient la courbe rouge sur la figure 4 : le temps d’exécution devient inversement proportionnel au nombre de threads, ce qui était le résultat attendu.
Conclusion
Cet article a été l’occasion de présenter le fonctionnement général des mémoires caches et de montrer certaines techniques de programmation pour en tirer le meilleur parti. À noter que même si nous avons illustré tous ces concepts par du code C, les mêmes principes restent valables pour tous les langages, y compris ceux de haut niveau comme Java, par exemple. Le lecteur intéressé par les problématiques de performance pourra se plonger dans le livre [6] qui aborde de nombreuses thématiques (CPU, mémoire, systèmes de fichiers, disque, réseau, outils perf, ftrace, bpf…).
Références
[1] Support de cours « Memory Prefetching » de l’université Stony Brook :
https://compas.cs.stonybrook.edu/~nhonarmand/courses/sp16/cse502/slides/13-prefetch.pdf
[2] Tutoriel sur l’outil perf : https://perf.wiki.kernel.org/index.php/Tutorial
[3] Intel 64 and IA-32 Architectures Software Developer's Manual Combined Volumes 3A, 3B, 3C, and 3D: System Programming Guide, chapitre 20.2 « Architectural Performance Monitoring » : https://www.intel.com/content/www/us/en/content-details/819717/intel-64-and-ia-32-architectures-software-developer-s-manual-combined-volumes-3a-3b-3c-and-3d-system-programming-guide.html
[4] « Découverte de la programmation parallèle avec OpenMP », Jean-Baptiste Vioix, GNU/Linux Magazine n°122, décembre 2009 - https://connect.ed-diamond.com/GNU-Linux-Magazine/glmf-122/decouverte-de-la-programmation-parallele-avec-openmp
[5] « Une introduction à la programmation parallèle avec Open MPI et OpenMP », Alban Mancheron, GNU/Linux Magazine HS n°99, novembre 2018 - https://connect.ed-diamond.com/GNU-Linux-Magazine/glmfhs-099/une-introduction-a-la-programmation-parallele-avec-open-mpi-et-openmp
[6] Livre « Systems Performance, Enterprise and the Cloud, 2nd edition », Brendan Gregg (ISBN-13 : 978-0-13-682015-4).