c++ technique 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?




plate forme java (8)

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


La question originale

Pourquoi une boucle est-elle tellement plus lente que deux boucles?

Conclusion:

Le cas 1 est un problème d'interpolation classique qui s'avère inefficace. Je pense également que c’est l’une des principales raisons pour lesquelles de nombreuses architectures de machines et développeurs ont fini par construire et concevoir des systèmes multicœurs capables de réaliser des applications multithreads ainsi que de la programmation parallèle.

Cette approche ne prend pas en compte la manière dont le matériel, le système d'exploitation et le (s) compilateur (s) fonctionnent ensemble pour effectuer des allocations de tas impliquant le travail avec la RAM, le cache, les fichiers de page, etc. la mathématique qui est à la base de ces algorithmes nous montre laquelle de ces deux solutions est la meilleure. Nous pouvons utiliser une analogie où un Boss ou une Summation qui représente une For Loop qui doit voyager entre les travailleurs A et B nous pouvons facilement voir que le cas 2 est au moins 1/2 aussi vite, voire un peu plus, que le cas 1 en raison de la différence de distance nécessaire pour voyager et le temps pris entre les travailleurs. Ce calcul correspond presque virtuellement et parfaitement à la fois au Bench Mark Times et à la quantité de différences entre les instructions de montage.

Je vais maintenant commencer à expliquer comment tout cela fonctionne ci-dessous.

Évaluer le problème

Le code de l'OP:

const int n=100000;

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

Et

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

La prise en compte

Considérant la question initiale du PO concernant les 2 variantes de la boucle for et sa question modifiée sur le comportement des caches ainsi que de nombreuses autres excellentes réponses et commentaires utiles; J'aimerais essayer de faire quelque chose de différent ici en adoptant une approche différente de cette situation et de ce problème.

L'approche

Compte tenu des deux boucles et de toute la discussion sur la mise en cache et le classement des pages, je souhaiterais adopter une autre approche pour aborder la question sous un angle différent. Celle qui n’implique ni les fichiers de cache et de page, ni les exécutions permettant d’allouer de la mémoire. En fait, cette approche ne concerne même pas le matériel ni les logiciels.

La perspective

Après avoir examiné le code pendant un moment, il est devenu évident que le problème est et ce qui le génère. Décomposons cela en un problème algorithmique et examinons-le sous l’angle des notations mathématiques, puis appliquons une analogie aux problèmes mathématiques ainsi qu’aux algorithmes.

Ce que nous savons

Nous savons que sa boucle fonctionnera 100 000 fois. Nous savons également que a1 , b1 , c1 et d1 sont des pointeurs sur une architecture 64 bits.Dans C ++, sur une machine 32 bits, tous les pointeurs ont une taille de 4 octets et sur une machine 64 bits, ils ont une taille de 8 octets, car les pointeurs ont une longueur fixe. Nous savons que nous avons 32 octets à allouer dans les deux cas. La seule différence est que nous allouons 32 octets ou 2 ensembles de 2 à 8 octets à chaque itération. Dans le deuxième cas, nous allouons 16 octets pour chaque itération pour les deux boucles indépendantes. Ainsi, les deux boucles représentent toujours 32 octets d'allocation totale. Avec cette information, allons de l'avant et montrons la mathématique générale, son algorithme et son analogie. Nous savons combien de fois le même ensemble ou groupe d'opérations devra être exécuté dans les deux cas. Nous connaissons la quantité de mémoire à allouer dans les deux cas. Nous pouvons évaluer que la charge de travail globale des allocations entre les deux cas sera approximativement la même.

Ce qu'on ne sait pas

Nous ne savons pas combien de temps cela prendra pour chaque cas, sauf si nous définissons un compteur et effectuons un test d'évaluation. Cependant, les points de repère étaient déjà inclus dans la question initiale et dans certaines des réponses et commentaires, et nous pouvons constater une différence significative entre les deux. C’est là le raisonnement complet de cette question à ce problème et de la commencer avec.

Enquêtons

