Supposons a1, b1, c1, et le d1point de segment de mémoire et mon code numérique comprend la boucle de base 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 forboucle 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 Intel Core 2 Duo (x64), le premier exemple prend 5,5 secondes et l'exemple à double boucle ne prend que 1,9 secondes. Ma question est: (Veuillez vous référer à ma question reformulée en bas)

PS: je ne sais pas si cela aide:

Le désassemblage de la première boucle ressemble à 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 boucle double 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 fortement des tailles des tableaux (n) et du cache du processeur. Donc s'il y a plus d'intérêt, je reformule la question:

Pourriez-vous fournir des informations solides sur les détails qui conduisent aux différents comportements de cache, comme illustré par les cinq régions sur le 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.

PPS: Voici le code complet. Il utilise TBB Tick_Count pour une synchronisation de résolution supérieure, qui peut être désactivée en ne définissant pas la TBB_TIMINGmacro:

#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 affiche 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 points. Cela entraînera un certain niveau de conflits de banque / chemin de cache.

Si j'ai bien deviné comment vous allouez vos tableaux, ils 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é du 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 encore plus lent que, disons, à 2 voies.

EDIT: Il semble en fait que vous allouez 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 au 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 véritable machine d'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 seconds 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 vous vous en doutez normalement.

Comme le souligne @Stephen Cannon dans les commentaires, il est très probable que cet alignement provoque un faux alias dans les unités de chargement / stockage ou dans le cache. J'ai cherché sur Google pour cela et j'ai constaté qu'Intel a en fait un compteur matériel pour les décrochages d' alias 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. L'ensemble de données est si petit que les performances sont dominées par des frais généraux comme le bouclage et la ramification.

Région 2:

Ici, à mesure que la taille des données augmente, la quantité de surcharge relative diminue et les performances «saturent». Ici, deux boucles sont plus lentes car elles ont deux fois plus de boucles et de frais généraux de branchement.

Je ne sais pas exactement ce qui se passe ici ... L'alignement pourrait toujours avoir un effet car Agner Fog mentionne des conflits de banque de cache . (Ce lien concerne Sandy Bridge, mais l'idée devrait toujours être applicable au 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:

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

Cependant, pour qu'un faux alias se produise, il doit y avoir un pas assez important entre les jeux de données. C'est pourquoi vous ne voyez pas cela dans la région 3.

Région 5:

À ce stade, rien ne tient dans le cache. Vous êtes donc lié à la bande passante mémoire.

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

Il existe de nombreuses réponses, qui ont conduit à de nombreuses 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 injuste: il s'est avéré être à un point très intéressant dans le graphique du cache.

@ La réponse de Mysticial a convaincu beaucoup de gens (dont 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 vs séparée) et les conseils 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és comme complètement faux ou vrais selon le scénario exact et les 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 allocation continue) bat la version à deux boucles. (Cela 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 c'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

Toutes les questions liées aux performances de bas niveau sur Stack Overflow doivent être requises pour fournir des informations MFLOPS pour toute la gamme de tailles de données pertinentes pour le cache! C'est une perte de temps pour chacun de penser aux réponses et surtout d'en discuter avec les autres sans ces informations.

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

Imaginez que vous travaillez sur une machine où nla juste valeur était juste pour qu'il soit possible de conserver deux de vos baies en mémoire en même temps, mais la mémoire totale disponible, via la mise en cache du 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];
}

serait d'abord provoquer aet bêtre chargé dans la RAM, puis être travaillé entièrement dans la RAM. Lorsque la deuxième boucle démarre, cet dserait ensuite chargé du disque dans la RAM et opéré.

l'autre boucle

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

va paginer deux tableaux et paginer dans les deux autres à chaque fois dans la boucle . Ce serait évidemment beaucoup plus lent.

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

Il semble y avoir un peu de confusion / malentendu ici, donc j'essaierai d'élaborer un peu en utilisant un exemple.

Dites n = 2et 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 considérablement plus lent (disons un accès 100 fois plus long).

