Spunti di ottimizzazione del codice (versione 3/2007)

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.4, gcc 4.1.2, gcc 4.2.1 su un Pentium4 HT a 3.2Ghz, mentre sotto Gentoo per l'icc 9.1.

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

gcc 3.4, gcc 4.0, gcc 4.1, gcc 4.2: -march=pentium4 -O2
gcc 4.0, gcc 4.1, gcc 4.2 + autovettorizzazione: -march=pentium4 -O2 -ftree-vectorize -ftree-vectorizer-verbose=5
icc 9.1 : -march=pentium4 -O2

Nota: esiste anche -ftree-vectorizer-verbose=7 :)

ATTENZIONE:

Molti dei pattern che venivano vettorizzati sul gcc4.1.0 , ora con il gcc 4.1.2 non hanno dato buon fine. Non vengono vettorizzati perche':

note: not vectorized: can't determine dependence between *D.11390_42
and *D.11388_40

per paura di aliasing (i puntatori di input e di output si sovrappongono) il codice ora non viene vettorizzato?

Eppure nel gcc 4.1.0 tale problematica non c'era:
[Precedente versione del documento per GCC4.0 e 4.1.0]

Nelle prossime versioni del gcc probabilmente verra' introdotta la parola chiave __restricted__  per risolvere tale problema. Esempio:
typedef int aint __attribute__ ((__aligned__(16)));
foo (int n, aint * __restricted__ p, aint * __restricted q) {

   /* feature: support for (aligned) pointer accesses.  */
   while (n--){
      *p++ = *q++;
   }
}
----

Il simbolo * indica che e' stato vettorizzato il codice nel test.

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 (65536 bytes)

Codice
 gcc 3.4
 gcc 4.0/gcc 4.1
 gcc 4.0/gcc 4.1 + autovettorizzazione
 icc 9.1
 
memset(dst, x, size);
 7.2 us
 7.2 us
 7.2 us
 
for(i=0;i<size;i++)
    dst[i] = x;
 44 us
 41 us
 5.9 us * (4.1.1-21
*
 
while(size--)
  *dst++ = x;

 43 us
 38 us
 5.8 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.

Non e' chiaro se viene sfruttato o meno il fatto se la memoria e' allineata a 16 byte o meno.

2.2 Copia della memoria

Anche se il codice usato negli esempi 2.2 e' simile a quello degli esempi 2.1 il fatto di usare due buffer sorgenti, distrugge la possibilita' di vettorizzare il codice.

Vediamo ora un primo test per confrontare i diversi compilatori su un buffer di memoria fisso (65536 bytes)
Codice
 gcc 3.4
 gcc 4.0/gcc 4.1/gcc 4.2
 gcc 4.1 + autovettorizzazione icc 9.1
 
memcpy(dst, src, size);
 22 us
 23 us
  =
 
for(i=0;i<size;i++)
    dst[i] = src[i];
 78 us
 78 us
 4.1.2: 85us / 4.1.0: 10.6us *
 
do {
  *dst++ = *src++;
 } while(--size)
 79 us
 78 us
 4.1.2: 85us / 4.1.0: 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.1
 gcc 4.0 + autovettorizzazione
 gcc 4.1 + autovettorizzazione 
a[i] = b[i] + c[i]
 101us
 103us
 102 us
 
a[i] = b[i] * c[i]
 111us
 102us
 115 us
 
a[i] = max(b[i],c[i])
 155us
 160us
 152 us

su int
Codice
 gcc 3.4/gcc 4.0/gcc 4.1
 gcc 4.0 + autovettorizzazione
 gcc 4.1 + autovettorizzazione 
a[i] = b[i] + c[i]
 145us
 172
 132 us
 
a[i] = b[i] * c[i]
 146us
 174
 129 us
 
a[i] = max(b[i],c[i])
 171us
 181
 166 us

Nessuno di questi pattern ora, anche su gcc4.1.2 ha dato buon fine. Non vengono vettorizzati perche':

note: not vectorized: can't determine dependence between *D.11390_42 and *D.11388_40

per paura di aliasing (i puntatori di input e di output si sovrappongono) il codice ora non viene vettorizzato?

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

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.6us
 1.0us
 4.3us
 28.9us
 355us
 5621.2 us
sorted vector
(binary search)
 0.7us
 0.9us
 3.4us
 16.1us
 64.6us
 289.4 us
map
 0.7us
 1.2us
 4.9us
 23.2us
 106us
 421.7 us
list
 0.6us
 0.9us
 5.4us
 59.9us
 892us
 26790 us

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

std::set e std::map hanno prestazioni uguali.
I tempi di creazione delle tabelle non sono considerati, perche' si fa l'ipotesi di tante ricerche e percio' il tempo di creazione e' trascurabile.

Nota: l'autovettorizzazione non e' stata possibile.

Le conclusioni sono che le STL sono utili, ma con un po' di sano uso di tali strutture c'e' un guadagno di prestazioni.
La differenza tra `map' e 'sorted vector' e' nel codice della ricerca: map usando std::map::find mentre per il binary search del codice scritto da me. Da notae infatti che l'ordine di grandezza e' lo stesso, ma con un fattore moltiplicativo di circa 2 tra i due sistemi.

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.

Esistono altri siti di benchmark fatti sicuramente meglio:

GCC Code-Size Benchmark Environment (CSiBE)

PHP / GCC / ICC Benchmark




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