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]