Ottimizzare il codice

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Questa frase è stata attribuita a Donald E. Knuth, e se lo dice lui che ha scritto “The Art of Computer Programming”, ha inventato il TeX, e ha sviluppato la teoria della complessità degli algoritmi, potete stare certi che sia vero.

Il significato della frase è che bisognerebbe evitare di ottimizzare il codice prima di aver finito di scriverlo. Il modo di programmare “corretto” sarebbe:

  • primo, si scrive il codice nella maniera più semplice possibile, possibilmente in maniera elegante e leggibile
  • poi ci si accerta della sua correttezza (testing , debugging, e quello che pare a voi)
  • Infine, pensiamo alle performance, ottimizzando il codice dove necessario

Spesso invece il programmatore comincia fin dall’inizio a complicare il codice e la strrutra del programma, alla ricerca del programma già perfettamente ottimizzato. Nel fare così, spesso viene fuori codice molto complicato e probabilmente pieno di bug. Da qui la sentenza di Knuth: l’ottimizzazione prematura è la radice di tutti i mali!

L’osservazione chiave è che spesso il codice contiene alcuni (pochi) “colli di bottiglia”, ed è lì che l’ottimizzatore deve concentrarsi per far andare veloce il suo programma. Come identificare questi “colli di bottiglia”? Per esempio, funzioni chiamate molto frequentemente, strutture dati usate pesantemente in tutto il codice, ecc. I programmatori esperti ormai lo fanno ad occhio, ma per programmi molto grandi e complessi non è affatto facile. Sarebbe bene ci fosse qualche strumento di ausilio al programmatore.

oggi vediamo come fare analisi delle prestazioni con due tool disponibili su Linux con licenza GPL: valgrind e kcachegrind.

Il primo è una specie di “emulatore” del vostro PC. Prende in ingresso un file eseguibile, e lo esegue su un “processore virtuale”. Nel portare avanti l’esecuzione, però, è in grado di effettuare una serie di analisi sul codice. Valgrind è una piattaforma generica su cui sono stati sviluppati diversi strumenti. Il più famoso è memchek che serve a controllare l’uso della memoria, ed individuare possibili “memory leak“. Quello di cui ci occupiamo oggi, invece, è callgrind che serve a stimare le performance delle varie parti di codice del nostro programma.

Per installare questi tool, su Ubuntu si deve scrivere sul terminale:

sudo apt-get install valgrind
sudo apt-get install kcachegrind

e siamo pronti per i nostri esperimenti.

Proveremo ad utilizzarlo sui programmini che Juhan ci ha proposto per fare confronti fra il Fortran e vari altri linguaggi. Cominciamo dalla versione C/C++ di tale programma, che riporto qui per comodità (anche perché ho fatto due modifiche).

#include <stdio.h>
#include <math.h>

double f[14];

#define POW(x,y) pow(x,y)
//#define POW(x,y) mypow(x,y)

inline double mypow(double x, int y)
{
    double r = 1;
    for (int i=0; i<y; i++) r *= x;
    return r;
}

double fsin(double a) {
    return a - POW(a, 3) / f[3] + POW(a, 5) / f[5]
        - POW(a, 7) / f[7] + POW(a, 9) / f[9]
        - POW(a, 11) / f[11] + POW(a, 13) / f[13];
}

static double fcos(double a) {
    return 1.0 - POW(a, 2) / f[2] + POW(a, 4) / f[4]
        - POW(a, 6) / f[6] + POW(a, 8) / f[8]
        - POW(a, 10) / f[10] + POW(a, 12) / f[12];
}

static double myln(double x) {
    if (x == 0.0) {
        return -1.0e20;
    } else {
        double r = (x - 1.0) / (x + 1.0);
        return 2.0 * (r + POW(r, 3) / 3.0
                      + POW(r, 5) / 5.0
                      + POW(r, 7) / 7.0
                      + POW(r, 9) / 9.0);
    }
}

double mylog(double x) {
    static double ln10 = myln(10.0);

    return x / ln10;
}

int main(int argc, char **argv)
{

    int i, j;
    f[0] = 1.0;
    for (i = 1; i < 14; i++)
        f[i] = i * f[i - 1];
    int deg = 60;// * 60;
    int nsteps = 180 * deg;
    double step = M_PI / nsteps;
    double ssum;
    double csum;
    double a, s, c, t = 0.0;
    double ls, lc;
    for (j = 1; j < 11; j++)
    {
        ssum = 0.0;
        csum = 0.0;
        for (i = 0; i < nsteps; i++)
        {
            a = i * step;
            s = fsin(a);
            ls = mylog(myln(s));
            ssum += s;
            c = fcos(a);
            lc = mylog(myln(c));
            csum += c;
            if ((i % (10 * deg)) == 0)
            {
                if (c != 0.0)
                    t = s / c;
                printf("%3d %11.8f %11.8f %11.8f %15.8e\n", (i / deg), a, s, c, t);
                printf(" %15.8e %15.8e\n", ls, lc);
            }
        }
    }
    printf("%g\n", ssum);
    printf("%g\n", csum);
}

Le due modifiche fatte sono le seguenti: ho sostituito tutte le chiamate a pow() con la macro POW. Quest’ultima si traduce per il momento nella chiamata di libreria pow() (che, come discusso nel post precedente, è più lenta). Inoltre, ho diminuito il numero di cicli da svolgere per accorciare un po la durata dell’esecuzione: adesso il conto viene fatto per deg = 60 invece che per deg = 60*60 (vedi linea 54).

Salvate il programma qui su sul vostro HD con il nome prova.cpp, e poi compilatelo con il seguente comando:

g++ -g prova.cpp -o provacpp

Il flag -g serve per inserire i simboli di debug nel file eseguibile, e la qual cosa ci permetterà di associare il costo delle operazioni alle relative istruzioni nel codice sorgente.

Adesso siamo pronti per l’esecuzione, ecco il comando da dare:

valgrind --tool=callgrind ./provacpp

Questo manda in esecuzione il tool callgrind sul file eseguibile provacpp. Il quale viene eseguito a una velocità molto inferiore a quella normale (parliamo di un rallentamento di quasi 100 volte!) e vengono collezionati i dati di performance. L’output è un file che si chiama

callgrind.out.PID

Dove PID è l’ID del processo che è stato eseguito.
Per visualizzare i dati, date il comando:

kcachegrind callgrind.out.PID

(dove naturalmente avrete sostituito PID con il numero giusto), e si aprirà una finestra come questa:

La finestra principale di KCacheGrind

Questo tool ci visualizza i risultati dell’esecuzione. Faccio zoom sulla finesta a sinistra dove viene mostrato il “call graph” (ovvero il grafo delle chiamate):

Come vedete, il main() chiama le funzioni myln, fsin e fcos, e ciascuna chiama la funzione pow, la quale a sua volta chiama le funzioni interne per fare operazioni floating point. Subito sotto il nome delle funzioni viene riportato il tempo (in percentuale) speso dal programma dentro quella funzione. Questo programma ha speso il 95.73% del suo tempo dentro la funzione pow()! Notare anche una certa asimmetria: myln prende il 50% del tempo, mentre fsin e fcos ciascuna circa il 25%.

Adesso riproviamo utilizzando la funzione mypow() (quella che fa le moltiplicazioni per fare le potenze): basta commentare la linea 6 e scommentare la 7, e ricompilare. Se rifate tutto il percorso otterrete questo callgraph:

Come vedete, le cose sono un po’ cambiate. In particolare, mypow() non chiama alcuna funzione in floating point (come ci si aspetta), e inoltre le percentuali di myln, fsin e fcos sono un po’ cambiate.

È anche possibile mostrare questi numeri direttamente sul sorgente, cliccando sulla tab “Source Code”, ed ecco lo snapshot relativo:

Infine: si può fare una cosa del genera anche per il fortran? Ovviamente sì! Vi riporto semplicemente il comando di compilazione e di esecuzione:

gfortran -g m_c10l.f08 fc10l.f08 -o provaf
valgrind --tool=callgrind ./provaf

E poi tutto come prima. Ecco lo screenshot del callgraph per il fortran:

Qui notiamo che la funzione per la stampa a video (_gfortran_transfer_real_write) prende ben il 13% del tempo, ed è probabilmente lei la causa delle peggiori prestazioni del fortran rispetto al C/C++. Inoltre, notate come da nessuma parte ci sia una chiamata ad alcuna pow(), perché nel fortran l’elevazione a potenza per un numero intero è una operazione del linguaggio.

Ovviamente, questi tool funzionano bene per codice eseguibile, non funzionano affatto bene su Java e su Python. Ci sono però altri tool, più o meno professionali, che fanno cose analoghe. Semmai se ne parla un’altra volta!

Spero che questo post possa esservi utile nel vostro lavoro di “ottimizzatori!”, e ricordate le parole di Knuth!

Nota di Juhan: Mi ricordo il profiler id Borland; questo è molto più bello e anche il prezzo. Vero? Vero dikiyvolk?

Posta un commento o usa questo indirizzo per il trackback.

Commenti

  • Dikiyvolk  Il 25 luglio 2012 alle 22:42

    Io avevo usato il turbo profiler di borland e una libreria per trovare i memory leak in C++ di cui non mi ricordo il nome mi sembra un Shield… qualche cosa.
    Purtroppo non trovo più il mio tasto F1 per l’help.
    Il turbo profiler non faceva i grafici ed era ancora testuale, ma funzionava bene, proverò anche questo 🙂 mi piace ancora imparare cose nuove per mia fortuna.
    Riguardo al prezzo non tutto quello che si compra vale e neanche tutto quello che viene regalato 🙂

    “Quando sei nel dubbio scegli sempre il sentiero più difficile” FTC

  • dikiyvolk  Il 26 luglio 2012 alle 14:27

    Trovato!!! Ricordavo male il tools di Borland per i memory leak era ed è codeguard, niente Shield… anche se faceva molto più Star Trek 😀

    • glipari  Il 26 luglio 2012 alle 14:32

      Gli IDE Borland erano bellissimi, e Codeguard era un gran tool. A me mancano un sacco F4 e F5 …. va beh, tutto passa, e adesso devi accontentarti dei tool GPL ! 🙂

      • dikiyvolk  Il 26 luglio 2012 alle 14:47

        Non è proprio accontentarsi, ci sono ottimi tools opensource, come anche pessimi tools sia opensource che a pagamento.
        Si lavora con quello che si ha… certo che un bel IDE con tutto integrato è meglio che mettere le printf nel codice 🙂

        Quando è uscito il turbo pascal 4 con il debugger integrato a fine anni ’80 sono rimasto a bocca aperta vedendo il debug.

        Bei tempi… per il momento sulla mia opensuse ho installato sia valgrind che kcachegrind, così li provo.

  • juhan  Il 26 luglio 2012 alle 15:30

    L’ottimo al3hex https://twitter.com/al3hex segnala questo http://www.huyng.com/posts/python-performance-analysis per Python. Interessante anche se meno strepitoso di valgrind. Ma è colpa di Python, se producesse un eseguibile… O, meglio usarlo per quello che è.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: