2001: Odissea nell'ottimizzazione considerazioni sull'ottimizzazione del codice in C

HAL9000: Nessun calcolatore 9000 ha mai commesso un errore o alterato un'informazione. Noi siamo, senza possibili eccezioni di sorta, a prova di errore, e incapaci di sbagliare.

In 2001: Odissea nello spazio il computer HAL9000 era così sicuro di essere infallibile che sabotò la missione (oops: spoiler!... va beh, ma è un film del 1968, se non l'avete ancora visto sarà mica colpa mia...). Ecco, in questo articolo tratteremo un argomento spinoso, l'ottimizzazione del codice, che andrà a toccare miti e leggende (urbane) su cui molti colleghi programmatori hanno certezze magari un po' datate. Sarò costretto a dire delle eresie, delle cose poco ortodosse, ma cercherò, come sempre, di usare un linguaggio il più possibile soft, perché non mi sento ancora preparato per finire sul rogo dell'Inquisizione Informatica.

...ottimizzare il codice noonnnn serxyzh!!11wu?ve aaa nizxrn!!11mm-x?ente....

Come ho appena detto: un tema spinoso, su cui ho già scritto in passato. Ma i tempi cambiano, l'informatica avanza, i compilatori crescono e si fanno adulti... e il mio vecchio articolo è diventato obsoleto (anzi, peggio: deprecated), e non ho nessuna difficoltà ad ammetterlo (non sono mica HAL9000!): i risultati dei test di allora (era il 2012) ora non sono più validi. E quindi non sono più valide neanche le conclusioni. Comunque, prima di andare avanti vi spoilero il piano dell'articolo, così nessuno potrà dire che non vi avevo avvertito prima (potete saltare la lettura del piano se vi piacciono le sorprese: attenzione SPOILER):

Piano dell'articolo

1. Le basi: la descrizione sommaria di cosa è e cosa non è una ottimizzazione.
2. L'illusione: la descrizione di alcune promettenti forme di ottimizzazione (solo alcune tra le mille disponibili, eh!).
3. La delusione: il test sperimentale che dimostra l'inutilità del punto 2.
4. Il Gran Finale: le ultime considerazioni e le parole di un profeta che aveva già previsto tutto questo.

1. Le basi
Chiariamo subito una cosa: le ottimizzazioni di cui parleremo sono quelle strettamente legate al codice, alle istruzioni di base. Non si parla di algoritmi, perché è evidente che quelli si che devono essere ottimizzati: se voglio fare un sort dei valori in un grande array è meglio scrivere un quick-sort che un insertion-sort! E, tornando alle istruzioni di base, anche qui bisogna fare dei distinguo: ad esempio, se devo aggiungere cinque volte lo stesso un valore ad una variabile e lo faccio con un loop non è una ottimizzazione, è semplice senso comune! Quindi vediamo un po' di codice per spiegare meglio l'argomento:

#include <stdio.h>
#include <time.h>

// funzione main
int main(int argc, char ** argv)
{
    int array[5];

    // VERSIONE STUPIDA (senza senso comune)
    int i = 0;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;
    i++;
    array[i] = i * 2;

    printf("Test 1: array[4] = %d\n", array[4]);

    // VERSIONE BASE (con senso comune)
    int n;
    for (n = 0; n < 5; n++)
        array[n] = n * 2;

    printf("Test 2: array[4] = %d\n", array[4]);

    // VERSIONE OTTIMIZZATA: è la base con shift logico invece di moltiplicazione
    int k;
    for (k = 0; k < 5; k++)
        array[k] = k << 1;

    printf("Test 3: array[4] = %d\n", array[4]);

    return 0;
}

Come si nota nel semplicissimo esempio, abbiamo un problema e lo possiamo risolvere in maniera "stupida", "normale" o "ottimizzata": sulla maniera "stupida" preferisco non commentare, mentre su quella ottimizzata faccio notare che ho usato uno Shift Logico al posto della (dispendiosa) moltiplicazione per due.

E per chiudere questa sezione non posso non citare una tra le tante Leggende Urbane che girano nella comunità C: quella secondo cui è meglio mettere la definizione di una variabile fuori da un loop "se no ogni volta che si entra nel loop viene allocata nuovamente e il programma rallenta"... Quindi, secondo alcuni, quando è stato introdotto nel C il concetto di scope grazie al quale possiamo (tra le altre cose) dichiarare e usare una variabile solo dove serve, si sono dimenticati di dirci di non usare questa caratteristica perché "rallenta il codice"... ma si, continuiamo così, facciamoci del male. Vabbè, vi propongo un piccolo esempio di codice da compilare per estrarre l'assembly (ad esempio con gcc -S): vedrete che le due funzioni (una con variabile dentro il loop e l'altra con la variabile fuori) generano lo stesso codice: Leggenda Urbana, confermato.

