Problema di prestazioni per vector :: size () in un ciclo

ciao quando si ha un vector var; for(int i=0; i< var.size();i++) , la funzione size() chiamata ogni volta o solo una volta?


dalle risposte credo sia meglio usare iteratori, o semplicemente avere variabili prima del ciclo

In teoria , viene chiamato ogni volta, dal momento che un ciclo for:

 for(initialization; condition; increment) body; 

è espanso per qualcosa di simile

 { initialization; while(condition) { body; increment; } } 

(nota le parentesi graffe, perché l’inizializzazione è già in un ambito interno)

In pratica , se il compilatore comprende che un pezzo della tua condizione è invariante per tutta la durata del ciclo e non ha effetti collaterali , può essere abbastanza intelligente da spostarlo. Questo è fatto di routine con strlen e cose del genere (che il compilatore conosce bene) nei loop in cui la sua argomentazione non è scritta.

Tuttavia si deve notare che quest’ultima condizione non è sempre banale da dimostrare; in generale, è facile se il contenitore è locale alla funzione e non viene mai passato a funzioni esterne; se il contenitore non è locale (ad es. è passato per riferimento – anche se è const ) e il corpo del loop contiene chiamate ad altre funzioni, spesso il compilatore deve presumere che tali funzioni possano alterarlo, bloccando così il sollevamento del calcolo della lunghezza.

Fare quell’ottimizzazione a mano è degno se sai che una parte della tua condizione è “costosa” da valutare (e tale condizione di solito non lo è, dal momento che di solito si riduce a una sottrazione puntatore, che è quasi sicuramente in linea).


Modifica: come altri hanno detto, in generale con i contenitori è meglio usare gli iteratori, ma per i vector non è così importante, perché l’accesso casuale agli elementi tramite operator[] è garantito come O (1); in realtà con i vettori di solito è una sum puntatore (vettore base + indice) e dereferenziazione rispetto all’incremento del puntatore (elemento precedente + 1) e dereferenza degli iteratori. Dato che l’indirizzo di destinazione è sempre lo stesso, non penso che tu possa ottenere qualcosa dagli iteratori in termini di localizzazione della cache (e anche se così, se non stai camminando con grandi array in loop stretti non dovresti nemmeno notarli tipo di miglioramenti).

Per gli elenchi e gli altri contenitori, invece, utilizzare gli iteratori anziché l’accesso casuale può essere davvero importante, dal momento che l’utilizzo dell’accesso casuale può significare percorrere ogni volta l’elenco, mentre l’incremento di un iteratore è solo un dereferenziamento del puntatore.

Viene “chiamato” ogni volta, ma inserisco le virgolette tra virgolette perché probabilmente è solo una chiamata al metodo inline, quindi non devi preoccuparti delle sue prestazioni.

Perché non usare vector::iterator invece?

La funzione membro size() viene chiamata ogni volta, ma sarebbe un’implementazione davvero pessima che non sarebbe in linea e una strana in cui non sarebbe un semplice accesso di un dato fisso o una sottrazione di due puntatori.
Ad ogni modo, non dovresti preoccuparti di tali banalità fino a quando non avrai profilato la tua domanda e scoprirai che questo è un collo di bottiglia.

Tuttavia, ciò che dovresti prestare attenzione è:

  1. Il tipo corretto per l’indice di un vettore è std::vector::size_type .
  2. Ci sono tipi (alcuni iteratori, per esempio) dove i++ potrebbe essere più lento di ++i .

Pertanto, il ciclo dovrebbe essere:

 for(vector::size_type i=0; i 

Deve essere chiamato ogni volta perché size () potrebbe restituire un valore diverso ogni volta.

Quindi non c’è una grande scelta che semplicemente deve essere.

Come altri hanno già detto

  • la semantica deve essere come se fosse chiamata ogni volta
  • è probabilmente in linea e probabilmente è una funzione semplice

in cima a cui

  • un ottimizzatore abbastanza intelligente può essere in grado di dedurre che si tratta di un ciclo invariante senza effetti collaterali e di eliderlo interamente (questo è più facile se il codice è in linea, ma potrebbe essere ansible anche se non lo è se il compilatore esegue l’ottimizzazione globale)

Penso che se il compilatore può dedurre in modo conclusivo che la variabile var non viene modificata all’interno del “loop body”

 for(int i=0; i< var.size();i++) { // loop body } 

allora quanto sopra può essere trasposto a qualcosa di equivalente a

 const size_t var_size = var.size(); for( int i = 0; i < var_size; i++ ) { // loop body } 

Tuttavia, non ne sono assolutamente sicuro, quindi i commenti sono benvenuti 🙂

Anche,

  • Nella maggior parte dei casi, la funzione membro size() è in linea, quindi il problema non giustifica

  • La preoccupazione è forse ugualmente applicabile alla end() che è sempre usata per il looping basato sull'iteratore, cioè it != container.end()

  • Per favore considera di usare size_t o vector::size_type per il tipo di i [vedi il commento di Steve Jessop sotto.]

Ma potrebbe essere fatto in questo modo (a condizione che questo ciclo intenda solo leggere / scrivere senza realmente cambiare la dimensione di un vettore):

 for(vector::size_type i=0, size = var.size(); i < size; ++i) { //do something } 

Nel ciclo precedente hai una sola chiamata alla dimensione indipendentemente dalla dimensione che è in linea o meno.

come altri hanno detto, il compilatore deciderà cosa fare con il codice reale scritto. La cifra chiave è che viene chiamato ogni volta. Ma se vuoi ottenere un incremento delle prestazioni, è meglio scrivere il tuo codice con alcune considerazioni. Il tuo caso è uno di questi, ce ne sono anche altri, come la differenza tra questi due pezzi di codice:

 for (int i = 0 ; i < n ; ++i) { for ( int j = 0 ; j < n ; ++j) printf("%d ", arr[i][j]); printf("\n"); } for (int j = 0 ; j < n ; ++j) { for ( int i = 0 ; i < n ; ++i) printf("%d ", arr[i][j]); printf("\n"); } 

La differenza è che il primo non cambierà la pagina ram troppo per i riferimenti, ma l'altro esaurirà la tua cache e TLB e altre cose.

Anche in linea non sarà di grande aiuto! perché l'ordine della funzione chiamante rimarrà come n (dimensione del vettore) volte. Aiuta comunque in alcuni posti, ma la cosa migliore è riscrivere il tuo codice.

Ma! se vuoi lasciare che un compilatore faccia le ottimizzazioni sul tuo codice, non mettere MAI volatile, in questo modo:

 for(volatile int i = 0 ; i < 100; ++i) 

Impedisce al compilatore di ottimizzare. Se hai bisogno di un altro suggerimento per le prestazioni usa il registro invece che volatile.

 for(register int i = 0 ; i < 100; ++i) 

Il compilatore proverà a non spostare I dai registri della CPU alla RAM. Non è garantito che possa farlo, ma farà il suo meglio;)

Testato per 900k iterazioni Il tempo impiegato è di 43 secondi per le dimensioni precalcolate e di 42 secondi per l’utilizzo della chiamata size ().

Se la dimensione del vettore garantita non cambia nel ciclo, meglio usare le dimensioni precalcolate altrimenti non c’è scelta e devi usare size ().

 #include  #include  using namespace std; int main() { vector v; for (int i = 0; i < 30000; i++) v.push_back(i); const size_t v_size = v.size(); for(int i = 0; i < v_size; i++) for(int j = 0; j < v_size; j++) cout << ""; //for(int i = 0; i < v.size(); i++) // for(int j = 0; j < v.size(); j++) // cout << ""; }