en plus de la réponse de @Marc Claesen, je pense qu'un exemple classique instructif de code cache-unfriendly est un code qui scanne un tableau bidimensionnel C (par exemple une image bitmap) en colonne plutôt qu'en rangée.

les éléments qui sont adjacents dans une rangée sont également adjacents dans la mémoire, donc y accéder en séquence signifie y accéder dans l'ordre ascendant de la mémoire; c'est facile pour le cache, puisque le cache a tendance à préférer les blocs contigus de mémoire.

au lieu de cela, l'accès à de tels éléments par colonne est inamical par rapport au cache, puisque les éléments sur la même colonne sont éloignés l'un de l'autre dans la mémoire (en particulier, leur distance est égale à la taille de la rangée), donc quand vous utilisez ce modèle d'accès vous sautez dans la mémoire, gaspillant potentiellement l'effort du cache de retrouver les éléments à proximité dans la mémoire.

et tout ce qu'il faut pour ruiner la performance est d'aller de

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

à

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

cet effet peut être assez dramatique (plusieurs ordres de grandeur dans la vitesse) dans les systèmes avec de petites caches et/ou travaillant avec de grands tableaux (par exemple 10+ mégapixels 24 images bpp sur les machines actuelles); pour cette raison, si vous devez faire de nombreux scans verticaux, souvent il est préférable de tourner l'image de 90 degrés d'abord et d'effectuer les diverses analyses plus tard, limitant le code cache-unfriendly juste à la rotation.

L'optimisation de l'utilisation du cache se résume en grande partie à deux facteurs.

localité de référence

