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


Supposer a1, b1, c1, et d1 point de mémoire tas et mon code numérique a 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 un autre 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 Intel Core 2 Duo (x64), le premier exemple prend 5,5 secondes et l'exemple de double boucle prend seulement 1,9 secondes. Ma question est: (Veuillez vous référer à la question reformulée en bas)

PS: Je ne suis pas sûr, 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 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 importance, car le comportement dépend fortement de la taille des tableaux (n) et du cache CPU. Donc, s'il y a plus d'intérêt, je reformule la question:

Pourriez-vous donner un aperçu solide des détails qui mènent 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 plus élevée, qui peut être désactivée en ne définissant pas TBB_TIMING Macro:

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

//#define TBB_TIMING

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

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

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


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

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

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

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

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

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

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

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


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

    char *s = " ";

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

    cout << "n";

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

    cout << endl;

    long long nmax = 1000000;

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

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

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

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

enter image description here


1995
2017-12-17 20:40


origine


Réponses:


Après une analyse plus poussée de ceci, je crois que ceci est (au moins partiellement) causé par l'alignement des données des quatre pointeurs. Cela entraînera un certain niveau de conflits de banque / voie 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 eu une associativité de cache L1 à 8 voies pendant un certain temps. Mais en réalité, la performance n'est pas complètement uniforme. L'accès aux 4 voies est toujours plus lent que les 2 voies.

EDIT: Il semble en fait que vous alliez tous les tableaux séparément. Habituellement, lorsque des allocations aussi importantes sont demandées, l'allocateur demande de nouvelles pages au système d'exploitation. Par conséquent, il y a de fortes chances que des allocations importantes apparaissent au même décalage d'une frontière 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 un réel Core 2 architecture 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. Cela reproduit exactement les résultats de l'OP.

  • 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 derniers 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 pouvez l'attendre normalement.

Comme l'indique @Stephen Cannon dans les commentaires, il y a de fortes chances que cet alignement provoque faux aliasing dans les unités de chargement / stockage ou dans le cache. J'ai cherché Google pour cela et j'ai trouvé que Intel avait un compteur de matériel pour aliasing d'adresse partielle stalles:

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 la performance est dominée par des frais généraux comme la mise en boucle et la dérivation.

Région 2:

Ici, à mesure que la taille des données augmente, la quantité de données relatives diminue et la performance "sature". Ici, deux boucles sont plus lentes car elles ont deux fois plus de boucles et de ramifications.

Je ne sais pas exactement ce qui se passe ici ... L'alignement pourrait encore jouer un rôle comme le mentionne Agner Fog conflits de banque de cache. (Ce lien concerne Sandy Bridge, mais l'idée devrait toujours s'appliquer 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 de performance dans la boucle unique est ce que nous observons. Et comme mentionné, cela est dû à l'alignement qui (le plus probable) provoque faux aliasing stalles dans les unités de chargement / stockage du processeur.

Cependant, pour qu'un faux repliement se produise, il doit y avoir une foulée suffisamment grande entre les ensembles de données. C'est pourquoi vous ne voyez pas cela dans la région 3.

Région 5:

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


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


1544
2017-12-17 21:17



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

Il y a beaucoup de réponses, qui ont conduit à beaucoup de discussions, mais soyons réalistes: les problèmes de cache peuvent être très complexes et ne sont pas unidimensionnels. Ils dépendent beaucoup 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 (y compris moi), probablement parce que c'était la seule qui semblait s'appuyer sur des faits, mais c'était seulement un "point de données" de la vérité.

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

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 complètement faux ou faux selon le scénario 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 la plus grande différence 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, du tout.)

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

Enter image description here

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

Enter image description here

Et ceci 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:

Enter image description here

Proposition

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


194
2017-12-18 01:29



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


63
2017-12-17 20:47



Imaginez que vous travaillez sur une machine où n était juste la bonne valeur pour qu'il soit possible de garder deux de vos tableaux en mémoire en même temps, mais la mémoire totale disponible, via la mise en cache de disque, était encore suffisante pour contenir tous les quatre.

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

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

serait la première cause a et b être chargé dans la RAM et ensuite être entièrement travaillé en RAM. Lorsque la deuxième boucle commence, c et d serait alors chargé à partir du disque dans la RAM et exploité.

l'autre boucle

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

va page deux tableaux et la page dans les deux autres chaque fois autour de la boucle. Ce serait évidemment beaucoup Ralentissez.

Vous ne voyez probablement pas la mise en cache 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 je vais essayer d'élaborer un peu en utilisant un exemple.

Dire n = 2 et nous travaillons avec des octets. Dans mon scénario, nous avons donc seulement 4 octets de cache et le reste de notre mémoire est significativement plus lent (disons 100 fois plus long).

En supposant une politique de mise en cache assez stupide de si l'octet n'est pas dans le cache, placez-le et obtenez 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] et a[1] puis b[0] et b[1] Et mettre a[0] = a[0] + b[0] dans le cache - il y a maintenant quatre octets dans le cache, a[0], a[1] et b[0], b[1]. Coût = 100 + 100.

  • ensemble a[1] = a[1] + b[1] dans le cache. Coût = 1 + 1.
  • Répétez pour c et d.
  • Coût total = (100 + 100 + 1 + 1) * 2 = 404

  • Avec

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • cache a[0] et a[1] puis b[0] et b[1] Et mettre a[0] = a[0] + b[0] dans le cache - il y a maintenant quatre octets dans le cache, a[0], a[1] et b[0], b[1]. Coût = 100 + 100.

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

C'est un scénario de thrash de cache classique.


37
2017-12-18 01:36



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 est, par conséquent, il ne mappe qu'une fraction de celui-ci.

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

Le second code n'alterne pas: il circule juste deux fois sur les adresses adjacentes. Cela rend tout le travail à remplir dans le cache, l'invalider seulement après le début de la deuxième boucle.


27
2017-12-17 20:49



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

Les tailles de tableau vont de 2 ^ 16 à 2 ^ 24, en utilisant huit boucles. J'ai pris soin d'initialiser les tableaux source afin que le += cession ne demandait pas la FPU pour ajouter de la mémoire ordonnée interprétée comme un double.

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

Comme vous pouvez vous y attendre, initialiser b et d à l'intérieur de la boucle en utilisant InitToZero[j] l'approche combinée a été avantageuse, puisqu'elles ont été effectuées l'une après l'autre avant a et c, mais toujours dans les 10%. Allez comprendre.

Le matériel est Dell XPS 8500 avec 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 respectivement de 44,987 et 40,965. Visual C ++ 2010, entièrement optimisé.

PS: J'ai changé les boucles pour compter jusqu'à zéro, et la méthode combinée était légèrement plus rapide. Gratter ma tête. Notez le nouveau dimensionnement de la baie 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 un indicateur pertinent. Je pensais que l'idée était de se concentrer sur les accès 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 directe sans calcul serait 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. Peut-être que j'ai manqué quelque chose dans la conversation, mais cela vaut la peine de réfléchir à deux fois. Si le plus est laissé hors de l'affectation, le temps cumulé est presque identique à 31 secondes chacun.


16
2017-12-30 01:34



C'est parce que le processeur n'a pas autant d'erreurs de mémoire 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 de sorte que vous dépassez les tailles de cache de niveau 1 (L1), puis cache de niveau 2 (L2), de votre CPU et tracer le temps nécessaire pour que votre code s'exécute contre les tailles des tableaux. Le graphique ne devrait pas être une ligne droite comme on s'y attendrait.


14
2017-12-17 20:52



La première boucle alterne l'écriture dans chaque variable. Les deuxième et troisième font seulement 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 une fois de finir l'une puis l'autre et essayez une autre fois en écrivant alternativement une croix dans chaque ligne.


12
2017-08-17 15:23



La question originale

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


É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 sur les 2 variantes des boucles for et sa question modifiée sur le comportement des caches ainsi que de nombreuses autres excellentes réponses et commentaires utiles; Je voudrais essayer de faire quelque chose de différent en adoptant une approche différente de cette situation et de ce problème.


L'approche

Considérant les deux boucles et toute la discussion sur le cache et l'archivage de pages, j'aimerais adopter une autre approche pour considérer cela sous un angle différent. Une qui n'implique pas les fichiers de cache et de page ni les exécutions pour allouer de la mémoire, en fait cette approche ne concerne même pas le matériel réel ou le logiciel du tout.


