example - vector array c++

C++ STL: Array vs Vector: rendimiento de acceso al elemento sin formato

Question

Estoy construyendo un intérprete y como estoy buscando la velocidad bruta esta vez, cada ciclo de reloj me importa en este caso (crudo).

¿Tiene alguna experiencia o información sobre cuál de los dos es más rápido: Vector o Array? Lo único que importa es la velocidad a la que puedo acceder a un elemento (recepción de código de operación), no me importa insertar, asignar, clasificar, etc.

Ahora me voy a inclinar por la ventana y diré:

• Las matrices son al menos un poco más rápidas que los vectores en términos de acceder a un elemento i.

Parece realmente lógico para mí. Con los vectores tiene toda esa seguridad y control de sobrecarga que no existe para las matrices.

(¿Por qué) estoy equivocado?

No, no puedo ignorar la diferencia de rendimiento, incluso si es tan pequeña, ya he optimizado y minimizado todas las demás partes de la máquina virtual que ejecuta los códigos de operación :)

Answer 1

Estás comparando manzanas con naranjas. Las matrices tienen un tamaño constante y se asignan automáticamente, mientras que los vectores tienen un tamaño dinámico y se asignan dinámicamente. El que uses depende de lo que necesites.

Generalmente, las matrices son "más rápidas" de asignar (entre comillas porque la comparación no tiene sentido) porque la asignación dinámica es más lenta. Sin embargo, acceder a un elemento debe ser el mismo. (Es probable que una matriz sea más probable que esté en la memoria caché, aunque eso no importa después del primer acceso).

Además, no sé de qué "seguridad" está hablando, los vector tienen muchas formas de obtener un comportamiento indefinido al igual que las matrices. Aunque tienen at() , que no necesita usar si sabe que el índice es válido.

Por último, perfila y mira el ensamblaje generado. Nadie adivina va a resolver nada.

Answer 2

No. Bajo el capó, std::vector y C ++ 0x std::array encuentran el puntero al elemento n al sumar n al puntero al primer elemento.

vector::at puede ser más lento que array::at porque el primero se debe comparar con una variable, mientras que el último se compara con una constante. Esas son las funciones que proporcionan la verificación de límites, no el operator[] .

Si se refiere a matrices estilo C en lugar de C ++ 0x std::array , entonces no hay miembro at miembro, pero el punto permanece.

EDITAR: si tiene una tabla de opcode, una matriz global (como con enlaces extern o static ) puede ser más rápida. Los elementos de una matriz global serían direccionables individualmente como variables globales cuando una constante se coloca entre corchetes, y los códigos de operación a menudo son constantes.

De todos modos, esto es una optimización prematura. Si no usa ninguna de las características de cambio de tamaño del vector , se parece bastante a una matriz que debería poder convertir fácilmente entre las dos.

Answer 3

Para obtener resultados decentes, utilice std::vector como almacenamiento de respaldo y tome un puntero a su primer elemento antes de su ciclo principal o lo que sea:

std::vector<T> mem_buf;
// stuff
uint8_t *mem=&mem_buf[0];
for(;;) {
    switch(mem[pc]) {
    // stuff
    }
}

Esto evita cualquier problema con las implementaciones demasiado útiles que realizan la comprobación de límites en operator[] , y facilita el paso simple al entrar en expresiones como mem_buf[pc] más adelante en el código.

Si cada instrucción hace suficiente trabajo, y el código es lo suficientemente variado, esto debería ser más rápido que usar una matriz global en una cantidad insignificante. (Si la diferencia es notable, los códigos de operación se deben complicar más).

En comparación con el uso de una matriz global, en x86 las instrucciones para este tipo de despacho deben ser más concisas (sin campos de desplazamiento de 32 bits en cualquier lugar), y para obtener más objetivos RISC debería haber menos instrucciones generadas (sin búsquedas TOC o torpe 32 -bit constantes), ya que los valores comúnmente utilizados están todos en el marco de la pila.

Realmente no estoy convencido de que la optimización del ciclo de despacho de un intérprete produzca un buen retorno en el tiempo invertido; las instrucciones deberían realmente ser más importantes, si es un problema, pero supongo que no debería llevar mucho tiempo. probar algunos enfoques diferentes y medir la diferencia. Como siempre en el caso de un comportamiento inesperado, el lenguaje ensamblador generado (y, en x86, el código máquina, ya que la longitud de la instrucción puede ser un factor) debe consultarse para verificar ineficiencias obvias.

Answer 4

Usted puede estar ladrando el árbol equivocado. Las fallas de caché pueden ser mucho más importantes que la cantidad de instrucciones que se ejecutan.

Answer 5

El tiempo de acceso al elemento en una implementación típica de un std::vector es el mismo que el tiempo de acceso al elemento en una matriz ordinaria disponible a través de un objeto puntero (es decir, un valor de puntero en tiempo de ejecución )

std::vector<int> v;
int *pa;
...
v[i];
pa[i]; 
// Both have the same access time

Sin embargo, el tiempo de acceso a un elemento de una matriz disponible como un objeto de matriz es mejor que los dos accesos anteriores (equivalente al acceso a través de un valor de puntero en tiempo de compilación )

int a[100];
...
a[i];
// Faster than both of the above

Por ejemplo, un acceso de lectura típico a una matriz int disponible a través de un valor de puntero en tiempo de ejecución se verá de la siguiente manera en el código compilado en la plataforma x86

// pa[i]
mov ecx, pa // read pointer value from memory
mov eax, i
mov <result>, dword ptr [ecx + eax * 4]

El acceso al elemento vector se verá más o menos igual.

Un acceso típico a una matriz int local disponible como un objeto de matriz se verá de la siguiente manera

// a[i]
mov eax, i
mov <result>, dword ptr [esp + <offset constant> + eax * 4]

Un acceso típico a una matriz int global disponible como un objeto de matriz se verá de la siguiente manera

// a[i]
mov eax, i
mov <result>, dword ptr [<absolute address constant> + eax * 4]

La diferencia en el rendimiento surge de esa instrucción extra mov en la primera variante, que tiene que hacer un acceso extra a la memoria.

Sin embargo, la diferencia es insignificante. Y se optimiza fácilmente hasta el punto de ser exactamente igual en el contexto de acceso múltiple (al cargar la dirección de destino en un registro).

Por lo tanto, la afirmación de que "las matrices son un poco más rápidas" es correcta en casos limitados cuando se puede acceder directamente a la matriz a través del objeto de matriz, no a través de un objeto de puntero. Pero el valor práctico de esa diferencia es prácticamente nada.