[c++] Perché le aggiunte elementwise sono molto più veloci in cicli separati rispetto a un ciclo combinato?


Answers

OK, la risposta giusta deve sicuramente fare qualcosa con la cache della CPU. Ma usare l'argomento della cache può essere abbastanza difficile, specialmente senza i dati.

Ci sono molte risposte, che hanno portato a molte discussioni, ma ammettiamolo: i problemi della cache possono essere molto complessi e non sono unidimensionali. Dipendono pesantemente dalla dimensione dei dati, quindi la mia domanda era ingiusta: si è rivelato essere in un punto molto interessante nel grafico della cache.

@ La risposta di Mysticial ha convinto un sacco di persone (me compreso), probabilmente perché era l'unico che sembrava fare affidamento sui fatti, ma era solo un "punto dati" della verità.

Ecco perché ho combinato il suo test (usando un'allocazione continua vs. separata) e il consiglio di Risposta di @James.

I grafici sottostanti mostrano che la maggior parte delle risposte e soprattutto la maggior parte dei commenti alla domanda e alle risposte possono essere considerate completamente sbagliate o vere a seconda dello scenario esatto e dei parametri utilizzati.

Nota che la mia domanda iniziale era a n = 100.000 . Questo punto (per caso) mostra un comportamento speciale:

  1. Possiede la più grande discrepanza tra la versione a uno e due loop (quasi un fattore di tre)

  2. È l'unico punto in cui un loop (ovvero con allocazione continua) batte la versione a due loop. (Questo ha reso possibile la risposta di Mysticial, per niente.)

Il risultato utilizzando i dati inizializzati:

Il risultato utilizzando dati non inizializzati (questo è ciò che Mysticial ha testato):

E questo è difficile da spiegare: dati inizializzati, che vengono allocati una volta e riutilizzati per ogni successivo caso di prova di dimensioni vettoriali diverse:

Proposta

Ogni domanda relativa alle prestazioni di basso livello su Stack Overflow dovrebbe essere richiesta per fornire informazioni su MFLOPS per l'intera gamma di dimensioni dei dati rilevanti per la cache! È uno spreco di tempo per tutti di pensare alle risposte e soprattutto discuterle con gli altri senza queste informazioni.

Question

Supponiamo che a1 , b1 , c1 e d1 puntino alla memoria heap e il mio codice numerico abbia il seguente ciclo centrale.

const int n = 100000;

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

Questo ciclo viene eseguito 10.000 volte tramite un altro ciclo for esterno. Per accelerarlo, ho cambiato il codice in:

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

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

Compilato su MS Visual C ++ 10.0 con ottimizzazione completa e SSE2 abilitato per 32-bit su Intel Core 2 Duo (x64), il primo esempio impiega 5,5 secondi e l'esempio di doppio ciclo richiede solo 1,9 secondi. La mia domanda è: (Si prega di fare riferimento alla mia domanda riformulata in fondo)

PS: non sono sicuro, se questo aiuta:

Il disassemblaggio del primo loop è essenzialmente simile a questo (questo blocco viene ripetuto circa cinque volte nel programma completo):

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]

Ogni loop dell''esempio double loop produce questo codice (il seguente blocco viene ripetuto circa tre volte):

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

EDIT: la domanda non ha avuto rilevanza, in quanto il comportamento dipende in gran parte dalle dimensioni degli array (n) e dalla cache della CPU. Quindi, se c'è ulteriore interesse, riformulo la domanda:

Potresti fornire alcune informazioni dettagliate sui dettagli che portano ai diversi comportamenti della cache, come illustrato dalle cinque regioni nel seguente grafico?

Potrebbe anche essere interessante sottolineare le differenze tra le architetture CPU / cache, fornendo un grafico simile per queste CPU.

PPS: ecco il codice completo. Utilizza TBB Tick_Count per tempi di risoluzione superiore, che possono essere disabilitati non definendo la macro TBB_TIMING :

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

//#define TBB_TIMING

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

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

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


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

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

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

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

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

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

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

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


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

    char *s = " ";

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

    cout << "n";

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

    cout << endl;

    long long nmax = 1000000;

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

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

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

(Mostra FLOP / s per diversi valori di n .)




Immagina di lavorare su una macchina in cui n era il giusto valore perché solo fosse possibile tenere in memoria due degli array in una volta, ma la memoria totale disponibile, tramite la memorizzazione nella cache del disco, era ancora sufficiente per contenere tutti e quattro.

Supponendo una semplice politica di caching LIFO, questo codice:

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

prima causerebbe a e b di essere caricato nella RAM e quindi essere lavorato interamente nella RAM. Quando viene avviato il secondo ciclo, c e d verrebbero quindi caricati dal disco nella RAM e utilizzati.

