Dr. Carlo Pescio Ottimizzazioni e C++

Pubblicato su Computer Programming No. 47

Introduzione

L'efficienza del codice generato è sempre stato uno dei parametri fondamentali nella valutazione di un compilatore. Negli ultimi anni abbiamo assistito ad un graduale spostamento dell'attenzione verso problematiche diverse, come la velocità di compilazione, l'esistenza di un ambiente di sviluppo integrato, l'evoluzione verso strumenti CASE; tuttavia, la generazione del codice resta il criterio cui più spesso si fa riferimento nella scelta di un compilatore.

L'importanza del problema ha portato a notevoli investimenti in ricerca e sviluppo, che hanno condizionato sia gli strumenti che i linguaggi di programmazione e la stessa architettura dei microprocessori; mentre agli albori della generazione del codice si riteneva "avanzato" un compilatore in grado di eseguire una peephole optimization, oggi si parla di induzione delle variabili, di determinazione statica dei tipi, e così via.

Tuttavia, ogni nuovo linguaggio porta con sé nuove problematiche, ed il C++ non fa eccezione: esistono costrutti comuni in C++ che possono rendere molto difficile l'ottimizzazione del codice da parte del compilatore. In questo articolo discuteremo le principali tecniche di ottimizzazione utilizzate dai compilatori C/C++, vedremo poi come il comportamento dinamico dei programmi C++ possa differire notevolmente da quello di programmi C, e di conseguenza quali ottimizzazioni specifiche possono essere applicate. Vedremo anche alcuni casi in cui il compilatore non riesce ad ottimizzare il codice senza l'aiuto del programmatore, ed alcune tecniche che possiamo utilizzare per migliorare l'efficienza dei programmi. Infine, vedremo come le migliori ottimizzazioni si ottengano ripensando gli algoritmi e le strutture dati, più che confidando ciecamente nelle capacità di ottimizzazione del compilatore.

Ovunque, ho cercato per quanto possibile di evitare considerazioni troppo legate ad una architettura particolare: quando ciò era necessario ho definito espressamente le caratteristiche essenziali della CPU affinché l'ottimizzazione abbia significato. Ho ritenuto opportuno evitare riferimenti ad architetture inusuali (parallele, Very Large Instruction Width, eccetera), concentrandomi invece sulle ottimizzazioni significative per le macchine più diffuse.

Ottimizzazione del codice C e C++

Esistono molte tecniche standard per l'ottimizzazione del codice, alcune delle quali visibili in figura 1; molte di esse sono indipendenti dall'architettura sottostante, mentre altre per la loro stessa natura sono legate alla CPU e talvolta anche al sistema operativo.

Osserviamo che uno dei fini dell'ottimizzazione è quello di permettere al programmatore di scrivere codice più leggibile, senza preoccuparsi eccessivamente dei dettagli di basso livello: sarà il compilatore ad eseguire la necessaria trasformazione in fase di ottimizzazione. Così, ad esempio, il programmatore potrà lasciare il calcolo di un fattore all'interno di un loop, per migliorare la comprensibilità dell'algoritmo, e sarà compito del compilatore "estrarre" il fattore dal loop se è indipendente dalla variabile indice. Semplici ottimizzazioni di questo tipo sono molto efficaci, ma in alcuni linguaggi (ad esempio di tipo interpretato) sono totalmente a carico del programmatore.

In altri casi, l'ottimizzazione non si pone come fine la leggibilità del sorgente, ma l'utilizzo delle piene potenzialità dell'architettura sottostante: ad esempio, di istruzioni particolari per la manipolazione di stringhe, o la presenza di più unità di elaborazione (processori superscalari) o semplicemente di una coda di prefetch. In questo caso, anche volendo, il programmatore ha scarso controllo sul codice generato (a meno che non decida di scriverne una parte in assembly) ed un buon compilatore ottimizzante può rivelarsi indispensabile per produrre codice veloce in tempi accettabili.

CPU-independent	CPU-dependent
Algebraic Optimizations	Instruction scheduling
Invariant code motion	Instruction Alignment
Common subexpression elimination	Global register allocation
Copy/Constant propagation	Register parameter passing
Strength reduction	Loop compaction (string move)
Variables Induction	Cross Jump Elimination
Dead store elimination	Tail Merging
Dead code elimination	Tail Recursion Optimization
Loop unrolling
Loop jamming

Vediamo ora, con riferimento alla figura 1, i principi su cui sono basate alcune delle tecniche più importanti:

Algebraic Optimizations

Si tratta del tipo più semplice di ottimizzazione, basato sulle proprietà fondamentali degli interi (distributività, simmetria, ecc), su alcune regole elementari (ad es. x * 0 = 0) e su alcune peculiarità della rappresentazione binaria (ad esempio, le moltiplicazioni/divisioni per potenze di 2 sono realizzabili tramite shift). Si tratta di tecniche che fanno parte del "bagaglio dei trucchi" di molti programmatori assembly, o anche di coloro che fanno parte della "vecchia guardia", quando i compilatori ottimizzanti erano più un sogno che una realtà. Lo scopo principale in questo caso è di permettere la scrittura di codice leggibile e mantenibile, scevro da tecniche dipendenti dall'architettura.

Invariant code motion:

Si parla di "codice invariante" ogni volta che un'espressione ha lo stesso valore per ogni esecuzione di un loop. Se il compilatore è in grado di determinare che il valore dell'espressione rimarrà effettivamente invariato, può semplicemente estrarlo dal loop e di conseguenza calcolarlo una sola volta. Ad esempio, nel caso seguente:

int a, b, c ;
// ...
for( int i = 0; i < 100; i++ )
  v[ i ] = a * i + b * c ;

L'espressione "b * c" può essere calcolata una sola volta, fuori dal loop. È importante capire, qui ed altrove, che la vera forza di queste semplici ottimizzazioni sta spesso nell'uso combinato. Infatti, mentre il caso precedente è piuttosto ovvio, il seguente lo è meno:

