Pourquoi elementwise ajouts beaucoup plus rapidement dans les boucles séparées que dans une boucle?

Suppose a1 , b1 , c1 , et d1 pointer à la mémoire de tas et mon code numérique a la boucle de coeur 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 extérieure for . 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 Duo Intel Core 2 (x64), le premier exemple prend 5,5 secondes et l'exemple à double boucle ne prend que 1,9 seconde. Ma question est la suivante: (Veuillez vous référer à la ma reformulé la question au bas de la page)

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

démontage pour la première boucle ressemble fondamentalement à 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 la double l'exemple de 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 fortement des tailles des tableaux (n) et du cache CPU. Donc s'il y a un autre intérêt, je reformule la question:

pourriez-vous fournir un aperçu solide des détails qui conduisent aux différents comportements de cache comme illustré par les cinq régions sur le 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 la synchronisation à plus haute résolution, qui peut être désactivé en ne définissant pas le 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

2029
demandé sur Rann Lifshitz 2011-12-18 00:40:52
la source

10 ответов

après une analyse plus approfondie de cela, je crois que cela est (au moins partiellement) causé par l'alignement des données des quatre indicateurs. Cela provoquera un certain niveau de conflits entre les banques de cache et les chemins.

si j'ai deviné correctement sur la façon dont vous répartissez vos tableaux, ils sont susceptibles d'être alignés à la ligne de page .

Cela signifie que tous vos accès dans chaque boucle va tomber sur le même cache. Cependant, Les processeurs Intel ont 8-way L1 associativity cache 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 l'accès à 2 voies.

EDIT : on dirait en fait que vous répartissez tous les tableaux séparément. Habituellement, lorsque de telles allocations importantes sont demandées, l'allocateur demandera de nouvelles pages à l'EO. Par conséquent, il est fort probable que les grandes affectations apparaissent à la même position à partir d'une page de limite.

voici le code d'essai:

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 actual 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. Ceci reproduit exactement les résultats de L'OP.

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

  • tests, les matrices sont empaquetées ensemble pour briser cet alignement. ici, vous remarquerez que les deux boucles sont plus rapides. De plus, la deuxième boucle (double) est maintenant la plus lente comme vous vous y attendiez normalement.

comme le souligne @Stephen Cannon dans les commentaires, il est très probable que cet alignement cause faux alias dans les unités de chargement/stockage ou la cache. J'ai Googlé autour de cette Et constaté que Intel a effectivement un compteur de matériel pour adresse partielle aliasing stands:

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html


5 Régions-Explications

Région 1:

celui-ci est facile. L'ensemble de données est si petit que la performance est dominée par les frais généraux comme la boucle et la ramification.

Région 2:

ici, à mesure que la taille des données augmente, le volume relatif des frais généraux diminue et les performances "saturent". Ici deux boucles est plus lent parce qu'il a deux fois plus de boucle et de branchement au-dessus.

Je ne sais pas exactement ce qui est se passe ici... L'alignement pourrait quand même jouer un effet puisque le brouillard D'Agner mentionne conflits de mémoire cache . (Ce lien concerne Sandy Bridge, mais l'idée devrait quand même s'appliquer au Core 2.)

Région 3:

à ce point, les données ne s'inscrivent plus dans le cache L1. Ainsi, la performance est plafonnée par la bande passante de la cache L1 <-> L2.

Région 4:

la chute de performance dans la boucle simple est ce que nous observons. Et comme mentionné, cela est dû à l'alignement qui (très probablement) provoque des décrochages faux aliasing dans les unités de charge/stockage du processeur.

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

région 5:

à ce point, rien ne correspond dans le cache. Donc, vous êtes 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

1563
répondu Mysticial 2014-04-05 23:42:18
la source

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 y a beaucoup de réponses, qui ont mené à beaucoup de discussions, mais regardons les choses en face: 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 est injuste: Il s'est avéré être à un point très intéressant dans le cache graphique.

La réponse de @Mysticial a convaincu beaucoup de gens (dont moi), probablement parce que c'était la seule qui semblait reposer 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 répartition continue par rapport à une répartition séparée) et les conseils de la réponse de @James.

les graphiques ci-dessous montrent que la plupart des réponses et surtout la majorité des commentaires à la question et les réponses peuvent être considérés comme complètement faux ou vrai 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 présente la plus grande différence entre la version à une et deux boucles (presque un facteur de trois)

  2. il est le seul point, où une boucle (à savoir avec attribution continue) c'est mieux que la version à deux boucles. (Cela a rendu Mysticial la réponse possible, à tous.)

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 testé):

