std :: vector en VisualStudio2008 parece estar implementado de manera subóptima: demasiadas llamadas al constructor de copias

Question

He estado comparando una implementación STL de una popular biblioteca XmlRpc con una implementación que sobre todo evita STL. La implementación de STL es mucho más lenta: obtuve 47s hasta 4.5s. He diagnosticado algunas de las razones: en parte se debe a que std :: string no se usó correctamente (por ejemplo, el autor debería haber utilizado "const std :: string &" siempre que sea posible; no use std :: string como si eran cadenas de Java), pero también es porque cada vez que el vector sobrepasaba sus límites, se llamaban continuamente a los constructores de copias, lo cual era muy frecuente. Los constructores de copias fueron muy lentos porque hicieron copias en profundidad de los árboles (de valores XmlRpc).

Otra persona me dijo en StackOverflow que las implementaciones de std :: vector suelen duplicar el tamaño del búfer cada vez que superan. Este no parece ser el caso en VisualStudio 2008: para agregar 50 elementos a un estándar, el vector tomó 177 llamadas del constructor de copia. Doblando cada vez debe llamar al constructor de copia 64 veces. Si estaba muy preocupado por mantener bajo el uso de la memoria, entonces aumentar en un 50% cada vez debería llamar al constructor de copias 121 veces. Entonces, ¿de dónde viene el 177?

Mi pregunta es: (a) ¿por qué se llama al constructor de copias con tanta frecuencia? (b) ¿hay alguna manera de evitar el uso del constructor de copia si solo está moviendo un objeto de una ubicación a otra? (En este caso, y de hecho la mayoría de los casos, una memcpy() hubiera sido suficiente, y esto marca una GRAN diferencia).

(NB: Yo sé de vector :: reserva(), estoy un poco decepcionado de que los programadores de aplicaciones se necesitan para poner en práctica el truco duplicación cuando algo como esto ya es parte de cualquier buena aplicación STL.)

Mi programa de pruebas:

#include <string> 
#include <iostream> 
#include <vector> 



using namespace std; 


int constructorCalls; 
int assignmentCalls; 
int copyCalls; 


class C { 
    int n; 

public: 
    C(int _n) { n = _n; constructorCalls++; } 
    C(const C& orig) { copyCalls++; n = orig.n; } 
    void operator=(const C &orig) { assignmentCalls++; n = orig.n; } 
}; 



int main(int argc, char* argv[]) 
{ 
    std::vector<C> A; 

    //A.reserve(50); 
    for (int i=0; i < 50; i++) 
     A.push_back(i); 
    cout << "constructor calls = " << constructorCalls << "\n"; 
    cout << "assignment calls = " << assignmentCalls << "\n"; 
    cout << "copy calls = " << copyCalls << "\n"; 
    return 0; 
} 

Answer 1

El STL tiende a causar este tipo de cosas. La especificación no permite memcpy'ing porque eso no funciona en todos los casos. Hay un documento que describe EASTL, un montón de alteraciones hechas por EA para hacerlo más adecuado para sus propósitos, que tiene un método para declarar que un tipo es seguro para memcpy. Desafortunadamente no es AFAIK de código abierto, así que no podemos jugar con él.

IIRC Dinkumware STL (el de VS) crece vectores en un 50% cada vez.

Sin embargo, hacer una serie de push_back en un vector es una ineficiencia común. Puede usar reserva para aliviarlo (a costa de una posible pérdida de memoria si sobreestima significativamente) o utilizar un contenedor diferente: deque tiene mejor rendimiento para una serie de inserciones como esa, pero es un poco más lento en el acceso aleatorio, que puede/puede no ser un buen intercambio para ti.

O podría mirar almacenar punteros en lugar de valores que harán que el cambio de tamaño sea mucho más barato si está almacenando elementos grandes. Si está almacenando objetos grandes, esto siempre ganará porque no tiene que copiarlos nunca; siempre guardará esa copia para cada artículo al insertarlos al menos.

Answer 2

Mi pregunta es:

(a) por qué se llama el constructor de copia tan a menudo?

Porque cuando se vuelve a clasificar según el tamaño del vector usted necesita copiar todos los elementos del almacenador intermediario viejo en el nuevo almacenador intermediario. Esto se debe a que el vector garantiza que los objetos se almacenan en ubicaciones de memoria consecutivas.

(b) ¿hay alguna manera de evitar el uso del constructor de copia si sólo está en movimiento un objeto de un lugar a otro?

No, no hay forma de evitar el uso del constructor de copia.
Esto porque el objeto tiene varios miembros que deben inicializarse correctamente.
Si usó memcpy, ¿cómo sabe que el objeto se ha inicializado correctamente para el objeto?

Por ejemplo. SI el objeto contenía un puntero inteligente. No se puede simplemente memcpy un puntero inteligente. Necesita hacer un trabajo extra para rastrear la propiedad. De lo contrario, cuando el original se sale del alcance, la memoria se elimina y el nuevo objeto tiene un puntero colgante. El mismo principio se aplica a todos los objetos que tienen un constructor (constructor de copia), el constructor realmente realiza el trabajo requerido.

La forma de detener la copia del contenido es reservar el espacio.
Esto hace que el vector asigne suficiente espacio para todos los objetos que almacenará.Por lo tanto, no necesita seguir reasignando el búfer principal. Simplemente copia los objetos en el vector.

Doblando cada vez debe llamar al constructor de copia 64 veces. Si estaba muy preocupado por mantener bajo el uso de la memoria, al aumentar en 50% cada vez debería llamar al constructor de copias 121 veces. Entonces, ¿de dónde viene el 177?

vectorial tamaño asignado = 1:
Añadir elemento 1: (sin reasignación) Pero elemento de copias 1 en el vector.
Agregue el elemento 2: reasigne el búfer (tamaño 2): Copie el elemento 1 a lo ancho. Copie el elemento 2 en el vector.
Agregue el elemento 3: reasigne el búfer (tamaño 4): copie el elemento 1-2 a través. Copie el elemento 3 en el vector.
Agregue el elemento 4: copie el elemento 4 en el vector
Agregue el elemento 5: reasigne el búfer (tamaño 8): copie el elemento 1-4 a través. Copie el elemento 5 en el vector.
Añadir elemento 6: copia elemento 6 en el vector
Añadir elemento 7: copia elemento 7 en el vector
Añadir elemento 8: Copiar elemento 8 en el vector
Añadir elemento 9: reasignar tampón (tamaño 16): copia elemento 1- 8 a través Copie el elemento 9 en el vector.
elemento Agregar 10: Copiar elemento 10 en el vector
etc.

primeros 10 elementos tomó 25 construcciones de copia.
Si hubiera utilizado la reserva primero, solo habría tomado 10 construcciones de copia.

Answer 3

Si recuerdo correctamente, C++ 0x puede tener semántica de movimiento (además de semántica de copia), dicho esto, puede implementar un constructor de copia más eficiente si realmente lo desea.

A menos que el constructor de copia es complejo, normalmente es muy eficiente - después de todo, se supone que deben hacer algo más que simplemente copiar el objeto, y la memoria de copia es muy rápido en estos días.

Answer 4

Parece que las adiciones a C++ 0x ayudarán aquí; ver Rvalue y STL upgrades.

Answer 5

No olvide contar las llamadas al constructor de copia necesarias para push_back un objeto temporal C en el vector. Cada iteración llamará al constructor de copias de C al menos una vez.

Si agrega más código de impresión, que es un poco más claro lo que está pasando:

std::vector<C> A; 
std::vector<C>::size_type prevCapacity = A.capacity(); 

for (int i=0; i < 50; i++) { 
    A.push_back(i); 
    if(prevCapacity != A.capacity()) { 
     cout << "capacity " << prevCapacity << " -> " << A.capacity() << "\n"; 
    } 
    prevCapacity = A.capacity(); 
} 

Esto tiene el siguiente resultado:

capacity 0 -> 1 
capacity 1 -> 2 
capacity 2 -> 3 
capacity 3 -> 4 
capacity 4 -> 6 
capacity 6 -> 9 
capacity 9 -> 13 
capacity 13 -> 19 
capacity 19 -> 28 
capacity 28 -> 42 
capacity 42 -> 63 

Así que sí, la capacidad aumenta en un 50% cada uno hora, y esto representa 127 de las copias:

1 + 2 + 3 + 4 + 6 + 9 + 13 + 19 + 28 + 42 = 127 

Agregue las 50 copias adicionales de la llamada 50 s a push_back y tiene 177:

127 + 50 = 177 

Answer 6

Para evitar este problema, ¿por qué no usar un vector de punteros en lugar de un vector de objetos? Luego, delete cada elemento al destruir el vector.

En otras palabras, std::vector<C*> en lugar de std::vector<C>. Los indicadores de Memcpy son muy rápido.

Answer 7

Sólo una nota, tenga cuidado de añadir punteros al vector como una manera de reducir al mínimo el costo de copiado, ya que

1. La mala localidad de datos de los punteros en el vector hace que la versión no-puntero con objetos consecutivos ejecutar círculos alrededor de la versión del puntero cuando el vector es realmente usado.
2. La asignación de montón es más lenta que la asignación de la pila.

¿Te más a menudo uso el vector o añadir cosas a ella?