Qu'est-ce qu'un code" cache-friendly"?

Quelle est la différence entre " cache hostile code " et " cache-friendly code"?

Comment puis-je m'assurer d'écrire du code efficace pour le cache?

624
demandé sur Keet Sugathadasa 2013-05-22 22:37:01
la source

9 ответов

préliminaires

sur les ordinateurs modernes, seules les structures de mémoire de niveau le plus bas (le enregistre ) peuvent déplacer des données dans des cycles d'horloge simples. Cependant, les registres sont très coûteux et la plupart des ordinateurs centraux ont moins de quelques douzaines de registres (quelques centaines À peut-être un millier bytes total). À l'autre extrémité du spectre de la mémoire ( DRAM ), la mémoire est très bon marché (i.e. littéralement millions de fois moins cher ) mais prend des centaines de cycles après une demande pour recevoir les données. Pour combler cet écart entre super rapide et cher et super lent et bon marché sont les mémoires de cache , nommé L1, L2, L3 dans la vitesse décroissante et le coût. L'idée est que la plupart du code d'exécution va frapper un petit ensemble de variables souvent, et le reste (un ensemble beaucoup plus grand de variables) rarement. Si le processeur ne trouve pas les données dans le cache L1, puis il regarde dans le cache L2. Si ce n'est pas le cas, alors le cache L3, et si ce n'est pas le cas, la mémoire principale. Chacun de ces" manques " est coûteux à temps.

(L'analogie est la mémoire cache est une mémoire de la mémoire système, comme le système de la mémoire, disque dur de stockage. Le stockage sur disque dur est super bon marché, mais très lent).

"1519130920 la mise en Cache" est l'une des principales méthodes pour réduire l'impact de la "1519160920 temps de" latence . Pour paraphraser Herb Sutter (cfr. les liens ci-dessous): augmenter la bande passante est facile, mais nous ne pouvons pas acheter notre façon de sortir de la latence .

Les données

sont toujours récupérées à travers la hiérarchie de la mémoire (la plus petite == la plus rapide à la plus lente). Un cache hit/miss fait habituellement référence à un hit / miss dans le niveau le plus élevé de cache dans le CPU -- par niveau le plus élevé je veux dire le plus grand == le plus lent. Le taux de succès du cache est crucial pour la performance, car chaque défaut du cache entraîne la récupération de données à partir de la mémoire vive (ou pire). ...) qui prend beaucoup de temps (des centaines de cycles pour la mémoire vive, des dizaines de millions de cycles pour le disque dur). En comparaison, la lecture des données du cache (niveau le plus élevé) ne prend généralement qu'une poignée de cycles.

dans les architectures informatiques modernes, le goulot d'étranglement de la performance laisse le processeur en panne (par exemple, accès à la mémoire vive ou à une mémoire supérieure). Cela ne fera que s'aggraver plus de temps. L'augmentation de la fréquence du processeur est actuellement plus pertinents pour augmenter les performances. le problème est l'accès mémoire. les efforts de conception de matériel dans les CPU se concentrent donc fortement sur l'optimisation des caches, la préfixation, les pipelines et la concurrence. Par exemple, les CPU modernes dépensent environ 85% de la matrice sur les caches et jusqu'à 99% pour stocker/déplacer des données!

il y a beaucoup à dire à ce sujet. Voici quelques grandes références sur les caches, les hiérarchies de mémoire et la programmation correcte:

Principaux concepts de cache-friendly code

un aspect très important du code cache-friendly est tout au sujet de le principe de la localité , dont le but est de placer des données connexes près en mémoire pour permettre une mise en cache efficace. En ce qui concerne le cache CPU, il est important d'être conscient des lignes de cache pour comprendre comment cela fonctionne: Comment fonctionnent les lignes de cache?

les aspects particuliers suivants sont d'une grande importance pour optimiser la mise en cache:

  1. localité temporelle : lorsqu'un emplacement mémoire donné a été accédé, il est probable que le même endroit est accédé à nouveau dans le proche avenir. Idéalement, cette information sera encore mise en cache à ce moment-là.
  2. localisation géographique : il s'agit de placer des données connexes à proximité l'une de l'autre. La mise en cache se produit à de nombreux niveaux, pas seulement dans le CPU. Par exemple, lorsque vous lisez à partir de la RAM, typiquement un plus grand morceau de mémoire est récupéré que ce qui a été spécifiquement demandé parce que très souvent le programme exigera que les données bientôt. Les caches HDD suivent la même ligne de pensée. Spécifiquement pour CPU caches, la notion de lignes de cache est importante.

utiliser des conteneurs

un exemple simple de cache-friendly versus cache-unfriendly est 's std::vector versus std::list . Les éléments d'un std::vector sont stockés dans une mémoire contiguë, et à ce titre y accéder est beaucoup plus cache-friendly que l'accès aux éléments dans un std::list , qui stocke son contenu partout. Cela est dû à la localité spatiale.

une très belle illustration en est donnée par Bjarne Stroustrup dans ce clip youtube (merci à @Mohammad Ali Baydoun pour le lien!).