Enter image description here

et celui-ci est difficile à expliquer: données initialisées, qui sont allouées une fois et réutilisées pour chaque cas d'essai suivant de tailles de vecteurs différentes:

Enter image description here

proposition

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

200
répondu Johannes Gerer 2016-09-22 20:12:11
la source

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.

67
répondu Puppy 2011-12-18 00:47:55
la source

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

en supposant une politique de mise en cache 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];
}

aurait d'abord pour effet de charger a et b dans la mémoire vive, puis de travailler entièrement en mémoire vive. Lorsque la deuxième boucle commence, c et d sont alors chargés à partir du disque dans la mémoire vive et activés.

l'autre boucle

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

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

vous ne voyez probablement pas la mise en cache du disque dans vos tests mais vous voyez probablement le côté effets 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.

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

supposant un assez muet Politique de mise en cache de si l'octet n'est pas dans le cache, mettez-le là et obtenez l'octet suivant aussi pendant que nous y sommes vous obtiendrez un scénario 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] en cache il y a maintenant quatre octets dans la mémoire cache, a[0], a[1] et b[0], b[1] . Coût = 100 + 100.

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

  • Ejecter a[0], a[1], b[0], b[1] de cache et cache c[0] et c[1] puis d[0] et d[1] et mettre c[0] = c[0] + d[0] en cache. Coût = 100 + 100.
  • je soupçonne que vous commencez à voir où je vais.
  • coût Total = (100 + 100 + 100 + 100) * 2 = 800

scénario classique de cache thrash.

41
répondu OldCurmudgeon 2018-10-03 14:12:55
la source

ce n'est pas à cause d'un code différent, mais à cause de la mise en cache: la mémoire vive est plus lente que les registres CPU et une mémoire cache est à l'intérieur du CPU pour éviter d'écrire la mémoire vive chaque fois qu'une variable change. Mais la cache n'est pas aussi grande que la mémoire vive, donc elle ne correspond qu'à une fraction de celle-ci.

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

le deuxième code ne alternate: il circule juste sur les adresses adjacentes deux fois. Cela rend d'autant la tâche à effectuer dans le cache, l'invalider, seulement après la deuxième boucle commence.

28
répondu Emilio Garavaglia 2011-12-18 00:49:03
la source

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 juste un peu plus rapide que deux - comme vous vous y attendez.

La taille des réseaux

varie de 2^16 à 2^24, en utilisant huit boucles. J'ai pris soin d'initialiser les tableaux source pour que le += assignment ne demandait pas au FPU d'ajouter des déchets de mémoire interprétés comme un double.

j'ai joué avec divers schémas, tels que la mise de l'affectation de b[j] , d[j] à InitToZero[j] à l'intérieur des boucles, et aussi avec l'utilisation de += b[j] = 1 et += d[j] = 1 , et j'ai obtenu des résultats assez consistants.

comme on pouvait s'y attendre, initialiser b et d à l'intérieur de la boucle en utilisant InitToZero[j] donne l'approche combinée un avantage, car ils ont été faits dos-à-dos avant les affectations à a et c , mais toujours à l'intérieur de 10%. Aller à la figure.

Matériel 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 respectivement de 44.987 et 40.965. Visual C++ 2010, entièrement optimisé.

PS: j'ai changé le des boucles pour compter jusqu'à zéro, et la méthode combinée était légèrement plus rapide. De me 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 métrique pertinente. Je pensais que l'idée était de se concentrer sur les accès de mémoire, donc j'ai essayé de minimiser la quantité de temps de calcul de virgule flottante. Je suis parti dans le += , mais je ne sais pas pourquoi.

Un droit de cession sans calcul serait un test plus propre du temps d'accès à la mémoire et créerait un test qui est uniforme indépendamment du nombre de boucles. Peut-être que j'ai manqué quelque chose dans la conversation, mais ça vaut la peine d'y réfléchir à deux fois. Si le plus est exclu de l'affectation, le temps cumulatif est presque identique à 31 secondes chacune.

18
répondu Hovercraft Full Of Eels 2017-12-16 04:55:04
la source

c'est parce que le CPU n'a pas beaucoup de cache qui manque (où il doit attendre que les données du tableau viennent des puces de RAM). Il serait intéressant pour vous d'ajuster la taille des tableaux continuellement de sorte que vous dépassiez les tailles du niveau 1 cache (L1), et puis le niveau 2 cache (L2), de votre CPU et de tracer le temps pris pour votre code à exécuter par rapport aux tailles des tableaux. Le graphique ne devrait pas être une ligne droite comme vous pouvez vous attendre.