Il est déjà évident que beaucoup l'ont déjà fait en examinant les allocations de tas, les tests d'évaluation, la RAM, le cache et les fichiers de page. L'examen de points de données spécifiques et d'index d'itération spécifiques a également été inclus et les diverses discussions sur ce problème spécifique ont amené de nombreuses personnes à s'interroger sur d'autres aspects connexes du problème. Alors, comment pouvons-nous commencer à regarder ce problème en utilisant des algorithmes mathématiques et en y appliquant une analogie? Nous commençons par faire quelques affirmations! Ensuite, nous construisons notre algorithme à partir de là.

Nos affirmations:

  • Nous allons laisser notre boucle et ses itérations être une sommation qui commence à 1 et se termine à 100000 au lieu de 0, car dans les boucles car nous n'avons pas à nous soucier du schéma d'indexation 0 de l'adressage en mémoire car nous sommes simplement intéressés par l'algorithme lui-même.
  • Dans les deux cas, nous avons 4 fonctions avec lesquelles travailler et 2 appels de fonction, 2 opérations étant effectuées pour chaque appel de fonction. Nous allons donc définir ces fonctions et comme des appels de fonctions à être F1(), F2(), f(a), f(b), f(c)et f(d).

Les algorithmes:

1er cas: - Un seul cumul mais deux appels de fonction indépendants.

Sum n=1 : [1,100000] = F1(), F2();
                       F1() = { f(a) = f(a) + f(b); }
                       F2() = { f(c) = f(c) + f(d);  }

2ème cas: - Deux sommations mais chacune a son propre appel de fonction.

Sum1 n=1 : [1,100000] = F1();
                        F1() = { f(a) = f(a) + f(b); }

Sum2 n=1 : [1,100000] = F1();
                        F1() = { f(c) = f(c) + f(d); }

Si vous avez remarqué F2()n'existe que dans Sumoù les deux Sum1et Sum2ne contient que F1(). Cela sera également évident par la suite lorsque nous commencerons à conclure qu'il y a une sorte d'optimisation à partir du deuxième algorithme.

Les itérations à travers les premiers Sumappels de cas f(a)qui s'ajouteront à f(b)lui- f(c)même seront ensuite appelées qui feront la même chose mais s'ajouteront f(d)pour chacune d'elles 100000 iterations. Dans le second cas, nous avons Sum1et Sum2Et agissons tous les deux comme si la même fonction était appelée deux fois de suite. Dans ce cas , nous pouvons traiter Sum1et Sum2comme tout simplement vieux SumSumdans ce cas ressemble à ceci: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }et maintenant cela ressemble à une optimisation où l' on peut simplement considérer qu'il est la même fonction.

Résumé avec analogie

Avec ce que nous avons vu dans le second cas, il semble presque y avoir une optimisation puisque les deux boucles for ont la même signature exacte, mais ce n’est pas le vrai problème. La question n'est pas le travail qui est fait par f(a), f(b), f(c)et f(d)dans les deux cas et la comparaison entre les deux est la différence de la distance que le Summation doit voyager dans les deux cas que vous donne la différence dans l' exécution du temps.

Pensez à l' For Loopscomme étant le Summationsqui fait les itérations comme étant un Bossqui donne des ordres à deux personnes Aet Bet que leurs emplois sont à la viande Cet , Drespectivement , et de ramasser quelques paquet d'eux et de le retourner. Dans l'analogie ici, les itérations de boucle for ou de sommation et les vérifications de condition ne représentent pas réellement le Boss. Ce qui représente en fait l' Bossest pas ici des algorithmes mathématiques réels directement, mais du concept même de Scopeet Code Blockdans une routine ou sous-routine, la méthode, la fonction, l' unité de traduction, etc. Le premier algorithme a 1 champ où le 2ème algorithme a 2 portées consécutives.

Dans le premier cas de chaque appel, le Bossdestinataire se voit Aattribuer l'ordre et s'en Ava chercher le B'scolis, puis le Bossdestinataire Creçoit l'ordre de faire de même et de recevoir le colis Dà chaque itération.

Dans le second cas, l’ Bossopérateur travaille directement avec Apour aller chercher le B'spaquet jusqu’à ce que tous les paquets soient reçus. Ensuite, les Bosstravaux avec Cpour faire la même chose pour obtenir tous les D'spaquets.

