Esercizi ottimizzazione di programmi
Si vedano le discussioni e le soluzioni sul
forum.
Esercizio 1 (Profilazione delle prestazioni)
Si usi il tool
gprof per profilare il seguente programma C formato dalla header
array.h e dai due moduli
array.c e
main.c. Il programma deve essere compilato con livello di ottimizzazione O1 e l'opzione
-m32.
typedef struct {
int* v;
int term;
} array;
int len(array* a);
#include "array.h"
int len(array* a) {
int cnt = 0, *p = a->v;
while (*p++ != a->term) cnt++;
return cnt;
}
#include <stdlib.h>
#include <stdio.h>
#include "array.h"
int ordinato
(array* a
) {
int i =
1;
while (1) {
if (a->v
[i
-1] > a->v
[i
]) return 0;
if (++i == len
(a
)) return 1;
}
}
#define N 16000000
int main
() {
int i;
array a;
a.
v = malloc
(N*
sizeof(int));
a.
v[N
-1] = a.
term =
-1;
for (i=
0; i<N
-1; i++
) a.
v[i
] = i;
printf("%d [corretto = 1]\n", ordinato
(&a
));
free
(a.
v);
return 0;
}
Qual è la funzione che da sola, cioè senza considerare il tempo speso nelle funzioni da essa chiamate, richiede la maggior parte del tempo di esecuzione?
Esercizio 2 (Analisi delle prestazioni)
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?
- Suggerimento: applicare la legge di Amdahl.
Esercizio 3 (Ottimizzazione di programmi)
Si consideri il programma dell'esercizio 1:
1. Che tecnica di ottimizzazione useresti per ridurre il tempo di esecuzione del programma? Perché?
2. Applicare al programma l'ottimizzazione indicata al punto 1.
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).
4. L'ottimizzazione del punto 1 deve essere applicata manualmente dal programmatore, oppure possiamo aspettarci che venga effettuata in automatico dal compilatore?
5. L'ottimizzazione del punto 1 modifica il costo asintotico del programma?
- Suggerimento: per misurare il tempo di esecuzione di un programma usare il comando time ./pippo, che lancia il programma eseguibile pippo nella directory corrente e riporta il tempo totale richiesto dal programma (considerare il tempo real).
Esercizio 4 (Ottimizzazioni del compilatore)
Si consideri il seguente modulo C:
int cmp(int x, int y) {
return x-y;
}
int ord(int* v, int n) {
int b = 1;
while (--n>=b) if (cmp(v[n-1], v[n]) > b-1) return 0;
return 1;
}
e lo si compili in
gcc con livello di ottimizzazione
-O1, creando il file assembly
es4.s. Ispezionando
es4.s, quali delle seguenti ottimizzazioni sono state effettuate dal compilatore?
1. Loop-invariant code motion
2. Function inlining
3. Constant propagation
4. Constant folding
Se si risponde sì, motivare la risposta riportando frammenti di codice IA32 che illustrano da dove si evince che l'ottimizzazione è stata applicata.
[
Soluzioni]