15
répondu James 2013-02-16 13:38:15
la source

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

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

13
répondu Guillaume Kiz 2013-02-16 13:47:53
la source

La Question Originale

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


Évaluation Du Problème

L'OP du code:

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 Considération

compte tenu de la question originale de L'OP sur les 2 variantes de la for loops et sa question modifiée vers le comportement des caches avec beaucoup d'autres excellentes réponses et commentaires utiles, je voudrais essayer et faire quelque chose de différent ici en adoptant une approche différente de cette situation et du problème.


L'Approche

Compte tenu des deux boucles et de toute la discussion au sujet de la mise en cache et du classement de la page, j'aimerais adopter une autre approche pour examiner cette question d'un point de vue différent. Une qui n'implique pas les fichiers cache et 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 certain temps, il est devenu tout à fait évident ce que le problème est et ce qui le génère. Décomposons cela en un problème algorithmique et regardons-le du point de vue de l'utilisation des notations mathématiques puis appliquons une analogie aux problèmes mathématiques aussi bien qu'aux algorithmes.


Ce Que Nous Savons

on sait que sa boucle va tourner 100 000 fois. Nous savons aussi que a1 , b1 , c1 & d1 sont des pointeurs sur une architecture 64 bits. Dans C++ sur une machine 32 bits tous les pointeurs sont 4 octets et sur une machine 64 bits ils sont 8 octets de taille puisque les pointeurs sont d'une longueur fixe. Nous savons que nous avons 32 octets pour lesquels allouer dans les deux cas. La seule différence est que nous attribuons 32 octets ou 2 ensembles de 2-8 octets sur chaque itération où dans le second cas nous attribuons 16 octets pour chaque itération pour les deux itérations indépendantes. boucle. Donc les deux boucles sont toujours égales à 32 octets dans les attributions totales. Avec cette information, nous allons de l'avant et de montrer les mathématiques générales, l'algorithme et l'analogie de celui-ci. Nous connaissons le nombre de fois que le même ensemble ou groupe d'opérations devra être effectué dans les deux cas. Nous savons que la quantité de mémoire qui doit être allouée dans les deux cas. Nous pouvons évaluer que la charge de travail globale des répartitions entre les deux cas sera à peu près la même.


Ce que Nous Ne Savons pas

nous ne savons pas combien de temps cela prendra pour chaque cas à moins que nous mettions un compteur et exécuter un test de référence. Cependant, les points de repère étaient déjà inclus à partir de la question d'origine et de certaines des réponses et des commentaires ainsi 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 répondre à commencer avec.


enquêtons sur

il est déjà évident que beaucoup l'ont déjà fait en regardant les allocations tas, les tests de bench mark, en regardant les fichiers RAM, Cache et Page. L'examen de points de données spécifiques et d'indices d'itération spécifiques a également été inclus et les différentes conversations sur ce problème spécifique a beaucoup de gens commencent à s'interroger sur d'autres choses liées à il. Alors, comment pouvons-nous commencer à regarder ce problème en utilisant des algorithmes mathématiques et en appliquant une analogie? Nous commençons par quelques affirmations! Puis 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 à 0 comme dans les boucles pour nous ne vous inquiétez pas du schéma d'indexation 0 de l'adressage mémoire puisque nous sommes simplement intéressés par l'algorithme lui-même.
  • dans les deux cas, nous avons 4 fonctions à travailler et 2 appels de fonction avec 2 opérations effectuées sur chaque appel de fonction. Nous allons donc les mettre en place comme des fonctions et des appels de fonction à être F1() , F2() , f(a) , f(b) , f(c) et f(d) .

Les Algorithmes:

1er cas: - un seul résumé 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);  }

2nd Case: - 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() existe seulement 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 appelle f(a) qui ajoutera à lui-même f(b) puis il appelle f(c) qui fera la même chose mais ajoutera f(d) à lui-même pour chaque 100000 iterations . Dans le second cas nous avons Sum1 et Sum2 et les deux agissent le même comme s'ils étaient de la même fonction appelée deux fois dans une rangée. Dans ce cas, nous pouvons traiter Sum1 et Sum2 comme tout simplement vieux SumSum 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 juste considérer qu'il est la même fonction.


résumé par analogie

