una - libreria vector c++

¿Es std:: vector mucho más lento que los arreglos simples?

Question

Siempre he pensado que es la sabiduría general que std::vector se "implementa como una matriz", bla bla bla. Hoy bajé y lo probé, y parece que no es así:

Aquí hay algunos resultados de la prueba:

UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds

Eso es aproximadamente 3 - 4 veces más lento! No justifica realmente el comentario "el vector puede ser más lento para unos pocos nanosegs".

Y el código que utilicé:

#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>
#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>
class TestTimer
{
public:
TestTimer(const std::string & name) : name(name),
start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
{
}
~TestTimer()
{
using namespace std;
using namespace boost;
posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
posix_time::time_duration d = now - start;
cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
" seconds" << endl;
}
private:
std::string name;
boost::posix_time::ptime start;
};
struct Pixel
{
Pixel()
{
}
Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
{
}
unsigned char r, g, b;
};
void UseVector()
{
TestTimer t("UseVector");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels;
pixels.resize(dimension * dimension);
for(int i = 0; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
}
}
void UseVectorPushBack()
{
TestTimer t("UseVectorPushBack");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels;
pixels.reserve(dimension * dimension);
for(int i = 0; i < dimension * dimension; ++i)
pixels.push_back(Pixel(255, 0, 0));
}
}
void UseArray()
{
TestTimer t("UseArray");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);
for(int i = 0 ; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
free(pixels);
}
}
int main()
{
TestTimer t1("The whole thing");
UseArray();
UseVector();
UseVectorPushBack();
return 0;
}

¿Lo estoy haciendo mal o algo así? ¿O acabo de romper este mito del rendimiento?

Estoy usando el modo Release en Visual Studio 2005 .

En Visual C ++ , #define _SECURE_SCL 0 reduce UseVector a la mitad (reduciéndolo a 4 segundos). Esto es realmente enorme, OMI.

Answer 1

Así es como funciona el método push_back en vector:

1. El vector asigna X cantidad de espacio cuando se inicializa.
2. Como se indica a continuación, verifica si hay espacio en la matriz subyacente actual para el elemento.
3. Hace una copia del artículo en la llamada push_back.

Después de llamar a push_backX elementos:

3. El vector reasigna la cantidad de espacio kX en una segunda matriz.
4. Copia las entradas de la primera matriz en la segunda.
5. Descarta la primera matriz.
6. Ahora usa la segunda matriz como almacenamiento hasta que alcanza las entradas de kX.

Repetir.Si no estás en el reservingespacio, definitivamente va a ser más lento. Más que eso, si es caro copiar el elemento, entonces ''push_back'' así te va a comer vivo.

En cuanto a lo de la vectormatriz, voy a tener que estar de acuerdo con las otras personas. Ejecute el lanzamiento, active las optimizaciones y coloque unas cuantas marcas más para que las personas amigables de Microsoft no lo hagan por usted @ @% $ ^.

Una cosa más, si no necesita cambiar el tamaño, use Boost.Array.

Answer 2

El STL de GNU (y otros), dado el vector<T>(n) , crea un objeto prototípico T() , el compilador optimizará el constructor vacío, pero luego una copia de cualquier basura que se encuentre en las direcciones de memoria ahora reservadas para el objeto es tomado por __uninitialized_fill_n_aux la STL, que recorre las copias de ese objeto como valores predeterminados en el vector. Por lo tanto, "mi" STL no está construyendo en bucle, sino construyendo luego en bucle / copiando. Es contrario a la intuición, pero debería haber recordado como comenté en una pregunta reciente sobre el flujo de apilamiento sobre este punto: la construcción / copia puede ser más eficiente para los objetos contados de referencia, etc.

Asi que:

vector<T> x(n);

o

vector<T> x;
x.resize(n);

es - en muchas implementaciones de STL - algo como:

T temp;
for (int i = 0; i < n; ++i)
x[i] = temp;

El problema es que la generación actual de optimizadores del compilador no parece funcionar a partir de la idea de que la temperatura es basura no inicializada, y no logran optimizar las invocaciones del constructor de copia por defecto y bucle. Usted podría argumentar de manera creíble que los compiladores no deberían optimizar esto, ya que un programador que escribe lo anterior tiene una expectativa razonable de que todos los objetos serán idénticos después del bucle, incluso si hay basura (advertencias habituales sobre ''idéntico'' / operator == vs memcmp / operator = etc se aplican). No se puede esperar que el compilador tenga una visión adicional del contexto más amplio de std :: vector <> o el uso posterior de los datos que sugieran esta optimización segura.

Esto se puede contrastar con la implementación directa más obvia:

for (int i = 0; i < n; ++i)
x[i] = T();

Lo que podemos esperar es que un compilador se optimice.

Para ser un poco más explícito sobre la justificación de este aspecto del comportamiento del vector, considere:

std::vector<big_reference_counted_object> x(10000);

Claramente, es una gran diferencia si hacemos 10000 objetos independientes frente a 10000 que hacen referencia a los mismos datos. Existe un argumento razonable de que la ventaja de proteger a los usuarios casuales de C ++ de hacer algo tan caro accidentalmente supera el muy pequeño costo en el mundo real de la construcción de copias difíciles de optimizar.

RESPUESTA ORIGINAL (para referencia / dar sentido a los comentarios): No hay posibilidad. El vector es tan rápido como una matriz, al menos si reserva el espacio con sensatez. ...