La perspective

Après avoir regardé le code pendant un moment, il est devenu évident quel est le problème et qu'est-ce qui le génère. Laissons tomber ceci dans un problème algorithmique et regardons-le du point de vue d'employer des notations mathématiques puis appliquons une analogie aux problèmes de maths aussi bien qu'aux algorithmes.


Ce que nous savons

Nous savons que sa boucle fonctionnera 100 000 fois. Nous savons aussi que a1, b1, c1 & d1 sont des pointeurs sur une architecture 64 bits. En C ++ sur une machine 32 bits, tous les pointeurs ont 4 octets et sur une machine 64 bits, ils ont une taille de 8 octets puisque les pointeurs ont une longueur fixe. Nous savons que nous avons 32 octets dans lesquels pour 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, alors que dans le deuxième cas, nous allouons 16 octets pour chaque itération pour les deux boucles indépendantes. Donc, les deux boucles sont toujours égales à 32 octets dans les allocations totales. Avec cette information, allons-y et montrons les mathématiques générales, l'algorithme et l'analogie. Nous connaissons le nombre de fois que le 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 estimer 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 établissons un compteur et effectuons un test de benchmark. Cependant, les repères ont déjà été inclus dans la question initiale et dans certaines réponses et commentaires, et nous pouvons voir une différence significative entre les deux et c'est tout le raisonnement de cette question à ce problème et pour la réponse à cela. commencer avec.


Enquêtons 

Il est déjà évident que beaucoup l'ont déjà fait en regardant les allocations de tas, les tests de benchmarks, en regardant RAM, Cache et Page Files. L'examen de points de données spécifiques et d'index 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. Alors, comment pouvons-nous commencer à regarder ce problème en utilisant des algorithmes mathématiques et en appliquant une analogie à celui-ci? Nous commençons par faire quelques affirmations! Ensuite, nous construisons notre algorithme à partir de là.


Nos assertions

  • 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 mémoire puisque nous sommes juste intéressés par l'algorithme lui-même.
  • Dans les deux cas, nous avons 4 fonctions à utiliser et 2 appels de fonction avec 2 opérations effectuées sur chaque appel de fonction. Nous allons donc les définir comme des fonctions et des appels de fonction à être 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é F2() n'existe que dans Sum où les deux Sum1 et Sum2 contient seulement F1(). Cela sera également évident plus tard lorsque nous commencerons à conclure qu'il y a une sorte d'optimisation qui se produit à partir du deuxième algorithme.

Les itérations à travers le premier cas Sum appels f(a) cela va ajouter à son auto f(b) alors il appelle f(c) cela fera la même chose, mais ajouter f(d) à lui-même pour chaque 100000 iterations. Dans le second cas, nous avons Sum1 et Sum2 Et 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 Sum1 et Sum2 comme tout simplement vieux Sum où Sum dans ce cas 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 analogie

Avec ce que nous avons vu dans le second 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)&f(d) dans les deux cas et la comparaison entre les deux, c'est la différence de distance que la sommation doit parcourir dans les deux cas qui vous donne la différence dans l'exécution du temps.

Pensez à la For Loops comme étant le Summations cela fait les itérations comme étant un Boss c'est donner des ordres à deux personnes A & B et que leurs emplois sont à la viande C & D respectivement et de ramasser un paquet d'eux et le retourner. Dans l'analogie ici, les itérations de boucle for ou de sommation et les vérifications de condition elles-mêmes ne représentent pas réellement le Boss. Qu'est-ce qui représente réellement le Boss ici ne vient pas directement des algorithmes mathématiques réels, mais du concept même de Scope et Code Block dans une routine ou une sous-routine, une méthode, une fonction, une unité de traduction, etc. Le premier algorithme a 1 étendue où le 2ème algorithme a 2 étendues consécutives.

Dans le premier cas sur chaque feuillet d'appel, le Boss va à A et donne l'ordre et A va chercher B's paquet puis le Boss va à C et donne les ordres de faire la même chose et recevoir le paquet de D à chaque itération.

