2008-09-18 21 views
34

Estoy escribiendo un bucle interno que necesita colocar struct s en el almacenamiento contiguo. No sé cuántos de estos struct s habrá antes de tiempo. Mi problema es que el vector de STL inicializa sus valores a 0, así que no importa lo que haga, incurro en el costo de la inicialización más el costo de establecer los miembros de struct en sus valores.vectores STL con almacenamiento no inicializado?

¿Hay alguna manera de evitar la inicialización, o hay un contenedor similar a STL con almacenamiento contiguo y elementos no inicializados redimensionables?

(estoy seguro de que esta parte del código debe ser optimizado, y estoy seguro de que la inicialización es un costo significativo.)

También, ver mis comentarios a continuación para una aclaración acerca de cuando el la inicialización ocurre.

algo de código:

void GetsCalledALot(int* data1, int* data2, int count) { 
    int mvSize = memberVector.size() 
    memberVector.resize(mvSize + count); // causes 0-initialization 

    for (int i = 0; i < count; ++i) { 
     memberVector[mvSize + i].d1 = data1[i]; 
     memberVector[mvSize + i].d2 = data2[i]; 
    } 
} 
+1

Nota - con ayuda de reserva() no es una solución, ya que no puede acceder legalmente los datos que están en ubicaciones finales() y por encima. –

+1

Otra aclaración: no es que el constructor inicialice los valores en 0. Es que el tamaño de las llamadas se inserta, lo que hace. –

+0

¿Podría darnos la declaración de estructura también? Gracias ... :-) – paercebal

Respuesta

23

std::vector debe inicializar los valores de la matriz de alguna manera, lo que significa algunos constructor (o constructor de copia) deben ser llamados. El comportamiento de vector (o cualquier clase de contenedor) no está definido si tuviera acceso a la sección no inicializada de la matriz como si se hubiera inicializado.

La mejor manera es usar reserve() y push_back(), para que se use el constructor de copias, evitando la construcción predeterminada.

Usando el código de ejemplo:

struct YourData { 
    int d1; 
    int d2; 
    YourData(int v1, int v2) : d1(v1), d2(v2) {} 
}; 

std::vector<YourData> memberVector; 

void GetsCalledALot(int* data1, int* data2, int count) { 
    int mvSize = memberVector.size(); 

    // Does not initialize the extra elements 
    memberVector.reserve(mvSize + count); 

    // Note: consider using std::generate_n or std::copy instead of this loop. 
    for (int i = 0; i < count; ++i) { 
     // Copy construct using a temporary. 
     memberVector.push_back(YourData(data1[i], data2[i])); 
    } 
} 

El único problema con llamar reserve() (o resize()) como esto es que usted puede terminar invocando el constructor de copia más a menudo de lo necesario. Si puede hacer una buena predicción sobre el tamaño final de la matriz, es mejor que reserve() el espacio una vez al principio. Sin embargo, si no conoce el tamaño final, al menos la cantidad de copias será mínima en promedio.

En la versión actual de C++, el bucle interno es un poco ineficiente ya que se construye un valor temporal en la pila, se construye una copia a la memoria de los vectores y finalmente se destruye el temporal. Sin embargo, la próxima versión de C++ tiene una característica llamada referencias R-Value (T&&) que ayudará.

La interfaz suministrada por std::vector no permite otra opción, que es usar alguna clase de fábrica para construir valores distintos al predeterminado. Aquí es un ejemplo aproximada de lo que este patrón se vería implementado en C++:

template <typename T> 
class my_vector_replacement { 

    // ... 

    template <typename F> 
    my_vector::push_back_using_factory(F factory) { 
     // ... check size of array, and resize if needed. 

     // Copy construct using placement new, 
     new(arrayData+end) T(factory()) 
     end += sizeof(T); 
    } 

    char* arrayData; 
    size_t end; // Of initialized data in arrayData 
}; 

// One of many possible implementations 
struct MyFactory { 
    MyFactory(int* p1, int* p2) : d1(p1), d2(p2) {} 
    YourData operator()() const { 
     return YourData(*d1,*d2); 
    } 
    int* d1; 
    int* d2; 
}; 

void GetsCalledALot(int* data1, int* data2, int count) { 
    // ... Still will need the same call to a reserve() type function. 

    // Note: consider using std::generate_n or std::copy instead of this loop. 
    for (int i = 0; i < count; ++i) { 
     // Copy construct using a factory 
     memberVector.push_back_using_factory(MyFactory(data1+i, data2+i)); 
    } 
} 

