Pourquoi les additions par éléments sont-elles beaucoup plus rapides dans des boucles séparées que dans une boucle combinée ?

Question

Supposons que a1 , b1 , c1 y d1 pointent vers la mémoire vive, et mon code numérique comporte la boucle centrale suivante.

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

Cette boucle est exécutée 10 000 fois via une autre boucle extérieure. for boucle. Pour l'accélérer, j'ai changé le code en :

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

Compilé le Microsoft Visual C++ 10.0 avec une optimisation complète et ESS2 activé pour 32 bits sur un Intel Core 2 Duo (x64), le premier exemple prend 5,5 secondes et l'exemple à double boucle ne prend que 1,9 seconde.

Le désassemblage de la première boucle se présente essentiellement comme suit (ce bloc est répété environ cinq fois dans le programme complet) :

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

Chaque boucle de l'exemple de la double boucle produit ce code (le bloc suivant est répété environ trois fois) :

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

La question s'est avérée sans intérêt, car le comportement dépend fortement de la taille des tableaux (n) et de la mémoire cache de l'unité centrale. Donc, s'il y a un intérêt supplémentaire, je reformule la question :

• Pourriez-vous nous éclairer sur les détails qui conduisent aux différents comportements du cache, tels qu'illustrés par les cinq régions du graphique suivant ?

• Il pourrait également être intéressant de souligner les différences entre les architectures CPU/cache, en fournissant un graphique similaire pour ces CPU.

Voici le code complet. Il utilise TBB Tick_Count pour une résolution plus élevée, qui peut être désactivée en ne définissant pas le paramètre TBB_TIMING Macro :

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;

void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}

void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

Il montre les FLOP/s pour différentes valeurs de n .

Answer 1

Après une analyse plus approfondie, je pense que cela est dû (au moins en partie) à l'alignement des données des quatre points. Cela entraînera un certain niveau de conflits entre les banques de cache et les voies.

Si j'ai bien deviné comment vous allouez vos tableaux, ils sont sont susceptibles d'être alignés sur la ligne de la page .

Cela signifie que tous vos accès dans chaque boucle tomberont sur le même chemin de cache. Cependant, les processeurs Intel ont une associativité de cache L1 à 8 voies depuis un certain temps. Mais en réalité, les performances ne sont pas complètement uniformes. L'accès à 4 voies est toujours plus lent que l'accès à 2 voies.

EDIT : Il semble en effet que vous allouez tous les tableaux séparément. En général, lorsque des allocations aussi importantes sont demandées, l'allocateur demande des pages fraîches au système d'exploitation. Il y a donc de fortes chances que des allocations importantes apparaissent au même endroit à partir d'une frontière de pages.

Voici le code de test :

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

---

Résultats de l'évaluation des performances :

EDIT : Résultats sur un réel Machine à architecture Core 2 :

2 x Intel Xeon X5482 Harpertown à 3,2 GHz :

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

Observations :

• 6,206 secondes avec une boucle et 2,116 secondes avec deux boucles. Cela reproduit exactement les résultats de l'OP.

• Dans les deux premiers tests, les tableaux sont alloués séparément. Vous remarquerez qu'ils ont tous le même alignement par rapport à la page.

• Dans les deux autres tests, les tableaux sont regroupés afin de rompre cet alignement. Vous remarquerez que les deux boucles sont plus rapides. En outre, la deuxième boucle (double) est maintenant la plus lente, comme on peut s'y attendre.

Comme le souligne @Stephen Cannon dans les commentaires, il est très probable que cet alignement cause des problèmes de santé publique. faux repliement dans les unités de chargement/stockage ou dans le cache. J'ai fait des recherches sur Google et j'ai découvert qu'Intel avait un compteur matériel pour le alias d'adresse partiel des étals :

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html

---

5 Régions - Explications

Région 1 :

Celui-ci est facile à réaliser. L'ensemble de données est si petit que les performances sont dominées par les frais généraux tels que les boucles et les branchements.

Région 2 :

Ici, au fur et à mesure que la taille des données augmente, le montant de la surcharge relative diminue et les performances "saturent". Ici, deux boucles sont plus lentes parce qu'il y a deux fois plus de frais généraux de boucle et de branchement.

Je ne sais pas exactement ce qui se passe ici... L'alignement peut toujours jouer un rôle, comme le mentionne Agner Fog conflits entre banques de caches . (Ce lien concerne Sandy Bridge, mais l'idée devrait être applicable au Core 2).

Région 3 :

À ce stade, les données ne peuvent plus être stockées dans le cache L1. Les performances sont donc limitées par la bande passante du cache L1 <-> L2.

Région 4 :

La baisse de performance dans la boucle unique est ce que nous observons. Et comme mentionné, cela est dû à l'alignement qui cause (très probablement) faux repliement les blocages dans les unités de chargement/stockage du processeur.

Cependant, pour qu'un faux aliasing se produise, il faut que l'écart entre les ensembles de données soit suffisamment grand. C'est pourquoi vous ne voyez pas ce phénomène dans la région 3.

Région 5 :

À ce stade, rien ne rentre dans le cache. Vous êtes donc limité par la bande passante de la mémoire.

---

Answer 2

OK, la bonne réponse a certainement un rapport avec le cache du processeur. Mais l'utilisation de l'argument du cache peut s'avérer assez difficile, surtout sans données.

Il existe de nombreuses réponses, qui ont donné lieu à de nombreuses discussions, mais soyons réalistes : Les problèmes de cache peuvent être très complexes et ne sont pas unidimensionnels. Ils dépendent fortement de la taille des données, et ma question était donc injuste : elle s'est avérée se situer à un point très intéressant du graphique de la mémoire cache.

La réponse de @Mysticial a convaincu beaucoup de gens (y compris moi), probablement parce que c'était la seule qui semblait s'appuyer sur des faits, mais ce n'était qu'un "point de données" de la vérité.

C'est pourquoi j'ai combiné son test (en utilisant une allocation continue par rapport à une allocation séparée) et le conseil de @James' Answer.

Les graphiques ci-dessous montrent que la plupart des réponses et surtout la majorité des commentaires à la question et aux réponses peuvent être considérées comme complètement fausses ou vraies en fonction du scénario et des paramètres utilisés.

Notez que ma question initiale était à l'adresse suivante n = 100.000 . Ce point (par accident) présente un comportement particulier :

1. Elle présente l'écart le plus important entre la version à une et à deux boucles (presque un facteur de trois).

2. C'est le seul point où la version à une boucle (c'est-à-dire avec une allocation continue) l'emporte sur la version à deux boucles. (C'est ce qui a rendu possible la réponse de Mysticial).

Le résultat en utilisant des données initialisées :

Le résultat en utilisant des données non initialisées (c'est ce que Mysticial a testé) :

Et celle-ci est difficile à expliquer : Les données initialisées, qui sont allouées une fois et réutilisées pour chaque cas de test suivant de taille de vecteur différente :

Proposition

Chaque question relative aux performances de bas niveau sur Stack Overflow devrait être tenue de fournir des informations sur les MFLOPS pour toute la gamme des tailles de données pertinentes pour le cache ! C'est une perte de temps pour tout le monde de penser à des réponses et surtout d'en discuter avec d'autres sans cette information.

Answer 3

La deuxième boucle implique beaucoup moins d'activité de la mémoire cache, de sorte qu'il est plus facile pour le processeur de répondre aux exigences de la mémoire.

Answer 4

Imaginez que vous travaillez sur une machine où n était juste la bonne valeur pour qu'il ne soit possible de garder en mémoire que deux de vos tableaux à la fois, mais la mémoire totale disponible, grâce à la mise en cache sur disque, était encore suffisante pour contenir les quatre tableaux.

En supposant une simple politique de mise en cache LIFO, ce code :

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

serait la première cause a y b à charger dans la mémoire vive et à travailler entièrement dans la mémoire vive. Lorsque la deuxième boucle commence, c y d serait alors chargée du disque dans la mémoire vive et exploitée.

l'autre boucle

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

va paginer deux tableaux et paginer les deux autres. à chaque fois que l'on fait le tour de la boucle . Il s'agirait évidemment mucho ralentissent.

Vous ne voyez probablement pas de mise en cache sur disque dans vos tests, mais vous voyez probablement les effets secondaires d'une autre forme de mise en cache.

---

Il semble qu'il y ait un peu de confusion ou d'incompréhension à ce sujet et je vais donc essayer d'apporter quelques précisions à l'aide d'un exemple.

Dites n = 2 et nous travaillons avec des octets. Dans mon scénario, nous avons donc seulement 4 octets de RAM et le reste de notre mémoire est nettement plus lent (accès 100 fois plus long, par exemple).

En supposant une politique de mise en cache assez stupide de si l'octet n'est pas dans le cache, l'y placer et récupérer l'octet suivant tant qu'à faire vous obtiendrez un scénario semblable à celui-ci :

• Avec

  for(int j=0;j<n;j++){
   a[j] += b[j];
  }
  for(int j=0;j<n;j++){
   c[j] += d[j];
  }

• cache a[0] y a[1] puis b[0] y b[1] et définir a[0] = a[0] + b[0] dans le cache - il y a maintenant quatre octets dans le cache, a[0], a[1] y b[0], b[1] . Coût = 100 + 100.

• fixer a[1] = a[1] + b[1] dans le cache. Coût = 1 + 1.

• Répéter pour c y d .

• Coût total = (100 + 100 + 1 + 1) * 2 = 404

• Avec

  for(int j=0;j<n;j++){
   a[j] += b[j];
   c[j] += d[j];
  }

• cache a[0] y a[1] puis b[0] y b[1] et définir a[0] = a[0] + b[0] dans le cache - il y a maintenant quatre octets dans le cache, a[0], a[1] y b[0], b[1] . Coût = 100 + 100.

• éjecter a[0], a[1], b[0], b[1] de la cache et de la cache c[0] y c[1] puis d[0] y d[1] et définir c[0] = c[0] + d[0] dans le cache. Coût = 100 + 100.

• Je pense que vous commencez à voir où je veux en venir.

• Coût total = (100 + 100 + 100 + 100) * 2 = 800

Il s'agit d'un scénario classique de cache thrash.

Answer 5

Ce n'est pas dû à un code différent, mais à la mise en cache : la RAM est plus lente que les registres du CPU et une mémoire cache se trouve à l'intérieur du CPU pour éviter d'écrire dans la RAM à chaque fois qu'une variable change. Mais la mémoire cache n'est pas aussi grande que la RAM, et elle n'en cartographie donc qu'une fraction.

Le premier code modifie les adresses de mémoire distante en les alternant à chaque boucle, ce qui nécessite d'invalider continuellement le cache.

Le deuxième code n'est pas alterné : il s'écoule simplement deux fois sur des adresses adjacentes. Cela permet d'effectuer tout le travail dans le cache, en ne l'invalidant qu'après le démarrage de la deuxième boucle.