efficiente passaggio di std :: vector

Question

Quando una funzione C++ accetta un argomento std::vector, il modello usuale è di passare dal const riferimento, come ad esempio:

int sum2(const std::vector<int> &v) 
{ 
    int s = 0; 
    for(size_t i = 0; i < v.size(); i++) s += fn(v[i]); 
    return s; 
} 

Credo che risultati di questa codifica in doppia dereferenziazione quando gli elementi vettoriali sono accessibili, poiché la CPU deve prima chiamare il riferimento v per leggere il puntatore al primo elemento, il quale puntatore deve essere nuovamente dereferenziato per leggere il primo elemento. Mi aspetterei che sarebbe più efficiente passare una copia superficiale dell'oggetto vettoriale sullo stack. Tale copia superficiale incapsulerebbe un puntatore al primo elemento e la dimensione, con il puntatore che fa riferimento alla stessa area di memoria del vettore originale.

int sum2(vector_ref<int> v) 
{ 
    int s = 0; 
    for(size_t i = 0; i < v.size(); i++) s += fn(v[i]); 
    return s; 
} 

Prestazioni simili, ma molto meno la comodità potrebbe essere ottenuta passando una coppia di iteratori di accesso casuale. La mia domanda è: che cosa è difettoso con questa idea? Mi aspetto che ci sia una buona ragione per cui le persone intelligenti accettano di pagare il costo performace del riferimento vettoriale o di affrontare l'inconveniente degli iteratori.

Edit: Sulla base dei pervenire al seguente indirizzo di seguito, si prega di prendere in considerazione la situazione se ho semplicemente rinominare il suggerito vector_ref classe per fetta o gamma. L'intenzione è quella di utilizzare coppie iteratore ad accesso casuale con sintassi più naturale.

Answer 1

Credo che questo codice si traduce in doppia dereferenziazione quando gli elementi vettoriali sono accessibili

Non necessariamente. I compilatori sono abbastanza intelligenti e dovrebbero essere in grado di eliminate common subexpressions. Possono vedere che l'operatore [] non cambia il "puntatore al primo elemento", quindi non hanno bisogno di ricaricare la CPU dalla memoria per ogni iterazione del ciclo.

Answer 2

Passaggio di valore a meno che non si sia certi che il passaggio per riferimento migliora le prestazioni.

Quando si passa al valore, è possibile che si verifichi la copia di elisione che si tradurrà in prestazioni simili se non migliori.

Dave ha scritto su di esso qui:

http://cpp-next.com/archive/2009/08/want-speed-pass-by-value/

Answer 3

Che cosa è difettoso con questa idea?

Semplice: è l'ottimizzazione prematura. Alternative: accettare un vector<int> const& e utilizzare iteratori o pass iterator direttamente alla funzione.

Answer 4

Non esiste un doppio dereferenziamento poiché il compilatore probabilmente passerà il puntatore reale al vettore come argomento e non un puntatore a un puntatore. Si può semplicemente provare questo fuori e controllare la vista di smontaggio del vostro IDE per ciò che sta realmente succedendo dietro le quinte:

void Method(std::vector<int> const& vec) { 
int i = vec.back(); 
} 


void SomeOtherMethod() { 
    std::vector<int> vec; 
    vec.push_back(1); 
    Method(vec); 
} 

Cosa succede qui? Il vettore è allocato nello stack.La prima parte posteriore spinta è tradotto in:

push  eax // this is the constant one that has been stored in eax 
lea   ecx,[ebp-24h] // ecx is the pointer to vec on the stack 
call  std::vector<int,std::allocator<int> >::push_back 

Ora chiamiamo Method(), passando il const vettore &:

lea   ecx,[ebp-24h] 
push  ecx 
call  Method (8274DC0h) 

Non sorprende, il puntatore al vettore viene passato come riferimenti non sono altro che in modo permanente puntatori dereferenziati. Ora all'interno Method(), il vettore si accede nuovamente:

mov   ecx,dword ptr [ebp+8] 
call  std::vector<int,std::allocator<int> >::back (8276100h) 

Il puntatore del vettore è presa direttamente dalla pila e scritto ECX.

Answer 5

Hai ragione che qui c'è un'ulteriore indiretta. È concepibile (anche se sarebbe sorprendente) se il compilatore (con l'aiuto della generazione del codice link-time) lo ottimizzasse.

Quello che hai proposto viene talvolta chiamato slicing, ed è ampiamente utilizzato in alcune situazioni. Anche se, in generale, non sono sicuro che valga i pericoli. Devi stare molto attento a valutare la tua fetta (o quella di qualcun altro).

Si noti che se si è utilizzato iteratori per il circuito, invece di indicizzazione, allora si sarebbe Deref il riferimento solo un paio di volte (per chiamare e begin()end()) piuttosto che n volte (per indicizzare il vettore).

int sum(const vector<int> &v) 
{ 
    int s = 0; 
    for (auto it = v.begin(); it != v.end(); ++it) { 
     s += fn(*it); 
    } 
    return s; 
} 

(sto assumendo l'ottimizzatore issare le end() chiamate fuori dal giro. Si potrebbe fare in modo esplicito per essere certi.)

Passare un paio di iteratori invece del contenitore stesso sembra come l'idioma STL. Ciò ti darebbe maggiore generalità, dal momento che il tipo di contenitore può variare, ma anche il numero di dereferenze necessario.

Answer 6

Cosa c'è di sbagliato con la vostra idea è che si dispone già di due perfettamente buone soluzioni:

• passare il vettore come è, sia per valore (dove il compilatore spesso di eliminare la copia), o da (const) riferimento, e fidarsi del compilatore per eliminare la doppia indiretta, o
• Passare una coppia iteratore.

Ovviamente si può sostenere che la coppia iteratore è "sintassi meno naturale", ma non sono d'accordo. È perfettamente naturale per chiunque sia abituato alla STL. È efficiente e ti dà esattamente ciò che ti serve per lavorare con la gamma, usando gli algoritmi std o le tue funzioni.

Le coppie di Iterator sono un idioma C++ comune e un programmatore C++ che legge il codice li capirà senza problemi, mentre saranno sorpresi dai wrapper di vettori fatti in casa.

Se si è davvero paranoico sulle prestazioni, passare la coppia di iteratori. Se la sintassi ti infastidisce davvero, passa il vettore e si fida del compilatore.