c++ - Perché il mio programma rallenta quando esegui il ciclo su esattamente 8192 elementi?




performance memory-management (2)

Ecco l'estratto dal programma in questione. La matrice img[][] ha la dimensione SIZE × SIZE ed è inizializzata su:

img[j][i] = 2 * j + i

Quindi, si crea una matrice res[][] , e ogni campo in questo campo è fatto per essere la media dei 9 campi che lo circondano nella matrice img. Il bordo è lasciato a 0 per semplicità.

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

Questo è tutto ciò che c'è nel programma. Per completezza, ecco cosa viene prima. Nessun codice viene dopo. Come puoi vedere, è solo l'inizializzazione.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

Fondamentalmente, questo programma è lento quando SIZE è un multiplo di 2048, ad esempio i tempi di esecuzione:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

Il compilatore è GCC. Da quello che so, questo è dovuto alla gestione della memoria, ma non ne so molto su questo argomento, ed è per questo che sto chiedendo qui.

Anche come risolvere questo sarebbe bello, ma se qualcuno potesse spiegare questi tempi di esecuzione sarei già abbastanza felice.

Conosco già malloc / free, ma il problema non è la quantità di memoria utilizzata, è semplicemente il tempo di esecuzione, quindi non so come possa essere d'aiuto.


I seguenti test sono stati eseguiti con il compilatore di Visual C ++ poiché viene utilizzato dall'installazione Qt Creator predefinita (credo senza il flag di ottimizzazione). Quando si utilizza GCC, non c'è una grande differenza tra la versione di Mystical e il mio codice "ottimizzato". Quindi la conclusione è che le ottimizzazioni del compilatore si prendono cura della micro ottimizzazione meglio degli umani (io alla fine). Lascio il resto della mia risposta per riferimento.

Non è efficiente elaborare le immagini in questo modo. È meglio usare matrici a dimensione singola. L'elaborazione di tutti i pixel avviene in un unico ciclo. L'accesso casuale ai punti può essere fatto usando:

pointer + (x + y*width)*(sizeOfOnePixel)

In questo caso particolare, è meglio calcolare e memorizzare nella cache la somma di tre gruppi di pixel orizzontalmente perché vengono utilizzati tre volte ciascuno.

Ho fatto alcuni test e penso che valga la pena condividerlo. Ogni risultato è una media di cinque test.

Codice originale dall'utente1615209:

8193: 4392 ms
8192: 9570 ms

La versione di Mystical:

8193: 2393 ms
8192: 2190 ms

Due passaggi usando un array 1D: primo passaggio per somme orizzontali, secondo per somma verticale e media. Indirizzamento a due passaggi con tre puntatori e incrementi di questo tipo:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

Due passaggi utilizzando un array 1D e indirizzamento come questo:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

Una cache di passaggio passa somme orizzontali di una sola riga in modo che rimangano nella cache:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

Conclusione:

  • Nessun vantaggio nell'uso di più puntatori e incrementi (ho pensato che sarebbe stato più veloce)
  • Memorizzare le somme orizzontali è meglio che calcolarle più volte.
  • Due passaggi non sono tre volte più veloci, due volte soltanto.
  • È possibile ottenere 3,6 volte più velocemente utilizzando sia un singolo passaggio che un risultato intermedio nella cache

Sono sicuro che è possibile fare molto meglio.

NOTA Si noti che ho scritto questa risposta per risolvere problemi di prestazioni generali piuttosto che il problema della cache spiegato nell'eccellente risposta di Mystical. All'inizio era solo uno pseudo codice. Mi è stato chiesto di fare dei test nei commenti ... Ecco una versione completamente refactored con i test.


L'ordine di accesso all'elemento curato ci sono ancora alcuni frutti a bassa attaccatura. L'accumulo può essere fatto in modo tale che quando si esegue l'iterazione verso destra, solo 3 nuovi valori devono essere recuperati dalla memoria e accumulati. Il trucco è sapere come rilasciare la colonna più a sinistra; quando aggiungi una nuova colonna ricorda il suo valore finché non esce dalla finestra di campionamento.

Il costo prima: 9 leggi, 9 addizioni, 1 divisione Il costo dopo: 3 letti, 3 addizioni, 1 divisione

Pensa alla finestra di campionamento come casella 3x3 dove tieni traccia di ogni colonna (1x3) separatamente. Accumula una nuova colonna e rilascia quella più vecchia.

La divisione è un'istruzione ad alta latenza, quindi potrebbe essere vantaggioso nascondere la latenza, ma prima di andare lì l'output del compilatore dovrebbe essere controllato se la divisione per costante viene eliminata e se lo svolgimento del ciclo (dal compilatore) giunge già a una compensazione di latenza.

Ma dopo l'ottimizzazione più drammatica dell'uso corretto della cache, queste sono cose davvero secondarie.





gcc