Dans le second cas, le Boss travaille directement avec A aller chercher B's paquet jusqu'à la réception de tous les paquets. Puis le Bossmarche avec C de faire la même chose pour obtenir tous D's paquets.

Puisque nous travaillons avec un pointeur de 8 octets et que nous traitons l'allocation de tas, considérons ce problème ici. Disons que le Boss est à 100 pieds de A et cela A est à 500 pieds de C. Nous n'avons pas besoin de nous inquiéter de la distance Boss est initialement de C à cause de l'ordre des exécutions. Dans les deux cas, le Boss voyage d'abord à partir de A d'abord puis B. Cette analogie ne veut pas dire que cette distance soit exacte; c'est juste un scénario de test d'utilisation pour montrer le fonctionnement des algorithmes. Dans de nombreux cas, lorsque vous effectuez des allocations de tas et travaillez avec le cache et les fichiers de page, ces distances entre les emplacements d'adresses peuvent varier considérablement en fonction de la nature des types de données et de la taille des tableaux.


Les cas de test:

Premier cas: Au premier itération, le Boss doit d'abord aller à 100 pieds pour donner l'ordre à glisser vers A et A va et fait son truc, mais ensuite le Boss doit voyager 500 pieds à C pour lui donner son bon de commande. Puis sur l'itération suivante et toutes les autres itérations après le Boss doit aller et venir 500 pieds entre les deux.

Deuxième cas:  The Boss doit parcourir 100 pieds sur la première itération à A, mais après cela, il est déjà là et attend juste A pour revenir jusqu'à ce que tous les bordereaux soient remplis. Puis le Boss doit parcourir 500 pieds sur la première itération C car C est à 500 pieds de A depuis cela Boss( Summation, For Loop ) est appelé juste après avoir travaillé avec A et attend juste comme il l'a fait avec A jusqu'à ce que tous C's les bordereaux de commande sont faits.


La différence des 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 beaucoup moins de 10 millions. Maintenant, ce n'est pas exact, parce que nous ne connaissons pas la différence de distance entre l'adresse de RAM ou le cache ou le fichier de page que chaque appel va utiliser pour chaque itération, mais ceci est juste une évaluation de la situation à prendre en compte et à essayer de l'examiner dans le pire des cas.

Donc, par ces nombres, il semblerait presque que l'algorithme un devrait être 99% plus lent que l'algorithme deux; cependant, ceci est seulement le The Boss's partie ou la responsabilité des algorithmes et il ne tient pas compte des travailleurs réels A, B, C, & D et ce qu'ils doivent faire à chaque itération de la boucle. Ainsi, le travail des patrons ne représente qu'environ 15 à 40% du travail total accompli. Ainsi, la plus grande partie du travail effectué par les travailleurs a un impact légèrement plus grand sur le maintien du rapport des différences de vitesse à environ 50-70%


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

Dans cette situation, c'est la structure du processus du travail qui est fait et ça va montrer que Cas 2est plus efficace à la fois de cette optimisation partielle d'avoir une déclaration de fonction similaire et de la définition où seules les variables qui diffèrent par leur nom. Et nous voyons aussi que la distance totale parcourue Cas 1 est beaucoup plus loin qu'il ne l'est Cas 2 et nous pouvons considérer cette distance parcourue notre Facteur de temps entre les deux algorithmes. Cas 1 a beaucoup plus de travail à faire que Cas 2 Est-ce que. Cela a également été vu dans la preuve de la ASM cela 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 non plus compte du fait que Cas 1 le patron devra attendre les deux A & C revenir avant de pouvoir revenir à A encore une fois sur l'itération suivante et il ne tient pas compte du fait que si A ou B prend un temps extrêmement long puis à la fois Boss et le (s) autre (s) travailleur (s) attendent également au ralenti. Dans Cas 2 le seul étant inactif est le Boss jusqu'à ce que le travailleur revienne. Donc, même cela a un impact sur l'algorithme.


Conclusion:

Cas 1 est un problème d'interpolation classique qui s'avère inefficace. Je pense aussi que c'était l'une des principales raisons pour lesquelles de nombreuses architectures de machines et de développeurs ont fini par construire et concevoir des systèmes multi-core avec la possibilité de faire des applications multi-threads ainsi que la programmation parallèle.