#include <stdio.h>

// prototipi locali
int test1(int array[], int nelems);
int test2(int array[], int nelems);

// funzione main
int main(int argc, char ** argv)
{
    int array[5];

    // Test 1
    test1(array, 5);
    printf("Test 1: array[4] = %d\n", array[4]);

    // Test 2
    test2(array, 5);
    printf("Test 2: array[4] = %d\n", array[4]);

    return 0;
}

// funzione test1()
int test1(
    int array[],
    int nelems)
{
    // riempio array
    int n;  // n dichiarato fuori dal loop
    int i;
    for (i = 0; i < nelems; i++) {
        n = i * 2;
        array[i] = n;
    }
}

// funzione test2()
int test2(
    int array[],
    int nelems)
{
    // riempio array
    int i;
    for (i = 0; i < nelems; i++) {
        int n;  // n dichiarato dentro il loop
        n = i * 2;
        array[i] = n;
    }
}

2. L'illusione
Allora, stiamo parlando di ottimizzazione del codice, quindi di un argomento vastissimo (ci sono moltissime tecniche e moltissimi casi), ma visto che il tempo e la dimensione dell'articolo hanno dei limiti cercheremo di ottimizzare (!?) focalizzandoci solo su un tipo classico, anche perché il risultato finale (come vedremo nel punto 3) dovrebbe essere sempre (più o meno) lo stesso. E quale è la principale fonte di lentezza in una applicazione? ma è lui, è il (grande) loop! Quindi ho scritto sei piccoli esempi che riprendono i casi "base" e "ottimizzato" dell'esempio nel punto 1, vediamoli:

// TEST 1 - versione con moltiplicazione, array e indice
int array[1000];
int i;
for (i = 0; i < 1000; i++)
    array[i] = i * 2;

// TEST 2 - versione con calcolo incrementale invece di moltiplicazione
int array[1000];
int i, incr;
for (i = 0, incr = 0; i < 1000; i++) {
    array[i] = incr;
    incr += 2;
}

// TEST 3 - versione con calcolo incrementale e pointer invece di array
int array[1000];
int *ptr = array;
int i, incr;
for (i = 0, incr = 0; i < 1000; i++, ptr++) {
    *ptr = incr;
    incr += 2;
}

// TEST 4 - versione con calcolo incrementale, pointer e senza indice
int array[1000];
int *ptr = array;
int limit = 1000 * 2;
int incr;
for (incr = 0; incr < limit; incr += 2, ptr++)
    *ptr = incr;

// TEST 5 - versione con shift logico invece di moltiplicazione
int array[1000];
int i;
for (i = 0; i < 1000; i++)
    array[i] = i << 1;

// TEST 6 - versione con shift logico e pointer invece di array
int array[1000];
int *ptr = array;
int i;
for (i = 0; i < 1000; i++, ptr++)
    *ptr = i << 1;

Evidentemente la funzione Test 1 (già vista all'inizio dell'articolo) è semplicissima, però contiene un loop, e se la dimensione dell'array è molto grande potrebbe diventare dispendiosa. Ho provato a ottimizzarla usando due tecniche, la Strength Reduction e la Induction Variable, e attraverso vari passaggi (Test 2 e Test 3) si arriva alla versione super-ottimizzata in Test 4. Dato che c'ero ho riproposto in Test 5 la versione semplice ma con shift logico al posto della moltiplicazione e, infine, in Test 6 troviamo un ibrido con pointer al posto dell'array e shift logico al posto della moltiplicazione.

E a questo punto è doveroso uscire dalla teoria ed entrare nella pratica, quindi ho scritto un piccolo benchmark per analizzare i risultati delle varie versioni. Ho usato un grandissimo loop (se no i risultati sarebbero stati impossibili da valutare) e... vediamo i risultati (con GCC 7.4.0/Linux 4.15.0/Intel I7):

TEST con array di dimensione 0xfffffff

TEST con compilazione gcc senza ottimizzazioni
Test 1: Tempo trascorso: 0.903985 secondi
Test 2: Tempo trascorso: 0.881661 secondi
Test 3: Tempo trascorso: 0.863433 secondi
Test 4: Tempo trascorso: 0.844027 secondi
Test 5: Tempo trascorso: 0.899836 secondi
Test 6: Tempo trascorso: 0.896226 secondi

TEST con compilazione gcc con ottimizzazione -O1
Test 1: Tempo trascorso: 0.366814 secondi
Test 2: Tempo trascorso: 0.365151 secondi
Test 3: Tempo trascorso: 0.352550 secondi
Test 4: Tempo trascorso: 0.351188 secondi
Test 5: Tempo trascorso: 0.366156 secondi
Test 6: Tempo trascorso: 0.356479 secondi

TEST con compilazione gcc con ottimizzazione -O2
Test 1: Tempo trascorso: 0.359824 secondi
Test 2: Tempo trascorso: 0.363385 secondi
Test 3: Tempo trascorso: 0.362589 secondi
Test 4: Tempo trascorso: 0.356611 secondi
Test 5: Tempo trascorso: 0.361608 secondi
Test 6: Tempo trascorso: 0.362675 secondi

TEST con compilazione gcc con ottimizzazione -O3
Test 1: Tempo trascorso: 0.299029 secondi
Test 2: Tempo trascorso: 0.286266 secondi
Test 3: Tempo trascorso: 0.290292 secondi
Test 4: Tempo trascorso: 0.287927 secondi
Test 5: Tempo trascorso: 0.305653 secondi
Test 6: Tempo trascorso: 0.316873 secondi

Allora: effettivamente la versione Test 4 va meglio delle altre, ma il miglioramento è irrisorio, e i risultati con le ottimizzazioni del compilatore... beh, forse è meglio passare al punto 3.

3. La delusione
Ebbene si: dai risultati dei test si evince che:

• le "ottimizzazioni manuali" sono poco effettive.
• il compilatore ottimizza molto meglio di noi (ma che strano!), perfino usando la blanda opzione -O1.
• il compilatore ottimizza un po' anche senza dirglielo, vedi il risultato (senza ottimizzazioni) di Test 1 rispetto a quello di Test 5, ad esempio.

Il fatto è (e bisogna farsene una ragione) che le ottimizzazioni descritte (Strength Reduction, Induction Variable, e mille altre) le usa già il compilatore, nei punti e nelle maniere che ritiene più opportune, e quindi, se noi cerchiamo di ottimizzare già a livello di scrittura delle istruzioni base, stiamo perdendo tempo e energie per un lavoro che non è compito nostro (questo magari non era vero in passato ma ora lo è). Ed è altamente probabile che il compilatore farà questo lavoro meglio di noi. Ovviamente qui abbiamo visto solo una minima parte delle possibili "ottimizzazioni manuali" ma, in generale, il discorso fatto vale per tutte.

Solo mi preme precisare che le ottimizzazioni forzate (con GCC sono indicate con -O1, -O2 e -O3) bisogna usarle con cautela crescente in base al numero: -O1 si può usare quasi sempre, mentre -O2 in alcuni casi particolari può provocare comportamenti strani e -O3 è ancora più critico: infatti bisogna ricordarsi che un compilatore, anche se buono, è stato scritto da persone (non da HAL9000!) quindi può anche contenere bugs, e poi il processo di ottimizzazione interno è abbastanza complicato, anche perché contiene delle "decisioni" interne del compilatore che con un codice possono funzionare perfettamente mentre con un altro codice non funzionano altrettanto bene. Detto questo credo che ora siamo pronti per il punto 4.

4. Il Gran Finale
Nel mio vecchio articolo chiedevo: "Quando scrivo codice devo farlo in maniera naturale, o meglio, istintiva (beh, sempre se si possiede l'istinto del Programmatore...) o devo seguire linee un po' astruse ed ermetiche per rendere il programma più efficiente?". E chiedevo anche: "Vale la pena di trasformare un codice leggibile e chiaro come quello di Test 1 in uno molto più criptico, come ad esempio quello di Test 4, solo perché non ci fidiamo del compilatore?". La risposta è evidente: lasciamo questo lavoro al compilatore e concentriamoci sullo scrivere del buon codice, chiaro, leggibile, manutenibile, ben strutturato, con una architettura coerente e solida, ecc., ecc.: vivremo più tranquilli e faremo anche un bel favore a chi dovrà, un giorno, mettere le mani sul nostro lavoro. 

E, come promesso, concludo con le parole di un profeta, uno di quelli che hanno scritto la storia dell'informatica e da cui c'è sempre qualcosa da imparare, anche a distanza di molti anni:

"The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming" [Donald Ervin Knuth, "Computer Programming as an Art", 1974]

Ciao e al prossimo post!