Hacer esto no significa que tenga que crear su propia clase de vectores. En este caso, también complica lo que debería haber sido un simple ejemplo. Pero puede haber ocasiones en las que usar una función de fábrica como esta sea mejor, por ejemplo, si el inserto es condicional en algún otro valor, y de otro modo tendrías que construir incondicionalmente algún costoso temporal incluso si no fuera realmente necesario.

1

utilizar el método de std :: vector :: reserva(). No cambiará el tamaño del vector, pero asignará el espacio.

3

Err ...

tratar el método:

std::vector<T>::reserve(x) 

Se le permitirá reservar suficiente memoria para los elementos x sin inicializar ninguna (su vector sigue vacío). Por lo tanto, no habrá reasignación hasta que se pase por x.

El segundo punto es que el vector no inicializará los valores a cero. ¿Estás probando tu código en depuración?

Después de la verificación de g ++, el siguiente código:

#include <iostream> 
#include <vector> 

struct MyStruct 
{ 
    int m_iValue00 ; 
    int m_iValue01 ; 
} ; 

int main() 
{ 
    MyStruct aaa, bbb, ccc ; 

    std::vector<MyStruct> aMyStruct ; 

    aMyStruct.push_back(aaa) ; 
    aMyStruct.push_back(bbb) ; 
    aMyStruct.push_back(ccc) ; 

    aMyStruct.resize(6) ; // [EDIT] double the size 

    for(std::vector<MyStruct>::size_type i = 0, iMax = aMyStruct.size(); i < iMax; ++i) 
    { 
     std::cout << "[" << i << "] : " << aMyStruct[i].m_iValue00 << ", " << aMyStruct[0].m_iValue01 << "\n" ; 
    } 

    return 0 ; 
} 

da los siguientes resultados:

[0] : 134515780, -16121856 
[1] : 134554052, -16121856 
[2] : 134544501, -16121856 
[3] : 0, -16121856 
[4] : 0, -16121856 
[5] : 0, -16121856 

La inicialización que viste fue probablemente un artefacto.

[EDITAR] Después del comentario sobre el cambio de tamaño, modifiqué el código para agregar la línea de cambio de tamaño. El cambio de tamaño llama efectivamente al constructor predeterminado del objeto dentro del vector, pero si el constructor predeterminado no hace nada, entonces nada se inicializa ... Todavía creo que fue un artefacto (me las arreglé la primera vez para tener el vector completo con el cero siguiente código:

aMyStruct.push_back(MyStruct()) ; 
aMyStruct.push_back(MyStruct()) ; 
aMyStruct.push_back(MyStruct()) ; 

Entonces ... : -./

[EDIT 2] al igual que ya ofrece Arkadiy, la solución es utilizar un constructor en línea tomando los parámetros deseados Algo así como

struct MyStruct 
{ 
    MyStruct(int p_d1, int p_d2) : d1(p_d1), d2(p_d2) {} 
    int d1, d2 ; 
} ; 

Esto probablemente será incluido en tu código.

Pero de todos modos debe estudiar su código con un generador de perfiles para asegurarse de que este fragmento de código sea el cuello de botella de su aplicación.

+0

Escribí una nota arriba. No es el constructor de vector que se inicializa a 0. Es resize() que lo hace. –

+0

En este caso MyStruct tiene un constructor trivial por lo que nada se inicializa. Esto puede ser diferente a la situación del OP. –

+0

Creo que estás en el camino correcto. No tengo ningún constructor definido en la estructura, por lo que su constructor predeterminado (creo) se inicializa a cero. Verifico si agregar un constructor predeterminado que no resuelve el problema. –

0

¿Las estructuras mismas necesitan estar en la memoria contigua, o se puede salir con un vector de struct *?

Los vectores hacen una copia de lo que les agregue, por lo que utilizar vectores de punteros en lugar de objetos es una forma de mejorar el rendimiento.

+0

Deben ser contiguos. Están en un buffer que está a punto de ser enviado a través de la red como una gran parte. –

0

No creo que STL sea tu respuesta. Necesitará implementar su propio tipo de solución con realloc(). Tendrá que guardar un puntero y el tamaño o la cantidad de elementos, y usar eso para encontrar dónde comenzar a agregar elementos después de un realloc().

int *memberArray; 
int arrayCount; 
void GetsCalledALot(int* data1, int* data2, int count) { 
    memberArray = realloc(memberArray, sizeof(int) * (arrayCount + count); 
    for (int i = 0; i < count; ++i) { 
     memberArray[arrayCount + i].d1 = data1[i]; 
     memberArray[arrayCount + i].d2 = data2[i]; 
    } 
    arrayCount += count; 
} 
4

Así que aquí está el problema, cambiar el tamaño está llamando inserción, que está haciendo una construcción copia de un elemento por defecto construida para cada uno de los elementos recién añadidos. Para hacer esto con un costo de 0, necesita escribir su propio constructor predeterminado Y su propio constructor de copia como funciones vacías. Hacer esto con su constructor de copia es una muy mala idea porque romperá los algoritmos de reasignación interna de std ::.

Resumen: No podrá hacer esto con std :: vector.

+0

Este es el verdadero problema. std :: vector debería darse cuenta de que no tiene que hacer ninguna inicialización si T tiene un constructor predeterminado trivial. Gracias por señalar que el constructor de copia es lo que está haciendo el trabajo innecesario aquí. –

8

Para aclarar en las respuestas de reserva(): necesita usar reserve() junto con push_back(). De esta forma, el constructor predeterminado no se llama para cada elemento, sino el constructor de copia. Aún incurre en la penalidad de configurar su estructura en la pila y luego copiarla en el vector. Por otro lado, es posible que si utiliza

vect.push_back(MyStruct(fieldValue1, fieldValue2)) 

el compilador construirá la nueva instancia directamente en las thatbelongs memoria al vector. Depende de cuán inteligente sea el optimizador. Debe verificar el código generado para averiguarlo.

+2

Resulta que el optimizador para gcc, en el nivel O3, no es lo suficientemente inteligente como para evitar la copia. –

1

De tus comentarios a otros carteles, parece que te quedas con malloc() y amigos. Vector no le permitirá tener elementos no construidos.

1

Desde su código, parece que tiene un vector de estructuras, cada una de las cuales consta de 2 ints. ¿Podrías usar 2 vectores de ints? Luego

copy(data1, data1 + count, back_inserter(v1)); 
copy(data2, data2 + count, back_inserter(v2)); 

Ahora no paga por copiar una estructura cada vez.

+0

Interesante. Esto podría funcionar, parece que evitaría la construcción de un objeto intermedio. – nobar

0

Me gustaría hacer algo como:

void GetsCalledALot(int* data1, int* data2, int count) 
{ 
    const size_t mvSize = memberVector.size(); 
    memberVector.reserve(mvSize + count); 

    for (int i = 0; i < count; ++i) { 
    memberVector.push_back(MyType(data1[i], data2[i])); 
    } 
} 

Es necesario definir un ctor para el tipo que se almacena en el memberVector, pero eso es un pequeño costo, ya que le dará lo mejor de ambos mundos; no se realiza una inicialización innecesaria y no se realizará ninguna reasignación durante el ciclo.

+0

Esto no parece resolver el problema ya que usa un MyType temporal() y lo copia en el vector. Todavía hay una inicialización doble. – nobar

10

C++ 0x añade una nueva plantilla de función miembro emplace_back-vector (que se basa en las plantillas variadic y reenvío perfecto) que se deshace de cualquier temporales por completo:

memberVector.emplace_back(data1[i], data2[i]); 
1

Si realmente insiste en tener los elementos sin inicializar y sacrificar algunos métodos como front(), back(), push_back(), usa boost vector desde numérico. Le permite incluso no conservar elementos existentes al llamar a resize() ...

6

En C++ 11 (y aumentar) puede utilizar la versión de matriz de unique_ptr para asignar una matriz no inicializada. Este no es un contenedor stl completo, pero aún se maneja con memoria y C++ - ish, que será lo suficientemente bueno para muchas aplicaciones.

auto my_uninit_array = std::unique_ptr<mystruct[]>(new mystruct[count]); 
1

Puede usar un tipo de envoltorio alrededor de su tipo de elemento, con un constructor predeterminado que no hace nada. Ej .:

template <typename T> 
struct no_init 
{ 
    T value; 

    no_init() { static_assert(std::is_standard_layout<no_init<T>>::value && sizeof(T) == sizeof(no_init<T>), "T does not have standard layout"); } 

    no_init(T& v) { value = v; } 
    T& operator=(T& v) { value = v; return value; } 

    no_init(no_init<T>& n) { value = n.value; } 
    no_init(no_init<T>&& n) { value = std::move(n.value); } 
    T& operator=(no_init<T>& n) { value = n.value; return this; } 
    T& operator=(no_init<T>&& n) { value = std::move(n.value); return this; } 

    T* operator&() { return &value; } // So you can use &(vec[0]) etc. 
}; 

de usar:

std::vector<no_init<char>> vec; 
vec.resize(2ul * 1024ul * 1024ul * 1024ul); 
Cuestiones relacionadas