le premier facteur (auquel d'autres ont déjà fait allusion) est la localité de référence. La localité de référence a deux dimensions: l'espace et le temps.

• Spatiale

la dimension spatiale se résume également à deux choses: d'abord, nous voulons emballer nos Informations densément, donc plus d'information s'insérera dans cette mémoire limitée. Cela signifie (par exemple) que vous avez besoin d'une amélioration majeure de la complexité computationnelle pour justifier les structures de données basées sur de petits nœuds rejoints par des pointeurs.

Deuxièmement, nous voulons que les informations qui seront traitées ensemble soient également localisées ensemble. Un cache typique fonctionne en "lignes", ce qui signifie que lorsque vous accédez à certaines informations, d'autres informations aux adresses voisines seront chargées dans le cache avec la partie toucher. Par exemple, quand je touche un octet, le cache peut charger 128 ou 256 octets près de celui-là. Pour tirer avantage de cela, vous voulez généralement les données organisées pour maximiser la probabilité que vous utiliserez également que d'autres données qui a été chargé en même temps.

pour juste un exemple vraiment trivial, cela peut signifier qu'une recherche linéaire peut être beaucoup plus compétitive avec une recherche binaire que ce que vous attendez. Une fois que vous avez chargé un élément à partir d'une ligne de cache, en utilisant le reste de la les données dans cette ligne de cache sont presque libres. Une recherche binaire devient nettement plus rapidement que lorsque les données sont assez grand pour que la recherche binaire réduit le nombre de lignes de cache.

• Temps

la dimension temporelle signifie que lorsque vous effectuez certaines opérations sur certaines données, vous voulez (autant que possible) effectuer toutes les opérations sur ces données en même temps.

puisque vous avez étiqueté ceci comme C++, je vais pointer à un exemple classique d'un design relativement cache-inamical: std::valarray . valarray surcharge la plupart des opérateurs arithmétiques, donc je peux (par exemple) dire a = b + c + d; (où a , b , c et d sont tous des valarrays) pour faire l'addition de ces tableaux.

le problème avec ceci est qu'il marche à travers une paire d'entrées, met des résultats dans un temporaire, marche à travers une autre paire d'entrées, et ainsi de suite. Avec un grand nombre de données, le résultat d'un calcul peut disparaître du cache avant d'être utilisé dans le calcul suivant, donc nous finissons par lire (et écrire) les données à plusieurs reprises avant d'obtenir notre résultat final. Si chaque élément du résultat final sera quelque chose comme (a[n] + b[n]) * (c[n] + d[n]); , nous préférerions généralement lire chaque a[n] , b[n] , c[n] et d[n] une fois, faites le calcul, écrivez le résultat, incrémentez n et répétez jusqu'à ce que nous ayons fini. ²

Ligne De Partage

le deuxième facteur important est d'éviter le partage des lignes. Pour comprendre cela, nous devons probablement revenir en arrière et regarder un peu comment les caches sont organisées. La forme la plus simple de cache est directement mappée. Cela signifie une adresse dans la mémoire principale ne peut être stocké dans un endroit spécifique dans le cache. Si nous utilisons deux éléments de données qui pointent vers le même endroit dans le cache, cela fonctionne mal -- chaque fois que nous utilisons un élément de données, l'autre doit être vidé du cache pour faire de la place à l'autre. Le reste du cache peut être vide, mais ces objets n'utiliseront pas d'autres parties du cache.

pour éviter cela, la plupart des caches sont ce qu'on appelle"set associative". Par exemple, dans un cache 4-way set-associative, n'importe quel élément de la mémoire principale peut être stocké à n'importe lequel des 4 endroits différents dans le cache. Ainsi, lorsque le cache va charger un élément, il cherche l'élément le moins récemment utilisé ³ parmi ceux quatre, le jette à la mémoire principale, et charge le nouvel article à sa place.

le problème est probablement assez évident: pour un cache cartographié directement, deux opérandes qui se produisent à la même localisation de cache peuvent conduire à un mauvais comportement. Un cache n-way set-associative augmente le nombre de 2 à N+1. L'organisation d'un cache en plusieurs "façons" prend des circuits supplémentaires et s'exécute généralement plus lentement, donc (par exemple) un cache associatif en 8192-way set est rarement une bonne solution non plus.

finalement, ce facteur est plus difficile à contrôler en code portable. Votre contrôle sur l'emplacement de vos données est généralement assez limité. Pire, la correspondance exacte de l'adresse au cache varie entre des processeurs par ailleurs similaires. Dans certains cas, cependant, cela peut valoir la peine de faire des choses comme allouer un grand tampon, et ensuite utiliser seulement des parties de ce que vous avez alloué pour assurer contre le partage des données les mêmes lignes de cache (même si vous aurez probablement besoin de détecter le processeur exact et agir en conséquence pour le faire).

• False Sharing

il y a un autre article connexe appelé"faux partage". Cela se produit dans un système multiprocesseur ou multicore, où deux (ou plus) processeurs/noyaux ont des données qui sont séparées, mais tombent dans la même ligne de cache. Cela oblige les deux processeurs / noyaux à coordonner leur accès aux données, même si chacun a son propre élément de données distinct. Surtout si les deux modifient les données en alternance, ce qui peut conduire à un ralentissement massif car les données doivent être constamment acheminées entre les processeurs. Cela ne peut pas être facilement guéri en organisant la cache en d'autres "façons" ou n'importe quoi de ce genre soit. La principale façon de l'empêcher est de s'assurer que deux threads modifient rarement (de préférence jamais) des données qui pourraient éventuellement être dans la même ligne de cache (avec les mêmes mises en garde sur la difficulté de contrôler les adresses auxquelles les données sont attribuées).

1. ceux qui connaissent bien c++ pourraient se demander si cela est ouvert à l'optimisation via quelque chose comme des modèles d'expression. Je suis presque sûr que la réponse est que oui, cela pourrait être fait et si c'était le cas, ce serait probablement une victoire assez substantielle. Je ne suis pas au courant que quelqu'un l'ait fait, cependant, et étant donné le peu d'utilisation de valarray , je serais au moins un peu surpris de voir quelqu'un le faire non plus.

2. dans le cas où quelqu'un se demande comment valarray (conçu spécifiquement pour la performance) pourrait être ce mal, il se résume à une chose: il a été vraiment conçu pour les machines comme les anciens Crays, qui ont utilisé la mémoire principale rapide et pas de cache. Pour eux, c'était vraiment un design presque idéal.

3. Oui, je simplifie: la plupart des caches ne mesurent pas vraiment l'article Le moins récemment utilisé avec précision, mais ils utilisent une certaine heuristique qui est destiné à être proche sans avoir à garder à temps plein-timbre pour chaque accès.

Bienvenue dans le monde des Données de Conception Orientée. Le mantra de base est de trier, D'éliminer les Branches, de fournée, D'éliminer virtual appels - tous les pas vers une meilleure localité.

puisque vous avez étiqueté la question avec C++, voici le obligatoire typique C++ conneries . Le de Tony Albrecht, " pièges de la programmation orientée objet , est également une excellente introduction au sujet.

intéressantes: l'exemple classique de cache-hostiles rapport à cache-friendly code est le "cache blocage" de la matrice se multiplier.

naïve Matrix multiply ressemble à

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k==;k<N;i++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

si N est grand, par exemple si N * sizeof(elemType) est plus grand que la taille du cache, alors chaque accès à src2[k][j] sera une erreur de cache.

il y a plusieurs façons d'optimiser ceci pour un cache. Voici un très exemple simple: au lieu de lire un élément par ligne de cache dans la boucle intérieure, utilisez tous les éléments:

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k==;k<N;i++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

si la taille de la ligne de cache est de 64 octets, et que nous travaillons sur des flotteurs 32 bits (4 octets), alors il y a 16 éléments par ligne de cache. Et le nombre de trous dans le cache via cette simple transformation est réduit d'environ 16 fois.

transformations fantaisistes fonctionnent sur des tuiles 2D, optimiser pour des caches multiples (L1, L2, TLB), et ainsi de suite.

Quelques résultats de recherche sur google cache "blocage":

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

une belle animation vidéo d'un algorithme de blocage de cache optimisé.

http://www.youtube.com/watch?v=IFWgwGMMrh0

boucle carrelage est très étroitement lié:

http://en.wikipedia.org/wiki/Loop_tiling

fonctionnent aujourd'hui avec de nombreux niveaux de zones de mémoire en cascade. Donc le CPU aura un tas de mémoire qui est sur la puce CPU elle-même. Il a un accès très rapide à cette mémoire. Il y a différents niveaux de cache chacun un accès plus lent ( et plus grand ) que le suivant, jusqu'à ce que vous arriviez à la mémoire du système qui n'est pas sur le CPU et est relativement plus lent à accéder.

logiquement, au jeu d'instructions du CPU vous vous référez juste aux adresses de mémoire dans un géant virtuel adresse de l'espace. Lorsque vous accédez à une seule adresse mémoire, le CPU va la récupérer. dans les vieux jours, il allait chercher juste que seule adresse. Mais aujourd'hui le CPU va chercher un tas de mémoire autour du morceau que vous avez demandé, et le copier dans le cache. Il suppose que si vous avez demandé une adresse particulière, ce qui est très probable que vous allez demander une adresse à proximité, très bientôt. Par exemple, si vous copiez un tampon, vous liriez et écririez à partir d'adresses consécutives - une juste après autre.

donc aujourd'hui quand vous récupérez une adresse il vérifie le premier niveau de cache pour voir s'il a déjà lu cette adresse dans le cache, s'il ne la trouve pas, alors c'est une erreur de cache et il doit sortir au niveau suivant de cache pour la trouver, jusqu'à ce qu'il doive finalement sortir dans la mémoire principale.

Cache friendly code essaie de garder les accès proches en mémoire afin que vous minimisiez les erreurs de cache.

Donc un exemple serait imaginez que vous vouliez copier une table géante en 2 dimensions. Il est organisé avec reach row consécutivement en mémoire, et une rangée suit la suivante juste après.

si vous copiez les éléments une rangée à la fois de gauche à droite - ce serait facile à mettre en cache. Si vous décidez de copier la table une colonne à la fois, vous copiez exactement la même quantité de mémoire - mais ce serait cache inamical.

il faut préciser que non seulement les données doivent être compatibles avec le cache, mais elles sont tout aussi importantes pour le code. Cela s'ajoute à la prédiction de la branche, à la réorganisation de l'instruction, en évitant les divisions réelles et d'autres techniques.

généralement, plus le code est dense, moins de lignes de cache seront nécessaires pour le stocker. Il en résulte que plus de lignes de cache sont disponibles pour les données.

le code ne devrait pas appeler des fonctions partout car ils en général, il faut une ou plusieurs lignes de cache propres, ce qui entraîne une réduction du nombre de lignes de cache pour les données.

une fonction doit commencer à une adresse compatible avec la ligne de cache. Bien qu'il y ait des commutateurs de compilateur (gcc) pour cela, sachez que si les fonctions sont très courtes, il pourrait être inutile que chacun occupe une ligne de cache entière. Par exemple, si trois des fonctions les plus souvent utilisées se situent à l'intérieur d'une ligne de cache 64 octets, cela est moins coûteux que si chacune a sa propre ligne et se traduit par deux lignes de cache Moins disponibles pour un autre usage. Une valeur d'alignement typique pourrait être 32 ou 16.

passez donc un peu de temps supplémentaire pour rendre le code dense. Tester différentes constructions, compiler et examiner la taille et le profil de code généré.

@Marc Claesen mentionné que l'une des façons d'écrire cache amical code est d'exploiter la structure dans laquelle nos données sont stockées. En plus de cela, une autre façon d'écrire du code de cache convivial est: changez la façon dont nos données sont stockées, puis écrivez un nouveau code pour accéder aux données stockées dans cette nouvelle structure.

cela a du sens dans le cas de la façon dont les systèmes de base de données linéarisent les tuples d'une table et les stockent. Il existe deux méthodes de base pour stocker les tuples d'un tableau c.-à-d. magasin de ligne et Magasin de colonne. Dans la rangée stocker comme le nom suggère les tuples sont stockées ligne Sage. Supposons qu'une table appelée Product est stockée avec 3 attributs i.e. int32_t key, char name[56] et int32_t price , donc la taille totale d'un tuple est 64 octets.

nous pouvons simuler une exécution de requête de stockage de ligne très basique en mémoire principale en créant un tableau de Product structures avec la taille N, Où N est le nombre de lignes dans la table. Une telle disposition de mémoire est également appelé tableau de structures. Ainsi la structure pour le produit peut être comme:

struct Product
{
   int32_t key;
   char name[56];
   int32_t price'
}

/* create an array of structs */
Product* table = new Product[N];
/* now load this array of structs, from a file etc. */

de même, nous pouvons simuler une exécution de requête de stockage de colonne très basique en mémoire principale en créant 3 tableaux de taille N, Un tableau pour chaque attribut de la table Product . Une telle disposition de mémoire est aussi appelée struct des tableaux. Ainsi les 3 tableaux pour chaque attribut de produit peuvent être comme:

/* create separate arrays for each attribute */
int32_t* key = new int32_t[N];
char* name = new char[56*N];
int32_t* price = new int32_t[N];
/* now load these arrays, from a file etc. */

maintenant après avoir chargé à la fois le tableau des structures (disposition de la rangée) et les 3 tableaux séparés (disposition de colonne), nous avons Magasin de ligne et Magasin de colonne sur notre table Product présent dans notre mémoire.

nous passons maintenant à la partie Code de cache. Supposons que la charge de travail sur notre table est telle que nous avons une requête d'agrégation sur l'attribut de prix. Comme

SELECT SUM(price)
FROM PRODUCT

pour le magasin de rang nous pouvons convertir la requête SQL ci-dessus en

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + table[i].price;

pour le magasin de colonne que nous pouvons convertir la requête SQL ci-dessus dans

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + price[i];

le code pour le magasin de colonne serait plus rapide que le code pour la disposition de ligne dans cette requête car elle ne nécessite qu'un sous-ensemble d'attributs et dans la disposition de colonne nous faisons juste cela c.-à-d. accéder seulement la colonne de prix.

supposons que la taille de la ligne de cache soit de 64 octets.

dans le cas de la disposition de ligne quand une ligne de cache est lue, la valeur de prix de seulement 1 ( cacheline_size/product_struct_size = 64/64 = 1 ) tuple est lu, parce que notre taille de structure de 64 octets et il remplit toute notre ligne de cache, donc pour chaque tuple, une erreur de cache se produit en cas de disposition de ligne.

dans le cas d'une disposition de colonne lorsqu'une ligne de cache est lue, la valeur de prix de 16 tuples ( cacheline_size/price_int_size = 64/4 = 16 ) est lue, parce que 16 valeurs de prix contiguës stockées en mémoire sont introduites dans le cache, donc pour chaque tuple de seizième un cache miss ocurs en cas de disposition de colonne.

ainsi la disposition de la colonne sera plus rapide dans le cas d'une requête donnée, et est plus rapide dans de telles requêtes d'agrégation sur un sous-ensemble de colonnes de la table. Vous pouvez essayer une telle expérience pour vous-même en utilisant les données de TPC-H benchmark, et comparer les temps d'exécution pour les deux layouts. L'article wikipedia sur les systèmes de bases de données en colonne est également bon.

ainsi dans les systèmes de base de données, si la charge de travail de requête est connue à l'avance, nous pouvons stocker nos données dans les layouts qui conviennent aux requêtes dans la charge de travail et accéder aux données de ces layouts. Dans le cas de l'exemple ci-dessus, nous avons créé une mise en page de colonne et modifié notre code pour calculer la somme de façon à ce qu'elle devienne conviviale pour le cache.

soyez conscient que les caches ne se limitent pas à la mémoire continue. Ils ont plusieurs lignes (au moins 4) de sorte que la mémoire discontinue et se chevauchant peut souvent être stockée tout aussi efficacement.

ce qui manque dans tous les exemples ci-dessus, ce sont des points de repère mesurés. Il existe de nombreux mythes sur la performance. À moins de le mesurer, vous ne le savez pas. Ne compliquez pas votre code à moins que vous ayez une amélioration mesurée .