L'obiettivo di questi esercizi è riuscire ad ottimizzare dei programmi in C dopo aver identificato le porzioni di codice che richiedono più tempo durante l'esecuzione. L'analisi delle prestazione deve essere effettuata utilizzando il performance profiler
gprof. Lo studente deve individuare quali ottimizzazione sono possibili sul codice fornito ed eventualmente implementare manualmente quelle che non sono state effettuate in automatico (livello di ottimizzazione 1) dal compilatore. Per capire se un'ottimizzazione è stata effettuata dal compilatore occorre analizzare il codice assembly generato dal compilatore per il programma (usare
gcc -m32 -O1 -S per generarlo). Viene fornito un
main di prova per testare il codice fornito. Lo studente deve inoltre calcolare lo speedup ottenuto confrontando il tempo di esecuzione del programma non ottimizzato manualmente (compilato con
-O1) ed il tempo di esecuzione del codice ottimizzato manualmente (compilato con
-O1).
Esercizio 1
#include <stdlib.h>
#include "pila.h"
typedef struct nodo nodo;
struct nodo { // nodo lista
int elem;
nodo* next;
};
struct pila {
nodo* top; // nodo top della lista
};
pila* pila_new(){ // crea pila vuota
return calloc(1, sizeof(pila));
}
int pila_len(const pila* p){ // lunghezza
nodo* n;
int c = 0;
for (n = p->top; n != NULL; n = n->next) c++;
return c;
}
void pila_push(pila* p, int x){ // push in cima
nodo* n = malloc(sizeof(nodo));
n->elem = x;
n->next = p->top;
p->top = n;
}
int pila_pop(pila* p, int* x){ // pop dalla cima
if (pila_len(p) == 0) return -1;
nodo* dead = p->top;
if (x != NULL) *x = dead->elem;
p->top = dead->next;
free(dead);
return 0;
}
void pila_del(pila* p){ // dealloca pila
while (p->top != NULL) pila_pop(p, NULL);
free(p);
}
#ifndef __PILA__
#define __PILA__
typedef struct pila pila;
pila* pila_new();
int pila_len(const pila*);
void pila_push(pila*, int);
int pila_pop(pila*, int*);
void pila_del(pila*);
#endif
#include <stdio.h>
#include <stdlib.h>
#include "pila.h"
#define N 35000
int main
() {
int i;
pila* p = pila_new
();
for (i=
0; i<N; i++
) {
if (pila_len
(p
) != i
)
exit
((printf("Errore pila_len\n"),
1));
pila_push
(p, i
);
}
for (i=
0; i<N; i++
) {
int x, res = pila_pop
(p, &x
);
if (res ==
-1 || x != N
-1-i
)
exit
((printf("Errore pila_pop\n"),
1));
}
for (i=
0; i<N; i++
) pila_push
(p, i
);
pila_del
(p
);
printf("Apparentemente ok, usare valgrind per verifica più approfondita\n");
return 0;
}
Soluzioni
Ottimizzazioni possibili:
- augmentation: non applicata dal compilatore automaticamente
#include <stdlib.h>
#include "pila.h"
typedef struct nodo nodo;
struct nodo { // nodo lista
int elem;
nodo* next;
};
struct pila {
nodo* top; // nodo top della lista
int len; // lunghezza della lista
};
pila* pila_new(){ // crea pila vuota
return calloc(1, sizeof(pila));
}
int pila_len(const pila* p){ // lunghezza
return p->len;
}
void pila_push(pila* p, int x){ // push in cima
nodo* n = malloc(sizeof(nodo));
n->elem = x;
n->next = p->top;
p->top = n;
p->len++;
}
int pila_pop(pila* p, int* x){ // pop dalla cima
if (pila_len(p) == 0) return -1;
nodo* dead = p->top;
if (x != NULL) *x = dead->elem;
p->top = dead->next;
free(dead);
p->len--;
return 0;
}
void pila_del(pila* p){ // dealloca pila
while (p->top != NULL) pila_pop(p, NULL);
free(p);
}
Esercizio 2
#include "sort.h"
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void sort(int* v, int n) {
int k, i;
for (k=0; k<n; k++)
for (i=1; i<n; i++)
if (cmp(v+i-1, v+i) > 0) swap(v+i-1, v+i);
}
#ifndef __SORT__
#define __SORT__
void swap(int* a, int* b);
int cmp(int* a, int* b);
void sort(int* v, int n);
#endif
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "sort.h"
#define N 20000
int cmp
(int* a,
int* b
) {
return *a-*b;
}
int is_ordered
(int* v,
int n
) {
int i;
for (i=
1; i<n; i++
) if (v
[i
-1]>v
[i
]) return 0;
return 1;
}
int main
() {
int i, *v = malloc
(N*
sizeof(v
));
assert
(v !=
NULL);
for (i=
0; i<N; i++
) v
[i
] = i <
1000 ? N-i : i;
sort
(v, N
);
printf("Risultato %s\n", is_ordered
(v,N
) ?
"corretto" :
"errato");
free
(v
);
return 0;
}
La funzione sort implementa lalgoritmo di ordinamento bubblesort, che effettua passate successive sullarray (for interno) scambiando tutti gli elementi consecutivi che non sono in ordine.
Suggerimento per lottimizzazione: si noti che se nellambito di una passata non avviene nessuno scambio, allora si può concludere che larray è ordinato.
Soluzioni
Ottimizzazioni possibili:
- inlining: la funzione cmp non subisce inlining automatico perchè situata in un altro modulo
- short-circuit: se una passata non effettua scambi possiamo terminare esecuzione di sort
#include "sort.h"
static int my_cmp(int* a, int* b) {
return *a-*b;
}
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void sort(int* v, int n) {
int k, i;
for (k=0; k<n; k++) {
int changed = 0;
for (i=1; i<n; i++)
if (my_cmp(v+i-1, v+i) > 0) {
swap(v+i-1, v+i);
changed = 1;
}
if (!changed) break;
}
}