Nei titoli e nei testi troverete qualche rimando cinematografico (ebbene si, sono un cinefilo). Se non vi interessano fate finta di non vederli, già che non sono fondamentali per la comprensione dei post...

Di questo blog ho mandato avanti, fino a Settembre 2018, anche una versione in Spagnolo. Potete trovarla su El arte de la programación en C. Buona lettura.

domenica 14 maggio 2017

Il buono, il brutto, il VLA
come usare i Variable Length Arrays in C - pt.1

La referenza cinematografica di questo mese calza proprio a pennello: un Variable Length Array (VLA per gli amici) sarebbe perfetto per fare la parte del cattivo nel capolavoro "Il buono, il brutto, il cattivo" del mitico Sergio Leone. E alla fine del (prossimo) post sarà chiaro il perché.
...ciao sono un VLA: inizia a preoccuparti...
I VLAs sono una cosa relativamente nuova del C: sono stati introdotti nel C99, e sono, apparentemente, il sogno fatto realtà del mondo C: "Finalmente gli array con dimensione variabile! Ah, se li avessi avuti prima del '99!" Allora: l'idea è semplice, con un VLA potete scrivere cosucce tipo queste:
void myVla(
    int size1,
    int size2)
{
    // il mio VLA di int
    int ivla[size1];

    // fai qualcosa con il VLA di int
    ...

    // il mio VLA bidimensionale di float
    float fvla[size1][size2]:

    // fai qualcosa con il VLA bidimensionale di float
    ...
}
Fantastico, no? Troppo bello per essere vero... ma ci saranno delle controindicazioni? Sicuramente non nelle prestazioni: ho scritto giustappunto un po' di codice per testare le prestazioni dei VLAs rispetto alle alternative più immediate: array dinamici (con malloc()) e array statici (in heap e stack). Vai col codice!
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define MYSIZE  1000000

// variabile dummy per evitare lo svuotamento totale delle funzioni usando GCC -O2
int avoid_optimization;

// prototipi locali
void testVLA(int size);
void testMallocVLA(int size);
void testStackFLA(int dum);
void testHeapFLA(int dum);
void runTest(int iterations, void (*funcptr)(int), int size, const char *name);

// funzione main()
int main(int argc, char* argv[])
{
    // test argomenti
    if (argc != 2) {
        // errore: conteggio argomenti errato
        printf("%s: wrong arguments counts\n", argv[0]);
        printf("usage: %s vla iterations [e.g.: %s 10000]\n", argv[0], argv[0]);
        return EXIT_FAILURE;
    }

    // estrae iterazioni
    int iterations = atoi(argv[1]);

    // esegue test
    runTest(iterations, &testVLA, MYSIZE, "testVLA");
    runTest(iterations, &testMallocVLA, MYSIZE, "testMallocVLA");
    runTest(iterations, &testStackFLA, 0, "testStackFLA");
    runTest(iterations, &testHeapFLA, 0, "testHeapFLA");

    // esce
    return EXIT_SUCCESS;
}

// funzione runTest()
void runTest(
    int        iterations,      // iterazioni del test
    void       (*funcptr)(int), // funzione di test
    int        size,            // size dell'array
    const char *name)           // nome funzione di test
{
    // prende start time
    clock_t t_start = clock();

    // esegue iterazioni test
    for (int i = 0; i < iterations; i++)
        (*funcptr)(size);

    // prende end time e mostra il risultato
    clock_t t_end = clock();
    double t_passed = ((double)(t_end - t_start)) / CLOCKS_PER_SEC;
    printf("%-13s -  Tempo trascorso: %f secondi\n", name, t_passed);
}

// funzione testVLA()
void testVLA(
    int size)       // size per VLA
{
    int vla[size];

    // loop di test
    for (int i = 0; i < size; i++)
        vla[i] = i;

    // istruzione per evitare lo svuotamento totale della funzione usando GCC -O2
    avoid_optimization = vla[size / 2];
}

// funzione testMallocVLA()
void testMallocVLA(
    int size)      // size per malloc()
{
    int *mallocvla = malloc(size * sizeof(int));

    // loop di test
    for (int i = 0; i < size; i++)
        mallocvla[i] = i;

    // istruzione per evitare lo svuotamento totale della funzione usando GCC -O2
    avoid_optimization = mallocvla[size / 2];

    free(mallocvla);
}

// funzione testStackFLA()
void testStackFLA(
    int dum)        // parametro dummy
{
    int stackfla[MYSIZE];

    // loop di test
    for (int i = 0; i < MYSIZE; i++)
        stackfla[i] = i;

    // istruzione per evitare lo svuotamento totale della funzione usando GCC -O2
    avoid_optimization = stackfla[MYSIZE / 2];
}

