Comment écrire un code qui utilise le mieux le cache du processeur pour améliorer les performances?

Cela pourrait sembler être une question subjective, mais ce que je recherche, ce sont des cas spécifiques que vous auriez pu rencontrer en rapport avec cela.

  1. Comment créer du code, mettre le cache en vigueur / respecter le cache (plus de visites au cache, moins de cache possible)? Dans les deux outlook, le cache de données et le cache de programme (cache d’instructions), c’est-à-dire les éléments du code liés aux structures de données et aux constructions de code, devraient être pris en compte pour le rendre efficace.

  2. Existe-t-il des structures de données particulières à utiliser / éviter, ou existe-t-il un moyen particulier d’accéder aux membres de cette structure, etc. pour rendre le cache de code efficace.

  3. Existe-t-il des constructions de programme (if, for, switch, break, goto, …), code-flow (pour l’intérieur d’un if, if à l’intérieur d’un for, etc …), on devrait suivre / éviter en la matière?

J’ai hâte d’entendre des expériences individuelles liées à la création d’un code efficace de cache en général. Il peut s’agir de n’importe quel langage de programmation (C, C ++, Assembly, …), de toute cible matérielle (ARM, Intel, PowerPC, …), de tout système d’exploitation (Windows, Linux, Smbian, …), etc. .

La variété aidera à mieux le comprendre.

Le cache est là pour réduire le nombre de fois que le processeur est bloqué dans l’attente d’une demande de mémoire (évitant la latence de la mémoire) et, éventuellement, pour réduire la quantité totale de données à transférer (en préservant bande passante mémoire).

Les techniques pour éviter de souffrir de la latence de récupération de mémoire sont généralement les premières à prendre en compte, et aident parfois longtemps. La bande passante mémoire limitée est également un facteur limitant, en particulier pour les applications multicœurs et multithread où de nombreux threads souhaitent utiliser le bus mémoire. Un ensemble différent de techniques aide à résoudre ce dernier problème.

L’amélioration de la localisation spatiale signifie que vous vous assurez que chaque ligne de cache est utilisée intégralement une fois qu’elle a été mappée sur un cache. Lorsque nous avons examiné divers points de référence standard, nous avons constaté qu’une fraction étonnamment importante de ceux-ci n’utilisent pas 100% des lignes de cache récupérées avant que les lignes de cache ne soient expulsées.

L’amélioration de l’utilisation des lignes de cache aide à trois égards:

  • Il a tendance à contenir plus de données utiles dans le cache, augmentant essentiellement la taille effective du cache.
  • Il a tendance à contenir plus de données utiles dans la même ligne de cache, ce qui augmente la probabilité que les données demandées puissent être trouvées dans le cache.
  • Il réduit les besoins en bande passante mémoire, car il y aura moins de récupérations.

Les techniques courantes sont:

  • Utiliser des types de données plus petits
  • Organisez vos données pour éviter les trous d’alignement (le sorting des membres de votre structure par taille décroissante est à sens unique)
  • Faites attention à l’allocateur de mémoire dynamic standard, qui peut introduire des trous et répartir vos données en mémoire au fur et à mesure qu’il se réchauffe.
  • Assurez-vous que toutes les données adjacentes sont réellement utilisées dans les boucles dynamics. Sinon, envisagez de diviser les structures de données en composants chauds et froids, de sorte que les boucles chaudes utilisent des données à chaud.
  • éviter les algorithmes et les structures de données qui présentent des schémas d’access irréguliers et favoriser les infrastructures de données linéaires.

Nous devons également noter qu’il existe d’autres moyens de masquer la latence de la mémoire que l’utilisation de caches.

Les processeurs modernes ont souvent un ou plusieurs pré-récupérateurs de matériel . Ils s’entraînent sur les miss dans une cache et tentent de repérer les régularités. Par exemple, après quelques échecs sur les lignes de cache suivantes, le préfeteur hw commence à récupérer les lignes de cache dans le cache, anticipant les besoins de l’application. Si vous disposez d’un modèle d’access standard, le préfiltre matériel effectue généralement un très bon travail. Et si votre programme n’affiche pas les modèles d’access standard, vous pouvez améliorer les choses en ajoutant vous-même des instructions de lecture anticipée .

En regroupant les instructions de manière à ce que celles qui manquent toujours dans le cache se produisent à proximité les unes des autres, le processeur peut parfois se chevaucher afin que l’application ne supporte qu’un seul coup de latence ( parallélisme au niveau de la mémoire ).

Pour réduire la pression globale du bus de mémoire, vous devez commencer par traiter ce que l’on appelle la localité temporelle . Cela signifie que vous devez réutiliser les données alors qu’elles n’ont toujours pas été expulsées du cache.

Les boucles de fusion qui touchent les mêmes données ( fusion de boucle ) et qui utilisent des techniques de réécriture connues sous le nom de mosaïque ou de blocage visent toutes à éviter ces extractions de mémoire supplémentaires.

Bien qu’il existe quelques règles de base pour cet exercice de réécriture, vous devez généralement considérer avec soin les dépendances de données transmises en boucle, pour vous assurer que vous n’affectez pas la sémantique du programme.

C’est ce qui rapporte vraiment dans le monde multicœur, où l’on ne voit généralement pas beaucoup d’améliorations du débit après l’ajout du deuxième thread.

Je ne peux pas croire qu’il n’y a pas plus de réponses à cela. En tout cas, un exemple classique consiste à itérer un tableau multidimensionnel “à l’envers”:

pseudocode for (i = 0 to size) for (j = 0 to size) do something with ary[j][i] 

La raison pour laquelle ce cache est inefficace est que les processeurs modernes chargeront la ligne de cache avec des adresses mémoire «proches» de la mémoire principale lorsque vous accédez à une seule adresse mémoire. Nous parcourons les lignes “j” (externes) du tableau dans la boucle interne, donc pour chaque trajet à travers la boucle interne, la ligne de cache sera vidée et chargée avec une ligne d’adresses proches du [ j] [i] entrée. Si cela est changé à l’équivalent:

 for (i = 0 to size) for (j = 0 to size) do something with ary[i][j] 

Il fonctionnera beaucoup plus vite.

Je recommande de lire l’article en 9 parties Ce que chaque programmeur devrait savoir sur la mémoire d’Ulrich Drepper si vous êtes intéressé par la manière dont la mémoire et les logiciels interagissent. Il est également disponible en format PDF de 104 pages .

Les sections particulièrement pertinentes pour cette question peuvent être la partie 2 (caches de processeur) et la partie 5 (ce que les programmeurs peuvent faire – optimisation du cache).

Les règles de base sont en réalité assez simples. Où cela devient difficile, c’est dans la façon dont ils s’appliquent à votre code.

La cache fonctionne sur deux principes: la localité temporelle et la localité spatiale. Le premier est l’idée que si vous avez récemment utilisé un certain nombre de données, vous en aurez probablement besoin bientôt. Ce dernier point signifie que si vous avez récemment utilisé les données à l’adresse X, vous aurez probablement bientôt besoin de l’adresse X + 1.

Le cache essaie de s’y adapter en mémorisant les derniers morceaux de données utilisés. Il fonctionne avec des lignes de cache, généralement de 128 octets environ, de sorte que même si vous n’avez besoin que d’un seul octet, l’intégralité de la ligne de cache qui le contient est extraite du cache. Donc, si vous avez besoin de l’octet suivant, ce sera déjà dans le cache.

Et cela signifie que vous voudrez toujours que votre propre code exploite ces deux formes de localité autant que possible. Ne sautez pas partout sur la mémoire. Travaillez autant que possible sur une petite zone, puis passez à la suivante et faites le maximum de travail là-bas.

Un exemple simple est la traversée du tableau 2D que la réponse de 1800 a montrée. Si vous le parcourez une ligne à la fois, vous lisez la mémoire de manière séquentielle. Si vous le faites dans le sens des colonnes, vous allez lire une entrée, puis passer à un endroit complètement différent (le début de la prochaine ligne), lire une entrée et sauter à nouveau. Et quand vous reviendrez enfin à la première ligne, elle ne sera plus dans le cache.

