¿Hay alguna sobrecarga para la utilización de matrices de longitud variable?

Question

¿Hay alguna sobrecarga de uso de matrices de longitud variable? Podría el tamaño de la matriz se hace pasar por el argumento de línea de comandos en tiempo de ejecución? ¿Por qué es introducido, en comparación con automática y la asignación dinámica una matriz?

Answer 1

VLA tiene algo de sobrecarga (en comparación con "ordinario" llamado tiempo de compilación de tamaño array).

longitud de tiempo de ejecución En primer lugar, se ha y sin embargo el lenguaje le proporciona medios para obtener el tamaño real de la matriz en tiempo de ejecución (utilizando sizeof). Esto significa inmediatamente que el tamaño real de la matriz tiene que ser almacenado en alguna parte. Esto resulta en algunos insignificante sobrecarga de memoria per-matriz. Sin embargo, desde VLA sólo puede declararse como objetos automáticas, esta sobrecarga de la memoria no es algo que nadie se daría cuenta. Es como declarar una variable local adicional de tipo integral.

En segundo lugar, VLA normalmente se asigna en la pila, pero debido a su tamaño variable, con el caso general su ubicación exacta en la memoria no se conoce en tiempo de compilación. Por esta razón, la implementación subyacente por lo general tiene que implementarlo como un puntero a un bloque de memoria. Esto introduce algunos sobrecarga de memoria adicional (para el puntero), que de nuevo es completamente insignificante por las razones descritas anteriormente. Esto también introduce una ligera sobrecarga de rendimiento, ya que tenemos que leer el valor del puntero con el fin de encontrar la matriz real. Esta es la sobrecarga mismo que se obtiene al acceder a las matrices malloc de opinión (y no se consigue con las matrices de tamaño en tiempo de compilación en el encabezamiento).

Dado que el tamaño de la VLA es un valor entero de tiempo de ejecución, se puede, por supuesto, ser pasado como un argumento de línea de comandos. VLA no le importa donde su tamaño viene.

VLA se introdujeron como matrices con un bajo coste de asignación / desasignación de tamaño en tiempo de ejecución. Se adaptan entre arrays "ordinarios" nombre de compilación en tiempo de tamaño (que tienen prácticamente cero costo asignación-desasignación, pero de tamaño fijo) y matrices malloc-ED (tamaño en tiempo de ejecución que han, pero el coste relativamente alto de asignación-desasignación).

VLA obedecen [casi] las mismas reglas de toda la vida de alcance dependiente como objetos automáticos (es decir locales), lo que significa que, en caso general no pueden sustituir arrays malloc-ed. Ellos aplicabilidad se limita a situaciones en las que se necesita una rápida serie de tamaño en tiempo de ejecución con una duración típica automática.

Answer 2

Hay cierta sobrecarga en tiempo de ejecución con arreglos de longitud variable, pero que tendría que estar funcionando bastante difícil medirla. Tenga en cuenta que sizeof(vla) no es una constante de tiempo de compilación si vla es una matriz de longitud variable.

El tamaño de la matriz se puede pasar a una función en tiempo de ejecución. Si usted decide tomar el tamaño de un argumento de línea de comandos y convertir eso en un entero y pasar a la función que en tiempo de ejecución, que así sea -. Va a trabajar

arrays de longitud variable se usan porque las variables se asignan automáticamente al tamaño correcto y liberados automáticamente a la salida de la función. Esto evita la sobre-asignación de espacio (la asignación de espacio suficiente para el tamaño máximo posible cuando se trabaja sobre todo con tamaños mínimos), y evita problemas con la memoria limpiar.

Además, con matrices multidimensionales, Que yo sepa se comporta más como Fortran - se puede configurar de forma dinámica todas las dimensiones, en lugar de ser atrapado con tamaños fijos para todos, pero la dimensión principal de la matriz.

---

evidencia concreta de algo de sobrecarga de tiempo de ejecución para VLA -. Al menos con GCC 4.4.2 en SPARC (Solaris 10)

Tenga en cuenta los dos archivos a continuación:

vla.c - utilizando una matriz de longitud variable

#include <assert.h>
#include <stddef.h>
extern size_t identity_matrix(int n, int m);

size_t identity_matrix(int n, int m)
{
    int vla[n][m];
    int i, j;
    assert(n > 0 && n <= 32);
    assert(m > 0 && m <= 32);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            vla[i][j] = 0;
        }
        vla[i][i] = 1;
    }
    return(sizeof(vla));
}

fla.c - utilizando una matriz de longitud fija

#include <assert.h>
#include <stddef.h>
extern size_t identity_matrix(int n, int m);

size_t identity_matrix(int n, int m)
{
    int fla[32][32];
    int i, j;
    assert(n > 0 && n <= 32);
    assert(m > 0 && m <= 32);
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            fla[i][j] = 0;
        }
        fla[i][i] = 1;
    }
    return(sizeof(fla));
}

compilación de archivos y objetos tamaños

A efectos de comparación, los nombres de la matriz local son diferentes (vla vs fla), y las dimensiones de la matriz son diferentes cuando se declara -. De lo contrario, los archivos son los mismos

Me compilado usando:

$ gcc -O2 -c -std=c99 fla.c vla.c

Los tamaños de los archivos de objetos son algo diferentes - como se mide tanto por 'ls' y 'tamaño':

$ ls -l fla.o vla.o
-rw-r--r--   1 jleffler rd          1036 Jan  9 12:13 fla.o
-rw-r--r--   1 jleffler rd          1176 Jan  9 12:13 vla.o
$ size fla.o vla.o
fla.o: 530 + 0 + 0 = 530
vla.o: 670 + 0 + 0 = 670

No he hecho extensas pruebas para ver qué parte de los gastos indirectos se fija y la cantidad es variable, pero hay sobrecarga en el uso de un VLA.

Answer 3

  

Me pregunto si hay alguna sobrecarga de uso de matrices de longitud variable?

Nope

  

¿Puede el tamaño de la matriz podría ser pasado a través de argumentos de línea de comandos en tiempo de ejecución?

Sí.

  

¿Por qué es introducido, en comparación con automática y asignar dinámicamente una matriz?

automático sólo asignados permite a un tamaño fijo conocido en tiempo de compilación.

dinámicamente la asignación (malloc) almacenará la matriz en el heap , que tiene un espacio de memoria grande, pero es más lento de acceder.

VLA funciona mediante la colocación de la matriz en el pila . Esto hace que la asignación y acceso extremadamente rápido, y la pila suele ser pequeña (de unos pocos KB), y cuando el VLA se desbordó la pila, que es indistinguible de una recursión infinita.

Answer 4

No debe haber muy poca sobrecarga de VLA (A lo sumo, debería dar lugar a una adición al puntero de pila). La asignación dinámica requiere la gestión de memoria manual y es más lenta que la asignación basada en la pila de un VLA, y la declaración "automático" de una matriz requiere una expresión en tiempo de compilación para el tamaño de la matriz. Sin embargo, tenga en cuenta que si se produce un desbordamiento de pila, causará un comportamiento indefinido, a fin de mantener VLA relativamente pequeño.

Usted podría pasar el tamaño de una matriz a través de un argumento de línea de comandos, pero que tendría que escribir el código para manejar eso mismo.