Answer 3

Esta es una pregunta vieja pero popular.

En este punto, muchos programadores trabajarán en C ++ 11. Y en C ++ 11, el código del OP como escrito se ejecuta igualmente rápido para UseArray o UseVector .

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

El problema fundamental fue que, si bien su estructura de Pixel no estaba inicializada, std::vector<T>::resize( size_t, T const&=T() ) toma un Pixel construido por defecto y lo copia . El compilador no se dio cuenta de que se le pedía que copiara los datos sin inicializar, por lo que en realidad realizó la copia.

En C ++ 11, std::vector<T>::resize tiene dos sobrecargas. El primero es std::vector<T>::resize(size_t) , el otro es std::vector<T>::resize(size_t, T const&) . Esto significa que cuando invoca el cambio de resize sin un segundo argumento, simplemente construye de manera predeterminada, y el compilador es lo suficientemente inteligente como para darse cuenta de que la construcción predeterminada no hace nada, por lo que omite la transferencia sobre el búfer.

(Las dos sobrecargas se agregaron para manejar tipos móviles, construibles y no copiables; la mejora del rendimiento cuando se trabaja con datos no inicializados es una ventaja).

La solución push_back también realiza la comprobación del poste, lo que la ralentiza, por lo que sigue siendo más lento que la versión malloc .

Ejemplo en vivo (también reemplacé el temporizador con chrono::high_resolution_clock ).

Tenga en cuenta que si tiene una estructura que normalmente requiere inicialización, pero desea manejarlo después de aumentar su búfer, puede hacerlo con un asignador std::vector . Si desea luego moverlo a un std::vector más normal, creo que el uso cuidadoso de allocator_traits y la anulación de == podrían lograrlo, pero no estoy seguro.

Answer 4

Gran pregunta Vine aquí esperando encontrar alguna solución simple que acelerara las pruebas de vectores. ¡Eso no funcionó como yo esperaba!

La optimización ayuda, pero no es suficiente. Con la optimización activada, sigo viendo una diferencia de rendimiento de 2X entre UseArray y UseVector. Curiosamente, UseVector fue significativamente más lento que UseVectorPushBack sin optimización.

# g++ -Wall -Wextra -pedantic -o vector vector.cpp
# ./vector
UseArray completed in 20.68 seconds
UseVector completed in 120.509 seconds
UseVectorPushBack completed in 37.654 seconds
The whole thing completed in 178.845 seconds
# g++ -Wall -Wextra -pedantic -O3 -o vector vector.cpp
# ./vector
UseArray completed in 3.09 seconds
UseVector completed in 6.09 seconds
UseVectorPushBack completed in 9.847 seconds
The whole thing completed in 19.028 seconds

Idea # 1 - Usar nuevo [] en lugar de malloc

Intenté cambiar malloc() a new[] en UseArray para que los objetos se construyeran. Y cambiar de asignación de campo individual a asignar una instancia de Pixel. Ah, y cambiar el nombre de la variable de bucle interno a j .

void UseArray()
{
TestTimer t("UseArray");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
// Same speed as malloc().
Pixel * pixels = new Pixel[dimension * dimension];
for(int j = 0 ; j < dimension * dimension; ++j)
pixels[j] = Pixel(255, 0, 0);
delete[] pixels;
}
}

Sorprendentemente (para mí), ninguno de esos cambios hizo ninguna diferencia en absoluto. Ni siquiera el cambio a new[] que construirá por defecto todos los píxeles. Parece que gcc puede optimizar las llamadas de constructor predeterminadas cuando usa el new[] , pero no cuando usa vector .

Idea # 2 - Eliminar llamadas repetidas del operador []

También intenté deshacerme de la búsqueda del operator[] triple operator[] y guardar en caché la referencia a los pixels[j] . Eso en realidad ralentizó a UseVector! Ups.

for(int j = 0; j < dimension * dimension; ++j)
{
// Slower than accessing pixels[j] three times.
Pixel &pixel = pixels[j];
pixel.r = 255;
pixel.g = 0;
pixel.b = 0;
}
# ./vector
UseArray completed in 3.226 seconds
UseVector completed in 7.54 seconds
UseVectorPushBack completed in 9.859 seconds
The whole thing completed in 20.626 seconds

Idea # 3 - Eliminar constructores

¿Qué pasa con la eliminación de los constructores por completo? Entonces, tal vez gcc puede optimizar la construcción de todos los objetos cuando se crean los vectores. ¿Qué pasa si cambiamos Pixel a:

struct Pixel
{
unsigned char r, g, b;
};

Resultado: alrededor del 10% más rápido. Aún más lento que una matriz. Hm

# ./vector
UseArray completed in 3.239 seconds
UseVector completed in 5.567 seconds

Idea # 4 - Usar iterador en lugar de índice de bucle

¿Qué hay de usar un vector<Pixel>::iterator lugar de un índice de bucle?

for (std::vector<Pixel>::iterator j = pixels.begin(); j != pixels.end(); ++j)
{
j->r = 255;
j->g = 0;
j->b = 0;
}

Resultado:

# ./vector
UseArray completed in 3.264 seconds
UseVector completed in 5.443 seconds

No, no es diferente. Al menos no es más lento. Pensé que esto tendría un rendimiento similar al # 2 donde utilicé un Pixel& referencia.

Conclusión

Incluso si alguna cookie inteligente descubre cómo hacer que el bucle vectorial sea tan rápido como el de la matriz, esto no habla bien del comportamiento predeterminado de std::vector . Tanto para que el compilador sea lo suficientemente inteligente como para optimizar todo el C ++ ness y hacer contenedores STL tan rápido como matrices en bruto.

La conclusión es que el compilador no puede optimizar las llamadas del constructor predeterminado sin operación cuando usa std::vector . Si usas el new[] , los optimiza muy bien. Pero no con std::vector . Incluso si puedes reescribir tu código para eliminar las llamadas de constructor que se encuentran frente al mantra por aquí: "El compilador es más inteligente que tú. El STL es tan rápido como el simple C. No te preocupes por eso".

Answer 5

Intenta con esto:

void UseVectorCtor()
{
TestTimer t("UseConstructor");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
}
}

Tengo casi exactamente el mismo rendimiento que con la matriz.

Lo que pasa con el vector es que es una herramienta mucho más general que una matriz. Y eso significa que tienes que considerar cómo lo usas. Se puede usar de muchas maneras diferentes, proporcionando una funcionalidad que una matriz ni siquiera tiene. Y si lo usa "mal" para su propósito, incurre en una gran cantidad de gastos generales, pero si lo usa correctamente, generalmente es una estructura de datos de cero gastos generales. En este caso, el problema es que inicializó el vector por separado (lo que provocó que todos los elementos tuvieran su ctor predeterminado) y luego sobrescribiera cada elemento individualmente con el valor correcto. Eso es mucho más difícil para el compilador de optimizar que cuando haces lo mismo con una matriz. Es por eso que el vector proporciona un constructor que le permite hacer exactamente eso: inicialice N elementos con el valor X

Y cuando lo usas, el vector es tan rápido como una matriz.

Así que no, no has roto el mito del rendimiento. Pero ha demostrado que solo es cierto si usa el vector de manera óptima, lo que también es un buen punto. :)

En el lado positivo, es realmente el uso más simple que resulta ser el más rápido. Si comparas mi fragmento de código (una sola línea) con la respuesta de John Kugelman, que contiene montones y montones de ajustes y optimizaciones, que aún no eliminan la diferencia de rendimiento, está bastante claro que el vector está diseñado con mucha inteligencia después de todo. No tienes que saltar a través de aros para obtener una velocidad igual a una matriz. Por el contrario, tienes que usar la solución más simple posible.

Answer 6

Intenta deshabilitar los iteradores marcados y construir en modo de lanzamiento. No deberías ver mucha diferencia de rendimiento.

Answer 7

Los vectores también están llamando a los constructores de píxeles.

Cada uno está causando casi un millón de carreras de ctor que estás sincronizando.

Edición: luego está el bucle externo 1 ... 1000, ¡así que haz un billón de llamadas a ctor!

edición 2: sería interesante ver el desmontaje del caso UseArray. Un optimizador podría optimizar todo el proceso, ya que no tiene más efecto que la grabación de la CPU.

Answer 8

No fue una comparación justa cuando miré por primera vez su código; Definitivamente pensé que no estabas comparando manzanas con manzanas. Así que pensé, llamemos a los constructores y destructores en todas las pruebas; y luego comparar.

const size_t dimension = 1000;
void UseArray() {
TestTimer t("UseArray");
for(size_t j = 0; j < dimension; ++j) {
Pixel* pixels = new Pixel[dimension * dimension];
for(size_t i = 0 ; i < dimension * dimension; ++i) {
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = (unsigned char) (i % 255);
}
delete[] pixels;
}
}
void UseVector() {
TestTimer t("UseVector");
for(size_t j = 0; j < dimension; ++j) {
std::vector<Pixel> pixels(dimension * dimension);
for(size_t i = 0; i < dimension * dimension; ++i) {
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = (unsigned char) (i % 255);
}
}
}
int main() {
TestTimer t1("The whole thing");
UseArray();
UseVector();
return 0;
}

Mis pensamientos eran, que con esta configuración, deberían ser exactamente iguales. Resulta que estaba equivocado.

UseArray completed in 3.06 seconds
UseVector completed in 4.087 seconds
The whole thing completed in 10.14 seconds

Entonces, ¿por qué ocurrió esta pérdida de rendimiento del 30%? El STL tiene todo en los encabezados, por lo que debería haber sido posible para el compilador comprender todo lo que se requería.

Mi opinión fue que está en la forma en que el bucle inicializa todos los valores al constructor predeterminado. Así que realicé una prueba:

class Tester {
public:
static int count;
static int count2;
Tester() { count++; }
Tester(const Tester&) { count2++; }
};
int Tester::count = 0;
int Tester::count2 = 0;
int main() {
std::vector<Tester> myvec(300);
printf("Default Constructed: %i/nCopy Constructed: %i/n", Tester::count, Tester::count2);
return 0;
}

Los resultados fueron como sospechaba:

Default Constructed: 1
Copy Constructed: 300

Esta es claramente la fuente de la desaceleración, el hecho de que el vector utiliza el constructor de copia para inicializar los elementos de un objeto construido predeterminado.

Esto significa que el siguiente orden de pseudo operación está ocurriendo durante la construcción del vector:

Pixel pixel;
for (auto i = 0; i < N; ++i) vector[i] = pixel;

El cual, debido al constructor de copia implícito hecho por el compilador, se expande a lo siguiente:

Pixel pixel;
for (auto i = 0; i < N; ++i) {
vector[i].r = pixel.r;
vector[i].g = pixel.g;
vector[i].b = pixel.b;
}

Por lo tanto, el Pixel predeterminado permanece sin inicializar, mientras que el resto se inicializa con los valores no inicializados del Pixel predeterminado.

Comparado con la situación alternativa con New[] / Delete[] :

int main() {
Tester* myvec = new Tester[300];
printf("Default Constructed: %i/nCopy Constructed:%i/n", Tester::count, Tester::count2);
delete[] myvec;
return 0;
}
Default Constructed: 300
Copy Constructed: 0

Todos se dejan a sus valores no inicializados, y sin la doble iteración sobre la secuencia.

Armados con esta información, ¿cómo podemos probarlo? Intentemos sobrescribir el constructor de copia implícita.

Pixel(const Pixel&) {}

¿Y los resultados?

UseArray completed in 2.617 seconds
UseVector completed in 2.682 seconds
The whole thing completed in 5.301 seconds

Entonces, en resumen, si estás haciendo cientos de vectores muy a menudo: replantea tu algoritmo .

En cualquier caso, la implementación de STL no es más lenta por alguna razón desconocida, simplemente hace exactamente lo que pides; esperando que sepas mejor

Answer 9

Para ser justos, no puedes comparar una implementación de C ++ con una implementación de C, como llamaría tu versión de malloc. malloc no crea objetos, solo asigna memoria en bruto. El hecho de que usted trate esa memoria como objetos sin llamar al constructor es pobre en C ++ (posiblemente no válido; se lo dejaré a los abogados de idiomas).

Dicho esto, simplemente cambiando el malloc a un new Pixel[dimensions*dimensions] y liberarlo para delete [] pixels no hace mucha diferencia con la implementación simple de Pixel que tiene. Aquí están los resultados en mi caja (E6600, 64 bits):

UseArray completed in 0.269 seconds
UseVector completed in 1.665 seconds
UseVectorPushBack completed in 7.309 seconds
The whole thing completed in 9.244 seconds

Pero con un ligero cambio, las mesas giran:

Pixel.h

struct Pixel
{
Pixel();
Pixel(unsigned char r, unsigned char g, unsigned char b);
unsigned char r, g, b;
};

Pixel.cc

#include "Pixel.h"
Pixel::Pixel() {}
Pixel::Pixel(unsigned char r, unsigned char g, unsigned char b)
: r(r), g(g), b(b) {}

main.cc

#include "Pixel.h"
[rest of test harness without class Pixel]
[UseArray now uses new/delete not malloc/free]

Compilado de esta manera:

$ g++ -O3 -c -o Pixel.o Pixel.cc
$ g++ -O3 -c -o main.o main.cc
$ g++ -o main main.o Pixel.o

obtenemos resultados muy diferentes:

UseArray completed in 2.78 seconds
UseVector completed in 1.651 seconds
UseVectorPushBack completed in 7.826 seconds
The whole thing completed in 12.258 seconds

Con un constructor no en línea para Pixel, std :: vector ahora supera una matriz en bruto.

Parecería que la complejidad de la asignación a través de std :: vector y std: allocator es demasiado para ser optimizada tan efectivamente como un simple new Pixel[n] . Sin embargo, podemos ver que el problema es simplemente con la asignación y no con el acceso al vector mediante el ajuste de un par de funciones de prueba para crear el vector / matriz una vez moviéndolo fuera del bucle:

void UseVector()
{
TestTimer t("UseVector");
int dimension = 999;
std::vector<Pixel> pixels;
pixels.resize(dimension * dimension);
for(int i = 0; i < 1000; ++i)
{
for(int i = 0; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
}
}

y

void UseArray()
{
TestTimer t("UseArray");
int dimension = 999;
Pixel * pixels = new Pixel[dimension * dimension];
for(int i = 0; i < 1000; ++i)
{
for(int i = 0 ; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
}
delete [] pixels;
}

Obtenemos estos resultados ahora:

UseArray completed in 0.254 seconds
UseVector completed in 0.249 seconds
UseVectorPushBack completed in 7.298 seconds
The whole thing completed in 7.802 seconds

Lo que podemos aprender de esto es que std :: vector es comparable a una matriz sin procesar para el acceso, pero si necesita crear y eliminar el vector / matriz muchas veces, crear un objeto complejo consumirá más tiempo que crear una matriz simple cuando el constructor del elemento no está en línea. No creo que esto sea muy sorprendente.

Answer 10

Usando lo siguiente:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray completado en 2.196 segundos
UseVector completado en 4.412 segundos
UseVectorPushBack completado en 8.017 segundos
Todo ello completado en 14.626 segundos.

Así que la matriz es dos veces más rápida que un vector.

Pero después de mirar el código con más detalle, se espera esto; mientras recorres el vector dos veces y la matriz solo una vez. Nota: cuando resize() el vector, no solo está asignando la memoria, sino que también está ejecutando el vector y llamando al constructor en cada miembro.

Reorganizar el código ligeramente para que el vector solo inicialice cada objeto una vez:

 std::vector<Pixel> pixels(dimensions * dimensions, Pixel(255,0,0));

Ahora haciendo el mismo tiempo de nuevo:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector completado en 2.216 segundos

El vector ahora tiene un rendimiento ligeramente peor que el array. En mi opinión, esta diferencia es insignificante y podría ser causada por un montón de cosas que no están asociadas con la prueba.

También tomaría en cuenta que no está UseArrray() / destruyendo correctamente el objeto Pixel en el método UseArrray() , ya que no se llama a ningún constructor / destructor (esto puede no ser un problema para esta clase simple, pero es algo más complejo (es decir, con punteros o miembros con punteros) causarán problemas.

Answer 11

La respuesta de Martin York me molesta porque parece un intento de solucionar el problema de la inicialización debajo de la alfombra. Pero tiene razón al identificar la construcción predeterminada redundante como la fuente de problemas de rendimiento.

[EDITAR: la respuesta de Martin ya no sugiere cambiar el constructor predeterminado.]

Para el problema inmediato en cuestión, ciertamente podría llamar a la versión de 2 parámetros del vector<Pixel> ctor en su lugar:

std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));

Eso funciona si desea inicializar con un valor constante, que es un caso común. Pero el problema más general es: ¿Cómo se puede inicializar de manera eficiente con algo más complicado que un valor constante?

Para esto puede usar un back_insert_iterator , que es un adaptador de iterador. Aquí hay un ejemplo con un vector de int s, aunque la idea general funciona igual de bien para Pixel s:

#include <iterator>
// Simple functor return a list of squares: 1, 4, 9, 16...
struct squares {
squares() { i = 0; }
int operator()() const { ++i; return i * i; }
private:
int i;
};
...
std::vector<int> v;
v.reserve(someSize); // To make insertions efficient
std::generate_n(std::back_inserter(v), someSize, squares());

Alternativamente, puede usar copy() o transform() lugar de generate_n() .

El inconveniente es que la lógica para construir los valores iniciales debe moverse a una clase separada, lo cual es menos conveniente que tenerlos en su lugar (aunque las lambdas en C ++ 1x lo hacen mucho más agradable). También espero que esto todavía no sea tan rápido como una versión no STL basada en malloc() , pero espero que esté cerca, ya que solo hace una construcción para cada elemento.

Answer 12

Algunos datos del generador de perfiles (el píxel está alineado a 32 bits):

g++ -msse3 -O3 -ftree-vectorize -g test.cpp -DNDEBUG && ./a.out
UseVector completed in 3.123 seconds
UseArray completed in 1.847 seconds
UseVectorPushBack completed in 9.186 seconds
The whole thing completed in 14.159 seconds

Paja

andrey@nv:~$ opannotate --source libcchem/src/a.out | grep "Total samples for file" -A3
Overflow stats not available
* Total samples for file : "/usr/include/c++/4.4/ext/new_allocator.h"
*
* 141008 52.5367
*/
--
* Total samples for file : "/home/andrey/libcchem/src/test.cpp"
*
* 61556 22.9345
*/
--
* Total samples for file : "/usr/include/c++/4.4/bits/stl_vector.h"
*
* 41956 15.6320
*/
--
* Total samples for file : "/usr/include/c++/4.4/bits/stl_uninitialized.h"
*
* 20956 7.8078
*/
--
* Total samples for file : "/usr/include/c++/4.4/bits/stl_construct.h"
*
* 2923 1.0891
*/

En allocator:

 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
: // 402. wrong new expression in [some_] allocator::construct
: void
: construct(pointer __p, const _Tp& __val)
141008 52.5367 : { ::new((void *)__p) _Tp(__val); }

vector :

 :void UseVector()
:{ /* UseVector() total: 60121 22.3999 */
...
:
:
10790 4.0201 : for (int i = 0; i < dimension * dimension; ++i) {
:
495 0.1844 : pixels[i].r = 255;
:
12618 4.7012 : pixels[i].g = 0;
:
2253 0.8394 : pixels[i].b = 0;
:
: }

formación

 :void UseArray()
:{ /* UseArray() total: 35191 13.1114 */
:
...
:
136 0.0507 : for (int i = 0; i < dimension * dimension; ++i) {
:
9897 3.6874 : pixels[i].r = 255;
:
3511 1.3081 : pixels[i].g = 0;
:
21647 8.0652 : pixels[i].b = 0;

La mayor parte de la sobrecarga está en el constructor de copia. Por ejemplo,

 std::vector < Pixel > pixels;//(dimension * dimension, Pixel());
pixels.reserve(dimension * dimension);
for (int i = 0; i < dimension * dimension; ++i) {
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}

Tiene el mismo rendimiento que una matriz.

Answer 13

Bueno, porque vector :: resize () hace mucho más procesamiento que la asignación de memoria simple (por malloc).

Intente colocar un punto de interrupción en el constructor de copia (defínalo para que pueda hacerlo) y ahorra el tiempo de procesamiento adicional.

Answer 14

Mi laptop es Lenova G770 (4 GB RAM).

El sistema operativo es Windows 7 de 64 bits (el que tiene una computadora portátil)

El compilador es MinGW 4.6.1.

El IDE es Code::Blocks .

Pruebo los códigos fuente del primer post.

Los resultados

Optimización de O2

UseArray completado en 2.841 segundos

UseVector completado en 2.548 segundos

UseVectorPushBack completado en 11.95 segundos

Todo ello completado en 17.342 segundos.

pausa del sistema

Optimización de O3

UseArray completado en 1.452 segundos

UseVector completado en 2.514 segundos

UseVectorPushBack completado en 12.967 segundos

Todo ello completado en 16.937 segundos.

Parece que el rendimiento del vector es peor en la optimización de O3.

Si cambia el bucle a

 pixels[i].r = i;
pixels[i].g = i;
pixels[i].b = i;

La velocidad de la matriz y el vector bajo O2 y O3 son casi iguales.

Answer 15

Un mejor punto de referencia (creo ...), el compilador debido a las optimizaciones puede cambiar el código, ya que los resultados de los vectores / arrays asignados no se usan en ninguna parte. Resultados:

$ g++ test.cpp -o test -O3 -march=native
$ ./test
UseArray inner completed in 0.652 seconds
UseArray completed in 0.773 seconds
UseVector inner completed in 0.638 seconds
UseVector completed in 0.757 seconds
UseVectorPushBack inner completed in 6.732 seconds
UseVectorPush completed in 6.856 seconds
The whole thing completed in 8.387 seconds

Compilador:

gcc version 6.2.0 20161019 (Debian 6.2.0-9)

UPC:

model name : Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz

Y el código:

#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>
#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>
class TestTimer
{
public:
TestTimer(const std::string & name) : name(name),
start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
{
}
~TestTimer()
{
using namespace std;
using namespace boost;
posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
posix_time::time_duration d = now - start;
cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
" seconds" << endl;
}
private:
std::string name;
boost::posix_time::ptime start;
};
struct Pixel
{
Pixel()
{
}
Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
{
}
unsigned char r, g, b;
};
void UseVector(std::vector<std::vector<Pixel> >& results)
{
TestTimer t("UseVector inner");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel>& pixels = results.at(i);
pixels.resize(dimension * dimension);
for(int i = 0; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
}
}
void UseVectorPushBack(std::vector<std::vector<Pixel> >& results)
{
TestTimer t("UseVectorPushBack inner");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel>& pixels = results.at(i);
pixels.reserve(dimension * dimension);
for(int i = 0; i < dimension * dimension; ++i)
pixels.push_back(Pixel(255, 0, 0));
}
}
void UseArray(Pixel** results)
{
TestTimer t("UseArray inner");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);
results[i] = pixels;
for(int i = 0 ; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
// free(pixels);
}
}
void UseArray()
{
TestTimer t("UseArray");
Pixel** array = (Pixel**)malloc(sizeof(Pixel*)* 1000);
UseArray(array);
for(int i=0;i<1000;++i)
free(array[i]);
free(array);
}
void UseVector()
{
TestTimer t("UseVector");
{
std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
UseVector(vector);
}
}
void UseVectorPushBack()
{
TestTimer t("UseVectorPush");
{
std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
UseVectorPushBack(vector);
}
}
int main()
{
TestTimer t1("The whole thing");
UseArray();
UseVector();
UseVectorPushBack();
return 0;
}

Answer 16

Con las opciones correctas, los vectores y las matrices pueden generar asm idénticos . En estos casos, son, por supuesto, la misma velocidad, ya que obtienes el mismo archivo ejecutable de cualquier manera.

Answer 17

Hice algunas pruebas extensivas que quería hacer por un tiempo ahora. También podría compartir esto.

Esta es mi máquina de arranque dual i7-3770, 16GB Ram, x86_64, en Windows 8.1 y en Ubuntu 16.04. Más información y conclusiones, comentarios a continuación. Probado tanto en MSVS 2017 como en g ++ (tanto en Windows como en Linux).

Programa de prueba

#include <iostream>
#include <chrono>
//#include <algorithm>
#include <array>
#include <locale>
#include <vector>
#include <queue>
#include <deque>
// Note: total size of array must not exceed 0x7fffffff B = 2,147,483,647B
// which means that largest int array size is 536,870,911
// Also image size cannot be larger than 80,000,000B
constexpr int long g_size = 100000;
int g_A[g_size];
int main()
{
std::locale loc("");
std::cout.imbue(loc);
constexpr int long size = 100000; // largest array stack size
// stack allocated c array
std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
int A[size];
for (int i = 0; i < size; i++)
A[i] = i;
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
std::cout << "c-style stack array duration=" << duration / 1000.0 << "ms/n";
std::cout << "c-style stack array size=" << sizeof(A) << "B/n/n";
// global stack c array
start = std::chrono::steady_clock::now();
for (int i = 0; i < g_size; i++)
g_A[i] = i;
duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
std::cout << "global c-style stack array duration=" << duration / 1000.0 << "ms/n";
std::cout << "global c-style stack array size=" << sizeof(g_A) << "B/n/n";
// raw c array heap array
start = std::chrono::steady_clock::now();
int* AA = new int[size]; // bad_alloc() if it goes higher than 1,000,000,000
for (int i = 0; i < size; i++)
AA[i] = i;
duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
std::cout << "c-style heap array duration=" << duration / 1000.0 << "ms/n";
std::cout << "c-style heap array size=" << sizeof(AA) << "B/n/n";
delete[] AA;
// std::array<>
start = std::chrono::steady_clock::now();
std::array<int, size> AAA;
for (int i = 0; i < size; i++)
AAA[i] = i;
//std::sort(AAA.begin(), AAA.end());
duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
std::cout << "std::array duration=" << duration / 1000.0 << "ms/n";
std::cout << "std::array size=" << sizeof(AAA) << "B/n/n";
// std::vector<>
start = std::chrono::steady_clock::now();
std::vector<int> v;
for (int i = 0; i < size; i++)
v.push_back(i);
//std::sort(v.begin(), v.end());
duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
std::cout << "std::vector duration=" << duration / 1000.0 << "ms/n";
std::cout << "std::vector size=" << v.size() * sizeof(v.back()) << "B/n/n";
// std::deque<>
start = std::chrono::steady_clock::now();
std::deque<int> dq;
for (int i = 0; i < size; i++)
dq.push_back(i);
//std::sort(dq.begin(), dq.end());
duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
std::cout << "std::deque duration=" << duration / 1000.0 << "ms/n";
std::cout << "std::deque size=" << dq.size() * sizeof(dq.back()) << "B/n/n";
// std::queue<>
start = std::chrono::steady_clock::now();
std::queue<int> q;
for (int i = 0; i < size; i++)
q.push(i);
duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
std::cout << "std::queue duration=" << duration / 1000.0 << "ms/n";
std::cout << "std::queue size=" << q.size() * sizeof(q.front()) << "B/n/n";
}

Resultados

//////////////////////////////////////////////////////////////////////////////////////////
// with MSVS 2017:
// >> cl /std:c++14 /Wall -O2 array_bench.cpp
//
// c-style stack array duration=0.15ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.130ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.90ms
// c-style heap array size=4B
//
// std::array duration=0.20ms
// std::array size=400,000B
//
// std::vector duration=0.544ms
// std::vector size=400,000B
//
// std::deque duration=1.375ms
// std::deque size=400,000B
//
// std::queue duration=1.491ms
// std::queue size=400,000B
//
//////////////////////////////////////////////////////////////////////////////////////////
//
// with g++ version:
// - (tdm64-1) 5.1.0 on Windows
// - (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609 on Ubuntu 16.04
// >> g++ -std=c++14 -Wall -march=native -O2 array_bench.cpp -o array_bench
//
// c-style stack array duration=0ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.124ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.648ms
// c-style heap array size=8B
//
// std::array duration=1ms
// std::array size=400,000B
//
// std::vector duration=0.402ms
// std::vector size=400,000B
//
// std::deque duration=0.234ms
// std::deque size=400,000B
//
// std::queue duration=0.304ms
// std::queue size=400,000
//
//////////////////////////////////////////////////////////////////////////////////////////

Notas

• Montado por un promedio de 10 carreras.
• Inicialmente realicé pruebas std::sort()también (puede verlo comentado) pero las eliminé más tarde porque no hubo diferencias relativas significativas.

Mis conclusiones y observaciones

• Observe cómo la matriz global de estilo C tarda casi tanto tiempo como la matriz de estilo C de montón
• De todas las pruebas noté una notable estabilidad en std::arraylas variaciones de tiempo entre corridas consecutivas, mientras que otras, especialmente las estructuras de datos estándar, variaron enormemente en comparación
• La optimización de O3 no mostró diferencias de tiempo notables
• La eliminación de la optimización en Windows cl (no -O2) y en g ++ (Win / Linux no -O2, no -march = native) aumenta los tiempos SIGNIFICATIVAMENTE. Particularmente para std :: data structs. En general, tiempos más altos en MSVS que g ++, pero los std::arrayarreglos de estilo C son más rápidos en Windows sin optimización
• g ++ produce código más rápido que el compilador de microsoft (aparentemente se ejecuta más rápido incluso en Windows).

Veredicto

Por supuesto, este es el código para una construcción optimizada. Y ya que la pregunta era sobre std::vectorentonces sí, ¡es mucho! Más lento que los arreglos simples (optimizado / no optimizado). Pero cuando estás haciendo un punto de referencia, naturalmente quieres producir un código optimizado.

La estrella del show para mi aunque ha sido std::array.

Answer 18

Por cierto, la ralentización de la visualización en clases con vector también se produce con tipos estándar como int. Heres un código multiproceso:

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <typeinfo>
#include <vector>
#include <pthread.h>
#include <sstream>
#include <fstream>
using namespace std;
//pthread_mutex_t map_mutex=PTHREAD_MUTEX_INITIALIZER;
long long num=500000000;
int procs=1;
struct iterate
{
int id;
int num;
void * member;
iterate(int a, int b, void *c) : id(a), num(b), member(c) {}
};
//fill out viterate and piterate
void * viterate(void * input)
{
printf("am in viterate/n");
iterate * info=static_cast<iterate *> (input);
// reproduce member type
vector<int> test= *static_cast<vector<int>*> (info->member);
for (int i=info->id; i<test.size(); i+=info->num)
{
//printf("am in viterate loop/n");
test[i];
}
pthread_exit(NULL);
}
void * piterate(void * input)
{
printf("am in piterate/n");
iterate * info=static_cast<iterate *> (input);;
int * test=static_cast<int *> (info->member);
for (int i=info->id; i<num; i+=info->num) {
//printf("am in piterate loop/n");
test[i];
}
pthread_exit(NULL);
}
int main()
{
cout<<"producing vector of size "<<num<<endl;
vector<int> vtest(num);
cout<<"produced a vector of size "<<vtest.size()<<endl;
pthread_t thread[procs];
iterate** it=new iterate*[procs];
int ans;
void *status;
cout<<"begining to thread through the vector/n";
for (int i=0; i<procs; i++) {
it[i]=new iterate(i, procs, (void *) &vtest);
// ans=pthread_create(&thread[i],NULL,viterate, (void *) it[i]);
}
for (int i=0; i<procs; i++) {
pthread_join(thread[i], &status);
}
cout<<"end of threading through the vector";
//reuse the iterate structures
cout<<"producing a pointer with size "<<num<<endl;
int * pint=new int[num];
cout<<"produced a pointer with size "<<num<<endl;
cout<<"begining to thread through the pointer/n";
for (int i=0; i<procs; i++) {
it[i]->member=&pint;
ans=pthread_create(&thread[i], NULL, piterate, (void*) it[i]);
}
for (int i=0; i<procs; i++) {
pthread_join(thread[i], &status);
}
cout<<"end of threading through the pointer/n";
//delete structure array for iterate
for (int i=0; i<procs; i++) {
delete it[i];
}
delete [] it;
//delete pointer
delete [] pint;
cout<<"end of the program"<<endl;
return 0;
}

El comportamiento del código muestra que la instanciación de vector es la parte más larga del código. Una vez que pasas por ese cuello de botella. El resto del código corre extremadamente rápido. Esto es cierto sin importar cuántos subprocesos esté ejecutando.

Por cierto ignorar el número absolutamente loco de los incluidos. He estado usando este código para probar cosas para un proyecto, por lo que el número de incluye sigue creciendo.

Answer 19

Solo quiero mencionar que vector (y smart_ptr) es solo un agregado de capa delgada sobre arreglos en bruto (y punteros en bruto). Y en realidad, el tiempo de acceso de un vector en la memoria continua es más rápido que la matriz. El siguiente código muestra el resultado de inicializar y acceder al vector y la matriz.

#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <vector>
#define SIZE 20000
int main() {
srand (time(NULL));
vector<vector<int>> vector2d;
vector2d.reserve(SIZE);
int index(0);
boost::posix_time::ptime start_total = boost::posix_time::microsec_clock::local_time();
// timer start - build + access
for (int i = 0; i < SIZE; i++) {
vector2d.push_back(vector<int>(SIZE));
}
boost::posix_time::ptime start_access = boost::posix_time::microsec_clock::local_time();
// timer start - access
for (int i = 0; i < SIZE; i++) {
index = rand()%SIZE;
for (int j = 0; j < SIZE; j++) {
vector2d[index][index]++;
}
}
boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time();
boost::posix_time::time_duration msdiff = end - start_total;
cout << "Vector total time: " << msdiff.total_milliseconds() << "milliseconds./n";
msdiff = end - start_acess;
cout << "Vector access time: " << msdiff.total_milliseconds() << "milliseconds./n";
int index(0);
int** raw2d = nullptr;
raw2d = new int*[SIZE];
start_total = boost::posix_time::microsec_clock::local_time();
// timer start - build + access
for (int i = 0; i < SIZE; i++) {
raw2d[i] = new int[SIZE];
}
start_access = boost::posix_time::microsec_clock::local_time();
// timer start - access
for (int i = 0; i < SIZE; i++) {
index = rand()%SIZE;
for (int j = 0; j < SIZE; j++) {
raw2d[index][index]++;
}
}
end = boost::posix_time::microsec_clock::local_time();
msdiff = end - start_total;
cout << "Array total time: " << msdiff.total_milliseconds() << "milliseconds./n";
msdiff = end - start_acess;
cout << "Array access time: " << msdiff.total_milliseconds() << "milliseconds./n";
for (int i = 0; i < SIZE; i++) {
delete [] raw2d[i];
}
return 0;
}

La salida es:

 Vector total time: 925milliseconds.
Vector access time: 4milliseconds.
Array total time: 30milliseconds.
Array access time: 21milliseconds.

Así que la velocidad será casi la misma si la usas correctamente. (como otros mencionaron usando reserve () o resize ()).

Answer 20

Tengo que decir que no soy un experto en C ++. Pero para agregar algunos resultados de experimentos:

compile: gcc-6.2.0 / bin / g ++ -O3 -std = c ++ 14 vector.cpp

máquina:

Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz 

OS:

2.6.32-642.13.1.el6.x86_64

Salida:

UseArray completed in 0.167821 seconds
UseVector completed in 0.134402 seconds
UseConstructor completed in 0.134806 seconds
UseFillConstructor completed in 1.00279 seconds
UseVectorPushBack completed in 6.6887 seconds
The whole thing completed in 8.12888 seconds

Aquí lo único que me parece extraño es que el rendimiento de "UseFillConstructor" en comparación con "UseConstructor".

El código:

void UseConstructor()
{
TestTimer t("UseConstructor");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels(dimension*dimension);
for(int i = 0; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
}
}
void UseFillConstructor()
{
TestTimer t("UseFillConstructor");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels(dimension*dimension, Pixel(255,0,0));
}
}

Así que el "valor" adicional proporcionado ralentiza bastante el rendimiento, lo que creo que se debe a la llamada múltiple para copiar el constructor. Pero...

Compilar:

gcc-6.2.0/bin/g++ -std=c++14 -O vector.cpp

Salida:

UseArray completed in 1.02464 seconds
UseVector completed in 1.31056 seconds
UseConstructor completed in 1.47413 seconds
UseFillConstructor completed in 1.01555 seconds
UseVectorPushBack completed in 6.9597 seconds
The whole thing completed in 11.7851 seconds

Entonces, en este caso, la optimización de gcc es muy importante, pero no puede ayudarlo mucho cuando se proporciona un valor por defecto. Esto, está en contra de mi matrícula en realidad. Esperemos que ayude a los nuevos programadores a elegir qué formato de inicialización vectorial.