La même chose s’applique au code. Les sauts ou les twigs signifient une utilisation du cache moins efficace (parce que vous ne lisez pas les instructions de manière séquentielle, mais que vous passez à une adresse différente). Bien sûr, les petites instructions if ne changeront probablement rien (vous ne faites que sauter quelques octets, alors vous vous retrouverez toujours dans la région mise en cache), mais les appels de fonction impliquent généralement que vous sautiez complètement à un autre adresse qui ne peut pas être mise en cache. À moins que cela ait été appelé récemment.

L’utilisation du cache d’instructions pose généralement moins de problèmes. Ce dont vous devez généralement vous soucier, c’est le cache de données.

Dans une structure ou une classe, tous les membres sont disposés de manière contiguë, ce qui est bien. Dans un tableau, toutes les entrées sont également contiguës. Dans les listes liées, chaque nœud est alloué à un emplacement complètement différent, ce qui est mauvais. Les pointeurs en général ont tendance à pointer vers des adresses non liées, ce qui entraînera probablement un échec du cache si vous le déréférenciez.

Et si vous voulez exploiter plusieurs cœurs, cela peut devenir vraiment intéressant, comme d’habitude, un seul CPU peut avoir une adresse donnée dans son cache L1 à la fois. Ainsi, si les deux cœurs accèdent constamment à la même adresse, cela entraînera des échecs constants dans le cache, car ils se disputent l’adresse.

Outre les modèles d’access aux données, la taille des données est un facteur majeur du code compatible avec le cache. Moins de données signifie qu’il y en a plus dans le cache.

Ceci est principalement un facteur avec les structures de données alignées sur la mémoire. La sagesse “conventionnelle” dit que les structures de données doivent être alignées aux limites des mots car le processeur ne peut accéder qu’à des mots entiers, et si un mot contient plus d’une valeur, vous devez faire un travail supplémentaire (read-modify-write au lieu d’une simple écriture) . Mais les caches peuvent invalider complètement cet argument.

De même, un tableau booléen Java utilise un octet entier pour chaque valeur afin de permettre le fonctionnement direct des valeurs individuelles. Vous pouvez réduire la taille des données d’un facteur 8 si vous utilisez des bits réels, mais l’access aux valeurs individuelles devient beaucoup plus complexe, nécessitant un décalage des bits et des opérations de masquage (la classe BitSet fait pour vous). Cependant, à cause des effets de cache, cela peut être beaucoup plus rapide que d’utiliser un booléen [] lorsque le tableau est volumineux. L’IIRC I a atteint un facteur 2 ou 3 par une fois.

La structure de données la plus efficace pour un cache est un tableau. Les caches fonctionnent mieux si votre structure de données est disposée de manière séquentielle lorsque les processeurs lisent des lignes de cache entières (généralement 32 octets ou plus) à la fois de la mémoire principale.

Tout algorithme qui accède à la mémoire dans un ordre aléatoire vide les caches car il a toujours besoin de nouvelles lignes de cache pour accueillir la mémoire à access aléatoire. D’un autre côté, un algorithme, qui s’exécute séquentiellement dans un tableau, est préférable car:

  1. Cela donne au processeur une chance de lire à l’avance, par exemple en mettant plus de mémoire dans le cache, auquel on accédera ultérieurement. Cette lecture anticipée donne un énorme coup de pouce à la performance.

  2. Exécuter une boucle serrée sur un grand tableau permet également au processeur de mettre en cache le code en cours d’exécution dans la boucle et, dans la plupart des cas, d’exécuter un algorithme entièrement à partir de la mémoire cache sans avoir à bloquer l’access à la mémoire externe.

Une remarque à “l’exemple classique” par l’utilisateur 1800 INFORMATION (trop long pour un commentaire)

Je voulais vérifier les différences de temps pour deux ordres d’itération (“outter” et “inner”), j’ai donc fait une expérience simple avec un grand tableau 2D:

 measure::start(); for ( int y = 0; y < N; ++y ) for ( int x = 0; x < N; ++x ) sum += A[ x + y*N ]; measure::stop(); 