Donc, même en regardant à partir de cette approche sans même impliquer comment le matériel, le système d'exploitation et le compilateur travaillent ensemble pour faire des allocations de tas qui implique de travailler avec la RAM, le cache, les fichiers de page, etc .; les mathématiques derrière elle nous montre déjà lequel de ces deux est la meilleure solution d'utiliser l'analogie ci-dessus où le Boss ou la Summations étant ceux les For Loops qui devait voyager entre les travailleurs A & B. Nous pouvons facilement voir que Cas 2 est au moins aussi rapide que 1/2 sinon un peu plus de Cas 1 en raison de la différence de distance parcourue et le temps pris. Et cette mathématique s'aligne quasiment virtuellement et parfaitement avec les deux Bench Mark Times ainsi que le montant de la différence dans le montant des instructions d'assemblage.



Les PO modifiés Question (s)

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

Pourriez-vous donner un aperçu solide des détails qui mènent 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.


En ce qui concerne ces questions

Comme je l'ai démontré sans l'ombre d'un doute, il y a un problème sous-jacent avant même que le matériel et le logiciel 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 de systèmes intégré entre: The Architecture {Matériel, micrologiciel, certains pilotes intégrés, noyaux et ensembles 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 Source Code lui-même avec son ensemble (s) d'algorithmes distinctifs; nous pouvons déjà voir qu'il y a un goulot d'étranglement qui se passe dans le premier algorithme avant même de l'appliquer à toute machine avec arbitraire Architecture, OS, et Programmable Languagepar rapport au deuxième algorithme. Donc, il existait déjà un problème avant d'impliquer l'intrinsèque d'un ordinateur moderne.


Les résultats finaux

Toutefois; Cela ne veut pas dire que ces nouvelles questions ne sont pas importantes 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 la performance globale, ce qui est évident avec les divers graphiques et évaluations de plusieurs personnes qui ont donné leur réponse (s) et / ou commentaire (s). Si vous faites attention à l'analogie de la Boss et les deux ouvriers A & B qui devait aller récupérer des paquets de C & D respectivement et compte tenu des notations mathématiques des deux algorithmes en question, vous pouvez voir que sans même l'implication de l'ordinateur Case 2 est environ 60% plus rapide que Case 1 et quand vous regardez les graphiques et les graphiques après que ces algorithmes ont été appliqués au code source, compilés et optimisés et exécutés par le système d'exploitation pour effectuer des opérations sur le matériel donné vous voyez même un peu plus de dégradation entre les différences dans ces algorithmes.

Maintenant, si l'ensemble "Données" est assez petit, cela peut ne pas sembler tout à fait désagréable au début mais Case 1 est à propos 60 - 70% plus lent que Case 2 on peut considérer la croissance de cette fonction comme étant en termes de différences dans 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, aussi bien algorithmiquement que mécaniquement, impliquant des optimisations logicielles et des instructions machine. Ainsi, lorsque l'ensemble de données augmente linéairement, la différence de temps entre les deux augmente également. L'algorithme 1 a plus d'extractions que l'algorithme 2, ce qui est évident lorsque Boss a dû voyager d'avant en arrière la distance maximale entre A & C pour chaque itération après la première itération tandis que l'algorithme 2 le Boss a dû voyager à A une fois et ensuite après avoir été fait avec A il devait voyager une distance maximale seulement une fois en allant de A à C.

Donc, en essayant d'avoir le Boss se concentrer sur deux choses semblables à la fois et les jongler d'avant en arrière au lieu de se concentrer sur des tâches consécutives similaires va le rendre très en colère à la fin de la journée parce qu'il devait voyager et travailler deux fois plus. Par conséquent, ne perdez pas l'ampleur de la situation en laissant votre patron entrer dans un goulot d'étranglement interpolé parce que le conjoint du patron et les enfants ne l'apprécieraient pas.


3
2018-01-30 14:00



Peut être vieux C ++ et optimisations. Dans mon ordinateur j'ai obtenu presque la même vitesse:

une boucle: 1.577ms deux boucles: 1.507ms

Je cours VS2015 sur le processeur 3.5Ghz E5-1620 avec RAM 16Gb


0
2017-07-11 07:00