Author Topic: Ottimizzazione - piccoli accorgimenti  (Read 924 times)

Offline CrashTest

Ottimizzazione - piccoli accorgimenti
« on: February 11, 2017, 05:38:08 PM »
Salve a tutti, ultimamente, lavorando ad un programma in C, mi è capitato di avere a che fare con qualche piccolo accorgimento riguardante l'ottimizzazione. Ho trovato poche informazioni in italiano quindi ho studiato dalle documentazioni di GCC e da vari articoli che parlano degli "internals" del linguaggio, decidendo di condividere questi, anche se piccoli, accorgimenti con voi: potrebbero tornarvi utili :D
Cercherò di essere il più chiaro possibile ed evitare fraintendimenti. Per comprendere questo articolo sono richieste delle conoscenze base relative ad array e puntatori.
Bene, dopo questa noiosa introduzione passiamo al dunque.

Nell'ottimizzazione di un programma, una delle prime cose da considerare è l'uso di array e indici. Per accedere ad un elemento di un array usando gli indici il compilatore dovrà eseguire una serie di calcoli, soprattutto moltiplicazioni. Il mio consiglio se si vuole ottimizzare un programma che fa largo uso di array è quello di vedere queste strutture per quello che realmente sono: un puntatore al primo elemento al quale applicare l'aritmetica dei puntatori. A primo impatto questo tipo di approccio potrebbe sembrare ostico, ma è abbastanza semplice, basta solo ragionarci un po' e una volta entrati nell'ottica diventa come contare normalmente. Usando l'aritmetica dei puntatori, l'incremento di un puntatore si riduce ad una banale somma che richiede molte meno risorse computazionali.
Snippets come quelli dell'esempio sottostante sarebbe meglio evitarli se il nostro obbiettivo è fare un programma molto più veloce ed ottimizzato.
Code: You are not allowed to view links. Register or Login
void somma_elementi(int *primo, int *secondo, int *somma, int elementi)
{
  for(int i = 0; i < elementi; i++)
    somma[i] = primo[i] + secondo[i] ;
}

Un'alternativa del tutto equivalente a questo codice (anche se migliorabile) potrebbe essere questa:
Code: You are not allowed to view links. Register or Login
void somma_elementi(int *primo, int *secondo, int *somma, int elementi)
{
  for(int i = 0; i < elementi; i++)
    *(somma + i) = *(primo + i) + *(secondo + i);
}

Possiamo notare come questo codice potrebbe essere riscritto in maniera leggermente differente e più chiara utilizzando l'operatore di post-incremento ottenendo uno snippet di questo tipo:
Code: You are not allowed to view links. Register or Login
void somma_elementi(int *primo, int *secondo, int *somma, int elementi)
{
  for(int i = 0; i < elementi; i++)
      *(somma++) = *(primo++) + *(secondo++);
}

Riflettendoci un attimo possiamo notare che le operazioni di post-incremento sono leggermente più lente di quelle di pre-incremento: questo perchè il compilatore è obbligato a conservare una copia del vecchio valore, restituirlo non ancora incrementato, eseguire il codice ed effettuare l'incremento. Se si tratta di poche iterazioni tutto questo non ha un peso rilevante, ma vi posso assicurare che su un numero eleveto di iterazioni la differenza in termini di prestazioni e complessità computazionale si nota. Per questo sono arrivato ad una soluzione che usi solo l'aritmetica dei puntatori e il pre-incremento.
Questo dovrebbe essere il risultato finale:
Code: You are not allowed to view links. Register or Login
void somma_elementi(int *primo, int *secondo, int *somma, int elementi )
{
    --primo;
    --secondo;
    --somma
    for(int i = 0; i < n; i++)
        *(++somma) = *(++primo) + *(++secondo);
}

Nello snippet qui sopra ho decrementato i puntatori per poi incrementarli nel ciclo for senza perdere informazioni. Arrivato a questo punto ero contento del mio programma perchè ero riuscito a ottimizzarlo e a compattare il codice. Però non è finita qui: c'è un grave errore nel mio programma, riuscite a notarlo da soli? Ok, ve lo dico nel caso non lo aveste notato. Parlando con un amico e rileggendo un attimo il manuale dell'ANSI C, nel paragrafo 6 (circa array e puntatori) ho notato che quello che avevo fatto non andava per niente bene: nonostante questo programma funzioni sulla quasi totalità delle CPU è presente un "undefined behavior", un comportamento indefinito. Decrementare il puntatore al primo elemento di un array non fa altro che farmi uscire dalla memoria dedicata all'array. Su alcuni compilatori o CPU questo non fa altro che bloccare il programma e lanciare una eccezione che potrebbe essere quella di Out of Memory o quella di Segmentation Fault. Per questo mi sono subito precipitato a correggere questo obbrobrio: avere codice non sicuro mi fa stare male. In questo caso la correzione era piuttosto banale e scontata, ve la mostro:
Code: You are not allowed to view links. Register or Login
void somma_elementi_ottimizzata(int *primo, int *secondo, int *somma, int elementi)
{
    for(int i = 0; i < elementi; i++)
    {
        *somma = *primo + *secondo;
        ++primo;
        ++secondo;
        ++somma;
    }
}

Perfetto, adesso ho l'anima in pace e il programma funziona correttamente senza un codice “unsafe”. Arrivati a questo punto possiamo provare ad analizzare brevemente questo pezzo di codice e relazionarlo ai precedenti. Come possiamo vedere, rispetto ai primi snippets non uso ne indici ne operatori di post-incremento, uso semplicemente l'aritmetica dei puntatori e gli operatori di pre-incremento.
Facendo invece un confronto con lo snippet precedente notiamo chiaramente come evitando il decremento all'inizio possiamo ridurre i cicli di clock necessari risparmiando tempo e soprattutto senza riscontrare problemi di "undefined behavior".

Spero di essere stato abbastanza chiaro, per qualsiasi dubbio o segnalazione di errori scrivete pure nei commenti. A breve pubblicherò altre guide, una riguardante l'aritmetica dei puntatori.

Saluti,
CrashTest
Fonte: You are not allowed to view links. Register or Login
« Last Edit: March 15, 2017, 07:33:13 PM by CrashTest »
Email: [email protected]
Website: You are not allowed to view links. Register or Login
 

 

Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40