et le deuxième cas avec les boucles for swappés.

La version la plus lente ("x first") était à 0.88sec et la plus rapide à 0.06sec. C'est le pouvoir de la mise en cache 🙂

J'ai utilisé gcc -O2 et les boucles n'ont pas encore été optimisées. Le commentaire de Ricardo selon lequel "la plupart des compilateurs modernes peuvent se débrouiller seuls" ne tient pas

Un exemple que j’ai vu utilisé dans un moteur de jeu était de déplacer des données hors des objects et de les placer dans leurs propres tableaux. Un object de jeu soumis à la physique peut également être associé à de nombreuses autres données. Mais lors de la mise à jour de la physique, tout ce qui concernait le moteur concernait la position, la vitesse, la masse, la boîte englobante, etc. Tout cela a été placé dans ses propres tableaux et optimisé autant que possible pour SSE.

Ainsi, pendant la boucle de physique, les données physiques ont été traitées dans un ordre de masortingce en utilisant le calcul vectoriel. Les objects du jeu utilisaient leur ID d’object comme index dans les différents tableaux. Ce n’était pas un pointeur car les pointeurs pouvaient être invalidés si les baies devaient être déplacées.

À bien des égards, cela violait les modèles de conception orientés object, mais cela accélérait le code en rapprochant les données qui devaient être utilisées dans les mêmes boucles.

Cet exemple est probablement obsolète car je pense que la plupart des jeux modernes utilisent un moteur physique préétabli comme Havok.

Un seul article a été abordé, mais un problème majeur se pose lors du partage de données entre processus. Vous voulez éviter que plusieurs processus tentent de modifier la même ligne de cache simultanément. Quelque chose à surveiller est le “faux” partage, où deux structures de données adjacentes partagent une ligne de cache et les modifications de l’une invalident la ligne de cache pour l’autre. Cela peut entraîner un déplacement inopiné des lignes de cache entre les caches de processeur partageant les données sur un système multiprocesseur. Un moyen d’éviter cela consiste à aligner et à insérer des structures de données pour les placer sur des lignes différentes.

Je peux répondre (2) en disant que dans le monde C ++, les listes liées peuvent facilement tuer le cache du processeur. Les tableaux sont une meilleure solution dans la mesure du possible. Aucune expérience quant à savoir si la même chose s’applique à d’autres langues, mais il est facile d’imaginer les mêmes problèmes se poseraient.

Le cache est organisé en “lignes de cache” et la mémoire (réelle) est lue et écrite dans des morceaux de cette taille.

Les structures de données contenues dans une seule ligne de cache sont donc plus efficaces.

De même, les algorithmes qui accèdent à des blocs de mémoire contigus seront plus efficaces que les algorithmes qui sautent en mémoire dans un ordre aléatoire.

Malheureusement, la taille de la ligne de cache varie considérablement d’un processeur à l’autre. Il est donc impossible de garantir qu’une structure de données optimale sur un processeur sera efficace sur un autre.

Demander comment créer un code, mettre en cache un cache efficace et la plupart des autres questions, consiste généralement à demander comment optimiser un programme, car le cache a un impact énorme sur les performances que tout programme optimisé est un cache. cache efficace efficace.

Je suggère de lire à propos de l’optimisation, il y a quelques bonnes réponses sur ce site. En ce qui concerne les livres, je recommande sur Computer Systems: A Programmer’s Perspective, qui contient des textes sur l’utilisation correcte du cache.

(btw – aussi mauvais qu’un cache-miss puisse être, il y a pire – si un programme est en train de paginer depuis le disque dur …)

Il y a eu beaucoup de réponses sur les conseils généraux tels que la sélection de la structure de données, le modèle d’access, etc. J’aimerais append un autre modèle de conception de code appelé pipeline de logiciels qui utilise la gestion active du cache.

L’idée est d’emprunter d’autres techniques de pipelining, par exemple l’instruction en pipeline.

