C'era una volta l'Ottimizzazione come ottimizzare il codice C

To be, or not to be, that is the question: Whether 'tis Nobler in the mind to suffer... oops, forse ho sbagliato blog. Non é questo il blog di letteratura inglese? È un blog di programmazione C? Va beh, dato che ci sono, basta modificare un po' la domanda: Ottimizzare, o non ottimizzare, questo è il dilemma...

La domanda in realtà sarebbe: "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, ovviamente, non sto parlando di algoritmi: in questo caso è evidente che un buon algoritmo è preferibile a uno cattivo. Sto parlando a livello di istruzioni e gruppi di istruzioni.

Facciamo una premessa: siamo nel 2012 (quasi 2013). E di conseguenza dobbiamo comportarci. Anticamente i computer erano (rispetto a ora) lenti e con poche risorse, e i compilatori erano molto più semplici di quelli odierni. E, a quei tempi, usando la parola magica register era possibile velocizzare un loop e, se si riusciva a scrivere qualche linea di codice in meno (vedi nota esplicativa), si ottenevano programmi molto più performanti. Ma ora? Ha ancora senso scrivere codice così? Il compilatore ha veramente bisogno del nostro aiuto ?

nota esplicativa  
(...a 6 anni di distanza dalla pubblicazione ho scoperto, grazie alla segnalazione del mio ottimo collega Andrea Simone Costa, che l'espressione "...qualche linea di codice in meno..." si può facilmente fraintendere. Beh, come tutti ben sanno, l'efficienza del codice non è inversamente proporzionale al numero di linee scritte (e questo si può ben vedere sia negli esempi successivi di questo post sia in un post più recente che vi invito a leggere) ma dipende da ben altri fattori. Il senso della sfortunata espressione "...qualche linea di codice in meno..." è da intendere come: "...scrivere un codice ridotto all'osso omettendo qualsiasi operazione (apparentemente) superflua...", il che portava, nella migliore delle ipotesi, a scrivere in assembly le parti critiche e/o ad usare espressioni "criptiche" come quelle che vedremo tra poco (che miglioravano l'efficienza rendendo illeggibile il codice). E nella peggiore delle ipotesi... vabbe', potete immaginarvi cosa si poteva arrivare a fare per ridurre (in tutti i sensi) un programma che doveva girare su un vecchio sistema embedded con risorse inesistenti... Ecco, questo è quanto, spero che questa nota abbia chiarito l'equivoco...)

La faccenda è complessa, e credo che richiederà piú di una puntata. In questa, tanto per cominciare, analizziamo un esempio facile facile (?), l'ottimizzazione di un loop, che è, come noto, una parte (anzi, La Parte) critica per le prestazioni di un programma. Cominciamo:

// myFunc1()
// versione con moltiplicazione, array e indice
int myFunc1(int array[], int nelems)
{
    int i;
    for (i = 0; i < nelems; i++)
        array[i] = i * 2;
}

La funzione è semplicissima, però contiene un loop, e se nelems è molto grande potrebbe diventare dispendiosa. Proviamo a ottimizzarla usando due tecniche, la Strength Reduction e la Induction Variable: vediamo, attraverso vari passaggi cosa possiamo ottenere:

// myFunc2()
// versione con incremento invece di moltiplicazione
int myFunc2(int array[], int nelems)
{
    int i, incr;
    for (i = 0, incr = 0; i < nelems; i++) {
        array[i] = incr;
        incr += 2;
    }
}

// myFunc3()
// versione con incremento e pointer invece di array
int myFunc3(int array[], int nelems)
{
    int *ptr = array;
    int i, incr;
    for (i = 0, incr = 0; i < nelems; i++, ptr++) {
        *ptr = incr;
        incr += 2 ;
    }
}

// myFunc4()
// versione con incremento, pointer e senza indice
int myFunc4(int array[], int nelems)
{
    int *ptr = array;
    int limit = nelems * 2;
    int incr;
    for (incr = 0; incr < limit; incr += 2, ptr++)
        *ptr = incr;
}

Come promesso e premesso, in questo post non voglio limitarmi a proporre tecniche di ottimizzazione senza fornire dati, per cui ho scritto un programma di test e, sulla mia macchina, con un valore di nelems abbastanza grande (0xFFFFFFF) i risultati sono questi:

- compilazione senza ottimizzazione
myFunc1 - Tempo trascorso: 1.720000 secondi.
myFunc2 - Tempo trascorso: 1.340000 secondi.
myFunc3 - Tempo trascorso: 1.160000 secondi.
myFunc4 - Tempo trascorso: 0.920000 secondi.

Quindi, sembrerebbe che le tecniche di ottimizzazione funzionano. Proviamo, però, a compilare ottimizzando, ovvero lasciamo fare al compilatore: useremo la opzione -O2 di GCC. Vediamo i nuovi risultati:

- compilazione con ottimizzazione (-O2)
myFunc1 - Tempo trascorso: 0.940000 secondi.
myFunc2 - Tempo trascorso: 0.540000 secondi.
myFunc3 - Tempo trascorso: 0.540000 secondi.
myFunc4 - Tempo trascorso: 0.540000 secondi.

Ohhh, che sorpresa! Pare che il compilatore sia più bravo di noi! Usando l'opzione -O2, la versione non ottimizzata (myFunc1) si comporta, più o meno, come quella ottimizzata da noi (myFunc4) senza usare -O2. E non è una sorpresa: semplicemente vuol dire che il compilatore ha eseguito (probabilmente) le nostre stesse ottimizzazioni manuali. Notiamo poi che, usando una qualsiasi delle versioni ottimizzate manualmente, il compilatore riesce a aggiungere un ulteriore plus di miglioramento.

Tanto per confonderci ulteriormente le idee, facciamo un altro test, sostituendo la moltiplicazione per due con uno Shift Logico:

// myFunc2Bis()
// versione con shift logico invece di moltiplicazione
int myFunc2Bis(int array[], int nelems)
{
    int i;
    for (i = 0; i < nelems; i++)
        array[i] = i << 1;
}

E vediamo la velocità senza ottimizzazione del compilatore:

- compilazione senza ottimizzazione
myFunc2Bis - Tempo trascorso: 0.950000 seconds.

Toh, pare che usando lo shift logico da solo si ottiene lo stesso risultato che si ottiene applicando tutte le tecniche illustrate (myFunc4). E se usiamo anche l'opzione -O2 cosa succede ?

- compilazione con ottimizzazione (-O2)
myFunc2Bis - Tempo trascorso: 0.540000 seconds.

otteniamo lo stesso risultato ottimizzato visto sopra. Forse abbiamo scoperto il segreto del compilatore...

Prima conclusione (ma seguiranno altri capitoli): vale la pena di trasformare un codice leggibile e chiaro come quello di myFunc1() in uno molto più criptico, come ad esempio quello di myFunc4(), solo perché non ci fidiamo del compilatore? O, aggiungerei, perchè siamo così presuntuosi da pensare di poter fare meglio del compilatore? Mi ripeto: siamo nel 2012 (quasi 2013), e bisognerebbe comportarsi di conseguenza.

Per quello visto fin'ora, pare che l'unico aiutino manuale che possiamo dare è usare (quando possibile, e solo in punti veramente critici) shift logici invece di moltiplicazioni. In questo caso raccomando però l'aggiuntina di un commento, per evitare maledizioni da parte di chi legge il nostro codice. E se siete impazienti di scoprire altre utili informazioni sull'ottimizzazione, e non volete aspettare le mie prossime puntate (traditori!), vi consiglio di farvi il solito giro su Google, oppure di leggervi direttamente un ottimo articolo dell'altrettanto ottimo Carlo Pescio.

Io tornerò sull'argomento, cercando di aggiungere dati reali e lavoro di testing (visto che ho mantenuto la promessa!) agli studi solo teorici disponibili in rete. E se no che ci sto a fare io?

Ciao e al prossimo post.