int a, b, c ;
// ...
for( int i = 0; i < 100; i++ )
  v[ i ] = (a + i) * (b + c) ;

Sfruttando la proprietà distributiva (un caso di algebraic optimization), ed applicando poi l'invariant code motion, il compilatore può trasformare il codice di cui sopra nella forma seguente, con un notevole vantaggio nei tempi di esecuzione:

int a, b, c ;
// ...
int x = b +c ;
int y = a * x ;
for( int i = 0; i < 100; i++ )
  v[ i ] = y + i * x ;

Common subexpression elimination

L'eliminazione di sottoespressioni comuni è simile al caso precedente, ma viene applicata indipendentemente dall'esistenza di un loop: implementando un algoritmo, è possibile che si ripeta la stessa sotto-espressione più volte in sequenza; se il compilatore è in grado di verificare che il valore dell'espressione non cambia nelle diverse istanze, può fattorizzare il calcolo della sottoespressione in un unico punto, evitando successivi ricalcoli. Anche in questo caso, si tratta di una ottimizzatione il cui obiettivo è di permettere la scrittura di codice più leggibile.

Copy/Constant propagation

La propagazione delle costanti cerca di risolvere a tempo di compilazione alcuni dei calcoli che sarebbero altrimenti rimandati al momento dell'esecuzione; vediamo un semplice esempio:

int a, b ;
a = 2 ;
b = a + 5 ;

In questo caso il compilatore può propagare la costante 2 nella riga successiva, ed interpretando l'espressione costante risultante (processo detto constant folding, che a rigore andrebbe considerato come un'ottimizzazione distinta) assegnare il valore 7 a b direttamente in fase di compilazione. Notiamo che questo consente di scrivere codice non solo più leggibile, ma anche più mantenibile; questa è una delle differenze fra gli strumenti ed i linguaggi professionali e quelli amatoriali, che spesso costringono il programmatore ad acrobazie che hanno un impatto negativo sulla mantenibilità del codice.

Strength reduction

Questa tecnica, che in generale cerca di ridurre l'overhead in un loop, è normalmente implementata attraverso l'ottimizzazione delle espressioni che coinvolgono le variabili indice, o che comunque cambiano valore ad ogni esecuzione del loop. Ad esempio, se il compilatore riconosce che un contatore è usato come indice in un array, può generare lo stesso codice che otterrebbe un programmatore che ottimizzasse manualmente, ovvero usando l'incremento di un puntatore anziché l'accesso indicizzato. Oppure, le espressioni possono essere trasformate in forma incrementale. Vediamo un esempio concreto:

for( int i = 0; i < 500; i++ )
  v[ i ] = i * 2 ;


Il primo passo di strength reduction tenta di eliminare la costosa operazione "i * 2" trasformandola in un calcolo incrementale, basato solo sulla somma:


for( int i = 0, t = 0 ; i < 500; i++ )
  {
  v[ i ] = t ;
  t += 2 ;
  }

Il secondo passo riconosce che la variabile i è usata come indice in un vettore, e trasforma il codice per usare l'incremento sui puntatori:

int* p = v ;
for( int i = 0, t = 0 ; i < 500; i++, p++ )
  {
  *p = t ;
  t += 2 ;
  }

Infine, la variabile i può essere eliminata modificando i limiti dell'iterazione:

int* p = v ;
for( int t = 0 ; t < 1000; t += 2, p++ )
  *p = t ;

Una ulteriore semplificazione dello stesso codice viene introdotta al punto seguente.

Variables Induction

Spesso, dopo aver applicato la strength reduction ad un loop, si ottiene un codice dove l'originaria variabile indice (o una che ne ha preso il posto) è utilizzata solo per il confronto; ad esempio, ricollegandoci a quanto sopra, applicando la strength reduction a:

for( int i = 0; i < 500; i++ )
  v[ i ] = 0 ;

otteniamo:

int* p = v ;
for( i = 0; i < 500; i ++, p++ )
  *p = 0 ;

in questo caso la variabile indice può essere successivamente eliminata dal compilatore, generando codice come segue:

int* q = v + 500 ;
for( int* p = v; p < q; p++ )
  *p = 0 ;

Nuovamente, notiamo che un'ottimizzazione tutto sommato "semplice" può essere ottenuta attraverso passi relativamente complessi.

Dead store elimination

Con questa operazione si intende l'eliminazione di variabili non utilizzate, siano esse introdotte dal programmatore o (più spesso) rese tali da precedenti fasi di ottimizzazione. Notiamo che il compilatore può determinare l'esistenza di variabili non utilizzate anche attraverso la propagazione delle costanti: ad esempio, se una variabile è utilizzata solo all'interno di codice di debugging, e tale codice si trova racchiuso in statement del tipo "if( debug ) ..." il compilatore può eliminare le variabili se il valore di "debug" è determinabile staticamente.

Dead code elimination

Si tratta dell'esatto analogo del dead store elimination, ma relativo al codice; spesso le due fasi vengono effettivamente inglobate in un unico passo all'interno del compilatore.

Loop unrolling

Lo "srotolamento" dei loop consiste nella replicazione del corpo del loop stesso, ed ha due distinte finalità: diminuire l'overhead del test/incremento rispetto all'esecuzione del body, e sfruttare al meglio le architetture con pipeline, dove l'esecuzione di un salto tende a far crollare le prestazioni rispetto all'esecuzione di una istruzione già nella coda di prefetch. Il compilatore normalmente sceglie il fattore di unrolling come un trade/off tra l'incremento di dimensioni del programma e lo speedup dello stesso, basandosi tra l'altro sul range del loop, la dimensione della coda di pipeline, della cache interna, e di altri fattori dipendenti dall'architettura (ad esempio, la natura superscalare della CPU). Ad esempio, il codice seguente:

for( int i = 0; i < 100; i++ )
  v[ i ] = x[ i ] * 4 ;

diventa, srotolando di un fattore 2:

for( int i = 0; i < 100; i += 2 )
  {
  v[ i ] = x[ i ] * 4 ;
  v[ i+1 ] = x[ i+1 ] * 4 ;
  }