Ce type de modèle s’applique mieux aux procédures

  1. pourrait être divisé en plusieurs sous-étapes raisonnables, S [1], S [2], S [3], … dont le temps d’exécution est à peu près comparable au temps d’access à la RAM (~ 60-70ns).
  2. prend un lot de saisie et fait les étapes multiples susmentionnées pour obtenir un résultat.

Prenons un cas simple où il n’y a qu’une seule sous-procédure. Normalement, le code aimerait:

 def proc(input): return sub-step(input)) 

Pour obtenir de meilleures performances, vous souhaiterez peut-être transmettre plusieurs entrées à la fonction dans un lot afin d’amortir la surcharge des appels de fonction et d’augmenter la localité du cache de code.

 def batch_proc(inputs): results = [] for i in inputs: // avoids code cache miss, but still suffer data(inputs) miss results.append(sub-step(i)) return res 

Cependant, comme indiqué précédemment, si l’exécution de l’étape est à peu près la même que le temps d’access à la RAM, vous pouvez encore améliorer le code en quelque chose comme ceci:

 def batch_pipelined_proc(inputs): for i in range(0, len(inputs)-1): prefetch(inputs[i+1]) # work on current item while [i+1] is flying back from RAM results.append(sub-step(inputs[i-1])) results.append(sub-step(inputs[-1])) 

Le stream d’exécution ressemblerait à ceci:

  1. prefetch (1) demande à l’UC de pré-charger l’entrée [1] dans le cache, où l’instruction prefetch prend P cycles elle-même et retourne, et dans l’arrière-plan, l’entrée [1] arriverait en cache après R cycles.
  2. works_on (0) miss miss froid sur 0 et travaille dessus, ce qui prend M
  3. prefetch (2) émet une autre extraction
  4. works_on (1) si P + R < = M, alors les entrées [1] doivent être dans le cache avant cette étape, évitant ainsi un échec du cache de données
  5. works_on (2)

Il pourrait y avoir plus d’étapes impliquées, puis vous pouvez concevoir un pipeline à plusieurs étapes tant que la synchronisation des étapes et des latences d’access à la mémoire correspond, vous risquez de manquer de code / cache de données. Cependant, ce processus doit être ajusté avec de nombreuses expériences pour trouver le bon regroupement des étapes et le temps de prélecture. Grâce à ses efforts, il est de plus en plus utilisé dans le traitement de données / paquets de données à hautes performances. Un bon exemple de code de production peut être trouvé dans la conception du pipeline DPDK QoS Enqueue: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Chapitre 21.2.4.3. Enqueue Pipeline.

Plus d’informations pourraient être trouvées:

https://software.intel.com/fr-fr/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf

Écrivez votre programme pour prendre une taille minimale. C’est pourquoi ce n’est pas toujours une bonne idée d’utiliser les optimisations -O3 pour GCC. Il prend une taille plus grande. Souvent, -Os est aussi bon que -O2. Tout dépend du processeur utilisé. YMMV.

Travailler avec de petits morceaux de données à la fois. C’est pourquoi un algorithme de sorting moins efficace peut s’exécuter plus rapidement que le sorting rapide si le jeu de données est volumineux. Trouvez des moyens de diviser vos ensembles de données plus volumineux en plus petits. D’autres l’ont suggéré.

Afin de vous aider à mieux exploiter l’instruction locale temporelle / spatiale, vous pouvez étudier comment votre code est converti en assembleur. Par exemple:

 for(i = 0; i < MAX; ++i) for(i = MAX; i > 0; --i) 

Les deux boucles produisent des codes différents même si elles ne font qu’parsingr un tableau. En tout cas, votre question est très spécifique à l’architecture. Ainsi, votre seul moyen de contrôler étroitement l’utilisation du cache est de comprendre le fonctionnement du matériel et d’optimiser votre code.

En plus d’aligner votre structure et vos champs, si votre structure si le tas est alloué, vous pouvez utiliser des allocateurs qui prennent en charge les allocations alignées; comme _aligned_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); sinon vous pourriez avoir un faux partage aléatoire; Rappelez-vous que sous Windows, le segment par défaut a un alignement de 16 octets.