Spunti di ottimizzazione del codice (versione 6/2009)

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 4.1.3, gcc 4.2.4, gcc 4.3.3 su un Pentium4 HT a 3.2Ghz, mentre sotto Gentoo per l'icc 9.1.
Sperimentale gcc-4.4.0

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 -msse2 -msse -mmx
gcc 4.0, gcc 4.1, gcc 4.2 + autovettorizzazione: -march=pentium4 -O2 -msse2 -msse -mmx -ftree-vectorize -ftree-vectorizer-verbose=5
gcc 4.3.3: -march=native -msse3 -msse2 -msse -mmx -O3

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

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 4.0/gcc 4.1 + autovettorizzazione
gcc 4.2 + autovettorizzazione
gcc 4.3
gcc 4.4
memset(dst, x, size);
7.2 us
7.3us
7.3us
7.4us
for(i=0;i<size;i++)
    dst[i] = x;
6.2 us
6.2us
6.3us
6.2us
while(size--)
  *dst++ = x;

5.8 us
6.2us
6.0us
5.9us

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 4.1 + autovettorizzazione gcc 4.2
gcc 4.3
gcc 4.4
memcpy(dst, src, size);
 22.0us
21.6us
22.2us
22us
for(i=0;i<size;i++)
    dst[i] = src[i];
4.1.2: 82us / 4.1.0: 10.6us *
83us
11.2us
11.4us
do {
  *dst++ = *src++;
 } while(--size)
4.1.2: 81us / 4.1.0: 10.6us * 72us
10.8us
10.6us
il GCC 4.3 finalmente riporta le prestazioni a quelle del GCC 4.1.0 vettorizzando nuovamente il codice.

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 4.1 + autovettorizzazione
gcc 4.2 + autovettorizzazione gcc 4.3
gcc 4.4
a[i] = b[i] + c[i]
103us
102 us
104us*
102us*
a[i] = b[i] * c[i]
117us
117 us
118us*
112us*
a[i] = max(b[i],c[i])
152us
156 us
158us*
153us*

su int
Codice
gcc 4.1 + autovettorizzazione gcc 4.2 + autovettorizzazione
gcc 4.3
a[i] = b[i] + c[i]
190 us
167us
178us*
a[i] = b[i] * c[i]
192 us
182us
185us*
a[i] = max(b[i],c[i])
263 us
256us
260us*

Tutti i loop vengono vettorizzati, ma non si vede un aumento di prestazioni.

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

il GCC4.3/GCC4.4 ha migliorato le prestazioni nei tempi di compilazione e riconosce quasi tutti i pattern di autovettorizzazione, senza tuttavia aumentare le prestazioni finali.

Esistono altri siti di benchmark fatti sicuramente meglio:

GCC Code-Size Benchmark Environment (CSiBE)

PHP / GCC / ICC Benchmark




[Precedente versione del documento per GCC4.0/4.1]