Newsgroup: it.comp.lang.c++
Titolo: Ottimizzare con  i template (lunghetto)

Salve a tutti,
provo a postare uno spunto di riflessione, sperando che qualcuno possa
aiutarmi
scrivo software di Computer Vision, dove uno dei requisiti fondamentali è la
velocità di esecuzione (almeno per la mia applicazione che è praticamente
real time).
Uno dei problemi che mi trovo spesso a dover affrontare, è quello di dover
scrivere parti di codice "quasi" identiche.
Il punto è quello di trovare una soluzione che mi permetta di avere una
buona manutenibilità del codice, una discreta "debuggabilità" e la migliore
velocità di esecuzione.
Provo a spiegarmi con un esempio in pseudocodice (banale ma efficace per
capire il problema):
bool bUseMask;
...
for(....) //foreach pixel in image i.e. 3 MPixel
{
    v = getpixel(x,y);
    if(!bUseMask || v != MASK_VALUE )
    {
        ... // do elaboration
    }
}
Supponiamo che questo sia l'algoritmo da implementare:
M (manutenibilità) OTTIMA: la parte da mantenere (do elaboration) è scritta
una volta sola in maniera compatta e chiara
D (debuggabilità) OTTIMA: con il mio debugger (VisualStudio) riesco a fare
qualunque cosa
V (velocità) PESSIMA: il test  if(!bUseMask || v != MASK_VALUE ) viene
eseguito per ogni pixel, anche per le immagini che non ne hanno bisogno che
potrebbero essere la maggior parte....
Nella mia testa ho ipotizzato 3 soluzioni praticabili:
1-Cut&Paste
Duplico il codice e aggiusto le parti necessarie. Questa tecnica è
mostrusamente efficace nelle prime fasi del progetto, ma è scarsamente
manutenibile:
M SCARSA: se modifico l'algoritmo devo ricordarmi di modificare tutte le
varianti e il rischio di sbagliare è alto
D OTTIMA
V OTTIMA: ogni ramo è hard coded in modo perfettamente ottimizzato
2-Preprocessore
Per piccole parti, utilizzo macro con parametri, oppure sfrutto il
preprocessore per fargli generare un analogo della sol. 1
Es.
...
#define USEMASK
#include "mycode.h"
...
#undef USEMASK
#include "mycode.h"
...
//mycode.h
for(....) //foreach pixel in image i.e. 3 MPixel
{
    v = getpixel(x,y);
#ifdef USEMASK
    if(v != MASK_VALUE )
 #endif
    {
        ... // do elaboration
    }
}
riassumendo:
M DISCRETA: in realtà è più complicato del previsto, si rischia un intreccio
complicato di files, certe macro sono complicate da scrivere in linea e
comunque il risultato è poco leggibile
D SCARSA: questo è il vero problema: con il mio debugger faccio una fatica
enorme a seguire il codice
V OTTIMA: come sopra
3- Template
Questa mi sembra la strada più promettente che ipotizzo potrebbe portarmi ad
ottenere
M OTTIMA
D BUONA
V OTTIMA : ATTENZIONE: questo requisito è ASSOLUTAMENTE indispensabile: non
posso permettermi di sprecare cicli macchina per
Es.
template <bool bUseMask> class test
{
public:
inline static void test()
{
    ...
    for(....) //foreach pixel in image i.e. 3 MPixel
    {
        v = getpixel(x,y);
        if(bUseMask)
        {
            if(v == MASK_VALUE ) continue;
        }
        {
            ... // do elaboration
        }
    }
}
...
La tecnica consiste nello sfruttare parametri di template per
attivare\disattivare parti di codice.
Ho però alcuni dubbi sulla V: qualcuno può garantire che il compilatore
effettivamente escluda i rami di codice non raggiungibili?
Bisogna fidarsi dell'ottimizzatore?
Se si (come suppongo) qualcuno ha esperienza, o esistono linee guida per
capire come scrivere codice ottimizzabile?
In ogni caso esiste la possibilità di vedere "codice intermedio" per capire
che cosa effettivamente sarà compilato, senza impazzire? (ho fatto alcuni
esperimenti e guardando i listati in assembler generati: purtroppo ho una
brutta impressione....)
P.S. tenete conto che in realtà capita di dover "cucire" parti di codice non
così facilmente "isolabili" tipo limiti di un for ecc.
Se qualcuno è interessato è necessario approfondire questo punto,
eventualmente posso postare alcuni esempi...
Spero di essere stato chiaro, e grazie per l'attenzione
Ciao
Beppe

 così facilmente "isolabili" tipo limiti di un for ecc.
Non capisco questa frase.
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 }
Ammetto di aver letto *moooolto* rapidamente, probabilmente
non ho capito la funzionalità del test nel ciclo for;
cosa intendi "escludere" parti di codice?
Per quanto ne so (ed è poco :-) ciò che si passa ad un template
non in veste di "specificatore di tipo" è una semplice variabile.
Per capirsi, in questo pezzo di codice:
 if(!bUseMask || v != MASK_VALUE )
 {
  ... // do elaboration
 }
la tabella di verità è:
bUseMask    (v!=MASK_VALUE)   eseguo_codice
   0              0                1
   0              1                1
   1              0                0
   1              1                1
In pratica, se bUseMask==0 si esegue *sempre* l'elaborazione
se bUSeMask==1 si esegue solo se sul pixel(x,y) è verificata una
certa condizione.
Quello che vorresti ottenere con il template è "l'evitarsi" il
controllo sui boolean SE E SOLO SE bUseMask==0
la stessa verifica potrebbe essere così riscritta (come hai
fatto nel template):
for( ... ){
  v=getpixel(x, y); <-- questo valore immagino ti serva anche in "do elab"
  if(bUseMask){
    if(v==MASK_VALUE)
      continue;
  }
   //do elab.
}
Se - sottolineo *SE* - bUseMask *NON* viene modificato nel ciclo un buon
compilatore se ne accorge, e con "se ne accorge" significa che il codice
relativo *non* *lo* *esegue* se prima di entrare nel [for] trova
bUseMask==0: questo accade regolarmente (ad esempio) in gcc con le
ottimizzazioni "-O", in particolare credo dalla -O2 in poi.
In caso contrario (bUseMask modificata nel ciclo) non penso tu possa
effettuare l'ottimizzazione che vorresti.
Forse, se lo hai a disposizione, prima potresti dare un'occhiata
al manuale del tuo compilatore per controllare cosa *lui* può
ottimizzare senza appesantire il codice (pensando di alleggerirlo)
con sovrastrutture non utili.
Ciao
SiMoStro

 Bisogna fidarsi dell'ottimizzatore?
Queste garanzie non esistono, devi comunque verificare il codice
generato. Un alternativa e' quella di forzare la costruzione dei due
rami separati in modo diverso, aggiungendo un paio di funzioni membro:
template <bool bUseMask> 
inline static void test<bUseMask>::loop(Pixel p) {
  elaborate(p);
}
template <> 
inline static void test<true>::loop(Pixel p) {
  if ( p != MASK_VALUE )
    elaborate(p);
}
Il problema qui e' di assicurarsi che il compilatore effettivamente
espanda in linea le chiamate, eliminando le copie superflue dei
parametri. La situazione potrebbe migliorare se elaborate() fosse una
macro.
Ciao,
Nicola

3- Template
In realta' esiste una quarta strada.
Usi un altro linguaggio (magari python) per generare il codice.
Il debug e' pessimo la scrittura e' scarsamente agevole, ma alla fine
il compilatore potrebbe (dico potrebbe) generare codice piu'
ottimizzato che se avesse a che fare con un template.
Io ho usato questa tecnica per risolvermi un altro problema. Dovevo
riempire un vettore con un migliaio di elementi, e non volevo che
l'eseguibile finale passasse attraverso un file o un db. Cosi' mi sono
scritto uno script python che leggesse un db, facesse un minimo di
precalcoli, e poi generasse del codice cpp con dei gran
vector<mio_oggetto>.push_back(..). Stupido e banale, ma quel pezzo di
codice e' li' intonso da anni, e va che e' una meraviglia.
-- 
sito Papero 1 (programmazione): censurato dai puzzoni di Lycos
sito Papero 2 (database):       
http://user.7host.com/papero/
sito Papero 3 (passatempi):     
http://digilander.iol.it/davidequack

 
Strada interessante..........spiegati + dettagliatamente, se puoi :)
-- 
Tnk
Luca "Kleidemos" Francesca
Un computer a un altro quando si incontrano:
"Ciao, come ti boota oggi???"

 ottimizzazioni "-O", in particolare credo dalla -O2 in poi.
Ma come fa il compilatore a sapere il valore di bUseMask?
L'unico modo in cui mi sembra possibile,  č mettendo bUseMask come parametro
di template,
solo cosě a compile time puň essere potato il ramo di codice
irraggiungibile.
A meno che l'ottimizzatore non produca due rami, uno da usare con
bUseMask==0 ( senza if(v==MASK....))
e uno da usare con bUseMask!=0.
Ciao
Beppe

 Non capisco questa frase.
Provo a spiegarmi meglio e posto un esempietto:
template <bool b> class CTest
{
public:
#define _I1 0
#define _I2 5
 static void Test()
 {
  int i;
  for(i = (b?_I1:_I2); b && (i<_I2) || !b && (i>_I1); b?(i++):(i--))
  {
   printf("%d ", i); //do elaboration
  }
 };
#undef _I1
#undef _I2
};
L'output è:
 CTest<true>::Test(); -> 0 1 2 3 4
 CTest<false>::Test(); -> 5 4 3 2 1
Questo è un tipo di problema che mi capita spesso: corpo del ciclo for
"quasi" costante (vedi post precedente)
e limiti del for e espressione inc/dec variabili.
Ho analizzato l'assembler NON ottimizzato è il risultato è pessimo: il
compilatore non utilizza (QUASI) il fatto che b sia in realtà costante!!!
Ciao
Beppe

 Beppe
SiMoStro

 codice e' li' intonso da anni, e va che e' una meraviglia.
A questo punto...
Ricordo un articolo apparso su C++ Informer di Carlo Pescio (era una
rivista/newsletter molto interessante, ma purtroppo defunta), in cui
spiegava come fare una cosa (credo) analoga coi template.
Mi spiego meglio: non e' relativa al problema di ottimizzare le funzioni
esposto da Beppe; si riferisce al riempimento di un vettore con dati *in
fase di compilazione*.
Non ricordo i dettagli, ma sono sicuro che con un po' di ricerche lo si
possa ancora trovare in rete. In caso contrario se siete interessati,
posso cercarlo tra i miei archivi e mandarvelo per mail.
 bye
	av.

Strada interessante..........spiegati + dettagliatamente, se puoi :)
L'idea non e' mia, l'avevo letta proprio in questo NG anni fa, per un
altro tipo di problematica ancora.
Nel mio caso specifico mi occupo di programmi, scritti in c++, per il
riconoscimento del linguaggio naturale. Il (sotto) problema specifico
era riconoscere i comuni/province/regioni e altro tenendo conto che,
per esempio, modena e' provincia in emilia, ma anche un sotto comune
di verona.
Le mie condizioni al contorno erano quindi che il mio "motore" di
riconoscimento quindi per funzionare doveva avere una elenco di dati
"relazionati", che i comuni "cambiano" poco frequentemente, ma che per
motivi miei volevo potere "segare" questo o quel comune che mi dava
fastidio, ed infine che non volevo scrivere codice per il caricamento
dei dati da un "qualcosa" di esterno, e di dovere portarmi in giro per
il mondo questo qualcosa di esterno. Tra l'altro evitando il
caricamento da "oggetti" esterni ti puoi svincolare da avere un parser
XML, o un driver ODBC, o cose simili, anche se nel mio caso specifico
non mi svincolai affatto per altri motivi.
La soluzione che ho adottato e' stata di mettere tutto in un DB,
diciamo, "strutturato". Poi con uno script in python lo leggo, e mi
genero un file cpp e un h, con le definizioni delle mie strutture, e
con il caricamento dati nel giusto ordine.
Una grande rottura di scatole fare i primi debug del codice generato,
ma adesso posso aggiungere/togliere un dato o una relazione, lanciare
lo script, e ricompilare il progetto. 
Alla fine mi sono trovato bene.
Soluzione estrema per casi estremi, pero' a volte puo' fare comodo.