Notiamo che il compilatore può applicare simultaneamente altre tecniche al loop, ad esempio la strength reduction, ottenendo codice simile a:

int* p = v ;
int* q = x ;
for( int i = 0; i < 100; i += 2, p++, q++)
  {
  *p = ( *q << 2 ) ;
  p++ ;
  q++ ;
  *p = ( *q << 2 ) ;
  }

Loop jamming

Questa tecnica (chiamata anche loop fusion) consiste nella fusione di due loop in uno solo; questo permette al compilatore di sfruttare la ridondanza delle operazioni, eliminando così l'overhead da uno dei loop, ed al programmatore di scrivere loop piccoli, separati e quindi facilmente comprensibili, anziché "ottimizzare a mano" e creare un unico grande loop. Ad esempio, il codice seguente:

for( int i = 0; i < 100; i++ )
  v[ i ] = x[ i ] * 4 ;
for( i = 0; i < 100; i++ )
  z[ i ] = y[ i ] + x[ i ] ;

Diventa:

for( int i = 0; i < 100; i++ )
  {
  v[ i ] = x[ i ] * 4 ;
  z[ i ] = y[ i ] + x[ i ] ;
  }

Eliminando così l'overhead del secondo loop. Notiamo che a questo punto la strenght reduction può talvolta ottimizzare il loop risultante più di quanto non fosse possibile fare operando singolarmente sui due loop.

Instruction scheduling

Letteralmente, significa eseguire le istruzioni in un ordine diverso da quello specificato; con "istruzioni" non si intende qui le macro-istruzioni del linguaggio ad alto livello, ma le singole istruzioni assembly del codice target. Il fine è di sfruttare le particolarità della CPU (si tratta infatti di una ottimizzazione machine-dependent): ad esempio, il Pentium può eseguire in parallelo alcuni tipi di istruzione, ma non tutti; se due istruzioni possono essere scambiate di posto senza influenzare il risultato (e ciò è spesso possibile a livello assembly) allora riordinare le istruzioni può comportare un notevole aumento delle prestazioni. Nell'esempio seguente, relativo proprio al Pentium:

INC EBX ; U pipe

INC ECX ; V pipe

INC EDX ; U pipe

MOV EAX, [EBX] ; V pipe:

; EBX not ready!!

MOV EDI, 0 ; U pipe

l'istruzione MOV EAX, [EBX] causa una attesa di un ciclo di clock, in quanto l'indirizzo [EBX] non può essere calcolato dall'unità in pipeline sino a quando l'istruzione INC EBX non è terminata. Basta tuttavia scambiare di posto tale istruzione con MOV EDI, 0 per eliminare lo stato di attesa; se tali istruzioni sono all'interno di un loop, la differenza di prestazioni può essere notevole..

Instruction Alignment

In questo caso si tratta di una tecnica molto banale ma efficace, nuovamente machine-dependent. Su molte architetture, l'accesso ad istruzioni che non siano allineate su indirizzi pari è significativamente più lento rispetto al caso di istruzioni allineate (in alcuni casi si genera addirittura un'eccezione che viene gestita dal sistema operativo, con uno slowdown di diversi ordini di grandezza!). Le istruzioni vengono allineate attraverso un riordino quando possibile, o attraverso l'introduzione di istruzioni di tipo NOP negli altri casi.

Global register allocation

Ogni processore dispone di un certo numero di registri interni; l'accesso a tali registri è significativamente più veloce dell'accesso in memoria, e consente un più alto grado di parallelismo interno dell'esecuzione. Su alcune macchine RISC, i registri sono nell'ordine delle centinaia, ma su molte macchine CISC, come i 486 o i Pentium, sono ridotti all'ordine della decina. Decidere quali variabili conservare nei registri diventa allora cruciale per l'ottimizzazione: non a caso il linguaggio C prevedeva sin dall'inizio la keyword "register", in modo che il programmatore potesse suggerire al compilatore cosa inserire nei registri e cosa lasciare in memoria. In realtà, i compilatori moderni fanno spesso un lavoro migliore del programmatore nell'allocare i registri, e soprattutto consentono al codice di rimanere CPU-independent pur conservando buone prestazioni. Un buon algoritmo di allocazione dei registri tiene normalmente conto anche dei parametri passati alle funzioni, discusso al punto seguente, nonché del flusso a livello globale e non semplicemente all'interno di una singola funzione.

Register parameter passing

La tecnica "ufficiale" del C per passare parametri alle funzioni consiste nell'inserire i parametri sullo stack, chiamare la funzione, e rimuovere poi i parametri dallo stack (la convenzione Pascal è invece che la funzione chiamata elimina i parametri dallo stack). Tuttavia, in alcuni casi si possono ottenere significativi miglioramenti delle prestazioni passando i parametri nei registri: notiamo però che sia il chiamante che il chiamato devono rispettare questa convenzione. Si tratta quindi di una ottimizzazione che viene spesso applicata alle sole funzioni statiche relative ad un modulo, in modo che sia semplice per il compilatore verificare il rispetto della convenzione.

Loop compaction (string move)

Molte CPU hanno a disposizione operazioni elementari per operare su sequenze di byte o word; in questi casi, operazioni sui vettori come l'azzeramento o la copia possono essere trasformate in funzioni di tali primitive, eventualmente sfruttando anche il loop unrolling e jamming. Non necessariamente si ha un aumento di prestazioni, ma spesso si ha una riduzione nelle dimensioni del codice.

Cross Jump Elimination

Si tratta nuovamente di una strategia che consente di scrivere codice più mantenibile, senza preoccuparsi di ottimizzare rispetto alle dimensioni dell'eseguibile. Consideriamo ad esempio uno statement switch/case:

switch( v )
  {
  case 0 :
    x = y ;
    y++ ;
    z++ ;
    break ;
  case 1 :
    f( v ) ;
    break;
  case 2 :
    x = y ;
    y++ ;
    z++ ;
    break ;
    // ...
  }

