Estoy construyendo un intérprete y como estoy apuntando para la velocidad pura que esta vez, cada ciclo de reloj importancia para mí en este (raw) caso.

¿Tienes alguna experiencia o información de cuál de los dos es más rápido: Vector o Matriz?
Todo lo que importa es la velocidad a la que puedo acceder a un elemento (código de operación de recepción), no me importa acerca de la inserción, la atribución, ordenación, etc.

Voy a inclinarse a mí mismo fuera de la ventana y decir:

  • Matrices son al menos un poco más rápido que los vectores en términos de acceso a un elemento i.

Parece muy lógico para mí. Con los vectores que tienen todos los de la seguridad y el control de la sobrecarga de que no existe para las matrices.

(Por qué) ¿me equivoco?

No, no puedo pasar por alto la diferencia de rendimiento – incluso si es así pequeña – ya he optimizado y minimiza cualquier otra parte de la máquina virtual que ejecuta los opcodes 🙂

  • Si es importante para usted, escriba un simple punto de referencia y el tiempo de la diferencia. Y que «la seguridad y el control de los gastos generales» están hablando? Y, en cualquier caso, este es un duplicado.
  • Op nombre es el mejor comentario 🙂 Medir, medir y medir de nuevo esa es la respuesta.
InformationsquelleAutor oh boy | 2010-04-29

