Spunti di ottimizzazione del codice (versione 2/2006)

Elenco di benchmark e idee su come massimizzare le performance senza dover scendere in linguaggio assembly su compilatori GCC.

I Test sono stati eseguiti sotto Debian Linux con programmi compilati usando gcc 3.4.6, gcc 4.0.3, gcc 4.1.0 su un Pentium4 a 3.2Ghz.

Salvo dove indicato sono state usate le seguenti opzioni di compilazione:

gcc 3.4, gcc 4.0, gcc 4.1: -march=pentium4 -O2
gcc 4.0.3, gcc 4.1.0 + autovettorizzazione: -march=pentium4 -O2 -ftree-vectorize -ftree-vectorizer-verbose=5

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 Confronto tra i compilatori

Per settare un buffer di memoria sono possibili diversi costrutti. Con il GCC 4.0 tali costrutti tuttavia sono finalmente equivalenti (dal punto di vista delle prestazioni, ma non del codice generato).

2.1 settaggio della memoria

Vediamo ora un primo test per confrontare i diversi compilatori su un buffer di memoria fisso (65536bytes)

Codice
 gcc 3.4
 gcc 4.0
 gcc 4.0 + autovettorizzazione
 gcc 4.1
 
memset(dst, x, size);
 7.6 us
 7.3 us
 /
 7.3 us
 
for(i=0;i<size;i++)
    dst[i] = x;
 59 us
 46 us
 6.0 us
 49 us
 
while(size--)
  *dst++ = x;

 58 us
 46 us
 6.4 us
 46 us

Faccio notare che il gcc 4.0 (e il 4.1) hanno prestazioni simili ora al gcc 3.3 (se non si auto vettorizza) mentre era il gcc3.4 ad avere alcuni problemi. La memset non puo' cambiare visto che viene usata la libreria di sistema che non viene ovviamente ricompilata di volta in volta. Sia il gcc 4.0 che il 4.1 mostrano la diminuzione dei tempi di un ordine di grandezza se viene usata l'autovettorizzazione del codice.
La memset e' di diversi ordini di grandezza inferiore, soprattutto per grandi numeri di byte spostati perche' internamente ha un codice scritto in assembly che massimizza tale operazione, che solo il codice autovettorizzato riesce a uguagliare.

2.2 Copia della memoria

Vediamo ora un primo test per confrontare i diversi compilatori su un buffer di memoria fisso (65536bytes)
Codice
 gcc 3.4
 gcc 4.0
 gcc 4.0 + autovettorizzazione
 gcc 4.1
 gcc 4.1 + autovettorizzazione 
memcpy(dst, src, size);
 22 us
 23 us
 /
 22 us
 /
 
for(i=0;i<size;i++)
    dst[i] = src[i];
 78 us
 78 us
 70 us
 79 us
 10.6us
 
do {
  *dst++ = *src++;
 } while(--size)
 79 us
 78 us
 76 us
 80 us
 10.6us

Nel caso della copia di memoria il limite piu che di codice generato e' un limite fisico del bus e della comunicazione tra cpu e memoria. In questo caso l'autovettorizzazione sul gcc4.0 non e' andata a buon termine, mentre sui nuovi pattern del gcc4.1 si, portando a un significativo aumento delle prestazioni.


2.3 copia di strutture

Nei casi precedenti si trattava di spostare memoria byte per byte.  Diverso discorso va fatto in caso di strutture di dati.

2.4 Pattern per l'autovettorizzazione

su unsigned char
Codice
 gcc 3.4
 gcc 4.0
 gcc 4.0 + autovettorizzazione
 gcc 4.1
 gcc 4.1 + autovettorizzazione 
a[i] = b[i] + c[i]
 103us
 104us
 103us
 104us
 15.0us*
 
a[i] = b[i] * c[i]
 105us
 101us
 102us
 104us
 15.8us*
 
a[i] = max(b[i],c[i])
 176us
 166us
 160us
 176us
 15.3us*

su int
Codice
 gcc 4.0
 gcc 4.0 + autovettorizzazione
 gcc 4.1 + autovettorizzazione 
a[i] = b[i] + c[i]
 180
 184
 101 us *
 
a[i] = b[i] * c[i]
 180
 184
 95 us *
 
a[i] = max(b[i],c[i])
 203
 194
 111 us*

(*) ovviamente solo in questo caso l'autovettorizzazione e' andata a buon termine

Il passaggio da unsigned char a int mostra comunque che buona parte dei tempi sono dovuti a spostamento di memoria. I tempi si rifersicono comunque a 65536 byte e 65536 int rispettivamente (pertanto 4 volte piu memoria)

3 Vector vs Map

Tempi di accessi a questi due contenitori STL. Ovviamente per Random Access Memory non ci sono paragoni: il vector vince sempre e in ogni caso.
Esaminiamo invece il caso di analisi di ricerca di elementi
Aggiungo anche il caso di list, solo per completezza.
Number Of elements>
 8
 16
 64
 256
 1024
 4096
vector
 0.7us
 1.0us
 4.8us
 34.8us
 482us
 7716us
map
 0.7us
 1.2us
 4.6us
 23.1us
 114us
 468us
list
 0.6us
 0.9us
 4.8us
 56.0us
 852us
 27722us

I numeri rappresentano il tempi necessari per trovare <n> volte gli elementi richiesti con inserimento di tali valori random.

Nota: l'autovettorizzazione non e' stata possibile.

4 Conclusioni

Tra il GCC3.4 e il GCC4.0 non ci sono significative differenze di prestazioni, tranne che quest'ultimo puo' autovettorizzare il codice generato.
Il GCC4.1 in piu riconosce piu pattern e permette di migliorare ulteriormente le performance sul codice generato.



[Precedente versione del documento per GCC3.3 e 3.4]