En supposant une politique de mise en cache assez stupide si l'octet n'est pas dans le cache, placez-le là et obtenez également l'octet suivant pendant que nous y sommes, vous obtiendrez un scénario quelque chose comme 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], a[1]puis b[0]et b[1]et mis a[0] = a[0] + b[0]en cache - il y a maintenant quatre octets en cache, a[0], a[1]et b[0], b[1]. Coût = 100 + 100.

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

• éjecter a[0], a[1], b[0], b[1]du cache et du cache c[0], c[1]puis d[0]et d[1]et définir c[0] = c[0] + d[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

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

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 du CPU et une mémoire cache est à l'intérieur du CPU pour éviter d'écrire la RAM chaque fois qu'une variable change. Mais le cache n'est pas grand comme la RAM, donc il n'en mappe qu'une fraction.

Le premier code modifie des adresses mémoire distantes en les alternant à chaque boucle, nécessitant ainsi en continu d'invalider le cache.

Le deuxième code ne change pas: il circule simplement deux fois sur les adresses adjacentes. Cela rend tout le travail à terminer dans le cache, l'invalidant uniquement après le démarrage de la deuxième boucle.

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

Je ne sais pas si un mauvais code de référence est à blâmer, ou quoi, mais les deux méthodes sont à moins de 10% l'une de l'autre sur ma machine en utilisant le 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 variaient de 2 ^ 16 à 2 ^ 24, en utilisant huit boucles. J'ai pris soin d'initialiser les tableaux source afin que l' +=affectation ne demande pas au FPU d'ajouter des déchets de mémoire interprétés comme un double.

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

Comme vous vous en doutez, l'initialisation bet dl'utilisation de la boucle ont InitToZero[j]donné un avantage à l'approche combinée, car elles ont été effectuées consécutivement avant les affectations à aetc , mais toujours dans les 10%. 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, en utilisant huit boucles, le temps cumulé était de 44,987 et 40,965 respectivement. Visual C ++ 2010, entièrement optimisé.

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

// 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 à la mémoire, j'ai donc essayé de minimiser le temps de calcul en virgule flottante. Je suis parti dans le +=, mais je ne sais pas pourquoi.

Une affectation directe sans calcul serait un test plus net du temps d'accès à la mémoire et créerait un test uniforme quel que soit le nombre de boucles. Peut-être que j'ai raté quelque chose dans la conversation, mais cela vaut la peine d'y réfléchir à deux fois. Si le plus est omis de l'affectation, le temps cumulé est presque identique à 31 secondes chacun.

C'est parce que le CPU n'a pas autant de ratés de cache (où il doit attendre que les données du tableau proviennent des puces RAM). Il serait intéressant pour vous d'ajuster 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 par rapport aux tailles des tableaux. Le graphique ne doit pas être une ligne droite comme vous vous y attendez.

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 par 20 cm. Essayez de terminer une fois puis l'autre ligne et essayez une autre fois en écrivant une croix dans chaque ligne en alternance.

La question d'origine

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

Conclusion:

Cas 1 est un problème d'interpolation classique qui s'avère être inefficace. Je pense également que c'était 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 avec la capacité de faire des applications multithread ainsi que la programmation parallèle.

Le regarder à partir de ce type d'approche sans impliquer comment le matériel, le système d'exploitation et les compilateurs fonctionnent ensemble pour effectuer des allocations de tas qui impliquent de travailler avec la RAM, le cache, les fichiers de page, etc. les mathématiques qui sont à la base de ces algorithmes nous montrent laquelle de ces deux est la meilleure solution.

Nous pouvons utiliser une analogie d'un Bossêtre Summationqui représentera un For Loopqui doit voyager entre les travailleurs Aet B.

Nous pouvons facilement voir que le cas 2 est au moins deux fois moins rapide, sinon un peu plus que le cas 1, en raison de la différence de distance à parcourir et du temps pris entre les travailleurs. Ces calculs s'alignent presque virtuellement et parfaitement avec le BenchMark Times ainsi qu'avec le nombre de différences dans 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 originale du PO sur les 2 variantes des boucles for et sa question modifiée concernant 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 le cache et le dépôt de pages, j'aimerais adopter une autre approche pour examiner les choses sous un angle différent. Celui qui n'implique pas le cache et les fichiers d'échange ni les exécutions pour allouer de la mémoire, en fait, cette approche ne concerne même pas du tout le matériel ou le logiciel.

La perspective

Après avoir regardé le code pendant un certain temps, il est devenu tout à fait évident quel est le problème et ce qui le génère. Décomposons cela en un problème algorithmique et examinons-le du point de vue de l'utilisation des notations mathématiques, puis appliquons une analogie aux problèmes mathématiques ainsi qu'aux algorithmes.

Ce que nous savons

Nous savons que cette boucle sera exécutée 100 000 fois. Nous savons aussi que a1, b1, c1et d1sont des pointeurs sur une architecture 64 bits. Dans C ++ sur une machine 32 bits, tous les pointeurs font 4 octets et sur une machine 64 bits, ils ont une taille de 8 octets car les pointeurs sont de 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.

Les deux boucles égalent toujours 32 octets dans les allocations totales. Avec ces informations, allons de l'avant et montrons les mathématiques générales, les algorithmes et l'analogie de ces concepts.

Nous savons le nombre de fois qu'un même ensemble ou groupe d'opérations devra être effectué dans les deux cas. Nous connaissons la quantité de mémoire qui doit être allouée 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 que nous ne savons pas

Nous ne savons pas combien de temps cela prendra pour chaque cas, sauf si nous définissons un compteur et exécutons un test de référence. Cependant, les repères étaient déjà inclus à partir de la question initiale et de certaines réponses et commentaires également; et nous pouvons voir une différence significative entre les deux et c'est tout le raisonnement pour cette proposition à ce problème.

Enquêtons

Il est déjà évident que beaucoup l'ont déjà fait en examinant les allocations de tas, les tests de référence, la RAM, le cache et les fichiers d'échange. L'examen de points de données spécifiques et d'indices d'itération spécifiques a également été inclus et les diverses conversations sur ce problème spécifique ont amené de nombreuses personnes à s'interroger sur d'autres sujets connexes. Comment commencer à regarder ce problème en utilisant des algorithmes mathématiques et en lui 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 commencer par 0 comme dans les boucles car nous n'avons pas à nous soucier du schéma d'indexation 0 de l'adressage de la 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 avec 2 opérations en cours sur chaque appel de fonction. Nous allons définir ces fonctions et comme des appels à des fonctions comme suit: F1(), F2(), f(a), f(b), f(c)et f(d).

Les algorithmes:

1er cas: - Une seule sommation 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é qu'il F2()n'existe que dans Sumd' Case1où F1()est contenu dans Sumde Case1et dans les deux Sum1et Sum2de Case2. Cela sera évident plus tard lorsque nous commencerons à conclure qu'il y a une optimisation qui se produit dans le deuxième algorithme.

Les itérations à travers les premiers Sumappels de cas f(a)qui s'ajouteront à lui-même f(b)puis les appels f(c)qui feront de même mais s'ajouteront f(d)à chaque 100000itération. Dans le second cas, nous avons Sum1et Sum2que les deux agissent de la même manière que s'ils étaient la même fonction appelée deux fois de suite.

Dans ce cas, nous pouvons traiter Sum1et Sum2comme tout simplement vieux Sumoù Sumdans ce cas, cela ressemble à ceci: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }et maintenant cela ressemble à une optimisation où nous pouvons simplement considérer que c'est la même fonction.