I casi 0 e 2 sono distinti, in quanto si prevede che possano cambiare in future versioni del programma. In questo caso il compilatore può ottimizzare il codice come se il programmatore avesse scritto:

switch( v )
  {
  case 0 :
  case 2 :
    x = y ;
    y++ ;
    z++ ;
    break ;
  case 1:
    f( v ) ;
    break;
  // ...
  }

Tail Merging

Il Tail merging ("fusione delle code") ottimizza il caso di salti ad istruzioni di return, nel qual caso il salto viene sostituito dal return stesso. Ad esempio, codice di questo tipo:

void f( int n )
  {
  // ...
  switch( n )
    {
    case 1 :
    // ...
    break ;
    // salta al return sotto
    case 2 :
    // ...
    }
  return ;
  }

può essere automaticamente modificato in:

void f( int n )
  {
  // ...
  switch( n )
    {
    case 1 :
      // ...
      return ;
    case 2 :
      // ...
    }
  return ;
  }

Questo permette al programmatore di avere un singolo punto di uscita in ogni funzione (vedere [3] per ulteriori commenti al proposito) senza penalizzare le prestazioni.

Tail Recursion Optimization

Questo schema di ottimizzazione è tipico dei linguaggi funzionali, ma è spesso implementato anche in compilatori per linguaggi imperativi come il C ed il C++; l'idea è di trasformare una funzione ricorsiva, con ricorsione di coda, in una funzione iterativa. Ad esempio:

void f( int a, int b )
  {
  // ...
  if( a )
    return;
  // ...
  f( a, b ) ;
  }

viene trasformato in:

void f( int a, int b )
  {
  start :
  // ...
  if( a )
    return;
  // ...
  goto start ;
  }

Questo elimina il costo della chiamata di funzione (quindi incluso il passaggio di parametri sullo stack) e soprattutto riduce drasticamente l'occupazione di memoria a run-time. Attenzione che solo la ricorsione di coda può essere automaticamente eliminata dal compilatore.

Differenze nel comportamento a run-time tra C e C++

Le tecniche che abbiamo sinora visto sono molto generali, e sono applicabili a quasi ogni linguaggio di programmazione di tipo imperativo; addirittura, in molti casi le case produttrici di compilatori utilizzano un unico ottimizzatore per una famiglia di linguaggi, cambiando invece il solo front-end del compilatore. Vi è una assunzione nascosta in questo modo di procedere, ovvero che il comportamento a run-time dei programmi sia più o meno "lo stesso" nei diversi linguaggi di programmazione, ad esempio che l'esecuzione dei loop richieda una percentuale significativa del tempo macchina, che valga la pena di ottimizzare i salti, e così via. Ogni linguaggio ha però idiomi di utilizzo tipici, e tale assunzione si rivela solo in parte azzeccata; ad esempio, in C i puntatori a funzione sono relativamente poco usati, ma in C++ il meccanismo (molto simile) delle funzioni virtuali è utilizzato in modo pesante.

Vale quindi la pena di chiedersi in cosa differiscano, ad esempio, il C ed il C++ nel comportamento a run-time, in modo da riconoscere le situazioni tipiche del C++ che richiedono ottimizzazioni specifiche. Ricerche comparative di questo tipo sono piuttosto complesse ed onerose, specialmente se si vuole che siano significative per programmi reali e non per semplici esempietti, che possono rivelare comportamenti patologici dei linguaggi ma che, per la loro stessa natura, non sono assolutamente rappresentativi; riprenderò comunque in questa sede i risultati di due esperimenti molto interessanti e ben strutturati, eseguiti presso centri di ricerca privati ed universitari.

Il primo [4] riguarda la percentuale di codice non raggiungibile all'interno di programmi C++, confrontata con la media per i programmi C; per fare ciò, sono stati confrontati alcuni programmi C piuttosto complessi (il compilatore GNU gcc, il debugger GNU gdb, un interprete lisp, eccetera) ed alcuni programmi C++ corrispondentemente complessi (un browser di classi, un cad per il layout di circuiti VLSI, ed altri). I risultati sono abbastanza negativi per il C++: nei programmi C, la media del codice non raggiunbile all'interno degli eseguibili è risultata del 5%, con deviazioni dalla media molto contenute; per i programmi C++, la media è risultata del 20% circa, con oscillazioni dal 10% al 26%.

Questo sembra indicare che una delle ottimizzazioni di cui abbiamo parlato in precedenza (dead code elimination) non è molto efficace nel caso del C++; in realtà il problema è più complesso, perché in questo caso non si tratta di piccole porzioni di codice, ma di intere procedure che non vengono mai chiamate dinamicamente. Per capire meglio il problema, consideriamo il seguente listato:

class Base
  {
  public :
    virtual void DoSomething() { ... } ;
  // ...
  } ;

class Derived : public Base
  {
  public :
    void DoSomething() { ... } ;
  // ...
  } ;

int main()
  {
  Derived d ;
  d.DoSomething() ;
  // ...
  return( 0 ) ;
  }

Si tratta di un idioma tipico del C++: una classe base definisce un comportamento "di default" per gli oggetti, ma una classe derivata può ridefinire tale comportamento; in alcuni casi, la classe derivata non richiama neppure il corrispondente metodo della classe base. Pur essendo molto frequente, è necessaria una analisi statica piuttosto complessa per capire se il metodo Base :: DoSomething() verrà mai chiamato; non solo, l'analisi va eseguita al momento del link, quando sono disponibili tutte le informazioni su quali funzioni vengono chiamate nei vari moduli. In programmi reali, infatti, Base, Derived e main() si troveranno probabilmente in file sorgente diversi. Infine, se vengono utilizzati i puntatori può essere impossibile determinare a compile-time se il metodo verrà chiamato o meno, e quindi il compilatore sarà comunque costretto ad includerne il codice (su questo punto torneremo in seguito). Ovviamente, occorre considerare anche il codice non accessibile in modo transitivo: Base :: DoSomething() potrebbe essere chiamato da Derived :: DoSomething(), ma se questo non viene a sua volta chiamato, entrambi sono non raggiungibili. Al momento, quasi nessun compilatore commerciale è molto forte su questo tipo di ottimizzazione a link-time: in molti casi, il linker è rimasto lo stesso (o quasi) usato nella generazione precedende dei linguaggi (C, Pascal) e non offre alcun tipo di ottimizzazione. Notiamo che il codice non raggiungibile non solo comporta un notevole overhead nelle dimensioni dell'eseguibile, ma può anche ridurre le prestazioni del programma in un sistema a memoria paginata.

Per il secondo esperimento [7], molto più complesso del precedente, sono stati nuovamente utilizzati programmi C e C++ di considerevoli dimensioni, nonché alcuni benchmark standard per la verifica delle prestazioni dei compilatori e/o delle CPU (Dhrystone, SPECint, SPECfp, ecc) per determinare se essi fossero significativi per linguaggi orientati agli oggetti come il C++; in effetti, il risultato piuttosto evidente è che tali benchmark falliscono nel rappresentare alcune caratteristiche dinamiche dei programmi C++. Poiché tali benchmark sono spesso utilizzati dai produttori di compilatori per misurare l'efficacia delle ottimizzazioni, non meraviglia che i compilatori stessi siano risultati abbastanza deboli nel gestire le situazioni che più differenziano il C++ dal C. Vediamo alcune di queste differenze:

Dimensione dei blocchi: nei programmi C++, la dimensione tipica di un blocco (corpo di funzione, di un while, di un if, eccetera) risulta molto più piccola della dimensione tipica di un programma C. Questo significa che le ottimizzazioni che puntano molto sui blocchi grandi (es. instruction scheduling) saranno meno efficaci, mentre ad esempio il loop unrolling funzionerà "meglio", nel senso che l'aumento di dimensioni sarà più contenuto. La ragione delle ridotte dimensioni dei blocchi va ricercata sia nella logica di "separation of concerns" tipica del paradigma orientato agli oggetti, sia nel fatto che in C++ gli statement condizionali vengono spesso rimpiazzati dal meccanismo delle funzioni virtuali.

Salti: abbiamo visto che alcune ottimizzazioni cercano di eliminare quando possibile i salti, in quanto responsabili di degrado delle prestazioni su CPU pipelined. In effetti, in accordo al fatto che esistono meno statement condizionali, il codice C++ esegue meno salti condizionali (e quindi tali ottimizzazioni sono meno importanti); tuttavia, se consideriamo i "salti indiretti" dovuti alla chiamata di funzioni virtuali, il C++ raggiunge sostanzialmente lo stesso livello del C. Sfortunatamente, al momento esistono ben poche ottimizzazioni sui salti indiretti (ne parleremo al prossimo paragrafo) che in ogni caso dovrebbero comunque essere realizzate a link-time.

Cache hit/miss: i programmi C e C++ sono più o meno equivalenti per quanto riguarda la percentuale di data cache miss (ovvero l'accesso a dati fuori dalla cache); la situazione è invece molto diversa per quanto riguarda la cache del codice, in quanto in C++ la media è più che doppia rispetto al C. Le cause vanno ricercate nella maggiore frammentazione in metodi delle funzioni C++: mentre questo ha indubbi vantaggi in termini di mantenibilità, riusabilità e così via, ha anche effetti negativi sulle prestazioni. Vedremo in seguito come si possa fare una scelta oculata utilizzando un profiler; vale invece la pena di notare immediatamente come le CPU con cache dati/codice separate siano intrinsecamente più adatte ad eseguire in modo efficiente il codice C++.

Ulteriori considerazioni portano alle seguenti conclusioni: il comportamento dinamico dei programmi C++ è sensibilmente diverso da quello dei programmi C, e le ottimizzazioni utilizzate per i programmi C sono solo parzialmente adatte ai programmi C++; in futuro, i migliori compilatori dovranno introdurre numerose nuove ottimizzazioni in fase di linking.

Ottimizzazioni specifiche per il C++

Come abbiamo visto, il C++ richiederebbe alcune ottimizzazioni specifiche, che non sono ancora implementate dalla maggior parte dei compilatori commerciali. Esistono però altri casi, che non sono stati considerati nei succitati esperimenti, e che vengono invece gestiti opportunamente da molti compilatori.

Un esempio è la gestione dell'overloading degli operatori: mentre sui tipi built-in come gli interi il compilatore riesce facilmente ad ottimizzare assegnazioni del tipo "a = b + c ;" attraverso un'unica fase di somma-e-assegna, lo stesso non si può dire per gli operatori definiti dall'utente. Codice come il seguente (dove assumiamo che la classe SomeClass abbia definito l'operatore '+'):

SomeClass a = ...
SomeClass b = ...
SomeClass c = ...

a = b + c ;

Lo statement di "somma" comporta in effetti:

1. Il passaggio di b e c all'operatore di somma; assumendo un passaggio per riferimento, il costo è normalmente contenuto.
2. Il calcolo della "somma" e la restituzione di un valore temporaneo
3. La chiamata del costruttore di copia per assegnare il valore del temporaneo ad a.

Il compilatore genera quindi di norma un codice del tipo:

somma-e-assegna( b, c, temp ) ;

assegna( temp, a ) ;

anziché la versione più efficiente usata per i tipi built-in.

Tuttavia, sotto determinate condizioni il compilatore può eliminare il temporaneo, ed ottenere codice con la stessa efficienza possibile nel caso, ad esempio, di operazioni tra interi: in particolare, è necessario che il compilatore riesca a determinare che l'operazione di somma e l'operazione di assegnazione sono indipendenti dalla variabile che viene assegnata.

Purtroppo, in molti casi la presenza dei puntatori e dei reference rende questa verifica molto ardua per il compilatore; vedremo in seguito alcuni piccoli accorgimenti per semplificare l'analisi dell'aliasing da parte del compilatore, che incrementano la probabilità di ottenere un codice migliore. In ogni caso, se l'operazione di copia è molto onerosa è consigliabile l'implementazione di un metodo più efficiente (come il reference counting o la lazy evaluation, che vedremo in seguito), piuttosto che affidarsi unicamente alle capacità di ottimizzazione del compilatore.

