2241 votes

Pourquoi une boucle beaucoup plus lent que les deux boucles?

Supposons a1, b1, c1, et d1 point d'un segment de mémoire et mon code numérique a la suite de base de la boucle.

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 de 10 000 fois par le biais d'un autre extérieure, for boucle. Pour l'accélérer, j'ai changé le code pour:

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 une optimisation complète et SSE2 activé pour 32 bits sur un processeur Intel Core 2 Duo (x64), le premier exemple prend en 5,5 secondes et la double boucle de l'exemple prend seulement 1,9 secondes. Ma question est la suivante: (Veuillez vous référer à la ma reformulé la question au bas de la page)

PS: je ne suis pas sûr que cela aide:

Démontage pour la première boucle de coeur ressemble à ceci (ce bloc est répété 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 la double boucle exemple produit ce code (le bloc suivant est répété 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

EDIT: La question s'est avéré être sans intérêt, comme le comportement gravement dépend de la taille des matrices (n) et la cache du PROCESSEUR. Donc, si il n'y a plus d'intérêt, je reformuler la question:

Pourriez-vous fournir un aperçu de l'détails qui mènent aux différents comportements de cache comme illustré par les cinq régions sur le graphique ci-dessous?

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

PPS: Le code complet est à http://pastebin.com/ivzkuTzG. Il utilise TBB Tick_Count pour minutage de résolution plus élevée, qui peut être désactivé en ne définissant pas la TBB_TIMING Macro.

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

enter image description here

1689voto

Mysticial Points 180300

Après une analyse plus approfondie de cela, je crois que c'est (au moins partiellement) causée par l'alignement des données des quatre pointeurs. Cela va entraîner un certain niveau de cache de la banque/chemin des conflits.

Si j'ai deviné correctement sur la façon dont vous êtes l'allocation de vos tableaux, ils sont susceptibles d'être aligné sur la page de la ligne.

Cela signifie que tous vos accès dans chaque boucle va tomber sur le même cache. Cependant, les processeurs Intel ont eu 8 voies de l'associativité du cache L1 pour un certain temps. Mais en réalité, la performance n'est pas complètement uniforme. Accès 4 voies est encore plus lent que dire de 2 façons.

EDIT : Il n'en fait pas ressembler à vous l'affectation de tous les tableaux séparément. Lorsque ces importantes allocations sont demandées, l'allocateur demandera des frais des pages de l'OS. Par conséquent, il est fort probable que les grandes affectations apparaîtra au même décalage à partir d'une page de limite.

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;
}

Les Résultats De Benchmark:

EDIT: les Résultats sur une réelle Core 2 l'architecture de la machine:

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. Il reproduit l'OP résultats exactement.

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

  • Dans les deux tests, les tableaux sont emballés ensemble pour briser l'alignement. Ici, vous remarquerez les deux boucles sont de plus en plus vite. En outre, le deuxième (double) de la boucle est maintenant le ralentissement de celle que vous auriez normalement s'attendre.

@Stephen Cannon points dans les commentaires, il est très probable que cet alignement causes de faux aliasing dans le load/store unités ou le cache. J'ai Googlé autour de cela et a constaté que Intel a fait un matériel de comptoir pour adresse partielle aliasing stands:

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:

C'est facile. Le dataset est si petite que la performance est dominé par les frais généraux comme le bouclage et la ramification.

Région 2:

Ici, comme la taille des données augmente, la quantité relative des frais généraux va vers le bas et de la performance "acides gras saturés". Ici, deux boucles est plus lent, car il a deux fois plus de boucle et la ramification des frais généraux.

Je ne suis pas sûr exactement ce qui se passe ici... Alignement pourrait encore jouer un effet Agner Brouillard mentionne cache de la banque des conflits. (Le lien est sur Sandy Bridge, mais l'idée doit encore être applicable aux Core 2.)

Région 3:

À ce stade, les données n'ont plus leur place dans le cache L1. Afin que les performances sont limitées par la L1 <-> cache L2 de la bande passante.

Région 4:

La chute des performances en boucle simple est ce que nous observons. Et comme mentionné, cela est dû à l'alignement (le plus probable) causes de faux aliasing étals de la charge du processeur/unités dans le magasin.

Toutefois, pour que le faux de l'aliasing à se produire, il doit y avoir une assez grande foulée entre les ensembles de données. C'est pourquoi vous ne voyez pas ce dans la région 3.

Région 5:

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


2 x Intel X5482 Harpertown @ 3.2 GHzIntel Core i7 870 @ 2.8 GHzIntel Core i7 2600K @ 4.4 GHz

224voto

Johannes Gerer Points 5662

OK, la bonne réponse est faire quelque chose avec le cache du PROCESSEUR. Mais utiliser l'argument cache peut être assez difficile, surtout en l'absence de données.

Il y a plusieurs réponses, ce qui a conduit à beaucoup de discussions, mais avouons-le: 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, donc ma question était unfiar: Il s'est avéré être à un point très intéressant dans le cache graphique.

@Mysticial réponse convaincu que beaucoup de gens (moi y compris), sans doute parce qu'il était le seul qui semblait compter sur des faits, mais c'était seulement un "point de données" de la vérité.

C'est pourquoi j'ai combiné son test (à l'aide d'un continu vs séparée de répartition) et @James Répondre à ses conseils.

Les graphiques ci-dessous montre que la plupart des réponses et surtout la majorité des commentaires à la question et les réponses peuvent être considérées comme complelety faux ou vrai selon le scénario exact et les paramètres utilisés.

Notez que ma question de départ était à n = 100.000. Ce point (par accident) présente un comportement particulier:

  1. Il possède le plus grand écart entre l'une et de deux boucle ed version (près d'un facteur de trois)

  2. C'est le seul point où l'on en boucle (c'est à dire avec continue d'allocation) bat les deux boucles de la version. (Ce fait Mysticial réponse du possible, à tous.)

Le résultat à l'aide de données initialisées:

Enter image description here

Le résultat à l'aide de données non initialisées (c'est ce que Mysticial testé):