ne négligez pas le cache dans la structure des données et la conception de l'algorithme

dans la mesure du possible, essayez d'adapter vos structures de données et l'ordre des calculs de manière à permettre une utilisation maximale du cache. Une technique courante à cet égard est cache blocking (Archive.org version) , qui est d'une importance extrême dans le calcul de haute performance (cfr. par exemple ATLAS ).

connaître et exploiter la structure implicite des données

un autre un exemple simple, que beaucoup de gens sur le terrain oublient parfois, est colonne-majeure (ex. , ) vs. ligne-commande principale(ex. , ) pour stocker des tableaux bidimensionnels. Par exemple, considérons la matrice suivante:

1 2
3 4

dans la rangée-commande principale, ceci est stocké en mémoire comme 1 2 3 4 ; dans la colonne-commande principale ce serait stocké comme 1 3 2 4 . Il est facile de voir que les implémentations qui n'exploitent pas cette commande va rapidement tourner en (facilement évitables!) problèmes de cache. Malheureusement, je vois des choses comme ceci très souvent dans mon domaine (apprentissage machine). @MatteoItalia a montré cet exemple plus en détail dans sa réponse.

lors de la récupération d'un certain élément d'une matrice de mémoire, les éléments proches de celle-ci seront également récupérés et stockés dans une ligne de cache. Si la commande est exploité, cela se traduira par moins d'accès mémoire (parce que les quelques valeurs suivantes qui sont nécessaires pour les calculs ultérieurs sont déjà dans une ligne de cache).

par souci de simplicité, supposons que le cache comporte une seule ligne de cache pouvant contenir 2 éléments de matrice et que lorsqu'un élément donné est récupéré de la mémoire, le suivant l'est aussi. Disons que nous voulons prendre la somme sur tous les éléments dans l'exemple 2x2 matrice ci-dessus (appelons-le M ):

Exploitation de l'ordre (Par exemple changement d'index de colonne en premier dans ):

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

n'exploitant pas l'ordre (p.ex. changement de l'indice de ligne en premier dans ):

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

dans cet exemple simple, l'exploitation de la commande double approximativement la vitesse d'exécution (puisque l'accès à la mémoire nécessite beaucoup plus de cycles que le calcul des sommes). Dans la pratique, la différence de performance peut être beaucoup plus plus grand.

éviter les branches imprévisibles

les architectures modernes disposent de pipelines et les compilateurs sont en train de devenir très bons pour réorganiser le code afin de minimiser les retards dus à l'accès à la mémoire. Lorsque votre code critique contient des branches (imprévisibles), il est difficile ou impossible de préfixer les données. Cela conduira indirectement à plus de mises en cache ratées.

c'est expliqué très bien ici (merci à @0x90 pour le lien): Pourquoi est-ce plus rapide de traiter un tableau trié qu'un tableau non trié?

éviter les fonctions virtuelles

dans le contexte de , virtual méthodes représentent une question controversée en ce qui concerne les erreurs de cache (un consensus général existe qu'ils devraient être évités lorsque possible en termes de performance). Les fonctions virtuelles peuvent induire des erreurs de cache pendant la recherche, mais cela ne se produit que si la fonction spécifique n'est pas appelée souvent (sinon elle serait probablement mise en cache), donc cela est considéré comme un non-problème par certains. Pour référence à ce sujet, consultez: Quel est le coût de performance d'avoir une méthode virtuelle dans une Classe C++?

problèmes fréquents

un problème courant dans les architectures modernes avec les caches multiprocesseur est appelé faux partage . Cela se produit lorsque chaque processeur individuel tente d'utiliser des données dans une autre région de mémoire et tente de les stocker dans la même ligne de cache . Cela provoque la ligne de cache -- qui contient des données qu'un autre processeur peut utiliser -- à être réécrite encore et encore. Effectivement, différents threads se font attendre en induisant des erreurs de cache dans cette situation. Voir aussi (merci à @Matt pour l' lien): comment et quand s'aligner à la taille de la ligne de cache?

un symptôme extrême d'une mauvaise mise en cache dans la mémoire vive (ce qui n'est probablement pas ce que vous voulez dire dans ce contexte) est appelé thrashing . Cela se produit lorsque le processus génère continuellement des défauts de page (par exemple accède à une mémoire qui n'est pas dans la page courante) qui nécessitent un accès disque.

812
répondu Marc Claesen 2018-08-21 06:08:56
la source

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.

122
répondu Matteo Italia 2017-04-26 05:31:34
la source

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

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

75
répondu Jerry Coffin 2013-05-31 22:18:20
la source

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.

29
répondu arul 2018-04-23 00:12:40
la source

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

20
répondu Krazy Glew 2013-05-29 13:17:34
la source
Les processeurs

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.

12
répondu Rafael Baptista 2013-05-22 23:58:06
la source

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

4
répondu Olof Forshell 2016-02-14 18:33:02
la source

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

2
répondu 2017-03-31 18:38:03
la source

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 .

0
répondu Tuntable 2017-02-27 07:42:54
la source

Autres questions sur c++ performance memory caching cpu-cache