C++ Vector vs Array (Time)

Question

Tengo aquí dos programas conmigo, ambos están haciendo exactamente la misma tarea. Solo están configurando una matriz/vector booleano para el valor verdadero. El programa que utiliza el vector tarda 27 segundos en ejecutarse, mientras que el programa que implica una matriz con un tamaño 5 veces mayor tarda menos de 1 s. Me gustaría saber la razón exacta de por qué hay una gran diferencia. ¿Son realmente ineficientes los vectores ?

programa usando vectores

#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 segundos

Programa utiliza matriz

#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 segundo

Plataforma - Visual Studio 2008 OS - Windows Vista 32 bit SP 1 procesador Intel (R) Pentium (R) Dual CPU T2370 @ 1.73GHz Memoria (RAM) 1,00 GB

Gracias

Amare

Answer 1

Estás usando std :: vector de bool y ¡eso no es lo que crees que es!

vector de bool es una especialización de plantilla de hijo bastardo que nunca debería haber existido y almacena 1 bool en cada bit. Los accesos a él son más complicados debido a la lógica de enmascaramiento y desplazamiento, por lo que definitivamente será algo más lento.

Click here for some info on vector of bool.

Además, puede que esté ejecutando una acumulación no optimizado (casi con toda seguridad dados los tiempos que enumeró, 27 segundos es exorbitante por 4 millones de iteraciones). La biblioteca de plantillas estándar depende en gran medida del optimizador para hacer cosas como llamadas a funciones en línea y temporales de elide. La falta de esta optimización provoca una degradación del rendimiento especialmente grande para el vector de bool porque tiene que devolver un objeto proxy cuando indexa en él, porque no puede tomar la dirección de un bit, por lo que el operador [] no puede devolver una referencia.

Click here for more info on proxied containers (La última media es aproximadamente de vectores de bool)

Además muchas implementaciones STL tienen bits de depuración de votos que no son parte de la norma que le ayudan a capturar errores, pero en realidad el rendimiento arrastran hacia abajo. Querrá asegurarse de que estén deshabilitados en su compilación optimizada.

Una vez que enciende el optimizador, tiene la configuración correcta (es decir, no hay depuración de STL activada), y en realidad está probando lo mismo en ambos bucles, casi no verá diferencia.

que tenía que hacer su lazo mucho más grande para probar en mi máquina, pero aquí es de dos compilaciones de su vector de bucle bool en mi máquina, que muestra el impacto de las banderas del optimizador de código AWL

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

Answer 2

Tener una mira a este

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

Answer 3

Otras respuestas son muy buenos, pero aquí se puede responder por sí mismo por this method.

AGREGADO: En respuesta a los comentarios, déjame mostrarte lo que quiero decir. Estoy ejecutando VC en Windows, pero esto funciona en cualquier idioma/sistema operativo. Tomé tu primer programa y aumenté el tamaño a 20000 para que funcione lo suficiente. Luego, mientras estaba funcionando, tomé varios Stackshots. Todos ellos se ven así:

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() 

Así que lo que dice es que se está gastando en esencia todo a su tiempo en la operación de indexación en la línea 24, y la razón se trata de pasar ese tiempo es que el operador [] es llamando al operador begin. En más detalle:

main() line 24 + 12 bytes 

es este código:

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

que llama:

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

que es el código (que formatear un poco):

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

que llama:

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

que está haciendo esto (con más detalle):

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 

Lo que está haciendo es escribir 68 bytes de 0xCC en la pila (por alguna razón depuración) como parte de conseguir la dirección begin de el vector, como parte de la computación de la dirección de v[i], antes de realizar la tarea.

La fracción de tiempo que pasa haciendo esto es cerca del 100%, porque lo estaba haciendo en cada una de las varias muestras que se tomaron. ¿Podrías haber adivinado que eso es lo que estaba pasando casi todo el tiempo haciendo? No podría haberlo hecho

Esto es, por supuesto, una compilación de depuración. Si cambia a una compilación de versión, pero activa la información de depuración, todas estas funciones se alinean y se optimizan, por lo que son 30 veces más rápidas, y una vez más los apilamientos dicen exactamente lo que está haciendo.

Por lo tanto - la gente se puede saber lo que podría estar haciendo, pero esto muestra cómo averiguar por sí mismo lo que es realmente haciendo.

En su entorno, sin duda será diferente.

Answer 4

std::vector<bool> está optimizado para el consumo de memoria en lugar del rendimiento.

Puede engañar utilizando std::vector<int>. No deberías tener inconvenientes de rendimiento entonces.