Additions:
// soluzione 2 con cambio completo dell'algoritmo + inlining
while (*a) { ma[_lower(*a)]++; a++; }
while (*b) { mb[_lower(*b)]++; b++: }
Deletions:
// soluzione 2 con cambio completo dell'algoritmo
while (*a) ma[*a++]++;
while (*b) mb[*b++]++;
No differences.
Additions:
==Soluzioni==
~- augmentation: non applicata dal compilatore automaticamente
==Soluzioni==
~- 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##
==Soluzioni==
~- inlining: la funzione ##distqr## non subisce inlining perchè situata in un altro modulo
~- common subexpression elimination: l'invocazione a ##count## in ##count_max## può essere effettuata una volta sola ed il suo risultato riutilizzato; non effettuata dal compilatore.
~- loop invariant code motion: una delle due invocazioni a ##distsqr## in ##count## può essere portata fuori dal loop; non effettuata dal compilatore
==Soluzioni==
~- short-circuit: se due stringhe hanno un numero di occorrenze diverso per una certa lettera allora non sono anagrammi; non effettuata dal compilatore
~- inlining: la funzione ##lower## non subisce inlining perchè situata in un altro modulo
Deletions:
===Soluzioni===
- augmentation: non applicata dal compilatore automaticamente
===Soluzioni===
- 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##
===Soluzioni===
- inlining: la funzione ##distqr## non subisce inlining perchè situata in un altro modulo
- common subexpression elimination: l'invocazione a ##count## in ##count_max## può essere effettuata una volta sola ed il suo risultato riutilizzato; non effettuata dal compilatore.
- loop invariant code motion: una delle due invocazioni a ##distsqr## in ##count## può essere portata fuori dal loop; non effettuata dal compilatore
===Soluzioni===
- short-circuit: se due stringhe hanno un numero di occorrenze diverso per una certa lettera allora non sono anagrammi; non effettuata dal compilatore
- inlining: la funzione ##lower## non subisce inlining perchè situata in un altro modulo
Additions:
- augmentation: non applicata dal compilatore automaticamente
Deletions:
- Augmentation: non applicata dal compilatore automaticamente
Additions:
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##).
Deletions:
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 -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##).
Additions:
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 -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##).
Deletions:
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 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 -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##).
Additions:
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 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 -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##).
Deletions:
L'obiettivo di questi esercizi è di ottimizzare dei programma in C dopo aver identificato le porzioni di codice che richiedono più tempo durante la loro 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 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 -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##).
Additions:
%%(c;pila.h)
#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 "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
for (i=1; i
if (cmp(v+i-1, v+i) > 0) swap(v+i-1, v+i);
%%(c;sort.h)
#ifndef __SORT__
#define __SORT__
void swap(int* a, int* b);
int cmp(int* a, int* b);
void sort(int* v, int n);
#endif
#include
#include "sort.h"
#define N 20000
int cmp(int* a, int* b) {
return *a-*b;
int is_ordered(int* v, int n) {
for (i=1; iv[i]) return 0;
return 1;
int i, *v = malloc(N*sizeof(v));
assert(v != NULL);
for (i=0; i
sort(v, N);
printf("Risultato %s\n", is_ordered(v,N) ? "corretto" : "errato");
free(v);
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.
- 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
int changed = 0;
for (i=1; i
if (my_cmp(v+i-1, v+i) > 0) {
swap(v+i-1, v+i);
changed = 1;
}
if (!changed) break;
#include "es4.h"
// conta punti inclusi nella circonferenza passante per l'origine
// centrata nel punto p
int count(int* x, int* y, int p, int n) {
int i, c;
for (i = c = 0; i < n; i++)
if (distsqr(x[p], y[p], x[i], y[i]) <
distsqr(x[p], y[p], 0, 0)) c++;
// conta il massimo numero di punti che sono inclusi nella circonferenza
// passante per l'origine centrata in uno dei punti dell'insieme
int count_max(int* x, int* y, int n) {
int i, max = 0;
for (i=0; i
if (count(x, y, i, n) > max)
max = count(x, y, i, n);
return max;
%%(c;es4.h)
#ifndef __ES4__
#define __ES4__
int distsqr(int x1, int y1, int x2, int y2);
int count_max(int* x, int* y, int n);
#endif
#include
#include "es4.h"
#define N 10000
int distsqr(int x1, int y1, int x2, int y2) {
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
void init(int* x, int* y, int n) {
for (i=0; i
for (i=1; i
int c, *x = malloc(N*sizeof(int)), *y = malloc(N*sizeof(int));
assert(x != NULL && y != NULL);
init(x, y, N);
c = count_max(x, y, N);
c = count_max(x, y, N);
c = count_max(x, y, N);
printf("Risultato %d\n", c);
free(x);
free(y);
- inlining: la funzione ##distqr## non subisce inlining perchè situata in un altro modulo
- common subexpression elimination: l'invocazione a ##count## in ##count_max## può essere effettuata una volta sola ed il suo risultato riutilizzato; non effettuata dal compilatore.
- loop invariant code motion: una delle due invocazioni a ##distsqr## in ##count## può essere portata fuori dal loop; non effettuata dal compilatore
#include "es4.h"
// conta punti inclusi nella circonferenza passante per l'origine e
// centrata nel punto p
int count(int* x, int* y, int p, int n) {
int i, c;
int d = distsqr(x[p], y[p], 0, 0); // hoisting
for (i = c = 0; i < n; i++)
// function inlining
if ((x[p]-x[i])*(x[p]-x[i])+(y[p]-y[i])*(y[p]-y[i]) < d) c++;
// conta il massimo numero di punti che sono inclusi nella circonferenza
// passante per l'origine e centrata in uno dei punti dell'insieme
int count_max(int* x, int* y, int n) {
int i, max = 0;
for (i=0; i
int c = count(x, y, i, n); // common subexpression elimination
if (c > max) max = c;
return max;
#include "anagrams.h"
int count(char c, const char* s) {
int cnt = 0;
while (*s) cnt += c == lower(*s++);
return cnt;
int anagrams(const char* a, const char* b) {
int cnt = 0;
const char* p = a;
while (*p) {
cnt += count(lower(*p), a) !=
count(lower(*p), b);
p++;
return cnt == 0;
%%(c;anagrams.h)
#ifndef __ANAGRAMS__
#define __ANAGRAMS__
char lower(char c);
int anagrams(const char* a, const char* b);
#endif
#include "anagrams.h"
#define N 1000000
char lower(char c) {
if (c >= 'A' && c <= 'Z') return c - 'A' + 'a';
int i, c = 0;
c += anagrams("algoritmo", "logaritmo");
c += anagrams("trancio", "cartoni");
c += anagrams("sfrenati", "finestra");
c += anagrams("minestra", "finestra");
c += anagrams("precipitazioni", "pioggia");
printf("%d (corretto=%d)\n", c, 3*N);
printf("%d (corretto=1)\n", anagrams("algoritmo", "logaritmo"));
printf("%d (corretto=1)\n", anagrams("trancio", "cartoni"));
printf("%d (corretto=1)\n", anagrams("sfrenati", "finestra"));
printf("%d (corretto=0)\n", anagrams("minestra", "finestra"));
printf("%d (corretto=0)\n", anagrams("precipitazioni", "pioggia"));
- short-circuit: se due stringhe hanno un numero di occorrenze diverso per una certa lettera allora non sono anagrammi; non effettuata dal compilatore
- inlining: la funzione ##lower## non subisce inlining perchè situata in un altro modulo
Approccio alternativo: l'algoritmo per la verifica di un anagramma può essere ripensato totalmente (vedere soluzione 2)
#include "anagrams.h"
#if 0
// soluzione 1 con inlining e cortocircuitazione
static char _lower(char c) {
if (c >= 'A' && c <= 'Z') return c - 'A' + 'a';
int count(char c, const char* s) {
int cnt = 0;
while (*s) cnt += _lower(c) == _lower(*s++);
return cnt;
int anagrams(const char* a, const char* b) {
const char* p = a;
while (*p) {
if (count(*p, a) != count(*p, b)) return 0;
p++;
return 1;
#else
// soluzione 2 con cambio completo dell'algoritmo
#include
int anagrams(const char* a, const char* b) {
char ma[256] = { 0 };
char mb[256] = { 0 };
while (*a) ma[*a++]++;
while (*b) mb[*b++]++;
return !memcmp(ma,mb,256);
#endif
Additions:
== Esercizio 2 ==
%%(c;f.c)
%%(c;f-opt.c)
== Esercizio 3 ==
%%(c;f.c)
%%(c;f-opt.c)
== Esercizio 4 ==
%%(c;f.c)
%%(c;f-opt.c)
Additions:
%%(c;main.c)
%%(c;pila-opt.c)
Deletions:
%%(C,main.c)
%%(C, pila-opt.c)