Spunti di ottimizzazione del codice


1. Introduzione


E' vero che un algoritmo di complessità di ordine inferiore risulta più veloce di un algoritmo di ordine superiore. E' altresì vero che un algoritmo di complessità inferiore ben scritto è più veloce di un algoritmo di complessità inferiore scritto male.

2. Esempi base

E' vero che deve essere compito del compilatore ottimizzare al meglio il codice. E' comunque vero che il compilatore non può riuscire sempre a generare il codice ottimo.

2.1 Le chiamate inline


size = 65536
 procedura inline
 Non Inline
 
for(i=0;i<size;i++)
    dst[i] = x;
 41us
 131us
 
do {
  *dst++ = x;
 } while(--size)
 48us
 50us
 
for(i=0;i<size;i++)
    dst[i] = src[i];
 62us
 146us


Il confronto e' stato fatto tra il codice scritto all'interno di una procedura abbastanza complessa, confrontato con il ciclo scritto in una procedura inline esterna. Come si vede, il compilatore quando incontra una procedura inline riesce a ottimizzare meglio il codice, rispetto al codice inserito in mezzo una procedura complessa.
Il secondo codice tuttavia e' gia scritto nella forma migliore per la conversione in assembly, e pertanto e' quello che risente meno di ottimizzazioni meno spinte.
In generale il compilatore va aiutato nella ottimizzazione del codice, usando strutture ad hoc e separando i blocchi funzionali, quando possibile.
Se non si riesce pertanto a creare a procedure inline, la scelta del ciclo do { } while sarebbe da preferirsi.

2.2 Settaggio della memoria


size=
 1 byte
 1024 bytes
 65536 bytes
 
memset(dst, x, size);
 0.02us
 0.21us
 7.2us
 
for(i=0;i<size;i++)
    dst[i] = x;
 <0.002us 0.66us
 42us
 
for(j=len;j;j--)
     dst[j] = value;
 <0.002us 0.66us
 42us
 
 for(j=len;j;j--)
     *dst++ = value;
 <0.002us 0.75us
 49us
 
do {
  *dst++ = x;
 } while(--size)
 <0.002us 0.75us
 48us

memset e' una chiamata di libreria, e come tale ha un overhead fisso. Internamente tuttavia e' scritta in assembler, e ottimizzata per settare 4 bytes alla volta, rispetto al codice dell'esempio proposto. Si vede infatti che i tempi della memset, a parte il leggero overhead per la creria, e' circa 4 volte inferiore al tempo degli altri approcci.
L'esempio e' tuttavia molto significativo nel confronto dei due esempi del codice. Lo stesso codice, scritto in maniera leggermente diversa, permette di risparmiare notevole tempo in fase di elaborazione.
Il ciclo do { } while(--i) viene tradotto in assembler direttamente con
 label: 

 MOV [EDX], CL
 INV EDX
 DEC ECX  ; puo' essere accoppiato in sistemi a piu' pipeline
 JNZ label ; la branch predition salta il confronto

2.3 Copia della memoria


size=
 1 byte
 1024 bytes
 65536 bytes
 
memcpy(dst, src, size);
 0.02us
 0.28us 14us
 
for(i=0;i<size;i++)
    dst[i] = src[i];
 <0.002us
 1.09us
 69us
 
do {
  *dst++ = *src++;
 } while(--size)
 <0.002us
 1.11us
 73us
Per la copia della memoria si possono fare le stesse considerazione del paragrafo precedente. Il compilatore non riesce a ottimizzare il codice in maniera paragonabile al codice assembler. Un solo byte per volta viene copiato.

2.4 Ottimizzazione specifica per la macchina.

-march=pentium4

size=65536
 macchina generica
 pentium4
 
for(i=0;i<size;i++)
    dst[i] = src[i];
 69us
 104us
 
i = size;
do {
  *dst++ = *src++;
 } while(--i)
 72us
 58us
 
for(i=0;i<size;i++)
    dst[i] = x;
 41us
 43us
 