5 Comentarios

  1. 54

    Elemento de tiempo de acceso de una implementación típica de un std::vector es el mismo como elemento de tiempo de acceso ordinario de la matriz disponible a través de un puntero de objeto (es decir, un tiempo de ejecución valor de puntero)

    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 una objeto de matriz de es mejor que el tanto de los de arriba de accesos (equivalente a acceso a través de un en tiempo de compilación valor de puntero)

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

    Por ejemplo, una típica acceso de lectura a un int matriz disponibles a través de un tiempo de ejecución de puntero de valor se verá como sigue en el código compilado en plataforma x86

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

    Acceso a elemento vector se ven más o menos el mismo.

    Una típica acceso a un local int matriz disponible como un objeto de matriz será como sigue

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

    Una típica acceso a un mundial int matriz disponible como un objeto de matriz será como sigue

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

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

    Sin embargo, la diferencia es insignificante. Y es fácilmente optimizado hasta el punto de ser exactamente el mismo en varios contexto de acceso (por la carga de la dirección de destino en un registro).

    Por lo que la afirmación acerca de que «las matrices de ser un poco más rápido» es la correcta, en caso estrecho cuando la matriz es accesible directamente a través de la matriz objeto, no a través de un puntero de objeto. Pero el valor práctico de que la diferencia es prácticamente nada.

    • ¿De qué estás hablando? Usted realmente debe ilustrar esto con algún tipo de nivel de máquina descripción de lo que iba a ser diferente.
    • Acabo de añadir un nivel de la máquina descripción.
    • OK. Pero el que se presupone que la matriz está en la pila, no en una estructura de datos, que se pasa por referencia, o en el ámbito de espacio de nombres. También se presume la vector puntero base no es promovido a un registro, el cual se espera que dentro de un bucle.
    • Sí, pero en primer lugar, cuando se pasa un vector en algún lugar, generalmente se pasan por referencia, así que en caso de un vector tienes que hacer dos elimina referencias: para llegar a la vector propio cuerpo y, a continuación, para llegar a la propia matriz. Por este motivo se puede tomar la primera a la eliminación de referencias fuera de la consideración (en ambos casos) y se centran en la matriz de acceso. En segundo lugar, como ya he dicho a mí mismo, en múltiples contexto de acceso (como un bucle), la diferencia es eaily optimizado de distancia por la pre-carga de la base de dirección en un registro.
    • Ahora que el tipo de respuesta detallada que me vienen en para!
    • Otra razón por la que algunas personas (yo) prefieren el uso de una matriz a través de un vector, es porque un vector se asigna de forma dinámica, lo que significa que se requiere una nueva llamada. Si el recipiente no tiene que ser dinámica, entonces yo uso una matriz estática, porque es una nueva llamada de menos. En cualquier caso, yo no conozco a ningún razones para preferir una matriz dinámica a través de un std::vector<>, ya que un vector hace internamente.

  2. 8

    Usted puede estar ladrando al árbol equivocado. Errores de caché puede ser mucho más importante que el número de instrucciones que se ejecutan.

  3. 3

    No. Bajo el capó, tanto std::vector y C++0x std::array encontrar el puntero al elemento n mediante la adición de n para el puntero al primer elemento.

    vector::at puede ser más lento que array::at porque el primero debe comparar contra de una variable mientras que el segundo se compara contra una constante. Los son las funciones que proporcionan la comprobación de los límites, no operator[].

    Si te refieres al estilo C matrices en lugar de C++0x std::array, entonces no hay at miembro, pero el punto sigue siendo.

    EDICIÓN: Si usted tiene un código de operación de la tabla, una matriz global (como con extern o static vinculación) puede ser más rápido. Elementos de un array global sería direccionables individualmente como variables globales cuando la constante es poner dentro de los corchetes, y opcodes a menudo son constantes.

    De todos modos, todo esto es prematuro optimización. Si no hace uso de ninguna de vector‘s características de redimensionamiento, se ve lo suficientemente similar a una matriz que debe ser capaz de convertir fácilmente entre los dos.

    • Lo array<>? El OP pregunta, parece ser incorporadas en las matrices, no se trata de unos array<>. Construido-en matrices no son punteros bajo el capó.
    • construido-en las matrices se convierten implícitamente a los punteros por la incorporada en el operador de subíndice, así que yo diría que son.
    • La conversión a puntero es puramente conceptual. Existe sólo en el nivel de idioma (sólo para definir la semántica de [] operador en el documento estándar). La resultante conceptual puntero es un tiempo de compilación valor, lo que significa que una vez que tengamos «bajo el capó» no existe un verdadero puntero involucrados allí.
    • es, invariablemente, un valor de tiempo de ejecución para los no-valores constantes dentro de los corchetes. No hay manera de hacerlo, además de la base+índice de abordar.
    • No, estoy hablando de la base valor por sí solo. En el caso de una matriz real, la base es una compilación de constante de tiempo, mientras que en el caso de un vector de la base es un valor de tiempo de ejecución.
    • la única manera de que la base puede ser una constante en tiempo de compilación es ser un mundial. Creo que usted acaba de decir es directamente desplazamiento del puntero de pila. De todos modos, creo que ambos hemos transmitido nuestro puntos.
    • Sí, estás en lo correcto. Pero todavía peeformance sabio constante desplazamiento de la pila está más cerca de una constante en tiempo de compilación que a una explícita de la memoria de lectura, porque desplazamiento de direccionamiento es utilizada normalmente por una sola instrucción (como en el ejemplo de arriba) y no requiere de la memoria de lectura.

  4. 2

    Usted está comparando manzanas con naranjas. Las matrices tienen una constante de tamaño y se asignan automáticamente, mientras que los vectores tienen una dinámica de tamaño y se asignan dinámicamente. Que depende de lo que usted necesita.

    Generalmente, las matrices son «más rápido» para asignar (entre comillas porque la comparación no tiene sentido) porque la asignación dinámica es más lento. Sin embargo, el acceso a un elemento debe ser el mismo. (Concedido una matriz es probablemente más propensos a estar en la caché, aunque eso no importa, después de que el primer acceso.)

    También, no sé qué de «seguridad» de que estás hablando, vector‘s tiene un montón de maneras de obtener un comportamiento indefinido como matrices. A pesar de que han at(), que no es necesario usar si usted sabe que el índice es válida.

    Por último, el perfil y la mirada en el ensamblado generado. Nadie sabe es que va a resolver nada.

  5. 0

    Decente resultados, utilice std::vector como el almacenamiento de respaldo y tomar un puntero a su primer elemento antes de su bucle principal o lo que sea:

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

    Evita problemas con la más útil de las implementaciones que realizar la comprobación de los límites en operator[], y hace solo paso más fácil cuando paso a expresiones tales como mem_buf[pc] más adelante en el código.

    Si cada una de las instrucciones no hay suficiente trabajo, y el código es lo suficientemente variada como, este debe ser más rápido que usando un array global por cierta cantidad insignificante. (Si la diferencia es notable, los códigos de operación deben ser más complicado.)

    Comparación con el uso de una matriz global, en x86 las instrucciones para este tipo de distribución debe ser más conciso (no de 32 bits de los campos de desplazamiento en cualquier lugar), y para más RISC como objetivos no debe ser menor número de instrucciones generadas (no TOC búsquedas o torpe de 32 bits constantes), como comúnmente se utilizan los valores están todos en el marco de pila.

    No estoy muy convencido de que la optimización de un intérprete del bucle de envío de esta manera va a producir un buen rendimiento en el tiempo invertido, las instrucciones que en realidad debería ser hecho para hacer más, si es un problema, pero supongo que no debería tardar mucho para probar un par de diferentes enfoques y medir la diferencia. Como siempre, en el caso de comportamiento inesperado el ensamblado generado lenguaje (y, en x86, el código de la máquina, como la instrucción de longitud puede ser un factor), debe ser consultado para comprobar ineficiencias evidentes.

Dejar respuesta

Please enter your comment!
Please enter your name here