Un notevole incremento nelle prestazioni dei programmi C++ è ottenibile ogniqualvolta sia possibile determinare staticamente il tipo di un oggetto, ed evitare così l'indirezione di una chiamata di funzione virtuale; considerando che, come visto sopra, le funzioni virtuali prendono il posto dei salti condizionati in molti programmi C++, questo tipo di ottimizzazione giocherà un ruolo fondamentale nell'evoluzione dei compilatori. Un algoritmo piuttosto efficiente per l'analisi statica del codice è stato presentato in [8], con l'unica limitazione di essere limitato al caso dei puntatori singoli; è ragionevole attendersi l'implementazione di tecniche analoghe da parte dei produttori di compilatori, il che non fa che rinforzare la mia raccomandazione (vedere [3]) di evitare quando possibile i puntatori a puntatori: in questo caso, anche un buon compilatore potrebbe non essere in grado di ottimizzare il codice.

Aiutare il compilatore

Quanto sopra può sembrare un pò in controtendenza: in teoria, dovremmo essere liberi di scrivere il codice come vogliamo, ed il compilatore dovrebbe sobbarcarsi il compito di ottimizzare. Come sempre, ciò è vero solo sino ad un certo punto, ed uno sviluppatore cosciente sa dove è necessario "aiutare" il compilatore.

D'altra parte, l'idea che il programmatore possa in qualche modo "suggerire" delle ottimizzazioni non è nuova: come abbiamo visto, sin dagli inizi il linguaggio C permetteva di suggerire quali variabili porre nei registri. Le nuove tecniche di allocazione dei registri rendono ora tali suggerimenti pressoché inutili, ma oggi possiamo ad esempio suggerire, attraverso la parola chiave inline, quali funzioni desideriamo che siano espanse in linea. In futuro, anche questo tipo di suggerimenti potrebbe diventare poco significativo. Esistono comunque altri casi, che ho approfondito in [3] ma che vale la pena di riprendere, in cui il programmatore può strutturare il codice in modo che sia più facilmente ottimizzabile dal compilatore:

Operatori prefissi e postfissi: se definite oggetti di grandi dimensioni, considerate la possibilità di non fornire gli operatori postfissi, o fate in modo che, in versione di debug, venga stampato un messaggio che suggerisca di usare la versione prefissa. Utilizzando librerie di classi che ridefiniscono gli operatori ++ e --, cercate quando possibile di usare le versione prefisse. In molti casi, gli operatori con side effect vengono utilizzati su linee singole, come:

a++ ;

ed in questo caso la versione postfissa genera un oggetto temporaneo che solo in pochi casi può essere eliminato dal compilatore. Diverso è naturalmente il caso di codice del tipo:

x = y + a++ ;

dove non è possibile utilizzare la forma prefissa, a meno di non copiare manualmente l'oggetto a, nel qual caso non si ha comunque alcun guadagno.

Operatori con side-effect: quando è possibile, utilizzando classi che ridefiniscano gli operatori, preferite sempre la versione a += b alla versione a = a + b. Il compilatore difficilmente è in grado di ottimizzare statement nella seconda forma (vedere spiegazione data al paragrafo precedente), e la prima è inerentemente più veloce.

Aggregazione diretta o tramite puntatori: quando un oggetto ne aggrega altri come sotto-oggetti, si ha spesso la possibilita' di aggregare direttamente un oggetto od un puntatore ad esso. Ogni volta che sia possibile, preferite la prima opzione: questo consente anche a compilatori con una analisi statica dei tipi non troppo perfezionata (ovvero, al momento, quasi tutti) di evitare l'overhead delle funzioni virtuali, ed in particolare di espandere in linea le funzioni inline, anche se dichiarate come virtuali.

Semplificare gli alias: Abbiamo visto che una delle debolezze del compilatore è l'analisi degli alias; proprio per questo, alcuni compilatori dispongono di un'opzione, normalmente chiamata "assume no pointer aliasing", che per l'appunto permette al compilatore stesso di ignorare potenziali alias e generare di conseguenza codice più efficiente in molte situazioni.

Si tratta naturalmente di un'opzione abbastanza pericolosa, e compilando un intero programma con tale opzione abilitata si ha quasi la certezza di incorrere in qualche errore a run-time; tuttavia, se il programmatore sa che in alcune funzioni è possibile assumere con certezza l'assenza di alias, può abilitare l'opzione per quella porzione di codice (spostandola in un file separato o usando una direttiva #pragma). In questi casi, non sarebbe una cattiva idea aggiungere delle opportune asserzioni nel codice, che verifichino in fase di debugging le assunzioni del programmatore: specialmente in caso di future modifiche o riuso del codice, controllare che le condizioni attese siano rispettate è molto importante.

In altri casi, è sufficiente modificare leggermente il sorgente per consentire al compilatore di generare codice più efficiente; ad esempio, nel seguente frammento:

*p = 8 ;

*q = 9 ;

x = *p ;

il compilatore non può ottimizzare l'assegnazione ad x, poiché p e q potrebbero avere lo stesso valore. Modificando però il codice come segue:

*q = 9 ;

*p = 8 ;

x = *p ;

il compilatore può invece ottimizzare come se avessimo scritto x = 8.

Osserviamo che, trasformando il codice, abbiamo assunto che p e q fossero diversi; nuovamente, qualora si potesse ipotizzare una violazione della nostra assunzione in fase di manutenzione, non sarebbe una cattiva idea aggiungere un commento, meglio se anche accompagnato da una asserzione del tipo assert( p != q ).

Infine, come ho già accennato in altri articoli, ricordate sempre che in molti casi il 20% del codice è responsabile per l'80% del tempo di esecuzione: inutile ottimizzare per prestazioni il restante 80% del codice, che va invece progettato con altri criteri (riusabilità, testabilità, e così via). L'uso di un profiler può aiutare a riconoscere il 20% di codice che necessita di una maggiore ottimizzazione; in alcuni casi, questa ottimizzazione si otterrà con alcuni piccoli accorgimenti come quelli su riportati, in altri ricorrendo all'assembler, in molti altri ancora la soluzione migliore è un algoritmo più efficiente od una struttura dati più adatta ai compiti svolti.