Avec ce que nous avons vu dans le deuxième cas il semble presque comme s'il y avait optimisation puisque les deux pour les boucles ont la même signature exacte, mais ce n'est pas le vrai problème. Le problème 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 dans la distance que la sommation doit parcourir dans les deux cas qui vous donne la différence dans l'exécution du temps.

pensez au For Loops comme étant le Summations qui fait les itérations comme étant un Boss qui donne des ordres à deux personnes A et B et que leurs travaux sont à la viande C et D respectivement et de ramasser un paquet d'eux et de le retourner. Dans cette analogie, les itérations pour boucle ou sommation et les vérifications de condition elles-mêmes ne représentent pas réellement le Boss . Ce qui représente en fait le Boss ici n'est pas à partir des algorithmes mathématiques réels directement, mais à partir du concept réel de Scope et Code Block dans une routine ou sous-routine, méthode, fonction, Unité de traduction, etc. Le premier algorithme a une portée où le deuxième algorithme a 2 portées consécutives.

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

dans le second cas, le Boss fonctionne directement avec le A pour aller chercher le paquet B's jusqu'à ce que tous les paquets soient reçus. Puis le Boss fonctionne avec C pour faire la même chose pour obtenir tous les paquets D's .

étant donné que nous travaillons avec un pointeur de 8 octets et que nous traitons de l'allocation des tas, examinons ce problème. ici. Disons que le Boss est à 100 pieds de A et que A est à 500 pieds de C . Nous n'avons pas besoin de nous inquiéter de la distance entre le Boss et le C à cause de l'ordre des exécutions. Dans les deux cas, le Boss se déplace initialement de A d'abord puis à B . Cette analogie ne veut pas dire que cette distance est exacte; c'est juste un scénario d'utilisation de cas d'essai pour montrer le fonctionnement des algorithmes. Dans de nombreux cas lorsque vous faites des attributions de tas et que vous travaillez avec les fichiers de cache et de page, ces distances entre les adresses peuvent ne pas varier beaucoup en différences ou elles peuvent très significativement dépendre de la nature des types de données et des tailles de tableaux.


Les Cas D'Essai:

premier cas: à la première itération le Boss doit d'abord aller de 100 pieds pour donner la fiche de commande à A et A va et fait son truc, mais alors le Boss doit voyager de 500 pieds à C pour lui donner sa fiche de commande. Puis sur la prochaine itération et toutes les autres itérations après le Boss doit aller et venir 500 pieds entre les deux.

Second cas: The Boss doit parcourir 100 pieds sur le 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 feuillets soient remplis. Puis le Boss doit parcourir 500 pieds sur la première itération de C parce que C est à 500 pieds de A puisque ce 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 les bons de commande C's 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 de valeurs arbitraires

nous pouvons facilement voir que 600 est bien moins de 10 millions. Maintenant, ce n'est pas exact, parce que nous ne savons pas la différence réelle dans la distance entre quelle adresse de RAM ou à partir de quel Cache ou fichier de Page chaque appel sur chaque itération va être dus à beaucoup d'autres invisibles variables, mais c'est juste une évaluation de la situation afin de connaître et d'essayer de le regarder à partir d'un scénario du pire.

donc par ces nombres, il semblerait presque que L'algorithme Un devrait être 99% plus lent que L'algorithme deux; cependant, ce n'est que la partie The Boss's ou la responsabilité des algorithmes et il ne tient pas compte des travailleurs réels A , B , C , & D et ce qu'ils ont à faire sur chaque itération de la boucle. Ainsi, le travail du patron ne représente que 15 à 40% du travail total effectué. Ainsi le gros du travail qui est fait par les travailleurs a un impact légèrement plus grand vers 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 en cours et il va de montrer que cas 2 est plus efficace à la fois de cette optimisation partielle d'avoir une déclaration de fonction similaire et la définition où il est seulement les variables qui diffèrent par leur nom. Et nous voyons aussi que la distance totale parcourue dans Cas 1 est beaucoup plus loin que dans cas 2 et nous pouvons considérer cette distance parcourue notre "15192520920 Facteur" Temps entre les deux algorithmes. Cas 1 a beaucoup plus de travail à faire que Cas 2 ne. Cela s'est également vu dans la preuve du ASM qui a été présentée entre les deux cas. Même avec ce qui a déjà été dit sur ces cas, il ne tient pas compte non plus du fait que dans Cas 1 le patron devra attendez que les deux A et C reviennent avant de pouvoir revenir à A à la prochaine itération et cela ne tient pas compte du fait que si A ou B prend un temps extrêmement long alors les deux Boss et les autres travailleurs attendent également à un ralenti. Dans cas 2 , le seul inactif est le Boss jusqu'à ce que le travailleur revienne. Donc même ceci a un impact sur l'algorithme.