Enter image description here

Et c'est difficile à expliquer: Initilized de données, qui est attribuée une fois et réutilisés pour chaque suite de cas de test de différentes taille de vecteur:

Enter image description here

Proposition

Chaque de bas niveau de performance liés à la question sur Stack Overflow devraient être tenus de fournir MFLOPS de l'information pour l'ensemble de la gamme de cache de données pertinentes tailles! C'est un gaspillage de tout le monde est temps de penser à des réponses et surtout discuter avec les autres sans cette information.

81voto

Puppy Points 90818

La deuxième boucle implique beaucoup moins de l'activité de cache, de sorte qu'il est plus facile pour le processeur de suivre les demandes de mémoire.

50voto

OldCurmudgeon Points 16615

Imaginez que vous travaillez sur une machine où n était juste la bonne valeur pour lui que pour être possible de tenir deux de vos tableaux dans la mémoire à un moment, mais la quantité totale de mémoire disponible, via la mise en cache disque, était encore suffisante pour accueillir tous les quatre.

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

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

serait la première cause a1 et b1 à être chargé dans la RAM et ensuite être travaillé entièrement en RAM. Lors de la deuxième boucle commence, c1 et d1 serait alors chargé à partir du disque en RAM et opéré.

l'autre boucle

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

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

Vous n'êtes probablement pas voir la mise en cache disque dans vos tests, mais vous êtes probablement en voyant les effets secondaires de certains 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 à l'aide d'un exemple.

Dire n = 2 , et nous travaillons avec des octets. Dans mon scénario, nous avons donc seulement 4 octets de mémoire cache et le reste de notre mémoire est sensiblement plus lent (par exemple 100 fois plus de temps d'accès).

En supposant une assez stupide politique de mise en cache de si l'octet n'est pas dans le cache, de le mettre là-bas et obtenir l'octet suivant de trop alors que nous sommes à elle , vous obtiendrez un scénario quelque chose comme ceci:

  • Avec

    for(int j=0;j<n;j++){
     a1[j] += b1[j];
    }
    for(int j=0;j<n;j++){
     c1[j] += d1[j];
    }
    
  • cache a1[0] et a1[1] alors b1[0] et b1[1] et définissez a1[0] = a1[0] + b1[0] dans le cache, il y a maintenant quatre octets dans la mémoire cache, a1[0], a1[1] et b1[0], b1[1]. Coût = 100 + 100.

  • ensemble a1[1] = a1[1] + b1[1] dans le cache. Coût = 1 + 1.
  • Répétez l'opération pour c1 et " d1.
  • Coût Total = (100 + 100 + 1 + 1) * 2 = 404

  • Avec

    for(int j=0;j<n;j++){
     a1[j] += b1[j];
     c1[j] += d1[j];
    }
    
  • cache a1[0] et a1[1] alors b1[0] et b1[1] et définissez a1[0] = a1[0] + b1[0] dans le cache, il y a maintenant quatre octets dans la mémoire cache, a1[0], a1[1] et b1[0], b1[1]. Coût = 100 + 100.

  • d'éjection a1[0], a1[1], b1[0], b1[1] à partir du cache et cache c1[0] et c1[1] alors d1[0] et d1[1] et définissez c1[0] = c1[0] + d1[0] dans le cache. Coût = 100 + 100.
  • Je soupçonne que vous commencez à voir où je vais.
  • Coût Total = (100 + 100 + 100 + 100) * 2 = 800

C'est un classique cache thrash scénario.

35voto

Emilio Garavaglia Points 9189

Ce n'est pas parce que d'un autre code, mais en raison de la mise en cache: mémoire RAM est plus lent que les registres du CPU et une mémoire cache est une mémoire à l'intérieur du PROCESSEUR pour éviter d'écrire la RAM à chaque fois qu'une variable est en train de changer. Mais le cache n'est pas grande, la RAM, donc, il cartes seulement une fraction de celui-ci.

Le premier code modifie lointain souvenir des adresses en les alternant à chaque tour de boucle, ce qui nécessite en permanence d'invalider le cache.

Le deuxième code n'est pas en alternance: il vient de flux sur les adresses deux fois. Cela rend d'autant la tâche à effectuer dans le cache, l'invalider, seulement après la deuxième boucle commence.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X