Puisque nous travaillons avec un pointeur de 8 octets et traitons avec l'allocation de tas, considérons ce problème ici. Disons que la Bossdistance est de 100 pieds Aet celle de A500 pieds C. Nous n’avons pas à nous inquiéter de la distance qui les Bosssépare initialement à Ccause de l’ordre des exécutions. Dans les deux cas, le Bossvoyage initial commence par le Apremier puis le B. Cette analogie ne veut pas dire que cette distance est exacte; il s'agit simplement d'un scénario de test d'utilisation permettant de montrer le fonctionnement des algorithmes. Dans de nombreux cas, lors de l'allocation de tas et de l'utilisation du cache et des fichiers de page, les distances entre les emplacements d'adresses peuvent ne pas varier beaucoup ou différemment selon la nature des types de données et la taille des tableaux.

Les cas de test:

Premier cas: Lorspremière itérationlaBossdoit allerabord 100 pieds pour donner le bon de commande pourAetAse éteint et fait sa chose, mais leBossdoit parcourir 500 pieds pourClui donner son bon de commande. Ensuite, à la prochaine itération et à toutes les autres itérations après,Bossil faut parcourir 500 pieds entre les deux.

Deuxième cas: il The Boss doit parcourir 100 pieds à la première itérationA, mais après cela, il est déjà là et attend justeAde revenir jusqu'à ce que tous les bordereaux soient remplis. Ensuite, ilBossdoit parcourir 500 pieds à la première itération,Ccar ilCest à 500 pieds de l’appel,Acar ilBoss( Summation, For Loop )est appelé juste après avoir travaillé avecAet attend ensuite comme il l’a faitAjusqu’à ce que tous lesC'sordres soient réglés.

La différence en distances parcourues

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); 
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst =  10000500;
// Distance Traveled On First Algorithm = 10,000,500ft

distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;    

La comparaison des valeurs arbitraires

Nous pouvons facilement voir que 600, c'est beaucoup moins que 10 millions. Or ce n’est pas exact, car nous ne connaissons pas la différence de distance entre l’adresse de mémoire vive ou le cache ou le fichier de page de chaque appel à chaque itération, ce qui sera dû à de nombreuses autres variables invisibles. une évaluation de la situation à connaître et à essayer de regarder du pire scénario.

Donc, à ces chiffres, on aurait presque l'impression que l'algorithme 1 devrait être 99% plus lent que l'algorithme 2; Cependant, ce n'est que la The Boss'spartie ou la responsabilité des algorithmes et il ne tient pas compte des travailleurs réels A, B, C, et Det ce qu'ils ont à faire sur chaque itération de la boucle. Ainsi, le travail des patrons ne représente que 15 à 40% du travail total accompli. Ainsi, la majeure partie du travail effectué par les ouvriers a un impact légèrement plus important sur le maintien du ratio des différences de taux de vitesse entre environ 50 et 70%.

L'observation: - Les différences entre les deux algorithmes

Dans cette situation, il s’agit de la structure du processus de travail en cours et cela montre que le cas 2 est plus efficace à la fois par cette optimisation partielle de la déclaration et de la définition d’une fonction similaire lorsque seules les variables diffèrent par leur nom. . Et nous voyons également que la distance totale parcourue dans le cas 1 est beaucoup plus éloignée que dans le cas 2 et nous pouvons considérer cette distance parcourue par notre facteur de temps entre les deux algorithmes. Le cas 1 a beaucoup plus de travail à faire que le cas 2 . Cela a également été vu dans le témoignage de laASMcela a été montré entre les deux cas. Même avec ce qui a déjà été dit à propos de ces cas, cela ne tient pas compte non plus du fait que dans le cas 1, le patron devra attendre les deux Aet Crevenir avant de pouvoir revenir à Ala prochaine itération et cela ne le fera pas non plus. Ne tenez pas compte du fait que si Aou Bprend beaucoup de temps Boss, le travailleur et les autres travailleurs attendent également au ralenti. Dans le cas 2, le seul moment d'inactivité est le Bossretour du travailleur. Donc, même cela a un impact sur l'algorithme.

Question (s) modifiée (s) sur les PO

EDIT: 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.

Concernant ces questions

Comme je l'ai démontré sans aucun doute, il existe un problème sous-jacent avant même que le matériel et les logiciels n'interviennent. Maintenant, en ce qui concerne la gestion de la mémoire et la mise en cache avec les fichiers de page, etc., qui fonctionnent tous ensemble dans un ensemble intégré de systèmes entre: The Architecture{Matériel, Firmware, certains pilotes intégrés, Noyaux et Jeux ASM}, The OS{Systèmes de gestion de fichiers et de mémoire , Pilotes et le registre}, The Compiler{Unités de traduction et optimisations du code source}, et même le Source Codemême avec ses ensembles d’algorithmes distinctifs; on peut déjà voir qu'il ya un goulot d' étranglement qui se passe dans le premier algorithme avant d' appliquer même à une machine avec un arbitraire Architecture, OSetProgrammable Languagepar rapport au deuxième algorithme. Donc, il existait déjà un problème avant impliquant les éléments intrinsèques d'un ordinateur moderne.

Les résultats finaux

Toutefois; cela ne veut pas dire que ces nouvelles questions n’ont pas d’importance parce qu’elles le sont et qu’elles jouent un rôle après tout. Ils ont un impact sur les procédures et la performance globale, ce qui est évident dans les divers graphiques et évaluations de nombreux auteurs qui ont donné leur réponse et / ou leurs commentaires. Si vous prêtez attention à l'analogie du Bosset des deux ouvriers A& Bqui doit aller récupérer les paquets de C& Drespectivement et en considérant les notations mathématiques des deux algorithmes en question, vous pouvez voir que même sans la participation de l'ordinateur, Case 2c'est environ 60% plus rapide queCase 1 et lorsque vous examinez les graphiques et les diagrammes une fois que ces algorithmes ont été appliqués au code source, compilés, optimisés et exécutés via le système d'exploitation pour effectuer des opérations sur le matériel donné, vous constatez même un peu plus de dégradation entre les différences entre ces algorithmes.

Maintenant, si le jeu "Data" est assez petit, cela ne vous semblera peut-être pas si différent au début, mais comme il Case 1est à peu près 60 - 70%plus lent que Case 2nous ne pouvons considérer la croissance de cette fonction comme étant la différence entre les exécutions temporelles:

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where 
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with 
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)

Et cette approximation est la différence moyenne entre ces deux boucles, tant sur le plan algorithmique que sur les opérations de la machine, impliquant des optimisations logicielles et des instructions de la machine. Ainsi, lorsque le jeu de données croît de manière linéaire, la différence de temps entre les deux augmente également. L' algorithme 1 a plus fetch que l' algorithme 2 qui est évident lorsque le Bossdevait se rendre dans les deux sens la distance maximale entre Aet Cpour chaque itération après la première itération alors que l' algorithme 2 le Bossdevait se rendre à Aune fois, puis après avoir été fait avec Ail a dû voyager une distance maximale seulement une fois pour aller de Aà C.

Donc, essayer de se Bossconcentrer sur deux choses similaires en même temps et les jongler entre elles au lieu de se concentrer sur des tâches consécutives similaires va le mettre très en colère à la fin de la journée car il devait voyager et travailler deux fois plus. Par conséquent, ne perdez pas de vue l'ampleur de la situation en laissant votre patron entrer dans un goulot d'étranglement interpolé, car son épouse et ses enfants ne l'apprécieraient pas.


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.


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.


La première boucle alterne l'écriture dans chaque variable. Les deuxième et troisième ne font que de petits sauts de taille d'élément.

Essayez d’écrire deux lignes parallèles de 20 croix avec un stylo et du papier séparés de 20 cm. Essayez de finir une ligne puis une autre et essayez une autre fois en écrivant une croix alternativement dans chaque ligne.


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.


Ce n'est pas à cause d'un code différent, mais à cause de la mise en cache: la RAM est plus lente que les registres de la CPU et une mémoire cache est à l'intérieur de la CPU pour éviter d'écrire la RAM chaque fois qu'une variable change. Mais le cache n’est pas aussi gros que la RAM, il ne mappe donc qu’une fraction de celle-ci.

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

Le second code n’alterne pas: il se contente d’adopter deux fois des adresses adjacentes. Cela rend tout le travail à terminer dans le cache, l'invalidant seulement après le début de la seconde boucle.


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