Inizializzazione vettoriale più lenta dell'array ... perché?

Question

Ho provato 2 cose: (pseudo codice qui sotto)

int arr[10000]; 
for (int i = 0; i < 10000; i++) 
{ 
    for (int j = 0; j < 10000; j++) 
    { 
     arr[j] = j; 
    } 
} 

e

vector<int> arr(10000); 
for (int i = 0; i < 10000; i++) 
{ 
    for (int j = 0; j < 10000; j++) 
    { 
     arr[j] = j; 
    } 
} 

I corse sia i programmi e contati utilizzando il comando shell "tempo". Il programma 1 viene eseguito in 5 secondi, il programma 2 viene eseguito in 30 secondi. Ho eseguito entrambi i programmi con l'ottimizzazione del compilatore attivata ed entrambi i programmi sono stati eseguiti all'incirca nello stesso tempo (0,38s). Sono confuso da questi risultati. Qualcuno può spiegarmi perché questo sta accadendo?

Grazie!

Answer 1

Per il modello, l'indice viene eseguito con l'operatore []. Con l'ottimizzazione disattivata, questo verrà generalmente generato come una vera chiamata di funzione, aggiungendo un sacco di overhead a qualcosa di semplice come l'iscrizione in un array. Quando attivi l'ottimizzazione, viene generato in linea, rimuovendo l'overhead.

Answer 2

In modalità di debug, le implementazioni di std::vector forniscono un sacco di controllo di runtime per facilità d'uso. Questo controllo non è disponibile per gli array nativi. Ad esempio, in VC2008, se si compila l'esempio vector in modalità di debug, ci sarà range-checkingpari a nel caso di operator[].

Answer 3

Se l'implementazione vettoriale non ottimizzata sta eseguendo il controllo dei limiti, ciò spiegherebbe la discrepanza.

Answer 4

perché quando si scrive vettore arr (10000); crei un oggetto, chiami le sue funzioni ... quando e sarà più lento di quando crei int arr [10000];

Answer 5

Negli esempi, la matrice è in pila. L'accesso ai dati nell'array comporta l'accesso ai dati nello stack. È veloce

D'altra parte, mentre lo vector è in pila, i dati per uno std::vector vengono allocati da qualche altra parte (per impostazione predefinita è allocato nello heap tramite std::allocator). L'accesso ai dati nello vector implica l'accesso ai dati nell'heap. È molto più lento dell'accesso ai dati nello stack.

Si ottiene qualcosa per la penalizzazione delle prestazioni, però. std::vector è coltivabile, mentre un array normale non lo è. Inoltre, la dimensione di un std::vector non deve essere costante di tempo di compilazione, mentre la dimensione di un array nello stack. Una matrice allocata su heap (tramite operator new[]) non deve essere una costante in fase di compilazione. Se confronti un array assegnato all'heap con un std::vector, troverai che le prestazioni sono molto più vicine.

int* arr = new int[10000]; 
for (int i = 0; i < 10000; i++) 
{ 
    for (int j = 0; j < 10000; j++) 
    { 
     arr[j] = j; 
    } 
} 

delete[] arr; // std::vector does this for you 

Answer 6

Queste sono buone risposte, ma c'è un modo rapido per scoprirlo da soli.

Stai vedendo una differenza di prestazioni 6 a 1, giusto? Basta eseguire quello lento e premere il pulsante "pausa". Quindi guarda lo stack delle chiamate. La probabilità è 5 su 6 (83%) che vedrai esattamente come si spendono quei 25 secondi in più. Fatelo diverse volte per ottenere tutte le informazioni che desiderate.

Per il caso ottimizzato, fare lo stesso con il programma 1. Poiché è 13 volte più lento del programma ottimizzato, vedrete il motivo per cui su ogni "pausa", con probabilità 12/13 = 92%.

Questa è un'applicazione di this technique.