Conclusion:

Cas 1 est un classique de l'interpolation problème qui se trouve être un inefficaces. Je pense également 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 capacité de faire des applications multi-threadées ainsi que la programmation parallèle.

donc même en le regardant à partir de cette approche sans même impliquer comment le matériel, L'OS et le compilateur travaillent ensemble pour faire des allocations tas qui implique de travailler avec la RAM, le Cache, les fichiers de Page, etc.; les mathématiques derrière elles nous montrent déjà laquelle de ces deux est la meilleure solution d'utiliser l'analogie ci-dessus où le Boss ou le Summations étant ceux le For Loops qui a dû voyager entre les travailleurs A et B . Nous pouvons facilement voir que Cas 2 est au moins aussi 1/2 aussi vite si ce n'est un peu plus que Cas 1 en raison de la différence dans les pris ses distances parcourue et le temps. Et ce calcul s'aligne presque virtuellement et parfaitement avec les temps de référence ainsi que la quantité de différence dans la quantité D'instructions de montage.



L'OPs a modifié la Question (s)

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

Pourriez-vous fournir un aperçu de l'détails qui mènent aux différents comportements de cache comme illustré par les cinq régions sur le graphique 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 j'ai démontré sans doute, il y a un problème sous-jacent avant même que le Matériel et le Logiciel devient impliqué. Maintenant que pour 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 { Hardware, Firmware, 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 le Registre}, The Compiler {Unités de traduction et optimisations du Code Source }, et même le Source Code lui-même avec ses ensembles d'algorithmes distinctifs; nous pouvons déjà voir qu'il y a un goulot d'étranglement qui se produit dans le premier algorithme avant même que nous l'appliquions à n'importe quelle machine avec n'importe quel arbitraire Architecture , OS , et Programmable Language par rapport au deuxième algorithme. Il y avait donc déjà un problème avant d'impliquer les intrinsèques d'un ordinateur moderne.


La Fin Résultats

; Cependant, il n'est pas à dire que ces nouvelles questions ne sont pas d'importance parce qu'ils sont eux-mêmes et qu'ils jouent un rôle après tout. Ils ont une incidence sur les procédures et le rendement global, ce qui est évident dans les divers graphiques et évaluations de nombreux répondants qui ont donné leur(S) réponse(s) et / ou commentaire (s). Si vous prêtez attention à l'analogie du Boss et les deux travailleurs A & B qui ont dû aller et récupérez les paquets de C et D respectivement et en considérant les notations mathématiques des deux algorithmes en question vous pouvez voir que sans même l'intervention 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é et optimisé et exécuté à travers L'OS pour effectuer des opérations sur le matériel donné, vous voyez même un peu plus dégradation entre les différences de ces algorithmes.

maintenant, si l'ensemble de "données" est assez petit, il peut ne pas sembler tout à fait mauvais d'une différence au début, mais depuis Case 1 est environ 60 - 70% plus lent que Case 2 nous pouvons regarder la croissance de cette fonction comme étant 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)

Et cette approximation est la différence moyenne entre ces deux boucles à la fois opérations algorithmiques et Machines impliquant des optimisations logicielles et des instructions machine. Ainsi, lorsque l'ensemble de données croît linéairement, le fait de la différence de temps entre les deux. L'algorithme 1 comporte plus de leviers que l'algorithme 2, ce qui est évident lorsque le Boss a dû parcourir la distance maximale entre A et C pour chaque itération après la première itération, tandis que L'algorithme 2 le Boss a dû voyager jusqu'à A une fois et ensuite après ayant terminé avec A , il ne devait parcourir qu'une seule distance maximale lorsqu'il passait de A à C .

donc essayer d'avoir le Boss se concentrer sur faire deux choses similaires à la fois et jongler entre elles au lieu de se concentrer sur des tâches consécutives similaires va le rendre assez en colère à la fin de la journée parce qu'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 du patron et les enfants ne l'apprécieraient pas.

5
répondu Francis Cugler 2017-08-05 03:42:00
la source

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

une boucle: 1.577 ms deux boucles: 1.507 ms

je cours VS2015 sur E5-1620 3.5 Ghz avec 16 go de ram

1
répondu mathengineer 2018-07-11 10:00:53
la source