do {
  *dst++ = x;
 } while(--size)
 48us
 39us

Ci sarebbe molto da dire su questi risultati, ma e' necessaria una analisi piu profonda del codice generato.
Quello che penso che avvenga quando viene richiesta l'ottimizzazione per uno specifico processore e' che comunque non vengano usate le istruzioni specifiche per la macchina obligatoriamente, ma, tra le possibili alternative della medesima istruzione viene scelta quella che e' piu facilmente accoppiabile nelle pipeline.

Per esempio nel codice sovrastante gli INC EAX vengono sostituiti nella ottimizzazione per pentium4 con degli ADD EAX,1. Che questa sostituzione  porti miglioramenti o peggioramenti, dipende molto da applicazione ad applicazione.

In generale diverse istruzioni SSE e SSE2 vengono usate nell'ottimizzazione Pentium4 (per esempio nelle conversioni da intero a double), ma sopratutto istruzioni atte a permettere al programma di entrambe le pipeline, e percio, in altre situazioni, si noteranno miglioramenti superiori.

3. STL


3.1 Le stringhe

Le STL allocano, in maniera trasparente all'utente, sia il puntatore alla memoria del testo contenuto nella stringa, anche un valore che indica quanto la stringa risulta lunga. Questo dato aggiuntivo permette di risparmiare tempo prezioso quando si eseguono operazioni intensive su stringhe.

La stessa cosa si puo' fare infatti creando una classe C++ che memorizza sia la lunghezza della stringa che il suo contenuto, per esempio
class bstring {
   unsigned int len;
   const char *str;
   public:
     ...
};

Una struttura come bstring ha le medesime prestazioni, se non migliori, delle std::string.

3.1.1 Allocazione della memoria per le stringhe


 10 bytes
 100 bytes
 1000 bytes
 
 unsigned int len = strlen(buffer) + 1;
 char *target = new char [len];
 memcpy(target, buffer, len);
 
 delete [] target
 0.16us
 0.26us 0.74us 
std::string s(buffer);
 0.15us
 0.21us 0.78us

I tempi sono molto simili. Internamente infatti saranno replicati i medesimi passaggi.

3.1.2 Copia delle stringhe

Nel caso della copia delle stringhe le STL astraggono molto questo processo, limitandosi a copiare i puntatori. In questo caso le prestazioni sono notevolmente superiori rispetto alla gestione classica dei buffer di stringa.

3.1.3 Lunghezza della stringa


 10 bytes
 100 bytes
 1000 bytes
strlen( )
 0.009us
 0.053us 0.378us 
s.size()
 <0.001us
 <0.001us <0.001us

Il comando size delle stringhe restituisce la lunghezza della stringa, memorizzata all'interno della struttura. Nessun accesso alla memoria viene fatto, se non quello del dato di lunghezza stesso.

3.1.3 concatenazione di stringhe


 10 bytes
 100 bytes
 1000 bytes
Approccio C
 0.20us
 0.33us
 1.01us
 
Approccio C++ con bstring
 0.20us
 0.27us 0.59us 
Approccio C++ con STL
 0.35us 0.47us 0.85us

3.2 Vettori


 time
{
unsigned char *v = new unsigned char [size];
v[0]=0;
delete [] v;
}
 		0.14us
 
{
vector<unsigned char> v(size);
v[0]=0;
}
 6.2us

3.2.1 Iteratori


size=
 16384 bytes
 
for(i=0;i<size;i++)
    dst[i] = x;
 34us
 
for(vector<unsigned char>::iterator i=stlmem.begin();i!=stlmem.end();i++)
   	(*i)=v;
 42us
 
vector<unsigned char>::iterator end = stlmem.end();
for(vector<unsigned char>::iterator i=stlmem.begin();i!=end;i++)
   	(*i)=v;
 43us
 
for(i=0;i<size;i++)
    stlmem[i] = x;
 36us

3.3 Dimensioni dell'eseguibile


4. Polimorfismo


5. MMX/SSE Inline


Confronto tra istruzioni MMX/SSE inline verso lo stesso codice ottimizzato dal GCC 3.3/3.4 usando la riga di comando  
-O3 -fexpensive-optimizations -march=pentium4

Tempi ottenuti su un Pentium4 su buffer di 307200 bytes.
gcc-3.3
 gcc-3.4
Codice MMX inline 
void ll_sse_diff_line(unsigned
char *d, const unsigned char *a, const unsigned char *b, unsigned int size)
{
    size/=8;
    do {
    __asm__ volatile ("movq %1, %%mm0\n\t"
	"movq %2, %%mm1\n\t"
	"movq %%mm0, %%mm2\n\t"
	"movq %%mm1, %%mm3\n\t"
	"PSUBUSB %%mm0, %%mm1\n\t"
	"PSUBUSB %%mm3, %%mm2\n\t"
	"PADDUSB %%mm2, %%mm1\n\t"
	"movq %%mm1, %0\n\t"
        : : "m"(*d), "m"(*a), "m"(*b)
	);   
    a+=8;
    b+=8;
    d+=8;

    } while(--size8);

    __asm__ volatile ("emms\n\t");    
}

 0.18ms


 0.18ms

Codice scritto in maniera tale da usare le 2 pipeline.		 
void ll_diff_line(unsigned char *d, const unsigned char *a, const unsigned char *b, unsigned int size)
{
  size/=2;
  if(size>0)
  do { 
    *d++ = subabs(*a++, *b++);
    *d++ = subabs(*a++, *b++);
  } while(--size);
}

 0.61ms

Se invece di 2, si usano 8 copie c'e' un peggioramento.
 0.61ms

Se invece di 2, si usano 8 copie stavolta non cambiano le prestazioni.

Codice Normale		 
void ll_diff_line(unsigned char *d, const unsigned char *a, const unsigned char *b, unsigned int size)
{
  if(size>0)
  do { 
    *d++ = subabs(*a++, *b++);
  } while(--size);
}
 1.6ms (1.2ms non usando march=pentium4)

 0.67ms
Codice Normale con il For
 
void ll_diff_line_for(unsigned char *d, const unsigned char *a, const unsigned char *b, unsigned int size)
{
 for(unsigned int i=0;i<size;i++)
	d[i] = subabs(a[i], b[i]);
}
 0.63ms
 0.76ms

Il for riesce a parallelizzare l'elaborazione, cosa che il codice scritto con do { } while nel gcc 3.3 non avviene. Questo problema sembra essere stato risolto nel gcc 3.4.4.

L'altra notevole differenza e' il tempo di sviluppo e la portabilita' di un codice scritto in assembly.

E' comunque da notare che le istruzione MMX scelta e' diversa dalla possibile implementazione che viene fatta nel codice normale.

T subabs(T a, T b)
    {
    return (a>b) ? (a-b) : (b-a);
    }

Il gcc-4.0.0 non e' riuscito a vettorizzare nessuno dei loop.

5.1 Autovettorizzazione


-O3 -fexpensive-optimizations -march=pentium4 -msse2 -ftree-vectorize -ftree-vectorizer-verbose=5


Descrizione
 Codice
 gcc-3.4.4
 gcc-4.0.0
SIZE=256*256*16 
int a[SIZE], b[SIZE], c[SIZE];
foo () {
  int i;

  for (i=0; i<SIZE; i++){
    a[i] = b[i] + c[i];
  }
}
 5.0ms
 4.3ms
 

unsigned char a[SIZE], b[SIZE], c[SIZE];
foo () {
  int i;

  for (i=0; i<SIZE; i++){
    a[i] = b[i] + c[i];
  }
}
5.0ms
 1.5ms

Note Finali

I Test sono stati eseguiti sotto Debian Linux con programmi compilati usando gcc 3.3.5 ottimizzato con -O3 -fexpensive-optimizations ed eseguiti su un Pentium4 a 3Ghz. Test fatti comunque con il gcc 3.4.4 hanno dato risultati equivalenti.