Usando matrices o std:: vectores en C++, ¿cuál es la brecha de rendimiento?
vector c++ (17)
Preámbulo para personas micro-optimizadoras
Recuerda:
"Los programadores pierden una enorme cantidad de tiempo pensando o preocupándose por la velocidad de las partes no críticas de sus programas, y estos intentos de eficacia realmente tienen un fuerte impacto negativo cuando se consideran la depuración y el mantenimiento. Debemos olvidarnos de pequeñas eficiencias, por ejemplo, 97% del tiempo: la optimización prematura es la raíz de todo mal. Sin embargo, no deberíamos dejar pasar nuestras oportunidades en ese crítico 3% ".
(Gracias a la metamorphosis de la cita completa)
No use una matriz C en lugar de un vector (o lo que sea) solo porque crea que es más rápido, ya que se supone que es de nivel inferior. Estarías equivocado.
Úselo por vector predeterminado (o el contenedor seguro adaptado a su necesidad), y luego, si su generador de perfiles dice que es un problema, vea si puede optimizarlo, ya sea utilizando un mejor algoritmo o cambiando el contenedor.
Dicho esto, podemos volver a la pregunta original.
Static / Dynamic Array?
Las clases de matriz de C ++ se comportan mejor que las de C de bajo nivel porque saben mucho sobre ellas mismas y pueden responder preguntas que las matrices C no pueden. Ellos son capaces de limpiar después de ellos mismos. Y lo que es más importante, generalmente se escriben utilizando plantillas y / o en línea, lo que significa que lo que parece ser una gran cantidad de código en depuración se resuelve con poco o ningún código producido en la compilación de lanzamiento, lo que significa que no hay diferencia con su competencia menos segura.
En general, se divide en dos categorías:
Arrays dinámicos
Usar un puntero a una matriz malloc-ed / new-ed será, en el mejor de los casos, tan rápido como la versión std :: vector, y mucho menos seguro (ver la publicación de litb ).
Entonces usa un std :: vector.
Matrices estáticas
Usar una matriz estática será, en el mejor de los casos:
- tan rápido como la versión std::array
- y mucho menos seguro.
Entonces usa std::array .
Memoria no inicializada
A veces, usar un vector lugar de un buffer en bruto incurre en un costo visible porque el vector inicializará el buffer en la construcción, mientras que el código que reemplaza no lo hizo, como comentó bernie en su answer .
Si este es el caso, puede manejarlo utilizando un unique_ptr lugar de un vector o, si el caso no es excepcional en su línea de código, escriba realmente un buffer_owner clase que será el propietario de esa memoria y le dará acceso fácil y seguro a incluyendo bonificaciones como redimensionarlo (usando realloc ?), o lo que sea que necesites.
En nuestro curso de C ++ sugieren no usar matrices C ++ en nuevos proyectos. Por lo que sé, el mismo Stroustroup sugiere no usar matrices. ¿Pero hay diferencias de rendimiento significativas?
Algunas veces, las matrices son mejores que los vectores. Si siempre manipulas un conjunto de objetos de longitud fija, las matrices son mejores. Considere los siguientes fragmentos de código:
int main() {
int v[3];
v[0]=1; v[1]=2;v[2]=3;
int sum;
int starttime=time(NULL);
cout << starttime << endl;
for (int i=0;i<50000;i++)
for (int j=0;j<10000;j++) {
X x(v);
sum+=x.first();
}
int endtime=time(NULL);
cout << endtime << endl;
cout << endtime - starttime << endl;
}
donde la versión de vector de X es
class X {
vector<int> vec;
public:
X(const vector<int>& v) {vec = v;}
int first() { return vec[0];}
};
y la versión de matriz de X es:
class X {
int f[3];
public:
X(int a[]) {f[0]=a[0]; f[1]=a[1];f[2]=a[2];}
int first() { return f[0];}
};
La versión de matriz de main () será más rápida porque evitamos la sobrecarga de "nuevo" cada vez en el ciclo interno.
(Este código fue publicado en comp.lang.c ++ por mí).
Definitivamente hay un impacto en el rendimiento al usar un std::vector frente a un conjunto sin formato cuando se quiere un buffer no inicializado (por ejemplo, para usar como destino para memcpy() ). Un std::vector inicializará todos sus elementos utilizando el constructor predeterminado. Una matriz en bruto no lo hará.
La especificación de C ++ para el constructor de std:vector tomando un argumento de count (es la tercera forma) dice:
`Construye un nuevo contenedor a partir de una variedad de fuentes de datos, opcionalmente utilizando una asignación asignada por el usuario.
3) Construye el contenedor con el conteo de incidencias de T. insertadas por defecto. No se realizan copias.
Complejidad
2-3) Recuento lineal
Una matriz sin formato no incurre en este costo de inicialización.
Consulte también ¿Cómo puedo evitar std :: vector <> para inicializar todos sus elementos?
La diferencia de rendimiento entre los dos depende en gran medida de la implementación: si comparamos un std :: vector mal implementado con una implementación de matriz óptima, la matriz ganaría, pero la cambiaría y el vector ganaría ...
Siempre y cuando compare manzanas con manzanas (ya sea la matriz y el vector tienen un número fijo de elementos, o ambos cambian de tamaño de forma dinámica), creo que la diferencia de rendimiento es insignificante, siempre y cuando siga la práctica de codificación STL. No olvide que el uso de contenedores C ++ estándar también le permite utilizar los algoritmos prelaminados que forman parte de la biblioteca estándar de C ++ y la mayoría de ellos es probable que tengan un mejor rendimiento que la implementación promedio del mismo algoritmo que construye usted mismo. .
Dicho esto, en mi humilde opinión, el vector gana en un escenario de depuración con un STL de depuración, ya que la mayoría de las implementaciones de STL con un modo de depuración adecuado pueden al menos resaltar los errores típicos cometidos por las personas al trabajar con contenedores estándar.
Ah, y no olvides que la matriz y el vector comparten el mismo diseño de memoria, por lo que puedes usar vectores para pasar datos a un código heredado de C o C ++ que espera arreglos básicos. Tenga en cuenta que la mayoría de las apuestas están desactivadas en ese escenario, sin embargo, y que está lidiando con la memoria bruta de nuevo.
La siguiente prueba simple:
C ++ Array vs Vector explicación de la prueba de rendimiento
contradice las conclusiones de "Comparación del código ensamblador generado para indexación básica, desreferenciación e incremento de operaciones en vectores y matrices / punteros".
Debe haber una diferencia entre las matrices y los vectores. La prueba lo dice ... solo inténtalo, el código está ahí ...
Los vectores son arreglos bajo el capó. El rendimiento es el mismo.
Un lugar donde puede encontrarse con un problema de rendimiento, no es dimensionar el vector correctamente para comenzar.
A medida que un vector se llena, se redimensionará a sí mismo, y eso puede implicar una nueva asignación de matriz, seguida de n constructores de copia, seguidos por aproximadamente n llamadas a destructor, seguidas por una eliminación de matriz.
Si tu construcción / destrucción es costosa, para empezar, es mucho mejor que el vector tenga el tamaño correcto.
Hay una manera simple de demostrar esto. Cree una clase simple que muestre cuándo se construye / destruye / copia / asigna. Crea un vector de estas cosas y comienza a empujarlas en la parte posterior del vector. Cuando el vector se llena, habrá una cascada de actividad a medida que el vector cambie de tamaño. Luego inténtelo de nuevo con el tamaño del vector al número esperado de elementos. Verás la diferencia.
Los vectores usan un poco más de memoria que las matrices, ya que contienen el tamaño de la matriz. También aumentan el tamaño del disco duro de los programas y, probablemente, la huella de memoria de los programas. Estos aumentos son pequeños, pero pueden importar si trabajas con un sistema integrado. Aunque la mayoría de los lugares donde estas diferencias importan son lugares donde usaría C en lugar de C ++.
Para responder a algo Mehrdad dijo:
Sin embargo, puede haber casos en los que aún necesite matrices. Al interactuar con código de bajo nivel (es decir, ensamblaje) o bibliotecas antiguas que requieren matrices, es posible que no pueda usar vectores.
No es cierto del todo. Los vectores se degradan muy bien en arreglos / punteros si usa:
vector<double> vector;
vector.push_back(42);
double *array = &(*vector.begin());
// pass the array to whatever low-level code you have
Esto funciona para todas las principales implementaciones de STL. En el siguiente estándar, se requerirá que funcione (aunque hoy funciona correctamente).
Puede haber algún caso de borde donde tenga acceso vectorial dentro de una función en línea dentro de una función en línea, donde haya ido más allá de lo que alineará el compilador y forzará una llamada de función. Eso sería tan raro que no valdría la pena preocuparse - en general, estaría de acuerdo con litb .
Me sorprende que nadie haya mencionado esto todavía: no se preocupe por el rendimiento hasta que se haya demostrado que es un problema, y luego un punto de referencia.
STL es una biblioteca muy optimizada. De hecho, incluso se sugiere usar STL en juegos en los que podría ser necesario un alto rendimiento. Las matrices son demasiado propensas a errores para ser utilizadas en las tareas diarias. Los compiladores de hoy también son muy inteligentes y realmente pueden producir código excelente con STL. Si sabe lo que está haciendo, STL generalmente puede proporcionar el rendimiento necesario. Por ejemplo, inicializando vectores al tamaño requerido (si lo sabe desde el inicio), básicamente puede lograr el rendimiento de la matriz. Sin embargo, puede haber casos en los que aún necesite matrices. Al interactuar con código de bajo nivel (es decir, ensamblaje) o bibliotecas antiguas que requieren matrices, es posible que no pueda usar vectores.
Se deben evitar el uso de matrices C ++ con las new (es decir, con matrices dinámicas). Existe el problema de que debe hacer un seguimiento del tamaño, y debe eliminarlos manualmente, y hacer todo tipo de tareas domésticas.
Tampoco se recomienda el uso de matrices en la pila porque no tiene control de rango, y al pasar la matriz perderá información sobre su tamaño (matriz a conversión de puntero). Debería usar boost::array en ese caso, que envuelve una matriz de C ++ en una clase pequeña y proporciona una función de size e iteradores para iterar sobre ella.
Ahora las matrices std :: vector vs. C ++ nativas (tomadas de internet):
// Comparison of assembly code generated for basic indexing, dereferencing,
// and increment operations on vectors and arrays/pointers.
// Assembly code was generated by gcc 4.1.0 invoked with g++ -O3 -S on a
// x86_64-suse-linux machine.
#include <vector>
struct S
{
int padding;
std::vector<int> v;
int * p;
std::vector<int>::iterator i;
};
int pointer_index (S & s) { return s.p[3]; }
// movq 32(%rdi), %rax
// movl 12(%rax), %eax
// ret
int vector_index (S & s) { return s.v[3]; }
// movq 8(%rdi), %rax
// movl 12(%rax), %eax
// ret
// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.
int pointer_deref (S & s) { return *s.p; }
// movq 32(%rdi), %rax
// movl (%rax), %eax
// ret
int iterator_deref (S & s) { return *s.i; }
// movq 40(%rdi), %rax
// movl (%rax), %eax
// ret
// Conclusion: Dereferencing a vector iterator is the same damn thing
// as dereferencing a pointer.
void pointer_increment (S & s) { ++s.p; }
// addq $4, 32(%rdi)
// ret
void iterator_increment (S & s) { ++s.i; }
// addq $4, 40(%rdi)
// ret
// Conclusion: Incrementing a vector iterator is the same damn thing as
// incrementing a pointer.
Nota: Si asigna matrices con objetos new y asignados que no pertenecen a la clase (como plain int ) o clases sin un constructor definido por el usuario y no desea que sus elementos se inicialicen inicialmente, el uso de new matrices asignadas puede tener ventajas de rendimiento porque std::vector inicializa todos los elementos a los valores por defecto (0 para int, por ejemplo) en la construcción (créditos a @bernie para recordarme).
Si compila el software en modo de depuración, muchos compiladores no alinearán las funciones de acceso del vector. Esto hará que la implementación del vector STL sea mucho más lenta en circunstancias donde el rendimiento es un problema. También hará que el código sea más fácil de depurar, ya que puede ver en el depurador cuánta memoria se asignó.
En modo optimizado, esperaría que el vector stl se acercara a la eficiencia de una matriz. Esto es así ya que muchos de los métodos vectoriales ahora están en línea.
Si no necesita ajustar dinámicamente el tamaño, tiene la sobrecarga de memoria para guardar la capacidad (un puntero / tamaño_t). Eso es.
Tiene aún menos razones para usar matrices simples en C ++ 11.
Hay 3 tipos de matrices en la naturaleza, de la más rápida a la más lenta, según las características que tienen (por supuesto, la calidad de la implementación puede hacer que las cosas sean realmente rápidas, incluso para el caso 3 de la lista):
- Estático con tamaño conocido en tiempo de compilación. ---
std::array<T, N> - Dinámico con tamaño conocido en tiempo de ejecución y sin cambio de tamaño. La optimización típica aquí es que si la matriz se puede asignar en la pila directamente. - No disponible . Tal vez
dynarrayen C ++ TS después de C ++ 14. En C hay VLAs - Dinámico y redimensionable en tiempo de ejecución. ---
std::vector<T>
Para 1. arrays estáticos simples con un número fijo de elementos, use std::array<T, N> en C ++ 11.
Para 2. arreglos de tamaño fijo especificados en tiempo de ejecución, pero eso no cambiará su tamaño, hay discusión en C ++ 14 pero se ha movido a una especificación técnica y finalmente se ha hecho de C ++ 14.
Para 3. std::vector<T> generalmente pedirá memoria en el montón . Esto podría tener consecuencias en el rendimiento, aunque podría usar std::vector<T, MyAlloc<T>> para mejorar la situación con un asignador personalizado. La ventaja comparada con T mytype[] = new MyType[n]; es que puedes redimensionarlo y que no decaerá a un puntero, como lo hacen las matrices simples.
Utilice los tipos de biblioteca estándar mencionados para evitar que las matrices decaigan a punteros . Ahorrará tiempo de depuración y el rendimiento será exactamente el mismo que con las matrices simples si utiliza el mismo conjunto de funciones.
Ve con STL. No hay penalización de rendimiento. Los algoritmos son muy eficientes y hacen un buen trabajo al manejar los tipos de detalles en los que la mayoría de nosotros no pensaríamos.
Yo diría que la principal preocupación no es el rendimiento, sino la seguridad. Puede cometer muchos errores con las matrices (considere cambiar el tamaño, por ejemplo), donde un vector le ahorraría mucho dolor.
La conclusión es que las matrices de enteros son más rápidas que los vectores de enteros (5 veces en mi ejemplo). Sin embargo, las matrices y vectores se encuentran alrededor de la misma velocidad para datos más complejos / no alineados.