¿Por qué el vector (tamaño) es más lento que el nuevo []?

Question

I fue el benchmarking algunos algoritmos STL, y yo estaba sorprendido por el tiempo empleado por el código siguiente: (Medí el código g ++ compilado [sin optimizaciones] con el comando time)

#include <vector> 
struct vec2{ 
    int x, y; 
    vec2():x(0), y(0) {} 
}; 
int main(int argc, char* argv[]){ 
    const int size = 200000000; 
    std::vector<vec2> tab(size); //2.26s 
// vec2* tab = new vec2[size]; //1.29s 
// tab[0].x = 0; 
// delete[] tab; 
    return 0; 
} 

El tiempo empleado por una la inicialización del vector es 2.26s mientras que new (y delete) toma 1.29s. ¿Qué está haciendo el vector ctor que tomaría mucho más tiempo? new[] llama al constructor en cada elemento, al igual que el ctor vector, ¿verdad?

entonces compilado con -O3, que fue todo más rápido, pero todavía había una brecha entre los dos códigos. (Obtuve respectivamente 0,83 sy 0,75)

¿Alguna idea?

Answer 1

La velocidad dependerá de la aplicación, pero lo más probable razón para el vector que siendo más lento que el vector no puede default-construir sus elementos. Los elementos del vector siempre se copian. Por ejemplo

std::vector<vec2> tab(size); 

es en realidad interpretada como

std::vector<vec2> tab(size, vec2()); 

es decir, el segundo argumento toma su valor de argumento predeterminado. El vector luego asigna memoria bruta y copias este elemento construido por defecto pasado desde el exterior a cada elemento del nuevo vector (usando copy-constructor). En general, esto podría ser más lento que el predeterminado: construir cada elemento directamente (como lo hace new[]).

Para ilustrar la diferencia con un esbozo de código, new vec2[size] es más o menos equivalente a

vec2 *v = (vec2 *) malloc(size * sizeof(vec2)); 

for (size_t i = 0; i < size; ++i) 
    // Default-construct `v[i]` in place 
    new (&v[i]) vec2(); 

return v; 

mientras vector<vec2>(size) es más o menos equivalente a

vec2 source; // Default-constructed "original" element 

vec2 *v = (vec2 *) malloc(size * sizeof(vec2)); 

for (size_t i = 0; i < size; ++i) 
    // Copy-construct `v[i]` in place 
    new (&v[i]) vec2(source); 

return v; 

Dependiendo de la aplicación, el segundo enfoque podría resultar más lenta .

La diferencia de dos veces en la velocidad es difícil de justificar sin embargo, pero la evaluación comparativa de código no optimizado no tiene sentido tampoco. La diferencia mucho menos significativa que observó con el código optimizado es exactamente lo que uno podría esperar razonablemente en este caso.

Answer 2

Ambas versiones inicializan la memoria.

Como varias personas han señalado, el vector utiliza la construcción de copia mientras la matriz utiliza el constructor predeterminado. Su compilador parece optimizar el último mejor que el primero.

Tenga en cuenta que en la vida real, que rara vez se desea inicializar una enorme variedad tal de un solo golpe. (¿De qué sirven un montón de ceros Obviamente tiene la intención de poner algo más ahí ... Y, finalmente, la inicialización de cientos de megabytes de caché es muy hostil?.)

En cambio, podría escribir algo como:

const int size = 200000000; 
std::vector<vec2> v; 
v.reserve(size); 

Entonces, cuando usted está listo para poner un elemento real en el vector, se utiliza v.push_back(element).El reserve() asigna memoria sin inicializarla; las construcciones de copia push_back() en el espacio reservado.

Alternativamente, cuando quiere poner un nuevo elemento en el vector, puede usar v.resize(v.size()+1) y luego modificar el elemento v.back(). (Así es como podría funcionar un "asignador de grupo"). Aunque esta secuencia inicializará el elemento y luego lo sobreescribirá, todo sucederá en la caché L1, que es casi tan rápido como no inicializarlo en absoluto.

Para una comparación justa, pruebe con un vector grande (con reserve) frente a una matriz para crear una secuencia de elementos no idénticos. Deberías encontrar que el vector es más rápido.

Answer 3

después de analizar ensamblado generado por VC++ para estos dos casos, esto es lo que encontré. El compilador introdujo prácticamente todo y generó bucles muy similares para la inicialización después de la asignación de memoria. En caso de bucle interior vector se ve así:

013E3FC0 test  eax,eax 
013E3FC2 je   std::_Uninit_def_fill_n<vec2 *,unsigned int,vec2,std::allocator<vec2>,vec2>+19h (13E3FC9h) 
013E3FC4 mov   dword ptr [eax],edx 
013E3FC6 mov   dword ptr [eax+4],esi 
013E3FC9 add   eax,8 
013E3FCC dec   ecx 
013E3FCD jne   std::_Uninit_def_fill_n<vec2 *,unsigned int,vec2,std::allocator<vec2>,vec2>+10h (13E3FC0h) 

donde se zerroed edx y esi registros fuera del bucle:

00013FB5 xor   edx,edx 
00013FB7 xor   esi,esi 
00013FB9 lea   esp,[esp] 

En caso de new[] bucle interior se ve así:

009F1800 mov   dword ptr [ecx],0 
009F1806 mov   dword ptr [ecx+4],0 
009F180D add   ecx,8 
009F1810 dec   edx 
009F1811 jns   main+30h (9F1800h) 

Las diferencias son muy insignificantes, unos más instrucciones en caso de vector, pero probablemente también más rápido mov s de registros. Como en la mayoría de los casos de la vida real, los constructores hacen mucho más que asignar ceros, esta diferencia apenas se nota. Entonces el valor de esta prueba es cuestionable.