Dr. Carlo Pescio Algoritmi come Metaprogrammi Template in C++

Pubblicato su Computer Programming No. 56

Introduzione
La metaprogrammazione template è la tecnica di programmazione C++ più recente, ed ancora poco nota nella comunità degli sviluppatori C++. Non a caso, dopo aver accennato alle potenzialità dei metaprogrammi nell'ottimizzazione del codice durante la presentazione "C++: lo stato del linguaggio" allo scorso C++ Forum, molte persone mi hanno richiesto via email di approfondire l'argomento, anche perché la relativa bibliografia è al momento piuttosto scarna. In questo articolo vedremo come sia possibile utilizzare la metaprogrammazione per spostare a tempo di compilazione alcuni calcoli che sarebbero normalmente eseguiti a run-time, o per generare automaticamente versioni specializzate di algoritmi generali, ottimizzate per l'insieme di dati che vogliamo trattare.

Metaprogrammi Template
Un metaprogramma template [1] è un programma che viene interpretato dal compilatore a tempo di compilazione, anziché essere eseguito a run-time. Come risultato dell'interpretazione, possiamo ottenere un valore oppure una funzione. Tutto questo, naturalmente, senza bisogno di estendere il linguaggio in alcun modo: tutti i listati che vedremo sono stati provati anche su compilatori non recentissimi (Borland 4.02, Microsoft 4.0) nonché su uno decisamente vecchio (GNU 2.6.0), anche se alcune tecniche più avanzate, qui solo accennate, potrebbero richiedere la specializzazione parziale dei template, tuttora assente in molti compilatori.
Il concetto di metaprogramma può sembrare un pò ostico, quindi è opportuno introdurre immediatamente un esempio; consideriamo una semplice funzione ricorsiva scritta in C++, che calcola a tempo di esecuzione 10^N, dove N è una costante:

int TenN( unsigned int n )
  {
  if( n == 0 )
    return( 1 ) ;
  else 
    return( 10 * TenN( n - 1 ) ) ;
  }

const int a = TenN( 4 ) ;
int b[ a ] ;

#include <iostream.h>

template <int N> struct TenN
  {
  enum 
    { val = 10 * 
      TenN< N-1 > :: val } ;
  } ;

struct TenN< 0 >
  {
  enum { val = 1 } ;
  } ;

int main()
  {
  const int n = 
    TenN< 4 > :: val ;
  cout << n ;
  return( 0 ) ;
  } 

;  const int n = 
;  TenN< 4 > :: val ;
;  cout << n ;
push	0
push	10000
push	offset DGROUP:_cout
call	near ptr @ostream@$blsh$ql

Come vedete, il risultato del metaprogramma TenN< 4 > :: val è esattamente la costante 10000, calcolata a tempo di compilazione. Questo può risultare abbastanza sorprendente, ed in effetti la metaprogrammazione template è una tecnica recente proprio perché nessuno aveva pensato di utilizzare i template in un modo così originale; d'altra parte, il fatto stesso che il compilatore sia in grado di interpretare un metaprogramma durante la compilazione fa capire quanto complesso sia ormai diventato il C++. I template "costringono" il compilatore ad includere al suo interno un interprete in grado di calcolare funzioni ricorsive; con le future estensioni, queste meta-funzioni potranno anche avere parametri default (come le funzioni "normali" del C++), ed il compilatore dovrà supportare anche una forma di overloading (specializzazione parziale) delle meta-funzioni. Non meraviglia, quindi, che parecchi compilatori abbiano dei bug nella gestione dei template, che è più complessa di quanto possa sembrare a prima vista.

Costanti Calcolate come Metaprogrammi
In generale possiamo usare un metaprogramma template per calcolare una qualsiasi funzione f: N ⁿ N, quando gli argomenti della funzione siano noti a tempo di compilazione. Ad esempio, molti programmi di grafica (e molti videogame) utilizzano delle tabelle precalcolate per velocizzare alcuni processi di calcolo: un caso tipico sono le tabelle di seni e coseni. Tali tabelle sono normalmente inserite a mano dal programmatore, come parte del codice. Sarebbe molto più elegante e mantenibile scrivere un metaprogramma che calcola la funzione, e lasciare poi al compilatore il compito di valutare la funzione nei punti desiderati. Dobbiamo, ovviamente, riuscire a scrivere il corrispondente metaprogramma template, ma questo è di solito piuttosto semplice una volta che siamo riusciti a scrivere la funzione in forma ricorsiva. Vediamo un esempio, ispirato da un algoritmo per il calcolo della radice quadrata tramite sviluppo in serie preso da [2], dove viene presentato in forma iterativa:

unsigned long 
sqrti( unsigned long n )
  {
  unsigned long m = n / 2 ;
  if( n <= 1 )
    return( n ) ;
  unsigned long c ;
  do
    {
    c = m ;
    m = ( m + n / m ) / 2 ;
    }
  while( m < c ) ;
  return( c ) ;
  }

Prima di passare al metaprogramma, è spesso utile scrivere un corrispondente programma ricorsivo in C++: ricordiamo infatti che il metaprogramma "gira" a tempo di compilazione, quando non sono disponibili strumenti di debugging e quindi, in generale, un errore nel metaprogramma sarà molto difficile da correggere rispetto ad un tradizionale errore di programmazione. Un debugger per metaprogrammi dovrebbe mostrare le strutture interne di parsing del compilatore, e per quanto una simile possibilità sia sinceramente auspicata dai programmatori esperti (per molte ragioni non direttamente collegate ai metaprogrammi) non credo sia nei piani di nessun produttore di compilatori. Un metaprogramma richiede quindi una fase preparatoria più accurata, almeno sin quando non si è raggiunta una certa confidenza con le tecniche di metaprogrammazione, e la prototipazione sotto forma di un tradizionale programma C++ può sicuramente aiutare. Trasformare un programma iterativo come il precedente in uno ricorsivo è in genere piuttosto semplice, trattandosi di poco più della trasformazione di ogni loop in una singola funzione ricorsiva: il seguente listato implementa ricorsivamente la stessa funzione sqrti del listato precedente.

unsigned long 
sq( unsigned long n, 
    unsigned long s )
  {
  unsigned long m = 
    ( s + n / s ) / 2 ;
  if( m >= s )
    return( s ) ;
  else
    return( sq( n, m ) ) ;
  }

unsigned long 
sqrti( unsigned long n )
  {
  if( n <= 1 )
    return( 1 ) ;
  else
    return( sq( n, n / 2 ) ) ;
  }

Adesso siamo pronti a trasformare il programma in un metaprogramma, anche se la trasformazione non sarà così immediata come potremmo aspettarci, e dovremo fare ricorso ad un piccolo trucco per garantire la corretta terminazione del metaprogramma (che, ricordiamo, significa corretta compilazione).

template< unsigned long s, 
          unsigned long n > 
struct SqrA
  {
  enum { 
    recurse = 
    ( s + n / s ) / 2 < s } ;
  enum { 
    value = 
    ! recurse ? 
    s : 
    SqrA< recurse * ( s + n / s ) / 2,
          recurse * n > :: value } ;
  } ;

struct SqrA< 0, 0 >
  {
  enum { value = 0 } ;
  } ;

template< unsigned long n > 
struct SqrtI
  {
  enum { value = 
         SqrA< n / 2, n > :: value } ;
  } ;

struct SqrtI< 0 >
  {
  enum { value = 0 } ;
  } ;

struct SqrtI< 1 >
  {
  enum { value = 1 } ;
  } ;s

Vediamo le particolarità del metaprogramma: innanzitutto, la funzione sqrti conteneva uno statement if che va eliminato, nuovamente usando la specializzazione di template; siccome il parametro n è di tipo unsigned, e la condizione è if( n <= 1 ), dobbiamo dare una specializzazione esplicita per i casi n = 0 ed n = 1. Come si vede, la trasformazione dei condizionali in clausole di specializzazione è un punto molto delicato nella metaprogrammazione, e non è totalmente meccanico. La parte più complessa del metaprogramma è comunque la seguente:

enum { 
  value = 
  ! recurse ? 
  s : 
  SqrA< recurse * ( s + n / s ) / 2,
        recurse * n > :: value } ;

In effetti, il primo approccio, guidato dal programma ricorsivo, potrebbe essere quello di scrivere il metaprogramma come segue:

enum { 
  value = 
  ! recurse ? 
  s : 
  SqrA< ( s + n / s ) / 2, 
        n > :: value } ;

che è una traduzione più o meno diretta del programma in un metaprogramma. Purtroppo il metaprogramma "banale" non termina, in quanto al momento dell'interpretazione del metaprogramma (che, dovrebbe ormai essere chiaro, è il momento della compilazione e non dell'esecuzione) il compilatore cercherà comunque di istanziare l'intera espressione prima di valutarla. Quindi, anche se la sottoespressione che segue i ":" non viene valutata, deve comunque essere istanziata, e questo impedisce la terminazione del metaprogramma. Rivediamo invece la versione "furba" (o più semplicemente, funzionante) del metaprogramma: recurse vale 1 quando dobbiamo valutare la sottoespressione template, e 0 quando non dobbiamo valutarla. Moltiplicando i parametri della sottoespressione template per recurse, otteniamo i valori stessi quando l'espressione deve essere valutata, e <0, 0> quando non deve. A questo punto, definiamo il template esplicitamente su <0, 0> e garantiamo così la terminazione del metaprogramma.

Appunti di metaprogrammazione
Naturalmente, potremmo desiderare una sintassi più leggibile nel punto di chiamata: scrivere SqrtI<5> :: value non è esattamente il modo migliore per rendere il codice cristallino. In questo caso lo strumento migliore è la buona vecchia #define, che ci consente di aggiungere un pò di zucchero sintattico dove serve; una macro come la seguente:

#define sqrti(N) \
SqrtI<(N)>::value)

ci permetterà di usare un più leggibile sqrti(5) in luogo della più complessa sintassi vista sopra.
Provando i vari metaprogrammi, sono emersi alcuni, immancabili problemi con qualche compilatore: in questo caso, si tratta del Borland C++ 4.02. Per quanto lo standard ANSI/ISO stabilisca che un enumerato può assumere qualunque valore nel range di un tipo integral (quindi int, unsigned, o long), il Borland utilizza solo 16 bit per i tipi enumerati. Quindi in alcuni casi le nostre funzioni potrebbero generare un overflow, che non viene segnalato a tempo di compilazione ma che, ovviamente, si riflette sul comportamento a run-time del programma. Purtroppo non vi sono molte soluzioni, se non limitare il range dei valori calcolati dal metaprogramma o passare ad un altro compilatore; mi risulta però che la versione 5.0 del Borland abbia problemi ben peggiori sui template, tanto da non riuscire a compilare molti dei metaprogrammi più semplici: non ho avuto modo di provare le versioni 5.x e non so quindi se tali problemi siano stati eliminati.
Esistono inoltre situazioni in cui la soluzione più elegante richiede l'uso della specializzazione parziale dei template, prevista dallo standard ANSI/ISO ma non ancora implementata dalla maggior parte dei compilatori. Vediamo un semplice esempio: supponiamo di voler scrivere un metaprogramma template per calcolare X ^N, dove X ed N sono costanti; possiamo "estendere" il metaprogramma TenN, e trascurando alcuni problemi su 0 ⁰, scrivere un metaprogramma Power come segue:

template <int X, int N> 
struct Power
  {
  enum { 
    val = X * 
    TenN< N-1 > :: val } ;
  } ;

template <int X, 0> 
struct Power
  {
  enum { val = 1 } ;
  } ;

Purtroppo questo metaprogramma non è (attualmente) legale; si può certamente risolvere il problema senza usare la specializzazione parziale, ma si devono necessariamente usare un pò di trucchi: provare a scrivere un metaprogramma Power che funzioni correttamente con il vostro compilatore è sicuramente un esercizio interessante.

Infine, ricordiamo che le espressioni coinvolte in un metaprogramma template devono essere costanti a tempo di compilazione: non possiamo quindi chiamare funzioni, dereferenziare puntatori, e così via. È comunque possibile sfruttare questa limitazione (molto forte dal punto di vista del riuso) per segnalare degli errori nel metaprogramma. Supponiamo infatti che solo certi valori siano ammissibili come parametri del metaprogramma: a titolo di esempio, supponiamo che solo gli interi pari siano ammissibili. Il nostro metaprogramma dovrebbe quindi avere una forma del tipo:

template <int N> struct S
  {
  enum { 
    val = (N&1) ? errore : 
    espressione } ;
  } ;

Con N&1 verifichiamo se il parametro è dispari o meno; "errore" dovrebbe far generare un errore di compilazione (dato che il metaprogramma è interpretato a compile-time), mentre "espressione" dovrebbe calcolare qualche valore, che al momento non ci interessa. Come possiamo generare un errore a compile-time? In effetti, in C++ non esiste un grande supporto per situazioni simili - la metaprogrammazione è una tecnica "collaterale" di programmazione, che pur essendo molto utile non fa parte degli idiomi di programmazione supportati ufficialmente dal linguaggio. Tuttavia, un minimo di creatività ci porta proprio a sfruttare la limitazione vista sopra a nostro vantaggio; il seguente metaprogramma genera un errore di compilazione se il parametro non è pari:

int NeedEvenParam()
  {
  return( 0 ) ;
  }

template <int N> struct S
  {
  enum { 
    val = (N&1) ? 
    NeedEvenParam() : 
    espressione } ;
  } ;

Se il parametro non è pari, il compilatore si troverà con una chiamata a NeedEvenParam che non sa gestire nel metaprogramma, e segnalerà un errore di compilazione; il messaggio di errore dipende dal singolo compilatore, ma conterrà il simbolo NeedEvenParam o, nel peggiore dei casi, conterrà il numero di riga dove NeedEvenParam è definita. Usando un nome significativo per la funzione (che spieghi quindi la ragione dell'errore), riusciremo comunque a comunicare l'errore in modo intelleggibile, pur senza grande supporto da parte del compilatore.
Possiamo ora riassumere per comodità le tecniche di conversione da programma a metaprogramma template viste sinora:

1. Le costanti vanno definite attraverso l'uso di tipi enumerati.
2. L'iterazione va trasformata in ricorsione.
3. Il condizionale va trasformato in specializzazione di template; questo può comportare l'introduzione di trucchi analoghi a quello visto sopra per l'operatore ?.
4. Le espressioni coinvolte in un metaprogramma devono essere costanti a compile-time.
5. In genere è opportuno usare una macro per semplificare la chiamata dei metaprogrammi.
6. Attenzione al range degli enumerati nel vostro compilatore se usate un metaprogramma per calcolare delle costanti.
7. Possiamo generare errori di compilazione intenzionali, chiamando funzioni esterne.

Algoritmi specializzati come Metaprogrammi
L'uso di un metaprogramma per calcolare dei valori a compile-time è interessante, ed ha anche potenzialità inaspettate [3], ma le possibilità dei metaprogrammi non si esauriscono qui; come accennato nell'introduzione, possiamo usare la metaprogrammazione per generare in modo automatico una versione ottimizzata di un algoritmo. Nuovamente, vediamo un esempio reale: quando dobbiamo ordinare un insieme di numeri, possiamo utilizzare la funzione di libreria qsort che ordina un array utilizzando l'algoritmo di quicksort, e che richiede solo di scrivere una funzione callback che effettua la comparazione degli elementi. D'altro canto, supponiamo di voler ordinare due soli elementi: allora fare una chiamata a quicksort è veramente inefficiente, e la maggior parte dei programmatori implementerà l'algoritmo "in linea" come segue:

if( a > b )
  Swap( a, b ) ;

E se dovessimo ordinare tre elementi? O quattro? O dieci? È difficile dire sino a quando un algoritmo specializzato per ordinare n elementi rimane conveniente rispetto ad una chiamata a quicksort; certamente scrivere un algoritmo specializzato per ordinare dieci elementi non è banale, e dal punto di vista della manutenzione un approccio del genere è raramente consigliabile. Ad esempio, in [4] l'autore propone un algoritmo ottimizzato per trovare l'elemento mediano tra 9 valori, un'operazione usata di frequente in image processing; tuttavia passare ad una griglia 5x5, ovvero 25 elementi, significa reimplementare da zero (o quasi) l'intera funzione.
D'altro canto, molti algoritmi "efficienti" sono studiati per ridurre l'ordine di complessità computazionale, ma la complessità è un concetto asintotico: di conseguenza, non è raro che su insiemi non troppo grandi algoritmi più semplici, ma ottimizzati per la cardinalità dell'insieme, risultino più veloci. L'ideale sarebbe poter definire un algoritmo "parametrico" e lasciare poi al compilatore il compito di specializzarlo sui singoli casi per ottenere un codice più efficiente. Rimanendo all'interno del C++, un metaprogramma template è la possibilità più vicina a questo ideale.
Vediamo come sia possibile implementare un algoritmo generale come metaprogramma: in questo caso ho preso come riferimento il selection sort, che è normalmente definito come segue (assumendo un array di N elementi):

for( int i = 0; i < n; i++ )
  {
  cerca il minimo tra 
  a[i], ..., a[ n-1 ]
  scambia a[i] con tale valore
  }

Come in precendenza, prima di passare ad un metaprogramma proviamo a scrivere una versione ricorsiva dell'algoritmo, in modo da poterla testare ed adattare con maggiore facilità:

void Swap( int& a, int& b )
  {
  int t = a ;
  a = b ;
  b = t ;
  }

int Min( int*a, 
         int base, 
         int len )
  {
  if( len )
    {
    int k = 
    Min( a, base+1, len-1 ) ;
    if( a[base] < a[k] )
      return( base ) ;
    else
      return(k) ;
    }
  else
    return( base ) ;
  }


void Sort( int* a, 
           int base, 
           int len )
  {
  if( len )
    {
    int i = Min( a, base, len ) ;
    Swap( a[base], a[i] ) ;
    Sort( a, base+1, len-1 ) ;
    }
  }

Usando una tecnica tipica della programmazione funzionale (dove l'uso della ricorsione anziché dell'iterazione è la norma e non l'eccezione) ho passato un ulteriore parametro alla funzione Sort, che ha lo stesso scopo dell'indice all'interno di un loop. Alla chiamata, il parametro base sarà sempre posto a zero. Vediamo ora una implementazione di Sort come metaprogramma template:

inline void Swap( int& a, int& b )
  {
  int t = a ;
  a = b ;
  b = t ;
  }

template< int len > 
struct SelSort
  {
  inline static void 
  Sort( int* a, int base )
    { 
    const int i = Min( a, base ) ;
    Swap( a[base], a[i] ) ;
    SelSort<len-1>::Sort( a, base+1 ) ;
    }
  inline static int 
  Min( int*a, int base )
    {
    int k = 
    SelSort<len-1>::Min( a, base+1 ) ;
    if( a[base] < a[k] )
      return( base ) ;
    else
      return(k) ;
    }
  } ;


struct SelSort<0>
  {
  inline static void 
  Sort( int*, int )
    {
    }
  inline static int 
  Min( int*, int base )
    {
    return( base ) ;
    }
  } ;

struct SelSort<1>
  {
  inline static void 
  Sort( int*, int )
    {
    }
  inline static int 
  Min( int*, int base )
    {
    return( base ) ;
    }
  } ;

int main()
  {
  int a[5] = { 11, 6, 9, 4, 1 } ;
  SelSort<5>::Sort( a, 0 ) ;

  return( 0 ) ;
  }

Possiamo osservare che il metaprogramma si ottiene in modo quasi automatico dal programma ricorsivo, applicando le regole di conversione viste prima. Anche in questo caso, una macro avrebbe reso la chiamata più leggibile ed eliminato la necessità di specificare il secondo parametro, che come detto sarà sempre zero. Un utile, per quanto semplice, esercizio di programmazione generica è la trasformazione del metaprogramma dato sopra (che ordina solo array di interi) in uno in grado di ordinare un tipo T qualunque. Rimanendo per semplicità nel campo degli interi, vi sono comunque due punti del metaprogramma che meritano un approfondimento, prima di discutere l'efficienza del codice generato dal compilatore:

1. il condizionale if( a[base] < a[k] ) è proprio uno di quelli che non possono essere trasformati in specializzazione di template, dal momento che la condizione non è verificabile a tempo di compilazione. Fortunatamente, nel contesto in cui appariva non è stato necessario trasformarlo. Se fosse apparso in un metaprogramma per il calcolo di una costante (non in un algoritmo specializzato) avremmo avuto dei seri problemi.
2. la specializzazione SelSort<1> è stata introdotta per incrementare ulteriormente l'efficienza, non per necessità. Avremmo potuto definire semplicemente la versione specializzata SelSort<0>, tuttavia SelSort<1> sarebbe implicitamente risultata come:

inline static void 
Sort( int* a, int base )
  { 
  const int i = Min( a, base ) ;
  Swap( a[base], a[i] ) ;
  }
inline static int 
Min( int*a, int base )
  {
  int k = base ;
  if( a[base] < a[k] )
    return( base ) ;
  else
    return(k) ;
  }

che è sensibilmente meno efficiente della specializzazione data. La specializzazione SelSort<0> è stata comunque lasciata per completezza.
Vediamo ora cosa avviene quando istanziamo il metaprogramma, il che avviene al momento di una chiamata come SelSort<5>::Sort( a, 0 ): il compilatore deve istanziare SelSort<5>, che consiste di due funzioni inline che richiamano funzioni inline di SelSort<4> e così via. Così come nel caso del metaprogramma per il calcolo di una costante il risultato era un unico valore, qui il risultato è un'unica funzione inline, ottenuta espandendo ricorsivamente il corpo delle funzioni inline richiamate. Naturalmente, il codice risultante da diverse chiamate a SelSort sarà ogni volta espanso in linea, e questo implica un aumento di dimensioni dell'eseguibile; come vedremo, ciò e in molti casi più che compensato dal corrispondente aumento di prestazioni.
Naturalmente, chi ha un pò di esperienza tende a diffidare di ogni soluzione miracolosa: viene quindi da chiedersi quale sia il lato oscuro dei metaprogrammi, tralasciando la maggiore difficoltà di sviluppo e l'aumento di dimensioni del codice. A mio parere, la più forte limitazione dei metaprogrammi è che richiedono la conoscenza statica, a compile-time, dei loro parametri; non possiamo quindi avere un algoritmo ottimizzato per ordinare n elementi se n è noto solo a tempo di esecuzione. Si tratta di un vincolo molto restrittivo, che rende la metaprogrammazione inutilizzabile in parecchi casi; quando però tale vincolo non si applica (pensiamo nuovamente al calcolo della mediana su una griglia di dimensione fissa) allora la metaprogrammazione è uno strumento di grande potenza.
Possiamo ora aggiungere alle precedenti note di metaprogrammazione i seguenti criteri:

1. La specializzazione può essere usata anche per aumentare l'efficienza dei metaprogrammi.
2. Gli algoritmi specializzati sono implementabili come metaprogrammi solo se le costanti di specializzazione sono note a tempo di compilazione.

Prestazioni
Fino a quando è conveniente usare un algoritmo ottenuto per istanziazione di un metaprogramma? Possiamo aspettarci che, per piccoli insiemi di dati, il metaprogramma si comporti meglio della funzione di libreria qsort, mentre al crescere della cardinalità il vantaggio tenderà ad invertirsi, anche (ma non solo) perché la nostra SelSort ha complessità nell'ordine di N² (dove N è la cardinalità dell'insieme da ordinare), mentre quicksort ha complessità nel caso medio in O(N log(N)), e nel caso peggiore O(N²). Sorprendentemente, soprattutto se confrontati con i risultati di Veldhuizen [1] (relativi ad un meno efficiente bubble sort come metaprogramma, ma confrontato sempre con un bubble sort e non con quicksort) il metaprogramma si comporta molto bene anche per insiemi non piccolissimi; usando il Microsoft Visual C++ 4.0 ho ottenuto i seguenti risultati: per N = 5, il metaprogramma è in media 15 volte più veloce di qsort. Per N = 10, in media 3 volte più veloce; per N = 20, sempre 3 volte più veloce; ho raggiunto i limiti del compilatore sulla ricorsione prima di poter invertire il rapporto di speedup. Ho ottenuto questi risultati lanciando più volte un programma che calcolava il tempo medio di sorting su due array con gli stessi elementi random, su 10000 diversi array, usando il metaprogramma e qsort; si tratta quindi di un risultato piuttosto significativo, considerando anche la dimensione ridotta degli array stessi.
È molto interessante notare che i risultati riportati per bubble sort [1] sono peggiori di un fattore 2 circa rispetto al selection sort, per quanto possano esserci differenze dovute al compilatore; a questo punto sarebbe un ottimo esperimento provare ad implementare come metaprogrammi degli algoritmi di sorting più sofisticati, ad esempio insertion sort o un sort binario. Purtroppo, da alcune prove mi sembra che un buon metaprogramma che implementi insertion sort richieda la specializzazione parziale, così come probabilmente accade per altri algoritmi più efficienti.
Va anche detto che, compilando con il massimo livello di warning, possiamo vedere che il compilatore non espande realmente in linea tutte le funzioni del template quando N = 10 (e ovviamente, anche per N=20); ricordiamo infatti che inline è solo un suggerimento al compilatore, il quale non è realmente tenuto ad espandere in linea il codice. Probabilmente, un compilatore che ponga limiti diversi all'espansione in linea potrebbe generare codice anche più efficiente di quello ottenuto con il Visual C++, che comunque si comporta già piuttosto bene.

Conclusioni
I metaprogrammi template sono l'attuale frontiera della programmazione C++, e consentono di risolvere problemi vecchi (e non) con un nuovo strumento: ad esempio, in [3] ho dimostrato come sia possibile usare un metaprogramma per implementare un supporto per le costanti binarie in C++ (che supporta solo costanti decimali, esadecimali ed ottali). Prima della metaprogrammazione template, un simile risultato era ottenibile solo con un preprocessore specializzato.
La metaprogrammazione ha subito riscosso un grande interesse nel campo del calcolo numerico [5], tanto che esiste un gruppo di ricerca che si occupa proprio di applicare le tecniche di metaprogrammazione ai problemi di algebra lineare: chi fosse interessato, può trovare maggiori dettagli su internet, alla home page del progetto Blitz.
Ed infine, la metaprogrammazione rappresenta anche la rivincita della ricorsione, dell'espansione in serie delle funzioni, e di un insieme di tecniche precedentemente un pò neglette ed accusate di inefficienza, che possono ora essere usate con successo per spostare a compile-time dei calcoli normalmente eseguiti a run-time. Anche se la metaprogrammazione è tuttora nella sua infanzia, chiunque abbia un interesse particolare per l'efficienza del codice dovrebbe provare ad implementare i suoi algoritmi come metaprogrammi: quando le estensioni ANSI/ISO ai template verranno rese disponibili su ogni compilatore, i metaprogrammi template diventeranno probabilmente la norma, più che l'eccezione, per risolvere problemi di efficienza.

Reader's Map

Molti visitatori che hanno letto questo articolo hanno letto anche:

Bibliografia
[1] Todd Veldhuizen, "Using C++ Template Metaprograms", C++ Report Vol 7 No 4.
[2] Cristopher J. Musial, "An Integer Square Root Algorithm", in Graphics Gems II, Academic Press.
[3] Carlo Pescio, "Binary Constants using Template Metaprogramming", C/C++ Users Journal, February 1997.
[4] Alan W. Paeth, "Median Finding on a 3x3 Grid", in Graphics Gems I, Academic Press.
[5] Todd Veldhuizen, Kumaraswamy Ponnambalam, "Linear Algebra with C++ Template Metaprograms", Dr. Dobb's Journal No 250, August 1996.

Biografia
Carlo Pescio (pescio@acm.org) svolge attività di consulenza in ambito internazionale nel campo delle tecnologie Object Oriented. Ha svolto la funzione di Software Architect in grandi progetti per importanti aziende europee e statunitensi. È incaricato della valutazione dei progetti dal Direttorato Generale della Comunità Europea come Esperto nei settori di Telematica e Biomedicina. È laureato in Scienze dell'Informazione ed è membro dell'ACM, dell'IEEE e della New York Academy of Sciences.