In C ++, è ancora cattiva pratica di restituire un vettore da una funzione?
https://stackoverflow.com/questions/3134831
-
01-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Versione corta: E 'comune per tornare oggetti di grandi dimensioni, ad esempio vettori / matrici-in molti linguaggi di programmazione. E 'questo stile ora accettabile in C ++ 0x se la classe ha un costruttore mossa, o fare i programmatori C ++ considerano strano / brutto / abominio?
Versione lunga:? in C ++ 0x è questa cattiva forma ancora considerato
std::vector<std::string> BuildLargeVector();
...
std::vector<std::string> v = BuildLargeVector();
La versione tradizionale sarebbe simile a questa:
void BuildLargeVector(std::vector<std::string>& result);
...
std::vector<std::string> v;
BuildLargeVector(v);
Nella versione più recente, il valore restituito da BuildLargeVector è un rvalue, così v dovrebbe essere costruito utilizzando il costruttore giocata std::vector, supponendo (N) RVO non avviene.
Anche prima C ++ 0x la prima forma sarebbe spesso "efficace" a causa di (N) RVO. Tuttavia, (N) RVO è a discrezione del compilatore. Ora che abbiamo i riferimenti rvalue è garantito che nessuna copia completa avrà luogo.
Modifica : non si tratta davvero di ottimizzazione. Entrambe le forme mostrate hanno prestazioni quasi identiche nei programmi del mondo reale. Considerando che, in passato, la prima forma avrebbe potuto avere prestazioni ordine di grandezza peggio. Di conseguenza, il primo modulo è stato un grande odore codice C ++ programmazione per lungo tempo. Non più, spero?
Soluzione
Dave Abrahams ha un'analisi piuttosto completa di la velocità di passaggio / valori ritornano .
Breve risposta, se è necessario restituire un valore, allora restituisce un valore. Non utilizzare i riferimenti di uscita perché il compilatore fa comunque. Naturalmente ci sono avvertimenti, quindi vi consigliamo di leggere questo articolo.
Altri suggerimenti
Almeno IMO, di solito è una cattiva idea, ma non per ragioni di efficienza. E 'una cattiva idea, perché la funzione in questione di solito dovrebbe essere scritto come un algoritmo generico che produce la sua uscita tramite un iteratore. Quasi qualsiasi codice che accetta o restituisce un contenitore, invece di operare su iteratori dovrebbe essere considerato sospetto.
Non fraintendetemi:. Ci sono volte ha senso passare in giro la raccolta-come oggetti (ad esempio, le stringhe), ma per l'esempio citato, mi piacerebbe prendere in considerazione il passaggio o la restituzione del vettore di una povera idea
Il succo è:
Copia Elision e RVO possono evitare le "copie spaventosi" (il compilatore non è tenuto ad attuare queste ottimizzazioni, e in alcune situazioni non può essere applicata)
riferimenti C ++ 0x rvalue permettere una stringa / implementazioni vettoriali che garanzie che.
Se è possibile abbandonare vecchi compilatori / implementazioni STL, vettori di ritorno liberamente (e assicurarsi che i propri oggetti supportano, anche). Se le vostre esigenze di base di codice per supportare compilatori "minori", il bastone per il vecchio stile.
Purtroppo, che ha grande influenza sulle interfacce. Se C ++ 0x non è un'opzione, e avete bisogno di garanzie, si potrebbe usare al posto di riferimento contato o copy-on-write oggetti in alcuni scenari. Hanno aspetti negativi con multithreading, però.
(vorrei solo una risposta in C ++ sarebbe semplice e lineare e senza condizioni).
In effetti, dal momento che C ++ 11, il costo di copiare il std::vector è andato nella maggior parte dei casi.
Tuttavia, si deve tenere presente che il costo di costruzione il nuovo vettore (quindi destructing it) esiste ancora, e utilizzando parametri di uscita invece di ritornare al valore viene ancora utile quando si desidera riutilizzare la capacità del vettore. Questo è documentato come eccezione in F.20 delle linee guida fondamentali C ++.
Let confrontare:
std::vector<int> BuildLargeVector1(size_t vecSize) {
return std::vector<int>(vecSize, 1);
}
con:
void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
v.assign(vecSize, 1);
}
Ora, supponiamo abbiamo bisogno di chiamare questi metodi volte numIter in un loop stretto, ed eseguire una certa azione. Ad esempio, supponiamo di calcolare la somma di tutti gli elementi.
Utilizzando BuildLargeVector1, si dovrebbe fare:
size_t sum1 = 0;
for (int i = 0; i < numIter; ++i) {
std::vector<int> v = BuildLargeVector1(vecSize);
sum1 = std::accumulate(v.begin(), v.end(), sum1);
}
Utilizzando BuildLargeVector2, si dovrebbe fare:
size_t sum2 = 0;
std::vector<int> v;
for (int i = 0; i < numIter; ++i) {
BuildLargeVector2(/*out*/ v, vecSize);
sum2 = std::accumulate(v.begin(), v.end(), sum2);
}
Nel primo esempio, ci sono molti inutili allocazioni dinamiche / deallocazioni andranno, che è impedito nel secondo esempio utilizzando un'uscita parametro alla vecchia maniera, riutilizzando memoria già allocata. O se non questa ottimizzazione è la pena di fare dipende dal costo relativo del allocazione / deallocazione rispetto al costo di calcolo / mutare i valori.
Indice di riferimento
un gioco da Let con i valori di vecSize e numIter. Manterremo vecSize * numIter costante in modo che "in teoria", occorre prendere contemporaneamente (= v'è lo stesso numero di compiti e integrazioni, con gli stessi valori), e la differenza di tempo può venire solo dal costo di allocazioni, deallocazioni, e migliore utilizzo delle cache.
In particolare, usiamo vecSize * numIter = 2 ^ 31 = 2147483648, perché ho 16GB di RAM e questo numero assicura che non più di 8 GB allocata (sizeof (int) = 4), assicurando che non sto scambiando su disco (tutti gli altri programmi sono stati chiusi, ho avuto ~ 15GB disponibile quando si esegue il test).
Ecco il codice:
#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
class Timer {
using clock = std::chrono::steady_clock;
using seconds = std::chrono::duration<double>;
clock::time_point t_;
public:
void tic() { t_ = clock::now(); }
double toc() const { return seconds(clock::now() - t_).count(); }
};
std::vector<int> BuildLargeVector1(size_t vecSize) {
return std::vector<int>(vecSize, 1);
}
void BuildLargeVector2(/*out*/ std::vector<int>& v, size_t vecSize) {
v.assign(vecSize, 1);
}
int main() {
Timer t;
size_t vecSize = size_t(1) << 31;
size_t numIter = 1;
std::cout << std::setw(10) << "vecSize" << ", "
<< std::setw(10) << "numIter" << ", "
<< std::setw(10) << "time1" << ", "
<< std::setw(10) << "time2" << ", "
<< std::setw(10) << "sum1" << ", "
<< std::setw(10) << "sum2" << "\n";
while (vecSize > 0) {
t.tic();
size_t sum1 = 0;
{
for (int i = 0; i < numIter; ++i) {
std::vector<int> v = BuildLargeVector1(vecSize);
sum1 = std::accumulate(v.begin(), v.end(), sum1);
}
}
double time1 = t.toc();
t.tic();
size_t sum2 = 0;
{
std::vector<int> v;
for (int i = 0; i < numIter; ++i) {
BuildLargeVector2(/*out*/ v, vecSize);
sum2 = std::accumulate(v.begin(), v.end(), sum2);
}
} // deallocate v
double time2 = t.toc();
std::cout << std::setw(10) << vecSize << ", "
<< std::setw(10) << numIter << ", "
<< std::setw(10) << std::fixed << time1 << ", "
<< std::setw(10) << std::fixed << time2 << ", "
<< std::setw(10) << sum1 << ", "
<< std::setw(10) << sum2 << "\n";
vecSize /= 2;
numIter *= 2;
}
return 0;
}
Ed ecco il risultato:
$ g++ -std=c++11 -O3 main.cpp && ./a.out
vecSize, numIter, time1, time2, sum1, sum2
2147483648, 1, 2.360384, 2.356355, 2147483648, 2147483648
1073741824, 2, 2.365807, 1.732609, 2147483648, 2147483648
536870912, 4, 2.373231, 1.420104, 2147483648, 2147483648
268435456, 8, 2.383480, 1.261789, 2147483648, 2147483648
134217728, 16, 2.395904, 1.179340, 2147483648, 2147483648
67108864, 32, 2.408513, 1.131662, 2147483648, 2147483648
33554432, 64, 2.416114, 1.097719, 2147483648, 2147483648
16777216, 128, 2.431061, 1.060238, 2147483648, 2147483648
8388608, 256, 2.448200, 0.998743, 2147483648, 2147483648
4194304, 512, 0.884540, 0.875196, 2147483648, 2147483648
2097152, 1024, 0.712911, 0.716124, 2147483648, 2147483648
1048576, 2048, 0.552157, 0.603028, 2147483648, 2147483648
524288, 4096, 0.549749, 0.602881, 2147483648, 2147483648
262144, 8192, 0.547767, 0.604248, 2147483648, 2147483648
131072, 16384, 0.537548, 0.603802, 2147483648, 2147483648
65536, 32768, 0.524037, 0.600768, 2147483648, 2147483648
32768, 65536, 0.526727, 0.598521, 2147483648, 2147483648
16384, 131072, 0.515227, 0.599254, 2147483648, 2147483648
8192, 262144, 0.540541, 0.600642, 2147483648, 2147483648
4096, 524288, 0.495638, 0.603396, 2147483648, 2147483648
2048, 1048576, 0.512905, 0.609594, 2147483648, 2147483648
1024, 2097152, 0.548257, 0.622393, 2147483648, 2147483648
512, 4194304, 0.616906, 0.647442, 2147483648, 2147483648
256, 8388608, 0.571628, 0.629563, 2147483648, 2147483648
128, 16777216, 0.846666, 0.657051, 2147483648, 2147483648
64, 33554432, 0.853286, 0.724897, 2147483648, 2147483648
32, 67108864, 1.232520, 0.851337, 2147483648, 2147483648
16, 134217728, 1.982755, 1.079628, 2147483648, 2147483648
8, 268435456, 3.483588, 1.673199, 2147483648, 2147483648
4, 536870912, 5.724022, 2.150334, 2147483648, 2147483648
2, 1073741824, 10.285453, 3.583777, 2147483648, 2147483648
1, 2147483648, 20.552860, 6.214054, 2147483648, 2147483648
(Intel i7-7700K @ 4.20GHz; 16GB DDR4 2400MHz; Kubuntu 18.04)
Notazione:. Mem (v) = V.SIZE () * sizeof (int) = V.SIZE () * 4 su mia piattaforma
Non sorprendentemente, quando numIter = 1 (cioè, mem (v) = 8 GB), i tempi sono perfettamente identici. Infatti, in entrambi i casi allochiamo sola volta un enorme vettore di 8 GB memoria. Questo dimostra anche che nessuna copia è accaduto quando si utilizza BuildLargeVector1 (!): Non avrei RAM sufficiente per eseguire la copia
Quando numIter = 2, riutilizzando la capacità vettore invece di ri-allocare un secondo vettore è 1.37x veloce.
Quando numIter = 256, riutilizzando la capacità vettore (invece di allocare / deallocare un vettore ripetutamente 256 volte ...) è 2.45x veloce :)
Possiamo notare che time1 è praticamente costante da numIter = 1 a numIter = 256, il che significa che l'attribuzione di un enorme vettore di 8GB è praticamente costosa come allocare 256 vettori di 32 MB. Tuttavia, l'attribuzione di un enorme vettore di 8GB è sicuramente più costoso di attribuzione di un vettore di 32 MB, in modo da riutilizzare la capacità del vettore fornisce miglioramento delle prestazioni.
Da numIter = 512 (MEM (v) = 16 MB) per numIter = 8M (MEM (v) = 1 KB), è il punto debole: entrambi i metodi sono esattamente il più veloce, e più veloce di tutte le altre combinazioni di numIter e vecSize. Questo probabilmente ha a che fare con il fatto che la dimensione della cache L3 del mio processore è 8MB, in modo che il vettore più o meno adatta completamente nella cache. Non mi spiego perché il salto improvviso di time1 è per mem (v) = 16 MB, sembrerebbe più logico che accada subito dopo, quando mem (v) = 8 MB. Si noti che surprisingly, in questo luogo dolce, non riutilizzando capacità è in realtà leggermente più veloce! Non mi spiego.
Quando le cose iniziano a farsi numIter > 8M brutto. Entrambi i metodi diventano più lenti, ma la restituzione del vettore per valore diventa ancora più lento. Nel caso peggiore, con un vettore contenente un solo singolo int, capacità riutilizzando invece di ritornare per valore è 3.3x più veloce. Presumibilmente, questo è dovuto ai costi fissi di malloc () che iniziano a dominare.
Si noti come la curva per tempo2 è più liscia la curva per tempo1:. Non solo ri-utilizzando capacità vettore è generalmente più veloce, ma forse ancora più importante, è più prevedibile
Si noti inoltre che nel punto dolce, siamo stati in grado di eseguire 2 miliardi di aggiunte di numeri interi a 64 bit in ~ 0.5s, che è proprio ottimale su un processore 4.2GHz a 64 bit. Potremmo fare meglio parallelizzando calcolo al fine di utilizzare tutte 8 core (test precedente utilizza solo core alla volta, che ho verificato eseguendo nuovamente la prova che il monitoraggio dell'utilizzo CPU). Le migliori prestazioni si ottengono quando mem (v) = 16 kbyte, che è dell'ordine di grandezza di L1 cache (cache L1 dati per l'i7-7700K è 4x32kB).
Naturalmente, le differenze diventano sempre meno rilevanti quanto più calcolo che in realtà hanno a che fare sui dati. Qui di seguito sono i risultati se si sostituisce sum = std::accumulate(v.begin(), v.end(), sum); da for (int k : v) sum += std::sqrt(2.0*k);:
Conclusioni
- Uso parametri di uscita invece di ritornare dal valore possono fornire vantaggi prestazionali dalla capacità riutilizzo.
- su un moderno computer desktop, questo sembra applicabile solo alle grandi vettori (> 16 MB) e piccoli vettori (<1kB).
- evitare di allocare milioni / miliardi di piccoli vettori (<1kB). Se la capacità possibile, il riutilizzo, o meglio ancora, progettare l'architettura in modo diverso.
I risultati possono differire su altre piattaforme. Come al solito, se la performance è, benchmark di scrittura per il vostro caso specifico utilizzo.
Continuo a pensare che sia una cattiva pratica, ma vale la pena notare che il mio team utilizza MSVC 2008 e GCC 4.1, quindi non stiamo utilizzando le più recenti compilatori.
In precedenza molti dei punti caldi indicati in VTune con MSVC 2008 è venuto giù alla copia stringa. Abbiamo avuto codice come questo:
String Something::id() const
{
return valid() ? m_id: "";
}
... Si noti che abbiamo usato il nostro tipo String (questo era necessario perché stiamo fornendo un kit di sviluppo software in cui gli scrittori di plugin potrebbero utilizzare diversi compilatori e quindi differenti implementazioni incompatibili di std :: string / std :: wstring).
ho fatto un semplice cambiamento nella risposta al grafico chiamata campionamento sessione di profilatura mostrando String :: String (const String &) per essere occupare una notevole quantità di tempo. Metodi come nell'esempio di cui sopra sono stati i maggiori contribuenti (in realtà la sessione di profiling ha mostrato l'allocazione della memoria e deallocazione di essere uno dei più grandi punti caldi, con il costruttore String copia essere il principale contributore per le assegnazioni).
Il cambiamento che ho fatto era semplice:
static String null_string;
const String& Something::id() const
{
return valid() ? m_id: null_string;
}
Tuttavia questo ha fatto un mondo di differenza! L'hotspot è andato via in sessioni successive Profiler, e oltre a questo facciamo un sacco di unit testing approfondito per tenere traccia delle nostre prestazioni dell'applicazione. Tutti i tipi di tempi di test di performance è sceso in modo significativo dopo queste modifiche semplici.
Conclusione: non stiamo usando gli ultimi compilatori assoluti, ma ancora non riesco a dipendere dal compilatore ottimizzare via la copia per la restituzione in base al valore in modo affidabile (almeno non in tutti i casi). Che non può essere il caso per coloro che utilizzano i compilatori più recenti, come MSVC 2010. Non vedo l'ora di quando siamo in grado di utilizzare C ++ 0x e semplicemente utilizzare i riferimenti rvalue e non sempre ci si deve preoccupare che stiamo pessimizing nostro codice restituendo complesso classi per valore.
[Modifica] Come Nate sottolineato, RVO applica a tornare provvisori creati all'interno di una funzione. Nel mio caso, non c'erano tali provvisori (ad eccezione del ramo nullo se si costruisce una stringa vuota) e quindi RVO non sarebbe stata applicabile.
Basta essere pignoli un po ': non è comune in molti linguaggi di programmazione per tornare array dalle funzioni. Nella maggior parte di esse, viene restituito un riferimento alla matrice. In C ++, l'analogia più vicina sarebbe tornato boost::shared_array
Se le prestazioni sono un problema reale si dovrebbe capire che la semantica mossa non sono sempre più veloce di copiare. Per esempio, se si dispone di una stringa che utilizza il piccola stringa di ottimizzazione poi per le piccole stringhe di un costruttore mossa deve fare la stessa quantità di lavoro come un costruttore di copia regolare.
