¿Hay alguna sobrecarga por usar arreglos de longitud variable?

8 minutos de lectura

avatar de usuario
Tim

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

avatar de usuario
Hormiga

VLA tiene algunos gastos generales (en comparación con la matriz de tiempo de compilación con nombre “ordinario”).

En primer lugar, tiene una duración de tiempo de ejecución y, sin embargo, el lenguaje le proporciona los medios para obtener el tamaño real de la matriz en tiempo de ejecución (usando 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 por arreglo insignificante. Sin embargo, dado que los VLA solo se pueden declarar como objetos automáticos, esta sobrecarga de memoria no es algo que nadie pueda notar. Es como declarar una variable local extra de tipo integral.

En segundo lugar, 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 implementarlo como un puntero a un bloque de memoria. Esto introduce una sobrecarga de memoria adicional (para el puntero), que nuevamente 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 obtiene al acceder malloc-ed arrays (y no se obtiene con los arrays del tamaño del tiempo de compilación con nombre).

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

Los VLA se introdujeron como arreglos del tamaño del tiempo de ejecución con un bajo costo de asignación/desasignación. Se ajustan entre matrices “ordinarias” con nombre de tiempo de compilación (que tienen un costo de asignación-desasignación prácticamente nulo, pero de tamaño fijo) y mallocmatrices -ed (que tienen un tamaño de tiempo de ejecución, pero un costo de asignación-desasignación relativamente alto).

VLA obedecer [almost] las mismas reglas de vida útil dependientes del alcance que los objetos automáticos (es decir, locales), lo que significa que, en general, no pueden reemplazar mallocmatrices -ed. Su aplicabilidad se limita a situaciones en las que necesita una matriz de tamaño de tiempo de ejecución rápido con una vida útil automática típica.

  • Los VLA en realidad obedecen casi las mismas reglas de vigencia que otros objetos automáticos (“desde la declaración del [VLA] hasta que la ejecución del programa sale del alcance de la declaración” vs. “desde la entrada en el bloque con el que [the object] está asociado hasta que la ejecución de ese bloque termina de alguna manera”) [from 6.2.4(5) and 6.2.4(6) of the C99 standard].

    – jjlin

    8 de febrero de 2012 a las 21:20

  • VLA normalmente se asigna en la pila,” — Normalmente? ¿Quiere decir que podría estar asignado en el montón?

    – Spikatrix

    13 mayo 2015 a las 12:11

  • @Cool Guy: quiero decir que la especificación del idioma no especifica dónde se asignan y ni siquiera postula la existencia de “pila”, por lo que normalmente prefiero agregar varias palabras de comadreja cada vez que hablo de algo que es formalmente un detalle de implementación.

    – Ant

    13 mayo 2015 a las 20:23


  • Una vez asignada, ¿hay alguna diferencia entre la variable asignada malloc() y la variable asignada alloca()? Por ejemplo, cargar/escribir las variables

    – dragonxlwang

    5 de agosto de 2015 a las 19:39

  • @dragonxlwang: Una vez asignado, no hay diferencia. (Aparte de consideraciones tales como la localidad de memoria: alloca asigna memoria “aquí mismo en la pila” junto a otras variables locales, mientras que malloc asigna la memoria “en algún lugar lejano, en el montón”.)

    – Ant

    5 de agosto de 2015 a las 20:39


avatar de usuario
jonathan leffler

Hay algo de sobrecarga en tiempo de ejecución con arreglos de longitud variable, pero tendría que trabajar bastante 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 línea de comando y convertirlo en un número entero y pasarlo a la función en tiempo de ejecución, que así sea, funcionará.

Las matrices de longitud variable se utilizan 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 asignación excesiva de espacio (asignar suficiente espacio para el tamaño máximo posible cuando se trabaja principalmente con tamaños mínimos) y evita problemas con la limpieza de la memoria.

Además, con arreglos multidimensionales, hasta donde se se comporta más como Fortran: puede configurar dinámicamente todas las dimensiones, en lugar de quedarse con tamaños fijos para todas las dimensiones de la matriz excepto para la principal.


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));
}

Tamaños de archivos de objetos y de compilación

Para propósitos de comparación, los nombres de la matriz local son diferentes (vla contra fla), y las dimensiones de la matriz son diferentes cuando se declara; de lo contrario, los archivos son los mismos.

Compilé usando:

$ 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ánto de los gastos generales es fijo y cuánto es variable, pero hay gastos generales al usar un VLA.

  • La línea “vla[i][i] = 1;” necesita una afirmación adicional (n == m). Mejor sería poner “vla[i][j] = ? yo==j? 1: 0; ” en el bucle interior. YMMV.

    – salvaje

    8 oct 2011 a las 17:51

Me pregunto si hay alguna sobrecarga por el uso de matrices 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 tiempo de ejecución?

Si.

¿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 tiempo de compilación.

Asignación dinámica (malloc) almacenará la matriz en el montónque tiene un gran espacio de memoria, pero es más lento de acceder.

VLA funciona colocando la matriz en el apilar. 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 desborda la pila, es indistinguible de una recursividad infinita.

  • Guau, ¡un empate por el tiempo en nuestras respuestas!

    –Jonathan Leffler

    9 de enero de 2010 a las 20:03


  • Y vea mi respuesta (modificada) para ilustrar que hay una sobrecarga de tiempo de ejecución para usar VLA, al menos en algunas implementaciones de compilador (usando GCC 4.4.2 en Sun SPARC y Solaris 10 como ejemplo específico).

    –Jonathan Leffler

    9 de enero de 2010 a las 20:24

  • No hay motivo para pensar que el acceso al montón es más lento. La asignación y desasignación son más lentas que la asignación y desasignación de pila (que solo requieren ajustar el puntero de pila), pero una vez que se asigna un objeto, es solo otro objeto en la memoria.

    –Keith Thompson

    8 oct 2011 a las 18:13

  • @KeithThompson: Hm, ¿almacenamiento en caché de memoria?

    – kennytm

    8 oct 2011 a las 18:20

  • (¿Cómo) puede averiguar el tamaño máximo permitido para un VLA y qué sucede si lo excede? (Referencias estándar bienvenidas.)

    – KerrekSB

    30 de diciembre de 2013 a las 10:03

Debería haber muy poca sobrecarga para los VLA (como máximo, debería resultar en una adición al puntero de pila). La asignación dinámica requiere una administración de memoria manual y es más lenta que la asignación basada en pilas 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, provocará un comportamiento indefinido, por lo tanto, 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 comandos, pero tendría que escribir el código para manejarlo usted mismo.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad