c++ - technique - plate forme java




Pourquoi les ajouts élément par élément sont-ils beaucoup plus rapides dans des boucles séparées que dans une boucle combinée? (7)

Supposons que a1 , b1 , c1 et d1 pointent vers la mémoire vive et que mon code numérique possède la boucle principale 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 for externe. 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é sur MS Visual C ++ 10.0 avec optimisation complète et SSE2 activé pour 32 bits sur un processeur Intel Core 2 Duo (x64), le premier exemple dure 5,5 secondes et le modèle à double boucle ne prend que 1,9 seconde. Ma question est la suivante: (Veuillez vous reporter à la question ma reformulée en bas)

PS: Je ne suis pas sûr, si cela aide:

Le désassemblage de la première boucle ressemble en gros à ceci (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 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 pertinence, car le comportement dépend énormément de la taille des tableaux (n) et du cache du processeur. Donc, s’il ya un intérêt supplémentaire, je reformule la question:

Pourriez-vous fournir des informations concrètes sur les détails qui conduisent aux différents comportements de cache, comme illustré par les cinq régions du graphique suivant?

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

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

#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 FLOP / s pour différentes valeurs de n .)


Après une analyse plus approfondie de cela, je pense que cela est (au moins partiellement) causé par l'alignement des données des quatre pointeurs. Cela entraînera un certain niveau de conflits entre la banque de cache et le chemin.

Si j'ai bien compris la façon dont vous allouez vos tableaux, ils seront probablement alignés sur la ligne de la page .

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

EDIT: Il semblerait en fait que vous allouiez tous les tableaux séparément. Habituellement, lorsque de telles allocations importantes sont demandées, l’allocateur demandera de nouvelles pages au système d’exploitation. Par conséquent, il y a de fortes chances que de grandes allocations apparaissent avec le même décalage par rapport à une limite de page.

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 référence:

EDIT: Résultats sur une machine d'architecture Core 2 réelle :

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. Ceci reproduit exactement les résultats du PO.

  • 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 pour rompre cet alignement. Ici, vous remarquerez que les deux boucles sont plus rapides. De plus, la deuxième (double) boucle est maintenant la plus lente, comme on pourrait s'y attendre.

Comme @Stephen Cannon l'a souligné dans les commentaires, il est fort probable que cet alignement provoque un faux aliasing dans les unités de chargement / stockage ou le cache. J'ai cherché sur Google pour cela et découvert qu'Intel avait en fait un compteur matériel pour les créneaux d'adresse partielle :

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. Le jeu 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, à mesure que la taille des données augmente, la surcharge relative diminue et la performance "sature". Ici, deux boucles sont plus lentes car elles ont deux fois plus de temps système.

Je ne sais pas exactement ce qui se passe ici ... L'alignement pourrait toujours jouer un rôle puisque Agner Fog mentionne les conflits liés à la banque de cache . (Ce lien concerne Sandy Bridge, mais l'idée devrait toujours s'appliquer à Core 2.)

Région 3:

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

Région 4:

Nous observons la baisse de performance dans la boucle unique. Et comme mentionné, cela est dû à l'alignement qui (le plus probable) provoque de faux décrochages dans les unités de chargement / stockage du processeur.

Toutefois, pour que les faux alias se produisent, il faut que la distance entre les jeux de données soit suffisamment grande. C'est pourquoi vous ne voyez pas cela dans la région 3.

Région 5:

À ce stade, rien ne tient dans le cache. Donc, vous êtes lié par la bande passante de la mémoire.


C'est parce que le processeur n'a pas tellement de cache manquants (où il doit attendre que les données de la matrice viennent des puces de RAM). Il serait intéressant pour vous de régler continuellement la taille des tableaux afin de dépasser les tailles du cache de niveau 1 (L1), puis du cache de niveau 2 (L2) de votre CPU et de tracer le temps nécessaire à votre code. exécuter contre les tailles des tableaux. Le graphique ne doit pas être une ligne droite comme on peut s'y attendre.


Imaginez que vous travailliez sur une machine où n était juste la valeur qui convient, car il était possible de conserver deux matrices en mémoire à la fois, mais la mémoire totale disponible, via la mise en cache sur le disque, était encore suffisante pour contenir les quatre.

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

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

provoquerait d'abord le chargement de a et b dans la RAM, puis le traitement complet de celle-ci. Lorsque la deuxième boucle commence, c et d seraient alors chargés du disque dans la RAM et exploités.

l'autre boucle

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

mettra en page deux tableaux et une page dans les deux autres à chaque fois autour de la boucle . Ce serait évidemment beaucoup plus lent.

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

Il semble y avoir un peu de confusion / malentendu ici, donc je vais essayer de développer un peu en utilisant un exemple.

Dites n = 2 et nous travaillons avec des octets. Dans mon scénario, nous n'avons donc que 4 octets de RAM et le reste de notre mémoire est beaucoup plus lente (disons un accès 100 fois plus long).

En supposant une politique de mise en cache assez stupide consistant à dire que si l'octet n'est pas dans le cache, mettez-le là et obtenez l'octet suivant aussi pendant que nous y sommes, vous obtiendrez un scénario ressemblant à ceci:

  • 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] et a[1] puis b[0] et b[1] et définit a[0] = a[0] + b[0] dans le cache - il y a maintenant quatre octets dans le cache, a[0], a[1] et b[0], b[1] . Coût = 100 + 100.

  • définir a[1] = a[1] + b[1] dans le cache. Coût = 1 + 1.
  • Répétez pour c et 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] et a[1] puis b[0] et b[1] et définit a[0] = a[0] + b[0] dans le cache - il y a maintenant quatre octets dans le cache, a[0], a[1] et b[0], b[1] . Coût = 100 + 100.

  • éjecter a[0], a[1], b[0], b[1] de cache et cache c[0] et c[1] puis d[0] et d[1] et initialise c[0] = c[0] + d[0] en cache. Coût = 100 + 100.
  • Je suppose que vous commencez à voir où je vais.
  • Coût total = (100 + 100 + 100 + 100) * 2 = 800

