C'è qualche overhead per l'utilizzo di matrici a lunghezza variabile?

Question

C'è qualche sovraccarico di utilizzo di matrici a lunghezza variabile? Potrebbe la dimensione della matrice essere passata attraverso la linea argomento di comando in fase di esecuzione? Perché è introdotto, rispetto a automatica e assegnare dinamicamente un array?

Answer 1

VLA ha un certo overhead (rispetto al "normale" di nome compile-time di dimensioni array).

lunghezza runtime In primo luogo, è ancora e la lingua che fornisce i mezzi per ottenere la dimensione effettiva della matrice in fase di esecuzione (utilizzando sizeof). Ciò significa immediatamente che la dimensione effettiva della matrice deve essere memorizzato da qualche parte. Ciò si traduce in qualche insignificante overhead di memoria per-array. Tuttavia, dal momento che i VLA può essere dichiarata solo come oggetti automatici, questo overhead di memoria non è qualcosa che chiunque avrebbe mai notato. E 'proprio come dichiarare una variabile in più locali di tipo integrale.

In secondo luogo, VLA è normalmente allocato sulla pila, ma a causa della sua dimensione variabile, nel caso generale la posizione esatta in memoria non è noto al momento della compilazione. Per questo motivo l'implementazione sottostante deve normalmente implementarlo come un puntatore a un blocco di memoria. Questo introduce un certo overhead memoria aggiuntiva (per il puntatore), che è ancora completamente insignificante per le ragioni sopra descritte. Questo introduce anche lieve sovraccarico delle prestazioni, dal momento che dobbiamo leggere il valore del puntatore al fine di trovare la matrice reale. Questo è lo stesso in testa che si ottiene quando si accede array malloc-ed (e non si ottiene con gli array di dimensioni compile-time-nome).

Poiché la dimensione del VLA è un valore intero runtime, può, naturalmente, essere passato come argomento della linea di comando. VLA non importa dove la sua dimensione viene.

VLA sono stati introdotti come runtime dimensioni array basso costo allocazione / deallocazione con. Si inseriscono tra gli array "ordinarie" di nome compile-time dimensioni (che hanno praticamente pari a zero costi di allocazione-deallocazione, ma dimensione fissa) e array malloc Misto (dimensioni in fase di esecuzione che sono, ma il costo relativamente alto allocazione-deallocazione).

VLA obbediscono [quasi] la stessa portata-dipendente norme durata come oggetti automatici (cioè locali), il che significa che nel caso generale non possono sostituire le matrici malloc-ed. Essi applicabilità è limitata a situazioni in cui è necessario un array di dimensioni in fase di esecuzione veloce con una tipica vita automatica.

Answer 2

Non è certo overhead di run-time con le matrici a lunghezza variabile, ma si dovrebbe essere a lavorare abbastanza difficile per misurarla. Si noti che sizeof(vla) non è una costante della fase di compilazione se vla è una matrice di lunghezza variabile.

La dimensione della matrice può essere passato a una funzione in fase di esecuzione. Se si sceglie di prendere la dimensione da un argomento riga di comando e convertire in un numero intero e passare che alla funzione a run-time, così sia -. Funzionerà

array di lunghezza variabile vengono utilizzati perché le variabili sono automaticamente assegnati alla dimensione corretta e liberati automaticamente all'uscita dalla funzione. Questo evita sovra-allocazione dello spazio (l'allocazione di spazio sufficiente per la dimensione massima possibile quando si lavora per lo più con dimensioni minime), ed evita problemi di memoria ripulire.

Inoltre, con gli array multidimensionali, per quanto ne so si comporta più come Fortran - è possibile configurare in modo dinamico tutte le dimensioni, piuttosto che essere bloccato con dimensioni fisse per tutti, ma la dimensione principale della matrice.

---

prova concreta di un certo overhead runtime per VLA -. Almeno con GCC 4.4.2 su SPARC (Solaris 10)

Si considerino i due file di seguito:

vla.c - utilizzando una matrice di lunghezza variabile

#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 - utilizzando una matrice di lunghezza fissa

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

Compilation e file oggetto formati

A titolo di confronto, i nomi della matrice locale sono diverse (vla vs fla), e le dimensioni dell'array sono diverse quando viene dichiarato -. In caso contrario, i file sono gli stessi

I compilato utilizzando:

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

Le dimensioni dei file oggetto sono un po 'diverso - come misurato sia con 'ls' e 'size':

$ 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

Non ho fatto test approfonditi per vedere quanto del sovraccarico è fisso e quanto è variabile, ma c'è in testa nell'uso di un VLA.

Answer 3

  

Mi chiedo solo se c'è qualche sovraccarico di utilizzo di matrici a lunghezza variabile?

No

  

Può il dimensione della matrice potrebbe essere passata attraverso argomento della riga di comando in fase di esecuzione?

Sì.

  

Perché è introdotto, rispetto a automatica e assegnare dinamicamente un array?

Automatica attribuita lo consente solo una dimensione fissa noto in fase di compilazione.

dinamicamente l'assegnazione (malloc) memorizzerà la matrice sulla mucchio , che ha un grande spazio di memoria, ma è più lento di accesso.

VLA funziona inserendo la matrice nel pila . Questo rende assegnazione e accesso estremamente veloce, ma la pila è solitamente piccolo (di pochi KB), e quando il VLA traboccava stack, è indistinguibile da una ricorsione infinita.

Answer 4

Ci dovrebbe essere molto poco overhead per i VLA (Al massimo si dovrebbe tradursi in un'aggiunta alla stack pointer). allocazione dinamica richiede una gestione manuale della memoria ed è più lenta di allocazione basata su stack di un VLA e dichiarazione "automatico" di un array richiede un'espressione fase di compilazione per la dimensione dell'array. Tuttavia, tenere presente che se si verifica un overflow dello stack, causerà un comportamento indefinito, in modo da mantenere i VLA relativamente piccolo.

È possibile passare la dimensione di un array tramite un argomento della riga di comando, ma si dovrà scrivere il codice per gestire quel te stesso.