l'altro ciclo

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

aprirà due matrici e una pagina negli altri due ogni volta attorno al ciclo . Questo ovviamente sarebbe molto più lento.

Probabilmente non stai vedendo il caching del disco nei tuoi test ma probabilmente stai vedendo gli effetti collaterali di qualche altra forma di memorizzazione nella cache.

Sembra che ci sia un po 'di confusione / incomprensione qui, quindi cercherò di elaborare un po' usando un esempio.

n = 2 e stiamo lavorando con i byte. Nel mio scenario abbiamo quindi solo 4 byte di cache e il resto della nostra memoria è molto più lento (diciamo 100 volte più lungo accesso).

Assumendo una politica di caching piuttosto stupida se il byte non è nella cache, mettilo lì e prendi il seguente byte anche mentre ci siamo , otterrai uno scenario come questo:

  • Con

    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] e a[1] poi b[0] e b[1] e imposta a[0] = a[0] + b[0] nella cache - ora ci sono quattro byte nella cache, a[0], a[1] e b[0], b[1] . Costo = 100 + 100.

  • imposta a[1] = a[1] + b[1] nella cache. Costo = 1 + 1.
  • Ripeti per c e d .
  • Costo totale = (100 + 100 + 1 + 1) * 2 = 404

  • Con

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • cache a[0] e a[1] poi b[0] e b[1] e imposta a[0] = a[0] + b[0] nella cache - ora ci sono quattro byte nella cache, a[0], a[1] e b[0], b[1] . Costo = 100 + 100.

  • espellere a[0], a[1], b[0], b[1] dalla cache e cache c[0] c[1] quindi d[0] e d[1] e impostare c[0] = c[0] + d[0] nella cache. Costo = 100 + 100.
  • Sospetto che tu stia cominciando a vedere dove sto andando.
  • Costo totale = (100 + 100 + 100 + 100) * 2 = 800

Questo è un classico scenario di cache thrash.




Il primo ciclo alterna la scrittura in ciascuna variabile. Il secondo e il terzo fanno solo piccoli salti di dimensioni dell'elemento.

Prova a scrivere due linee parallele di 20 croci con una penna e carta separate da 20 cm. Prova una volta terminato uno e poi l'altra linea e prova un'altra volta tagliando alternativamente una croce in ogni riga.




Non riesco a replicare i risultati discussi qui.

Non so se il codice di riferimento scarso sia da biasimare, o cosa, ma i due metodi si trovano entro il 10% l'uno dall'altro sulla mia macchina usando il seguente codice, e un ciclo di solito è solo leggermente più veloce di due - come faresti tu aspettarsi.

Le dimensioni degli array variavano da 2 ^ 16 a 2 ^ 24, usando otto cicli. Sono stato attento a inizializzare gli array di sorgenti in modo che += assegnazione non chiedesse alla FPU di aggiungere la memoria spazzatura interpretata come una doppia.

Ho giocato con vari schemi, come mettere l'assegnazione di b[j] , d[j] a InitToZero[j] all'interno dei loop, e anche usando += b[j] = 1 e += d[j] = 1 , e ho ottenuto risultati abbastanza coerenti.

Come ci si potrebbe aspettare, l'inizializzazione di b e d all'interno del ciclo usando InitToZero[j] dato un vantaggio all'approccio combinato, dato che sono stati eseguiti back-to-back prima dei compiti su c , ma comunque entro il 10%. Vai a capire.

L'hardware è Dell XPS 8500 con 3 core di generazione i7 a 3,4 GHz e 8 GB di memoria. Per 2 ^ 16 a 2 ^ 24, utilizzando otto cicli, il tempo cumulativo era rispettivamente di 44.987 e 40.965. Visual C ++ 2010, completamente ottimizzato.

PS: ho cambiato i loop per contare fino a zero, e il metodo combinato era leggermente più veloce. Grattandomi la testa. Notare il nuovo dimensionamento della matrice e il numero di cicli.

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

Non sono sicuro del motivo per cui è stato deciso che MFLOPS era una metrica rilevante. Pensavo che l'idea fosse di concentrarsi sugli accessi alla memoria, quindi ho cercato di minimizzare la quantità di tempo di calcolo in virgola mobile. Ho lasciato nel += , ma non sono sicuro del perché.

Un'assegnazione diretta senza calcoli sarebbe un test più pulito del tempo di accesso alla memoria e creerebbe un test che è uniforme indipendentemente dal numero di cicli. Forse ho perso qualcosa nella conversazione, ma vale la pena pensarci due volte. Se il vantaggio è escluso dall'assegnazione, il tempo cumulativo è quasi identico a 31 secondi ciascuno.




Related