Ceci est un scénario de thrash en cache classique.


La deuxième boucle implique beaucoup moins d'activité de la mémoire cache. Il est donc plus facile pour le processeur de répondre aux besoins en mémoire.


OK, la bonne réponse doit absolument faire quelque chose avec le cache du processeur. Mais utiliser l'argument cache peut être assez difficile, surtout sans données.

Il y a beaucoup de réponses qui ont conduit à beaucoup de discussions, mais avouons-le: les problèmes de cache peuvent être très complexes et ne sont pas unidimensionnels. Elles dépendent fortement de la taille des données, ma question était donc injuste: elle s’est avérée être à un point très intéressant du graphique en cache.

La réponse de @ Mysticial a convaincu beaucoup de gens (dont moi), probablement parce que c'était le seul 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 attribution continue ou distincte) et le conseil de @James 'Answer.

Les graphiques ci-dessous montrent que la plupart des réponses, et en particulier la majorité des commentaires sur la question et les 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 à n = 100 000 . Ce point (par accident) présente un comportement particulier:

  1. Il possède le plus grand écart entre la version à une et deux boucles (presque un facteur de trois)

  2. C'est le seul point où une boucle (à savoir avec une affectation continue) bat la version à deux boucles. (Cela rendait la réponse de Mysticial possible.)

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

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

Il s’agit d’un problème difficile à expliquer: des données initialisées, allouées une fois pour toutes et réutilisées pour chaque test élémentaire suivant, de taille de vecteur différente:

Proposition

Chaque question liée aux performances de bas niveau sur le dépassement de pile devrait être obligée de fournir des informations MFLOPS pour toute la gamme des tailles de données pertinentes du cache! Tout le monde perd son temps à réfléchir aux réponses et surtout à en discuter avec les autres sans cette information.


Je ne peux pas reproduire les résultats discutés ici.

Je ne sais pas si le code de référence médiocre est à blâmer, ou quoi, mais les deux méthodes sont proches de 10% l'une de l'autre sur ma machine à l'aide du code suivant, et une boucle est généralement légèrement plus rapide que deux - comme vous le feriez attendre.

Les tailles de tableau allaient de 2 ^ 16 à 2 ^ 24, en utilisant huit boucles. J'ai pris soin d'initialiser les tableaux source afin que l'assignation += ne demande pas à la FPU d'ajouter des déchets de mémoire interprétés comme un double.

J'ai joué avec différents schémas, tels que mettre l'affectation de b[j] , d[j] à InitToZero[j] dans les boucles, et aussi d'utiliser += b[j] = 1 et += d[j] = 1 et j'ai obtenu des résultats assez cohérents.

Comme on pouvait s’y attendre, l’initialisation de b et d à l’intérieur de la boucle à l’aide de InitToZero[j] conférait un avantage à l’approche combinée, car elles étaient exécutées dos à dos avant les assignations à a et c , mais à 10% près. Allez comprendre.

Le matériel est le Dell XPS 8500 avec la génération 3 Core i7 à 3,4 GHz et 8 Go de mémoire. Pour 2 ^ 16 à 2 ^ 24, avec huit boucles, le temps cumulé était respectivement de 44,987 et de 40,965. Visual C ++ 2010, entièrement optimisé.

PS: J'ai changé les boucles pour décompter à zéro et la méthode combinée était légèrement plus rapide. Me gratter la tête. Notez le nouveau dimensionnement et le nombre de boucles de la matrice.

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

Je ne sais pas pourquoi il a été décidé que MFLOPS était une mesure pertinente. Je pensais que l’idée était de se concentrer sur les accès en mémoire, alors j’ai essayé de minimiser le temps de calcul en virgule flottante. Je suis parti dans le += , mais je ne sais pas pourquoi.

Une affectation simple sans calcul constituerait un test plus clair du temps d'accès à la mémoire et créerait un test uniforme quel que soit le nombre de boucles. J'ai peut-être manqué quelque chose dans la conversation, mais cela vaut la peine d'y réfléchir à deux fois. Si le plus est laissé en dehors de l'affectation, le temps cumulé est presque identique à 31 secondes chacun.


Il peut s'agir d'ancien C ++ et d'optimisations. Sur mon ordinateur, j'ai obtenu presque la même vitesse:

Une boucle: 1,577 ms

Deux boucles: 1,507 ms

J'exécute Visual Studio 2015 sur un processeur E5-1620 de 3,5 GHz avec 16 Go de RAM.





vectorization