Ottimizza le prestazioni del loop

Question

Sto profilando un collo di bottiglia nel mio codice (una funzione mostrata di seguito) che viene chiamato diverse milioni di volte. Potrei usare suggerimenti per aumentare le prestazioni. I numeri XXXs sono stati presi da Sleepy.

Compilato con Visual Studio 2013, /O2 e altre impostazioni di rilascio tipiche.

indicies è in genere da 0 a 20 valori e altri parametri hanno la stessa dimensione (b.size() == indicies.size() == temps.size() == temps[k].size()).

1:   double Object::gradient(const size_t j, 
2:         const std::vector<double>& b, 
3:         const std::vector<size_t>& indices, 
4:         const std::vector<std::vector<double>>& temps) const 
5: 23.27s { 
6:    double sum = 0; 
7: 192.16s  for (size_t k : indices) 
8: 32.05s   if (k != j) 
9: 219.53s    sum += temps[k][j]*b[k]; 
10:  
11: 320.21s  return boost::math::isfinite(sum) ? sum : 0; 
13: 22.86s } 

Qualche idea?

Grazie per i suggerimenti ragazzi. Qui sono stati i risultati che ho ottenuto dalle suggestioni:

ho trovato interessante il fatto che il passaggio a cbegin() e cend() ha avuto un impatto così grande. Immagino che il compilatore non sia intelligente come potrebbe. Sono contento dell'urto, ma sono curioso di sapere se c'è più spazio qui attraverso lo srotolamento o la vettorizzazione.

Per chi fosse interessato, ecco il mio punto di riferimento per isfinite(x):

boost::isfinite(x): 
------------------------ 
SPEED: 761.164 per ms 
TIME: 0.001314 ms 
    +/- 0.000023 ms 

std::isfinite(x): 
------------------------ 
SPEED: 266.835 per ms 
TIME: 0.003748 ms 
    +/- 0.000065 ms 

Answer 1

Se si sa che il condizionale sarà soddisfatto (che in ogni iterazione si incontrerà k == j), eliminare il condizionale e sostituire la condizione di ritorno con un semplice archivio condizionale.

double sum = -(temps[j][j]*b[j]); 
for (size_t k : indices) 
    sum += temps[k][j]*b[k]; 
if (!std::isfinite(sum)) 
    sum = 0.0; 
return sum; 

Basato su intervallo è ancora abbastanza nuovo da non sempre ottenere una grande ottimizzazione. Puoi anche provare:

const auto it = cend(indices); 
for (auto it = cbegin(indices); it != end; ++it) { 
    sum += temps[*it][j]*b[*it]; 
} 

e vedere se il perf varia.

Answer 2

non sono sicuro che la sua possibile soluzione, ma perche la memorizzazione di dati in ingresso in modo che piedini di cache della CPU. Oltre ad altri costi come le chiamate implicite begin() di fine() che potresti ottimizzare alla fine, i problemi di cache mancati ti faranno sempre del male. Non utilizzare il puntatore al puntatore nel tuo codice critico. Si prega di provare anche

for (const size_t& k : indices) 

per evitare di copiare. Tuttavia ciò potrebbe essere ottimizzato per te da un compilatore.

Answer 3

Ci sono due punti che sporgono:

(a) boost :: :: matematica isFinite sta prendendo relativamente lungo. Se possibile, cerca di stabilire con altri modi in cui i risultati rientrino nell'intervallo valido.

(b) la memorizzazione di un array 2D come vettore annidato non è il metodo digiunato. Probabilmente sarebbe più veloce rendere temp un array 1D e passare la dimensione della riga come parametro. Per l'accesso a un elemento dovrai eseguire autonomamente il calcolo dell'indice. Ma poiché uno degli indici (j) è costante sul ciclo, è possibile calcolare l'indice dell'elemento di avvio prima del ciclo e all'interno solo incrementare l'indice 1. Ciò potrebbe comportare un miglioramento significativo.

Answer 4

La prima relativamente semplice ottimizzazione Mi piacerebbe tentare, è questa:

const std::vector<std::vector<double>>& temps 

Questo è potenzialmente in tutto il luogo in memoria e non nella cache-friendly di sorta, come è fondamentalmente una matrice dinamica di array dinamici con una matrice dinamica separata per ogni singola riga (o colonna) della matrice memorizzata in una posizione potenzialmente completamente diversa in memoria.

Se è possibile creare una classe "Matrix" che memorizza i dati in un singolo array (es: singolo vettore), ciò potrebbe aiutare un bel po '.

La prossima cosa che mi piacerebbe provare è questo:

7: 192.16s  for (size_t k : indices) 
8: 32.05s   if (k != j) 
9: 219.53s    sum += temps[k][j]*b[k]; 

Possiamo vedere che 'j' non cambia mai nel ciclo, quindi se 'temp' potrebbe essere trasposta in anticipo (anche facile da fare se si scrive una corretta classe Matrix), si può semplicemente accedere alla memoria in sequenza da sinistra a destra e accedere a più componenti della matrice in una singola riga della cache.

Ultimo ma non meno importante, ti imbatti davvero in infinito o in NaN con gli input con cui stai lavorando? In quest'ultimo caso, vedrei se potrei trasferire il controllo NaN altrove per verificare la validità di quegli array temps (a condizione di riutilizzare gli stessi più volte). A meno che tu non abbia già riscontrato errori o stia lavorando con un software veramente mission-critical, proverei a trasformare quel controllo in un'asserzione in modalità debug e gestirò solo un caso limite se lo incontrerai effettivamente in produzione.

Answer 5

Credo che otterrete un notevole incremento delle prestazioni se riorganizzate il vostro temps. Il codice seguente linea

temps[k][j]*b[k]

iterata attraverso i valori della k è (almeno quello mi risulta che sia) una moltiplicazione se un (trasposta) matrice per un vettore. Ora, l'accesso a un elemento temps[k][j] implica effettivamente la lettura di temps[k], il dereferenziamento (un puntatore al vettore assegnato) e la lettura dell'elemento [j].

Invece di utilizzare vector<vector<double>, è possibile utilizzare un 1-dimensionale vector Inoltre, poiché questa funzione è il collo di bottiglia, è possibile memorizzare i dati in esso in un modo "trasposto". Significa che l'accesso a temps[k][j] in un nuovo formato diventa temps[j * N + k] dove "N" è l'intervallo di j. Da questo si utilizza anche la cache in modo più efficiente.