Ottimizzazioni avanzate

Esistono numerose altre tecniche di ottimizzazione, soprattutto nel campo del calcolo numerico; alcune di esse sono inerentemente pensate per architetture parallele di vario genere, e non verranno qui discusse. Ne esistono tuttavia alcune che possono essere significative anche per le normali architetture monoprocessore: si tratta di tecniche sofisticate, ed al momento non mi risulta che siano implementate in alcun compilatore commerciale, se non su workstation di costo molto elevato. In particolare, una si presta anche all'implementazione "manuale" da parte del programmatore, per cui ne discuteremo brevemente i principi fondamentali.

La tecnica viene chiamata strip-mining [9], ed è applicabile ad operazioni su matrici, ad esempio per la moltiplicazione; per essere effettiva, la CPU deve avere una cache interna di primo livello (caso ormai molto diffuso, dal 486 al Pentium all'Alpha), e maggiori vantaggi si ottengono su architetture superscalari come Pentium ed Alpha. Consideriamo infatti una semplice implementazione del prodotto di due matrici n X n:

for( int i = 0; i < n; i++ )
  for( int j = 0; j < n; j++ )
  {
  C[ i ][ j ] = 0 ;
  for( int k = 0; k < n; k++ )
    C[ i ][ j ] += A[ i ][ k ] * B[ k ][ j ] ;
  }

Il difetto di un simile algoritmo è che, non appena le matrici hanno dimensioni significative, si esce dalla condizione di località dei dati che consente alla CPU di accedere ai dati direttamente dalla cache interna. Notiamo infatti che i termini A[ i ][ k ] vengono continuamente caricati in memoria per ogni iterazione su j, e viceversa per B[ k ][ j ].

L'idea dello strip mining è di suddividere l'operazione sulle matrici in più sotto-passi, ognuno dei quali corrisponda alla moltiplicazione di una sotto-matrice la cui dimensione è dipendente dalla CPU (più precisamente, dalla dimensione della sua cache). Il loop originale viene quindi suddiviso in block loops ed in strip loops: il block loop genera l'effettivo data-transfert da e verso la cache, e viene spostato fuori dal loop più interno. Lo strip loop esegue i calcoli veri e propri, e viene spostato dentro il loop più interno.

Il risultato è mostrato nel listato 1 (per l'eccessiva lunghezza non era possibile introdurlo direttamente nel testo). Su matrici piuttosto grandi, l'incremento di prestazioni può superare l'ordine di grandezza, soprattutto se vi è una notevole differenza tra la velocità della CPU e quella della cache di secondo livello (situazione comune per le CPU a frequenza molto elevata).

Migliorare strutture dati ed algoritmi

Il caso precedente può essere visto sotto due aspetti diversi: in un caso, un compilatore sofisticato può eseguire ottimizzazioni molto spinte; nell'altro, è il programmatore che modifica manualmente l'algoritmo di moltiplicazione delle matrici per ottenere prestazioni migliori. Il secondo caso è molto frequente, e giustifica tutta la ricerca sulle strutture dati e gli algoritmi: inutile ottimizzare allo spasimo una ricerca lineare, quando una ricerca binaria sarà comunque più veloce. Inutile impazzire sul codice di bubblesort, cercando di limare l'ultimo ciclo di clock, quando quicksort è di gran lunga più efficiente su grandi insiemi di dati.

Il C++ è un linguaggio molto potente, che consente alcuni tipi di ottimizzazione che in altri linguaggi sarebbero impensabili: occorre però lo sforzo cosciente del programmatore per ottenerla. Un esempio ormai noto è quello delle stringhe, nella loro implementazione con reference counting e copy-on-write. In tal modo, possiamo realizzare una classe stringa estremamente efficiente, dove la creazione di un temporaneo ha costo quasi nullo, così come l'operazione di copia. Solo al momento della modifica di una stringa è necessario creare un nuovo array di caratteri.

Questo tipo di implementazione, mutuando un termine dalla programmazione funzionale, si può considerare un caso di lazy evaluation (valutazione pigra); lo stesso criterio si può estendere ad altri casi, ad esempio le operazioni su matrici (è interessante notare che l'APL, un linguaggio molto usato per calcoli numerici, usa internamente una tecnica analoga). Una classe Matrix può ridefinire gli operatori di somma e moltiplicazione per consentire una sintassi più naturale ai suoi utilizzatori; tuttavia, una riga del tipo:

x = y + a * b ;

può comportare la creazione di due oggetti temporanei di dimensioni piuttosto grandi. Una soluzione, anche in questo caso, è di usare il reference counting; esiste però una alternativa, che bisognerebbe sempre considerare quando si manipolano oggetti di grandi dimensioni: in molti casi, infatti, non siamo interessati all'intero oggetto, ma solo ad alcune sue parti. In tal caso, dovremmo "sospendere" la valutazione sino a quando non occorre accedere ad una di queste parti. Ad esempio, nel caso precedente possiamo memorizzare le matrici risultato di operazioni come un albero di operatori e riferimenti ai fattori della computazione: la dimensione di questi oggetti è molto contenuta, ed espressioni anche complesse vengono "calcolate" (o meglio, non-calcolate) in pochi istanti. Nel momentonto in cui è necessario accedere ad un elemento (o anche ad una riga o colonna) possiamo invece valutare la sotto-espressione relativa, eventualmente sfruttando alcune proprietà per precalcolarne altre. Naturalmente, se alla fine si utilizzano sempre tutti gli elementi, l'approccio può non pagare; ma in generale (ed il suo utilizzo in APL non fa che confermarlo) solo alcuni elementi della matrice vengono realmente utilizzati, e la lazy evaluation è lo strumento migliore per gestire questi casi.

Il lato oscuro delle ottimizzazioni

L'informatica applicata è spesso basata su trade/off (o compromessi); ad esempio, possiamo ottimizzare il codice per velocità o per mantenibilità e riusabilità, e spesso le scelte sono tra loro esclusive. Anche se lasciamo al compilatore il compito di ottimizzare, possiamo trovarci in situazioni piuttosto scomode: ad esempio, il debugging di codice ottimizzato, sia a livello sorgente che di codice assembly, è reso spesso complicato a causa delle ottimizzazioni dei salti, lo spostamento di codice invariante, e così via (vedere [10] per altre considerazioni sul debugging). Lo stesso si può dire per i test di copertura. D'altra parte, se il codice che distribuiamo è quello ottimizzato, è necessario eseguire anche su di esso tutti i test opportuni.

Inoltre, le ottimizzazioni sono uno dei punti deboli dei compilatori, dove si annidano la maggior parte dei bug; non a caso, in fase di sviluppo è abbastanza normale disabilitare tutte le ottimizzazioni, per essere "certi" che eventuali bug siano nostri e non del compilatore, rimandando così a tempi successivi l'eliminazione di "bug da ottimizzazione". Ricordo ancora che il Microsoft C 6.0x, abilitando una qualunque ottimizzazione, non riusciva a compilare (terminando con errore interno) il seguente semplice programma:

int main(void)

{

int a;

a = 1 + (a * 2 - 2) * (a * 5 - 5);

return( 0 ) ;

}

Il bug è poi stato corretto nella versione 7.0. Anche i compilatori Borland della recente generazione 4.x sono tutt'altro che privi di bug nella fase di ottimizzazione.

Conclusioni:

Il compilatore C++ è in grado di eseguire un numero molto elevato di ottimizzazioni, lasciando il programmatore libero di scrivere codice più leggibile e strutturato. Esistono alcuni punti deboli nei compilatori attuali, che verranno indubbiamente migliorati nel prossimo futuro, ed in alcuni casi è possible aiutare il compilatore con piccole modifiche al sorgente. In ogni caso, la risorsa migliore per l'ottimizzazione resta la scelta dell'algoritmo migliore e della struttura dati più indicata per le operazioni eseguite dal programma. Una buona astrazione consentirà anche di modificare l'implementazione di tali classi per adeguarsi ai pattern computazionali tipici dell'applicazione, senza richiedere la modifica di altre porzioni di codice.

Reader's Map

Molti visitatori che hanno letto questo articolo hanno letto anche:

Bibliografia

[1] Aho, Sethi, Ullman: "Compilers: Principles, Techniques, and Tools", Addison-Wesley, 1986.

[2] Motwani, Palem, Sarkar, Reyen: "Combined Instruction Scheduling and Register Allocation" ,Technical Report, New York University, Department of Computer Science, July 1995.

[3] Carlo Pescio: "C++ Manuale di Stile", Edizioni Infomedia, 1995.

[4] Amitabh Srivastava: "Unreachable procedures in object-oriented programming" ACM Letters on Programming Language and Systems, December 1992.

[5] Srivastava, Wall: "A practical system for intermodule code optimization at link-time" Journal of Programming Languages , December 1992.

[6] Calder, Grunvald: "Reducing indirect function call overhead in C++ programs", Proceedings of the 21th Annual ACM Symposium on Principles of Programming Languages, 1994.

[7] Calder, Grunwald, Zorn: "Quantifying Behavioral Differences Between C and C++ Programs", Technical Report, University of Colorado, Department of Computer Science, 1994.

[8] Pande, Ryder: "Static Type Determination for C++", Proceedings of Sixth USENIX C++ Conference, 1995.

[9] Akiyoshi Wakatani: "A New Approach to Array Redistribution: Strip Mining Redistribution", Proceedings PARLE '94, 1994.

[10] Carlo Pescio: "Debugging: Tecniche e Tool", Computer Programming No 43, Gennaio 1996.

Biografia
Carlo Pescio svolge attività di consulenza in ambito internazionale sulle metodologie di sviluppo Object Oriented e di programmazione in ambiente Windows. È laureato in Scienze dell'Informazione, membro dell'Institute of Electrical and Electronics Engineers Computer Society, dei Comitati Tecnici IEEE su Linguaggi Formali, Software Engineering e Medicina Computazionale, dell'ACM e dell'Academy of Sciences di New York. Può essere contattato tramite la redazione o su Internet come pescio@programmers.net

Listato 1

int main()
  {
  const n = 20 ;
  const BLOCK_FACTOR = 10 ; // machine-dependent
  const STRIP_SIZE = ( n - 1 ) % BLOCK_FACTOR ;

  int A[ n ][ n ] ;
  int B[ n ][ n ] ;
  int C[ n ][ n ] ;

  // ...
  // init A, B, C

  int iMax = 0 ;
  int kMax = 0 ;
  int jMax = 0 ;

  int iMin = 0 ;
  int iSize = STRIP_SIZE ;
  for( int iBlock = 1; iBlock <= n; iBlock += BLOCK_FACTOR ) 
    {
    iMax = iMax + iSize - 1 ;
    int kMin = 0 ;
    int kSize = STRIP_SIZE ;
    for( int kBlock = 1; kBlock <= n; kBlock += BLOCK_FACTOR ) 
      {
      kMax = kMax + kSize - 1 ;
      int jMin = 0 ;
      int jSize = STRIP_SIZE ;
      for( int jBlock = 1; jBlock <= n; jBlock += BLOCK_FACTOR ) 
        {
        jMax = jMax + jSize - 1 ;
        for( int i = iMin; i <= iMax; i++ )
          for( int j = jMin; j <= jMax; j++ )
            for( int k = kMin; k <= kMax; k++ )
              C[i][j] += A[i][k] * B[k][j] ;
        jMin += jSize ;
        jSize = BLOCK_FACTOR ;
        }
      kMin += kSize ;
      kSize = BLOCK_FACTOR ;
      }
    iMin += iSize ;
    iSize = BLOCK_FACTOR ;
    }
  return( 0 ) ;
  }