Résumé avec l'analogie

Avec ce que nous avons vu dans le deuxième cas, il semble presque qu'il y ait optimisation car les deux boucles 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, c'est la différence de distance que doit parcourir la somme dans chaque cas qui vous donne la différence de temps d'exécution.

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 cette analogie, les boucles for ou les itérations de sommation et les vérifications de conditions elles-mêmes ne représentent pas réellement le Boss. Ce qui représente réellement le Bossn'est pas directement issu des algorithmes mathématiques réels, mais du concept réel de Scopeet Code Blockau sein d'une routine ou d'un sous-programme, d'une méthode, d'une fonction, d'une unité de traduction, etc.

Dans le premier cas sur chaque fiche d'appel, le Bossva à Aet donne la commande et Apart chercher le B'spaquet puis le Bossva à Cet donne les ordres de faire de même et de recevoir le paquet Dà chaque itération.

Dans le second cas, le programme Bosstravaille directement avec Apour aller chercher le B'spaquet jusqu'à ce que tous les paquets soient reçus. Ensuite, Bossfonctionne avec Cpour faire de même pour obtenir tous les D'spackages.

Étant donné que nous travaillons avec un pointeur de 8 octets et que nous traitons l'allocation de segment de mémoire, considérons le problème suivant. Disons que le Bossest à 100 pieds Aet à A500 pieds C. Nous n'avons pas à nous soucier de la distance qui les Bosssépare initialement en Craison de l'ordre des exécutions. Dans les deux cas, le Bossvoyage d' Aabord du premier au ensuite B. Cette analogie ne veut pas dire que cette distance est exacte; c'est juste un scénario de cas de test utile pour montrer le fonctionnement des algorithmes.

Dans de nombreux cas, lors de l'allocation de segments de mémoire et de l'utilisation du cache et des fichiers d'échange, ces distances entre les emplacements d'adresses peuvent ne pas varier beaucoup ou elles peuvent varier considérablement en fonction de la nature des types de données et des tailles de tableau.

Les cas de test:

Premier cas: lors de la première itération, leBossdoit d'abord parcourir 100 pieds pour donner le bon de commandeAet s'enAva et fait son truc, mais ilBossdoit ensuite parcourir 500 pieds pourClui donner son bon de commande. Ensuite, à la prochaine itération et à toutes les autres itérations après leBossdoit faire 500 allers-retours entre les deux.

Deuxième cas: LeBossdoit parcourir 100 pieds lors de la première itérationA, mais après cela, il est déjà là et attend justeAde revenir jusqu'à ce que tous les feuillets soient remplis. Ensuite, ilBossdoit parcourir 500 pieds lors de la première itérationCcar il seCtrouve à 500 pieds deA. Étant donné que celaBoss( Summation, For Loop )est appelé juste après avoir travaillé avec,Ail attend juste là comme il l'a faitAjusqu'à ce que tous lesbonsdeC'scommande soient effectués.

La différence de 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 est bien moins de 10 millions. Maintenant, ce n'est pas exact, car nous ne connaissons pas la différence réelle de distance entre quelle adresse de RAM ou de quel cache ou fichier d'échange chaque appel à chaque itération sera dû à de nombreuses autres variables invisibles. Il s'agit simplement d'une évaluation de la situation à prendre en compte et de l'examiner dans le pire des cas.

D'après ces chiffres, il semblerait presque que l'algorithme un devrait être 99%plus lent que l'algorithme deux; Cependant, ce n'est que la 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. Le travail du patron ne représente donc qu'environ 15 à 40% du travail total effectué. La majeure partie du travail effectué par les travailleurs a un impact légèrement plus important sur le maintien du rapport des différences de taux de vitesse à environ 50-70%

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

Dans cette situation, c'est la structure du processus de travail en cours. Cela montre que le cas 2 est plus efficace à la fois par l'optimisation partielle d'avoir une déclaration et une définition de fonction similaires où seules les variables diffèrent par leur nom et la distance parcourue.

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 comme notre facteur temps entre les deux algorithmes. Le cas 1 a beaucoup plus de travail à faire que le cas 2 .

Cela ressort de la preuve des ASMinstructions qui ont été montrées dans les deux cas. Avec ce qui a déjà été dit à propos de ces cas, cela ne tient pas compte du fait que dans le cas 1, le patron devra attendre les deux Aet Crevenir avant de pouvoir revenir à Anouveau à chaque itération. Cela ne tient pas compte non plus du fait que si Aou Bprend un temps extrêmement long, le Bossou les autres travailleurs sont inactifs en attente d'être exécutés.

Dans le cas 2, le seul qui est inactif est Bossjusqu'à ce que le travailleur revienne. Donc, même cela a un impact sur l'algorithme.

Question (s) modifiée (s) du PO

EDIT: La question s'est avérée sans pertinence, car le comportement dépend fortement des tailles des tableaux (n) et du cache du processeur. Donc s'il y a plus d'intérêt, je reformule la question:

Pourriez-vous fournir des informations solides sur les détails qui conduisent aux différents comportements de cache, comme illustré par les cinq régions sur le 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.

Concernant ces questions

Comme je l'ai démontré sans aucun doute, il y a un problème sous-jacent avant même que le matériel et les logiciels ne soient impliqués.

Maintenant, en ce qui concerne la gestion de la mémoire et de la mise en cache avec les fichiers de page, etc. qui fonctionnent tous ensemble dans un ensemble intégré de systèmes entre les éléments suivants:

• The Architecture {Matériel, micrologiciel, certains pilotes intégrés, noyaux et jeux d'instructions ASM}.
• The OS{Systèmes de gestion de fichiers et de mémoire, pilotes et registre}.
• The Compiler {Unités de traduction et optimisations du code source}.
• Et même le Source Codelui - même avec son ensemble 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, OSet par Programmable Languagerapport au deuxième algorithme. Il existait déjà un problème avant d'impliquer les 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 elles-mêmes et qu'elles jouent un rôle après tout. Ils ont un impact sur les procédures et les performances globales et cela est évident avec les différents graphiques et évaluations de beaucoup de ceux qui ont donné leur (s) réponse (s) et / ou commentaire (s).

Si vous avez fait attention à l'analogie entre le Bosset les deux travailleurs A& Bqui ont dû aller chercher des packages à partir de C& Drespectivement et en considérant les notations mathématiques des deux algorithmes en question; vous pouvez voir sans l'implication du matériel informatique et des logiciels Case 2est environ 60%plus rapide que Case 1.

Lorsque vous regardez les graphiques et les graphiques après que ces algorithmes ont été appliqués à du code source, compilés, optimisés et exécutés via le système d'exploitation pour effectuer leurs opérations sur un matériel donné, vous pouvez même voir un peu plus de dégradation entre les différences dans ces algorithmes.

Si l' Dataensemble est assez petit, il peut ne pas sembler si mauvais d'une différence au premier abord. Cependant, étant donné qu'il Case 1est à peu près 60 - 70%plus lent que Case 2nous pouvons regarder la croissance de cette fonction en termes de différences dans les exécutions de temps:

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)

Cette approximation est la différence moyenne entre ces deux boucles à la fois algorithmiquement et les opérations machine impliquant des optimisations logicielles et des instructions machine.

Lorsque l'ensemble de données croît de façon linéaire, la différence de temps entre les deux augmente également. L'algorithme 1 a plus de récupérations que l'algorithme 2, ce qui est évident lorsque le Bossdoit parcourir la distance maximale entre Aet Cpour chaque itération après la première itération tandis que l'algorithme 2 Bossdoit parcourir Aune fois puis après avoir terminé, Ail doit voyager une distance maximale une seule fois pour aller de Aà C.

Essayer de se Bossconcentrer sur deux choses similaires à la fois et de les jongler d'avant en arrière au lieu de se concentrer sur des tâches consécutives similaires va le mettre en colère à la fin de la journée car il a dû voyager et travailler deux fois plus. Par conséquent, ne perdez pas la portée de la situation en laissant votre patron entrer dans un goulot d'étranglement interpolé parce que le conjoint et les enfants du patron ne l'apprécieraient pas.

Amendement: principes de conception en génie logiciel

- La différence Local Stacket les Heap Allocatedcalculs au sein de l'itératif pour les boucles et la différence entre leurs usages, leurs efficacités et leur efficacité -

L'algorithme mathématique que j'ai proposé ci-dessus s'applique principalement aux boucles qui effectuent des opérations sur les données allouées sur le tas.

• Opérations de pile consécutives:
  • Si les boucles effectuent des opérations sur les données localement dans un seul bloc de code ou portée qui se trouve dans le cadre de la pile, cela s'appliquera toujours, mais les emplacements de mémoire sont beaucoup plus proches où ils sont généralement séquentiels et la différence de distance parcourue ou de temps d'exécution est presque négligeable. Puisqu'aucune allocation n'est effectuée dans le tas, la mémoire n'est pas dispersée et la mémoire n'est pas récupérée via RAM. La mémoire est généralement séquentielle et relative au cadre de pile et au pointeur de pile.
  • Lorsque des opérations consécutives sont effectuées sur la pile, un processeur moderne mettra en cache les valeurs répétitives et les adresses en conservant ces valeurs dans les registres de cache locaux. Le temps des opérations ou des instructions ici est de l'ordre de la nano-seconde.
• Opérations d'affectation de segments consécutives:
  • Lorsque vous commencez à appliquer des allocations de tas et que le processeur doit récupérer les adresses mémoire lors d'appels consécutifs, selon l'architecture du CPU, du contrôleur de bus et des modules Ram, le temps des opérations ou de l'exécution peut être de l'ordre du micro à millisecondes. Par rapport aux opérations de pile en cache, elles sont assez lentes.
  • Le CPU devra récupérer l'adresse mémoire de Ram et généralement tout ce qui se trouve sur le bus système est lent par rapport aux chemins de données internes ou aux bus de données au sein du CPU lui-même.

Ainsi, lorsque vous travaillez avec des données qui doivent se trouver sur le tas et que vous les parcourez en boucles, il est plus efficace de conserver chaque ensemble de données et ses algorithmes correspondants dans sa propre boucle unique. Vous obtiendrez de meilleures optimisations par rapport à la tentative de factoriser des boucles consécutives en mettant plusieurs opérations de différents ensembles de données qui sont sur le tas dans une seule boucle.

Il est correct de le faire avec les données qui sont sur la pile car elles sont fréquemment mises en cache, mais pas pour les données qui doivent avoir leur adresse mémoire interrogée à chaque itération.

C'est là que l'ingénierie logicielle et la conception de l'architecture logicielle entrent en jeu. C'est la capacité de savoir comment organiser vos données, de savoir quand mettre en cache vos données, de savoir quand allouer vos données sur le tas, de savoir comment concevoir et mettre en œuvre vos algorithmes, et de savoir quand et où les appeler.

Vous pourriez avoir le même algorithme qui appartient au même ensemble de données, mais vous voudrez peut-être une conception d'implémentation pour sa variante de pile et une autre pour sa variante allouée au tas juste en raison du problème ci-dessus qui est vu de son O(n) complexité de l'algorithme lors du travail avec le tas.

D'après ce que j'ai remarqué au fil des ans, beaucoup de gens ne prennent pas ce fait en considération. Ils auront tendance à concevoir un algorithme qui fonctionne sur un ensemble de données particulier et ils l'utiliseront indépendamment de l'ensemble de données mis en cache localement sur la pile ou s'il a été alloué sur le tas.

Si vous voulez une véritable optimisation, oui, cela pourrait ressembler à une duplication de code, mais pour généraliser, il serait plus efficace d'avoir deux variantes du même algorithme. Un pour les opérations de pile et l'autre pour les opérations de tas qui sont effectuées dans des boucles itératives!

Voici un pseudo exemple: deux structures simples, un algorithme.

struct A {
    int data;
    A() : data{0}{}
    A(int a) : data{a}{} 
};
struct B {
    int data;
    B() : data{0}{}
    A(int b) : data{b}{}
}                

template<typename T>
void Foo( T& t ) {
    // do something with t
}

// some looping operation: first stack then heap.

// stack data:
A dataSetA[10] = {};
B dataSetB[10] = {};

// For stack operations this is okay and efficient
for (int i = 0; i < 10; i++ ) {
   Foo(dataSetA[i]);
   Foo(dataSetB[i]);
}

// If the above two were on the heap then performing
// the same algorithm to both within the same loop
// will create that bottleneck
A* dataSetA = new [] A();
B* dataSetB = new [] B();
for ( int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]); // dataSetA is on the heap here
    Foo(dataSetB[i]); // dataSetB is on the heap here
} // this will be inefficient.

// To improve the efficiency above, put them into separate loops... 

for (int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]);
}
for (int i = 0; i < 10; i++ ) {
    Foo(dataSetB[i]);
}
// This will be much more efficient than above.
// The code isn't perfect syntax, it's only psuedo code
// to illustrate a point.

C'est à cela que je faisais référence en ayant des implémentations distinctes pour les variantes de pile par rapport aux variantes de tas. Les algorithmes eux-mêmes n'ont pas trop d'importance, ce sont les structures en boucle que vous allez utiliser dans ce cas.

Il peut s'agir d'anciens 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 3,5 GHz avec 16 Go de RAM.