C++ Vector vs Array (Time)

Question

Ho qui due programmi con me, entrambi stanno facendo esattamente lo stesso compito. Stanno semplicemente impostando un array/vettore booleano sul valore true. Il programma che utilizza il vettore impiega 27 secondi per essere eseguito mentre il programma che include una matrice con una dimensione 5 volte maggiore richiede meno di 1 s. Mi piacerebbe conoscere la ragione esatta del perché c'è una differenza così grande? I vettori sono davvero inefficienti?

programma utilizzando vettori

#include <iostream> 
#include <vector> 
#include <ctime> 

using namespace std; 

int main(){ 
const int size = 2000; 
time_t start, end; 
time(&start); 
vector<bool> v(size); 
for(int i = 0; i < size; i++){ 
    for(int j = 0; j < size; j++){ 
    v[i] = true; 
    } 
} 
time(&end); 
cout<<difftime(end, start)<<" seconds."<<endl; 
} 

Runtime - 27 secondi

Programma utilizzando Array

#include <iostream> 
#include <ctime> 

using namespace std; 

int main(){ 
const int size = 10000; // 5 times more size 
time_t start, end; 
time(&start); 
bool v[size]; 
for(int i = 0; i < size; i++){ 
    for(int j = 0; j < size; j++){ 
    v[i] = true; 
    } 
} 
time(&end); 
cout<<difftime(end, start)<<" seconds."<<endl; 
} 

Runtime - < 1 secondo

piattaforma - Visual Studio 2008 OS - Windows Vista 32 bit SP 1 processore Intel (R) Pentium (R) dual T2370 CPU @ 1.73GHz Memoria (RAM) 1.00 GB

Grazie

Amare

Answer 1

Stai usando std :: vector di bool e non è quello che pensi che sia!

vettore di bool è una specializzazione di modello bastardo bambino che non dovrebbe mai esistere e in realtà memorizza 1 bool in ogni bit. Gli accessi in esso sono più complicati a causa del mascheramento e della logica di spostamento, quindi sarà sicuramente un po 'più lento.

Click here for some info on vector of bool.

Inoltre, è possibile eseguire una build non ottimizzata (quasi certamente visti i tempi che hai elencato, 27 secondi è scandaloso per 4 milioni di iterazioni). La libreria di modelli standard si affida molto all'ottimizzatore per fare cose come chiamate di funzioni in linea ed elide temporaries. La mancanza di questa ottimizzazione causa un degrado delle prestazioni particolarmente pesante per il vettore di bool perché deve restituire un oggetto proxy quando ci si indicizza, perché non si può prendere l'indirizzo di un bit, quindi l'operatore non può restituire un riferimento.

Click here for more info on proxied containers (L'ultima metà è di circa vettore di bool)

Inoltre molte implementazioni STL hanno utile bit di debug che non fanno parte dello standard, che aiuterà a catturare gli insetti, ma in realtà trascinano verso il basso le prestazioni. Dovrai assicurarti che siano disabilitati nella tua build ottimizzata.

Una volta che si accende l'ottimizzatore, si hanno le impostazioni corrette (cioè non si attiva il debug STL) e si sta verificando la stessa cosa in entrambi i cicli, non vedrai quasi nessuna differenza.

ho dovuto fare il loop molto più grande di provare sulla mia macchina, ma ecco due build del vostro vettore di ciclo bool sulla mia macchina, che mostra l'impatto delle bandiere ottimizzatore sul codice STL

$ g++ main.cpp 
$ ./a.out 
17 seconds. 
$ g++ -O2 main.cpp 
$ ./a.out 
1 seconds. 

Answer 2

Avere un guarda a questo

Using arrays or std::vectors in C++, what’s the performance gap?

Answer 3

altre risposte sono molto buoni, ma si potrebbe facilmente rispondere voi stessi this method.

AGGIUNTO: In risposta ai commenti, lascia che ti mostri cosa intendo. Sto eseguendo VC su Windows, ma funziona su qualsiasi lingua/sistema operativo. Ho preso il tuo primo programma e ho aumentato le dimensioni a 20000, quindi funzionava abbastanza a lungo. Poi mentre era in esecuzione, ho preso diversi stackshots. Sembrano tutti in questo modo:

std::vector<bool,std::allocator<bool> >::begin() line 93 + 25 bytes 
std::vector<bool,std::allocator<bool> >::operator[]() line 132 + 37 bytes 
main() line 24 + 12 bytes 
mainCRTStartup() line 206 + 25 bytes 
KERNEL32! 7c817077() 

Allora, cosa che dice è che si sta spendendo in sostanza tutto di esso è tempo nella operazione di indicizzazione sulla linea 24, e la ragione è la spesa che il tempo è che l'operatore [] è chiamando l'operatore begin. Più in dettaglio:

main() line 24 + 12 bytes 

è questo codice:

for(int j = 0; j < size; j++){ 
==> v[i] = true; 
} 

che chiama:

std::vector<bool,std::allocator<bool> >::operator[]() line 132 + 37 bytes 

che è questo codice (che ho riformattato un po '):

reference operator[](size_type _P){ 
==> return (*(begin() + _P)); 
} 

che chiama:

std::vector<bool,std::allocator<bool> >::begin() line 93 + 25 bytes 

che sta facendo questo (più in dettaglio):

92:  iterator begin() 
93:   {return (_First); } 
00402890 push  ebp 
00402891 mov   ebp,esp 
00402893 sub   esp,44h 
00402896 push  ebx 
00402897 push  esi 
00402898 push  edi 
00402899 push  ecx 
0040289A lea   edi,[ebp-44h] 
0040289D mov   ecx,11h 
004028A2 mov   eax,0CCCCCCCCh 
004028A7 rep stos dword ptr [edi] 
004028A9 pop   ecx <=============== 
004028AA mov   dword ptr [ebp-4],ecx 
004028AD mov   eax,dword ptr [ebp-4] 
004028B0 mov   eax,dword ptr [eax+4] 
004028B3 pop   edi 
004028B4 pop   esi 
004028B5 pop   ebx 
004028B6 mov   esp,ebp 
004028B8 pop   ebp 
004028B9 ret 

quello che sta facendo sta scrivendo 68 byte di 0xCC sullo stack (per qualche motivo debug) come parte di ottenere l'indirizzo begin di il vettore, come parte del calcolo dell'indirizzo di v[i], prima di eseguire l'assegnazione.

La frazione di tempo che impiega a fare questo è vicino al 100%, perché lo stava facendo su ognuno dei numerosi campioni che sono stati presi. Potresti aver intuito che è quello che stava passando quasi tutto il tempo a fare? Non potevo avere.

Questa è, naturalmente, una build di debug. Se passi a una versione di Release, ma accendi le informazioni di debug, tutte queste funzioni vengono allineate e ottimizzate, quindi è 30 volte più veloce, e ancora gli stackshots dicono esattamente cosa sta facendo.

Così - la gente può dire quello che si potrebbe fare, ma questo dimostra come scoprire per lei che cosa si tratta veramente fare.

Sul tuo ambiente sarà indubbiamente diverso.

Answer 4

std::vector<bool> è ottimizzato per il consumo di memoria anziché le prestazioni.

È possibile ingannarlo utilizzando std::vector<int>. Quindi non dovresti avere svantaggi in termini di prestazioni.