Return Value Optimization, Named Value Optimization e Costruttori Operazionali

Dr. Carlo Pescio
Return Value Optimization, Named Value Optimization e Costruttori Operazionali

Pubblicato su C++ Informer No. 1, Dicembre 1997

(questo articolo riprende ed approfondisce uno dei temi discussi nell'intervento "Oggetti ed Efficienza" da me tenuto al Borland Forum '97).

Una delle ragioni per utilizzare il C++ e' l'efficienza del codice generato. I compilatori C++ impiegano un ampio numero di ottimizzazioni "tradizionali", ereditate dal C, ma per ottenere codice realmente efficiente e' necessario introdurre delle ottimizzazioni specializzate [1]. Alcune di esse sono state ritenute cosi' importanti da essere avallate esplicitamente nel documento standard ANSI/ISO (un evento molto raro): in questo articolo vedremo come trarre vantaggio da due di esse, rimandandone una terza al prossimo numero.

Consideriamo una classe piuttosto "corposa", ad esempio una che incapsuli in modo molto semplice un array di interi ed aggiunga una sola funzione "f":


const int SIZE = 500 ;
class Vector  
  {
  public :
    Vector() 
      {}
    Vector f( int x ) ;
  private :
    int v[ SIZE ] ;
  } ;

Notiamo che la funzione Vector::f restituisce un (nuovo) oggetto Vector per valore. La gestione tradizionale (non ottimizzata) di una funzione come f da parte del compilatore e' la seguente:

1) f viene trasformata in una funzione con risultato void, aggiungendo pero' un nuovo parametro che ospitera' il risultato:


// Versione originale
Vector Vector :: f( int x )  
  {
  Vector l ;
  // ...
  // fa qualcosa su l
  // ...
  return( l ) ;
  }
  
// versione trasformata dal compilatore
void Vector :: f( int x, Vector& _result )  
  {
  Vector l ;
  // ...
  // fa qualcosa su l
  // ...

  // applica costruttore di copia (pseudo C++):
  _result.Vector::Vector( l ) ;

  return ;
  }

2) le chiamate ad f vengono trasformate per allinearle alla versione "interna" di f:


// chiamata originale
Vector v ;
Vector g = v.f( 3 ) ;

// versione trasformata, in pseudo-C++
Vector v ; // questo chiama il costruttore di default
Vector g ; // gestione speciale: NO costruttore di default
v.f( 3, g ) ;

Osserviamo che per l'oggetto g NON viene chiamato il costruttore di default, in quanto il suo contenuto verra' comunque sovrascritto all'interno della funzione f.
Questa soluzione (che e' adottata in pratica da tutti i compilatori C++ esistenti) permette di evitare una chiamata al costruttore di default per g, ma richiede ugualmente la chiamata ad un costruttore di copia all'interno di f.
Esistono due possibilita' di ottimizzazione che eliminano anche la chiamata al costruttore di copia, permettendo quindi di generare codice molto piu' efficiente. In realta', entrambe le ottimizzazioni vengono ottenute applicando la stessa tecnica, ma in situazioni diverse.

Return Value Optimization
Supponiamo che sulla nostra classe Vector sia definito anche un operatore di somma, e che la versione originale di f fosse la seguente:


// versione iniziale
Vector Vector :: f( int x )  
  {
  Vector l ;
  // ... inizializza l con tutti 1
  return( *this + l ) ;
  }

notiamo che f restituisce un oggetto anonimo, ovvero non legato ad alcun identificatore. In questo caso f verra' trasformata (secondo l'approccio "classico" di cui sopra) in questa versione:


// versione "standard" trasformata dal compilatore
void Vector :: f( int x, Vector& _result )  
  {
  Vector l ;
  // ... inizializza l con tutti 1
  Vector tmp ; // NO costruttore di default
  Vector::operator+( *this, l, tmp ) ;
  // applica costruttore di copia (pseudo C++):
  _result.Vector::Vector( tmp ) ;
  return ;
  }

tuttavia il compilatore puo' facilmente eliminare l'oggetto tmp e il costruttore di copia da tmp in _result, semplicemente mettendo il risultato direttamente dentro _result:


// versione ottimizzata
void Vector :: f( int x, Vector& _result )  
  {
  Vector l ;
  // ... inizializza l con tutti 1
  Vector::operator+( *this, l, _result ) ;
  return ;
  }

Questa ottimizzazione viene detta Return Value Optimization (RVO) e si applica solo quando l'oggetto restituito e' anonimo. Un modo per ottenere un oggetto anonimo e' di "costruirlo al volo" nello statement return. Cio' significa (ad esempio) che usando un compilatore che implementa la (sola) RVO e' meglio scrivere codice come questo:


Vector Vector :: operator +( const Vector& r )
  {
  return( Vector( *this ) += r ) ;
  }

che codice come questo:

Vector Vector :: operator +( const Vector& r )
  {
  Vector l = *this ;
  l += r ;
  return( l ) ;
  }

o come questo:

Vector Vector :: operator +( const Vector& r )
  {
  Vector l ;
  // ... loop sugli elementi, assegna
  //     a l[i] la somma di *this[i] e r[i]
  return( l ) ;
  }

Solo nel primo caso, infatti, restituiamo un oggetto anonimo ed il compilatore riesce ad applicare la RVO. Nota importante: la RVO e' gia' implementata in molti compilatori commerciali, ad esempio Borland e Microsoft. Cercate di sfruttarla quando volete ottenere codice piu' efficiente, adattando lo stile di programmazione come sopra.

Named Value Optimizazion
In linea di principio, la stessa tecnica di trasformazione del codice che e' alla base della RVO puo' essere impiegata dal compilatore anche quando l'oggetto restituito ha un nome.
Supponiamo che f sia implementata come segue:

// versione iniziale
Vector Vector :: f( int x )  
   {
   Vector l ;
   l.v[ 0 ] = v[ 0 ] + x ;
   l.v[ 499 ] = v[ 499 ] + x ;
   return( l ) ;
   }

Il compilatore la trasformerebbe come segue:

// versione "standard" trasformata dal compilatore
void Vector :: f( int x, Vector& _result )  
  {
  Vector l ; // qui chiama costruttore di default
  l.v[ 0 ] = v[ 0 ] + x ;
  l.v[ 499 ] = v[ 499 ] + x ;
  // applica costruttore di copia 
  // (pseudo C++):
  _result.Vector::Vector( l ) ;
  return ;
  }

Aggiungiamo ora una ulteriore ipotesi, ovvero che tutti gli statement di return all'interno della versione iniziale si riferiscano allo stesso oggetto. La nostra funzione f ovviamente soddisfa questa ipotesi, perche' vi e' un solo return in tutta la funzione. Il compilatore puo' allora eliminare quell'oggetto ("l" nel nostro esempio) ed utilizzare al suo posto _result.


// Named Value Optimization
void Vector :: f( int x, Vector& _result )  
  {
  // applica costruttore di default 
  // a _result (pseudo C++):
  _result.Vector::Vector() ;
  _result.v[ 0 ] = v[ 0 ] + x ;
  _result.v[ 499 ] = v[ 499 ] + x ;
  return ;
  }

Notiamo che il costruttore di copia e' sparito, e che il costruttore di default ora viene chiamato su _result anziche' su l come avveniva nel listato caso precedente.
Vale la pena di ripetere che, affinche' il compilatore possa applicare la NVO, tutti i return devono essere riferiti allo stesso oggetto. Un buon metodo e' di evitare i return multipli (che peraltro spesso sono fonte di problemi), scrivendo funzioni con un unico punto di uscita. Nuovamente, puo' essere necessario adattare il proprio stile di programmazione, ma in genere il risultato e' un codice facilmente leggibile, proprio perche' non si restituiscono mai oggetti diversi in casi diversi.
Purtroppo la NVO e' una ottimizzazione relativamente recente: pochi compilatori la implementano, e tra questi non troviamo, ad esempio, Borland e Microsoft. Fortunatamente, se proprio vogliamo scrivere codice efficiente, esiste una tecnica "manuale" per ottenere gli stessi benefici.

Costruttori operazionali
Se il vostro compilatore implementa la RVO ma non la NVO (come la maggioranza in questo momento), potete arginare il problema creando un costruttore ad-hoc. Tornando all'esempio preso in esame per la NVO, possiamo modificare la classe Vector come segue:


class Vector
  {
  public :
    Vector() {}
    Vector f( int x ) ;
  private :
    int v[ 500 ] ;
    // costruttore operazionale:
    Vector( const Vector& r, int x ) ;
  } ;

Vector Vector :: f( int x )
  {
  // chiama direttamente 
  // il costruttore operazionale
  return( Vector( *this, x ) ) ;
  }

Vector :: Vector( const Vector& r, int x )
  {
  // fa quello che faceva f 
  // nei listati precedenti:
  v[ 0 ] = r.v[ 0 ] + x ;
  v[ 499 ] = r.v[ 499 ] + x ;
  }

L'idea di base e' molto semplice: introdurre un costruttore ad-hoc, mantenendolo privato, che svolge gli stessi compiti che erano originariamente svolti da f. A questo punto, f puo' restituire un oggetto anonimo, facendo intervenire la RVO. Volendo, f puo' anche diventare una funzione inline, dal momento che il suo corpo si riduce ad un semplice return.
Notiamo che e' preferibile definire il costruttore operazionale come private, in quanto si tratta di un dettaglio implementativo di f. Inoltre, nell'esempio dato il costruttore operazionale si distingue dagli altri grazie ai parametri aggiuntivi, ma in altri casi si dovranno introdurre degli appositi tipi "fasulli" per eliminare le ambiguita'. Provate ad esempio ad ottimizzare questa funzione, facendola convivere con f:


Vector Vector :: g( int x )  
   {
   Vector l ;
   l.v[ 0 ] = v[ 0 ] * x ;
   return( l ) ;
   }

Conclusioni

Vale la pena di scrivere codice meno leggibile (con costruttori operazionali) pur di ottimizzare le prestazioni? Dipende. A titolo di esempio, la versione originale di f, compilata con il Borland C++ Builder con tutte le ottimizzazioni abilitate, richiede circa 6500 cicli di clock su un processore Pentium. La versione con costruttore operazionale richiede circa 10 cicli di clock. In questo caso il salto di prestazioni e' enorme (650 volte piu' veloce), ma va in gran parte attribuito all'esempio un po' patologico ("effetto cache"). In casi piu' realistici (ad esempio, l'inversione di una matrice) l'incremento di prestazioni e' comunque molto sensibile, di solito nell'ordine del 25-30%. Naturalmente, se il vostro compilatore supporta la NVO, potete evitare i costruttori operazionali e scrivere codice efficiente e leggibile allo stesso tempo.

Bibliografia
[1] Carlo Pescio, "Ottimizzazioni e C++", Computer Programming No. 47.

Biografia
Carlo Pescio (pescio@eptacom.net) svolge attività di consulenza, progettazione e formazione in ambito internazionale. Ha svolto la funzione di Software Architect in grandi progetti per importanti aziende europee e statunitensi. È autore di numerosi articoli su temi di ingegneria del software, programmazione C++ e tecnologia ad oggetti, apparsi sui principali periodici statunitensi, nonché dei testi "C++ Manuale di Stile" ed "UML Manuale di Stile". Laureato in Scienze dell'Informazione, è membro dell'ACM, dell'IEEE e dell'IEEE Technical Council on Software Engineering.