programacion - matrices en lenguaje c

¿Existe alguna sobrecarga por usar arreglos de longitud variable?

Question

¿Hay alguna sobrecarga de usar matrices de longitud variable? ¿Se puede pasar el tamaño de la matriz a través del argumento de la línea de comandos en el tiempo de ejecución? ¿Por qué se introduce, en comparación con la asignación automática y dinámica de una matriz?

Answer 1

¿Me pregunto si hay algo de uso general de usar arreglos de longitud variable?

No

¿Se puede pasar el tamaño de la matriz a través del argumento de la línea de comandos en el tiempo de ejecución?

Sí.

¿Por qué se introduce, en comparación con la asignación automática y dinámica de una matriz?

La asignación automática solo permite un tamaño fijo conocido en el momento de la compilación.

La asignación dinámica ( malloc ) almacenará la matriz en el montón , que tiene un gran espacio de memoria, pero su acceso es más lento.

VLA trabaja colocando la matriz en la pila . Esto hace que la asignación y el acceso sean extremadamente rápidos, pero la pila suele ser pequeña (de unos pocos KB), y cuando el VLA desbordó la pila, es indistinguible de una recursión infinita.

Answer 2

Debería haber muy poca sobrecarga para los VLA (a lo sumo debería dar como resultado una adición al puntero de pila). La asignación dinámica requiere administración de memoria manual y es más lenta que la asignación basada en pila de un VLA, y la declaración "automática" de una matriz requiere una expresión de 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, así que mantenga los VLA relativamente pequeños.

Podría pasar el tamaño de una matriz a través de un argumento de línea de comando, pero tendría que escribir el código para manejarlo usted mismo.

Answer 3

Hay una sobrecarga de tiempo de ejecución con matrices de longitud variable, pero tendría que trabajar bastante duro para medirlo. 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 elige tomar el tamaño de un argumento de la línea de comando y convertirlo en un entero y pasarlo a la función en tiempo de ejecución, que así sea - funcionará.

Se utilizan matrices de longitud variable porque las variables se asignan automáticamente al tamaño correcto y se liberan automáticamente al salir de la función. Esto evita la sobre asignación de espacio (asignando el espacio suficiente para el tamaño máximo posible cuando trabaja principalmente con tamaños mínimos) y evita problemas con la limpieza de la memoria.

Además, con matrices multidimensionales, AFAIK se comporta más como Fortran: puede configurar dinámicamente todas las dimensiones, en lugar de quedarse atascado con tamaños fijos para todas las dimensiones excepto la dimensión principal de la matriz.

Evidencia concreta de cierta sobrecarga de tiempo de ejecución para VLA, al menos con GCC 4.4.2 en SPARC (Solaris 10).

Considere los dos archivos a continuación:

vla.c - usando 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 - usando 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 y tamaño de archivo objeto.

Para fines 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.

Compilé utilizando:

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

Los tamaños de los archivos de objetos son algo diferentes, medidos tanto por ''ls'' como por ''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 realizado pruebas exhaustivas para ver cuánta sobrecarga se fija y cuánto es variable, pero hay una sobrecarga en el uso de un VLA.

Answer 4

VLA tiene cierta sobrecarga (en comparación con una matriz de tamaño de compilación denominada "ordinaria").

En primer lugar, tiene una duración de tiempo de ejecución y, sin embargo, el idioma le proporciona los 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 debe almacenarse en algún lugar. Esto da como resultado una sobrecarga de memoria insignificante por matriz. Sin embargo, como los VLA solo se pueden declarar como objetos automáticos, esta sobrecarga de memoria no es algo que alguien notaría. Es como declarar una variable local extra de tipo integral.

En segundo lugar, el VLA normalmente se asigna en la pila, pero debido a su tamaño variable, en general, su ubicación exacta en la memoria no se conoce en el momento de la compilación. Por esta razón, la implementación subyacente generalmente tiene que implementarla como un puntero a un bloque de memoria. Esto introduce algo de 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 para encontrar la matriz real. Esta es la misma sobrecarga que se obtiene al acceder a matrices de Malloced (y no a las matrices de tamaño de compilación nombradas).

Como el tamaño del VLA es un valor entero en tiempo de ejecución, se puede pasar, por supuesto, como un argumento de línea de comando. A VLA no le importa de dónde viene su tamaño.

Los VLA se introdujeron como matrices de tiempo de ejecución con bajo costo de asignación / desasignación. Se ajustan entre las matrices de tamaño de compilación denominadas "ordinarias" (que tienen un costo de desasignación de la asignación prácticamente nulo, pero de tamaño fijo) y las matrices de tipo malloc (que tienen un tamaño de tiempo de ejecución, pero el costo de la desasignación de la asignación es relativamente alta).

Los VLA obedecen [casi] a las mismas reglas de vida dependientes del alcance que los objetos automáticos (es decir, locales), lo que significa que, en general, no pueden reemplazar los arreglos de Malloced. La aplicabilidad se limita a situaciones en las que necesita una matriz de tamaño de tiempo de ejecución rápida con una vida útil automática típica.