Esercizi ottimizzazione di programmi
Si vedano anche le discussioni e le soluzioni sul forum.
Esercizio 1 (Profilazione delle prestazioni)
Compilare con:
gcc -O1 -m32 -pg main.c array.c -o es1
Si noti l'opzione
-pg per collegare
gprof al programma.
Eseguire il programma con
./es1.
Poiché il programma è stato compilato con
-pg,
./es1 effettua una esecuzione "profilata" che genera un file binario
gmon.out.
Salvare il report in formato testo con
gprof ./es1 > mioreport.txt
Aprire il report con un editor di testo, es.
geany mioreport.txt. Ci aspettiamo un risultato simile:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
99.64 2.78 2.78 99998 0.00 0.00 len
0.36 2.79 0.01 1 0.01 2.79 ordinato
La funzione con il più alto tempo di esecuzione è
len, che prende oltre il 99% del tempo totale.
Esercizio 2 (Analisi delle prestazioni)
Domanda. Consideriamo un programma P che richiede 10 secondi, ottimizziamo una funzione f che richiede il 30% del tempo di esecuzione totale di P, e vediamo che il tempo totale di P scende a 8 secondi. Di quante volte abbiamo velocizzato f?
Risposta. Lo speedup del programma è 10/8. Usando la legge di Amdahl, abbiamo:
speedup = 1/(alpha/k+1-alpha),
dove alpha=0.3=3/10 e speedup=10/8.
Ricaviamo pertanto: k=3.
Esercizio 3 (Ottimizzazione di programmi)
Si consideri il programma dell'esercizio 1:
Domanda 1. Che tecnica di ottimizzazione useresti per ridurre il tempo di esecuzione del programma? Perché?
Risposta. La funzione che richiede più tempo totale è
len. Essa viene infatti chiamata ad ogni iterazione della funzione
ordinato sebbene restituisca sempre lo stesso valore. Possiamo pertanto applicare la tecnica del loop-invariant code motion.
Domanda 2. Applicare al programma l'ottimizzazione indicata al punto 1.
Risposta. Spostiamo la chiamata a
len fuori dal ciclo come segue:
int ordinato(array* a) {
int i = 1;
int n = len(a);
while (1) {
if (a->v[i-1] > a->v[i]) return 0;
if (++i == n) return 1;
}
}
Domanda 3. Misurare il tempo di esecuzione del programma prima e dopo l'ottimizzazione: di che fattore si è velocizzato il programma a seguito dell'ottimizzazione applicata? (es. 2x vuole dire che è due volte più veloce, cioè richiede la metà del tempo di esecuzione).
Risposta. Compiliamo il programma vecchio con il nome
es1 e quello ottimizzato con il nome
es1-opt. Misuriamo i tempi:
$ time ./es1
1 [corretto = 1]
real 0m2.815s
user 0m2.805s
sys 0m0.004s
$ time ./es1-opt
1 [corretto = 1]
real 0m0.002s
user 0m0.000s
sys 0m0.001s
Lo speedup ottenuto è pertanto: 2.815/0.002 = 1407.5x. Non male... Si noti che il valore è comunque approssimato poiché il valore a denominatore è inaccurato essendo vicino alla precisione con cui il sistema usato effettua le misurazioni (millisecondi).
Domanda 4. L'ottimizzazione applicata deve essere applicata manualmente dal programmatore, oppure possiamo aspettarci che venga effettuata in automatico dal compilatore?
Risposta. L'ottimizzazione deve essere effettuata manualmente poiché il compilatore non può fare alcuna assunzione su quello che viene fatto dalla funzione
len. Infatti, la funzione
len è in un modulo diverso da quello che contiene la funzione
ordina. In generale,
len potrebbe effettuare dei side-effect che renderebbero la trasformazione di loop-invariant code motion errata. Si noti infatti che i compilatori applicano solo trasformazioni dei programmi che non ne modificano il comportamento osservabile (la semantica).
Domanda 5. L'ottimizzazione del punto 1 modifica il costo asintotico del programma?
Risposta. Sì, il costo originale è quadratico nella lunghezza dell'array (perché?), quello ottimizzato è lineare.
Esercizio 4 (Ottimizzazioni del compilatore)
Il codice assembly generato da
gcc -O1 per il programma è:
ord:
.LFB1:
.cfi_startproc
movl 4(%esp), %edx
movl 8(%esp), %eax
jmp .L3
.L5:
movl -4(%edx,%eax,4), %ecx
subl (%edx,%eax,4), %ecx
testl %ecx, %ecx
jg .L6
.L3:
subl $1, %eax
testl %eax, %eax
jg .L5
movl $1, %eax
ret
.L6:
movl $0, %eax
ret
Possiamo ignorare .LFB1: e .cfi_startproc.
1.
Loop-invariant code motion: no (non ci sono espressioni invarianti nel ciclo che possono essere portate fuori dal ciclo)
2.
Function inlining: sì, infatti non ci sono istruzioni
call e il corpo della funzione
cmp è rimpiazzata dalle istruzioni:
movl -4(%edx,%eax,4), %ecx
subl (%edx,%eax,4), %ecx
che calcolano la differenza di elementi consecutivi dell'array.
3.
Constant propagation: sì, la costante
b=1 viene propagata sia nell'espressione
--n>=b, compilata nelle istruzioni:
subl $1, %eax
testl %eax, %eax
jg .L5
che nel test
> b-1, compilato nelle istruzioni:
4.
Constant folding: sì, il
b-1 del test
> b-1 viene precalcolato dal compilatore. Infatti, le istruzioni:
confrontano il risultato della
cmp direttamente con zero senza dover calcolare
b-1 a tempo di esecuzione.