// funzione testHeapFLA()
int heapfla[MYSIZE];
void testHeapFLA(
    int dum)        // parametro dummy
{
    // loop di test
    for (int i = 0; i < MYSIZE; i++)
        heapfla[i] = i;
}
Qui, come sempre, copio-e-incollo quello che scrivo sempre dopo aver mostrato il codice (squadra che vince non si cambia...): Ok, come vedete è ampiamente commentato e quindi è auto-esplicativo, per cui non mi dilungherò sulle singole istruzioni e/o gruppi di istruzioni (leggete i commenti! sono li per quello!), ma aggiungerò, solo, qualche dettaglio strutturale.

Allora: visto che si tratta di un test comparativo ho scritto una funzione runTest() che chiama n-iterazioni della funzione da testare e conta il tempo impiegato. Il main() si limita a chiamare quattro volte runTest(), una per ogni funzione. Le quattro funzioni di test che ho scritto testano (come richiamato dai nomi, ovviamente): un C99-VLA, un tradizionale malloc-VLA, un Fixed-LA allocato nello stack e un Fixed-LA allocato nello heap. Per ogni test viene usato un (gran) array-size di 1000000 e il numero di iterazioni si decide al lancio dell'applicazione (questo è molto utile come vedremo tra poco).

Notare che runTest() usa un function pointer per lanciare il test (avevamo visto qualcosa del genere parlando qui delle callback): ho usato la versione estesa della dichiarazione (void (*funcptr)(int) + passaggio della funzione con l'operatore &) ma vi ricordo che, ad esempio, GCC digerisce facilmente anche la dichiarazione semplificata (void funcptr(int) + passaggio senza l'operatore &). La versione estesa è, ovviamente, più portatile. E visto che siamo in tema di compilatori: anche se i VLAs (e i loop for (int...)) che uso nel codice di questo mese sono ammessi solo da C99 in avanti non c'è bisogno (se usate GCC) di specificare il flag -std=c99 in compilazione: le versioni recenti di GCC includono di default (come minimo) anche il C99 (oltre alle estensioni del GNU C): se proprio volete essere sicuri che quello che avete scritto rispetta uno standard in particolare  dovete usare altri flag: ad esempio, se volete scrivere usando solo il C89, dovete aggiungere sulla linea di compilazione: -std=c89 -pedantic. Se poi state usando un GCC più datato allora la compilazione dell'esempio vi darà warning e/o errori, e dovrete ricompilare forzando la compatibilità col C99.

(...Nota: grazie alla segnalazione di Ponchietto, un lettore attento e preparato, mi sono reso conto che avevo dimenticato di aggiungere, in ogni funzione di test, una semplice istruzione che usasse l'array creato, così da evitare che l'ottimizzatore del GCC azzerasse il contenuto della funzione stessa (visto che l'array non lo usava nessuno). Ovviamente così i risultati dei test con ottimizzazione cambiano. Adesso il post ha codice e risultati rinnovati...)

I risultati sono i seguenti:
aldo@ao-linux-nb:~/blogtest$ gcc vla.c -o vla
aldo@ao-linux-nb:~/blogtest$ ./vla 2000
testVLA       -  Tempo trascorso: 4.263985 secondi
testMallocVLA -  Tempo trascorso: 3.641929 secondi
testStackFLA  -  Tempo trascorso: 4.292963 secondi
testHeapFLA   -  Tempo trascorso: 4.285660 secondi
aldo@ao-linux-nb:~/blogtest$ gcc -O2 vla.c -o vla
aldo@ao-linux-nb:~/blogtest$ ./vla 2000
testVLA       -  Tempo trascorso: 0.767087 secondi
testMallocVLA -  Tempo trascorso: 0.690925 secondi
testStackFLA  -  Tempo trascorso: 0.678178 secondi
testHeapFLA   -  Tempo trascorso: 0.687785 secondi
Come vedete ho eseguito due test con/senza ottimizzazione (flag GCC -O2) e, ovviamente, è tornato utile il parametro n-iterazioni dell'applicazione, che mi ha permesso di trovare un valore adatto a ottenere risultati significativi e, allo stesso tempo, a evitare tempi di esecuzione biblici per la versione senza ottimizzazioni. Come possiamo commentare? Beh, il VLA se la cava egregiamente, con/senza ottimizzazioni! Ottiene, praticamente, gli stessi risultati del suo diretto concorrente, il malloc-VLA, ed è più semplice da usare!

Allora, torniamo al pezzo: VLA approvato!

MA PERÒ...

beh, il però del VLA cattivo ve lo spiegherò meglio nel prossimo post, e sappiate che non è tutto oro quello che luccica... e tanto per farvi un piccolo spoiler sulle considerazioni finali: io non uso mai i VLAs nel codice che scrivo!

Ciao e al prossimo post!