Additions:
int get_elem(unrolled_list_t * list, int k); // Parte III
void remove_elem(unrolled_list_t * list, int k); // Parte IV
void delete_unrolled_list(unrolled_list_t * list); // Parte V
Deletions:
int get_elem(unrolled_list_t * list, int k); // Parte II
void remove_elem(unrolled_list_t * list, int k); // Parte III
void delete_unrolled_list(unrolled_list_t * list); // Parte IV
Additions:
4) se il nodo non ha più elementi al suo interno: scollegare il nodo dalla lista e liberare la sua memoria
Deletions:
4) se il nodo non più elementi al suo interno: scollegare il nodo dalla lista e liberare la sua memoria
Additions:
=== Esercizio 1 - ottimizzazione località ===
Si ottimizzi la località del seguente codice, in modo da sfruttare in modo più efficiente le cache di memoria:
%%(c;stat.c)
// calcola le somme degli elementi di "in" a distanza "stride"
// fra loro a partire da "from" fino a "to"
static int sum_stride(const int* in, int from, int to,
int* out, int stride) {
int i, sum = 0;
for (i=from; i
return sum;
// calcola in "out[i]" le somme degli elementi di "in" a distanza
// "stride" fra loro a partire da "i", per ogni i in [0,stride-1]
void stat(const int* in, int n, int* out, int stride) {
int i;
for (i=0; i
out[i] = sum_stride(in, i, n, out, stride);
Si raccomanda di realizzare la versione ottimizzata all'interno di un file ##stat-opt.c## e di confrontare le prestazioni delle due versioni (base e ottimizzata) compilandole insieme con il seguente main di prova:
%%(c;main.c)
#include
#include
#define N 100000000
#define S 100
void stat(const int* in, int n, int* out, int stride);
void init(int* v, int n, int s) {
int i;
for (i=0; i
void print_array(int* v, int n) {
int i;
for (i=0; i
printf("%10d ", v[i]);
if ((i+1)%10 == 0) printf("\n");
}
int *in = malloc(N*sizeof(int));
int *out = malloc(S*sizeof(int));
assert(in != NULL && out != NULL);
init(in, N, S);
stat(in, N, out, S);
printf("Risultato: \n");
print_array(out, S);
free(in);
free(out);
Additions:
== Parte III: benchmarking ==
Scaricando il seguente [[http://www.dis.uniroma1.it/~sc/upload/esercitazioni/SC1-161216-bench.tgz archivio]] è possibile effettuare un primo confronto prestazionale tra la propra implementazione di lista unrolled e una linked list tradizionale, concentrandosi in particolare sulle due operazioni appena implementate.
Una volta decompresso l'archivio, copiare all'interno della cartella ##bench/## il file C ed il file header utilizzati per implementare la lista unrolled. Procedere dunque alla compilazione via ##Makefile## con il comando ##make## e confrontare i tempi riportati durante l'esecuzione dei due programmi generati (ovvero ##bench-linked## e ##bench-unrolled##). Quali conclusioni preliminari si possono trarre?
== Parte IV: rimozione del ##k##-esimo elemento ==
== Parte V (opzionale): eliminazione della lista ==
L'ultima parte dell'esercizio richiede l'implementazione della funzione:
Deletions:
== Parte III: rimozione del ##k##-esimo elemento ==
La terza parte dell'esercizio richiede l'implementazione della funzione:
== Parte IV (opzionale): eliminazione della lista ==
Additions:
=== Esercizio 2 - unrolled linked list ===
Deletions:
=== Esercizio 1 - unrolled linked list ===
Additions:
- definire nel file header ##unrolled_linked_list.h## un tipo C, chiamato ##node_t##, che definisce la struttura di un nodo. Assumiamo che gli elementi memorizzati nella lista siano di tipo ##int##
che restituisce una nuova lista unrolled (inizialmente senza alcun nodo).
Deletions:
- definire nel file header ##unrolled_linked_list.h## un tipo C, chiamato ##node_t##, che costituisce un nodo. Assumiamo che gli elementi memorizzati nella lista siano di tipo ##int##
che restituisce una nuova lista unrolled con un nodo (inizialmente senza alcun elemento al suo interno).
Additions:
~4) si eseguono gli step del CASO A
- (CASO C) se la lista non contiene alcun nodo:
~2) si collega il nodo alla lista;
~3) si inizializza il puntatore al nodo successivo nel nodo appena creato;
~4) si eseguono gli step del CASO A
Deletions:
~4) si esegue gli step del CASO A
Additions:
Si noti che ##r## è un intero positivo costante (ad esempio: ##r = 64##).
#define MAX_N_ELEM_NODE 8 // r = 8 per semplicita'
Deletions:
Si noti che ##r## è un intero positivo costante (ad esempio: ##r = 32##).
#define MAX_N_ELEM_NODE 8
Additions:
Si noti che ##r## è un intero positivo costante (ad esempio: ##r = 32##).
- (CASO A) se l'ultimo nodo della lista non è pieno (ospita meno di ##r## elementi):
- (CASO B) se l'ultimo nodo della lista è pieno (ospita esattamente ##r## elementi):
Deletions:
Si noti che ##r## è un intero positivo costante (ad esempio: ##r = 1024##).
- (CASO A) se l'ultimo nodo della lista non è pieno (ospita meno di ##q## elementi):
- (CASO B) se l'ultimo nodo della lista è pieno (ospita esattamente ##q## elementi):
Additions:
- l'accesso al ##k##-esimo elemento è un operazione immediata e richiede tempo costante.
- l'accesso al ##k##-esimo elemento richiede l'attraversamento di ##k## puntatori (partendo dal nodo in testa alla lista)
Deletions:
- l'accesso dell'##k##-esimo elemento è un operazione immediata e richiede tempo costante.
- l'accesso dell'##k##-esimo elemento richiede l'attraversamento di ##k## puntatori (partendo dal nodo in testa alla lista)
Additions:
Lo scopo dell'esercizio è implementare una struttura dati chiamata //unrolled linked list//. Questa struttura dati è una via di mezzo tra un array ed una lista collegata.
Deletions:
Lo scopo dell'esercizio è implementare una struttura dati chiamata //unrolled linked list//. Questa struttura dati è un compromesso tra un array ed una lista collegata.
Additions:
L'eliminazione del k-esimo elemento deve seguire la seguente strategia:
1) trovare il nodo che ospita il k-esimo elemento
2) decrementare il numero di elementi ospitati dal nodo
3) compattare gli elementi presenti nel nodo: tutti gli elementi successivi a quello che si vuole rimuovere devono essere spostati a sinistra di una posizione
4) se il nodo non più elementi al suo interno: scollegare il nodo dalla lista e liberare la sua memoria
Additions:
**Suggerimento:** eseguire il programma sotto Valgrind per verificare se la memoria allocata dinamicamente dal programma viene effettivamente liberata.
Additions:
void append_elem(unrolled_list_t * list, int x); // Parte I
int list_size(unrolled_list_t * list) // Parte I
int get_elem(unrolled_list_t * list, int k); // Parte II
void remove_elem(unrolled_list_t * list, int k); // Parte III
void delete_unrolled_list(unrolled_list_t * list); // Parte IV
void remove_elem(unrolled_list_t * list, int k);
printf("\n");
printf("Elemento [%d]: %d (corretto: %d)\n", k, get_elem(list, k), k);
printf("\n");
printf("Elemento [%d]: %d (corretto: %d)\n", k, get_elem(list, k), k + 16);
printf("Numero di elementi nella lista: %d (corretto: 4)\n", list_size(list));
== Parte IV (opzionale): eliminazione della lista ==
Tale funzione elimina tutta la memoria associata al lista (compresi i nodi della lista).
printf("\n");
printf("Elemento [%d]: %d (corretto: %d)\n", k, get_elem(list, k), k);
printf("\n");
printf("Elemento [%d]: %d (corretto: %d)\n", k, get_elem(list, k), k + 16);
printf("Numero di elementi nella lista: %d (corretto: 4)\n", list_size(list));
Deletions:
void append_elem(unrolled_list_t * list, int x); // Parte 1
int list_size(unrolled_list_t * list) // Parte 1
int get_elem(unrolled_list_t * list, int i); // Parte 2
void remove_elem(unrolled_list_t * list, int i); // Parte 3
void delete_unrolled_list(unrolled_list_t * list); // Parte 4
void remove_elem(unrolled_list_t * list, int i);
== Parte IV: eliminazione della lista ==
Tale funzione elimina tutta la memoria associata al lista (compresi nodi della lista).
Additions:
int get_elem(unrolled_list_t * list, int k);
Tale funzione ritorna il ##k##-esimo l'elemento contenuto nella lista ##list##. Se l'indice non è valido, viene terminato il programma stampando un messaggio di errore.
Deletions:
int get_elem(unrolled_list_t * list, int i);
Tale funzione ritorna ##k##-esimo l'elemento contenuto nella lista ##list##. Se l'indice non è valido, viene terminato il programma stampando un messaggio di errore.
No differences.
Additions:
unrolled_list_t * new_unrolled_list(); // Parte I
Deletions:
unrolled_list_t * new_unrolled_list(); // Parte I
Additions:
- definire nel file header ##unrolled_linked_list.h## (vedere lo scheletro completo proposto più in basso) un tipo C, chiamato ##unrolled_list_t##
che restituisce una nuova lista unrolled con un nodo (inizialmente senza alcun elemento al suo interno).
che inserisce in coda l'elemento ##x## nella lista ##list##.
int list_size(unrolled_list_t * list);
che ritorna il numero di elementi presenti nella lista ##list##.
L'inserimento in coda (append) di un elemento in una lista unrolled segue la seguente strategia:
- (CASO A) se l'ultimo nodo della lista non è pieno (ospita meno di ##q## elementi):
- (CASO B) se l'ultimo nodo della lista è pieno (ospita esattamente ##q## elementi):
~2) si collega l'ultimo nodo della lista al nodo appena creato;
~3) si inizializza il puntatore al nodo successivo nel nodo appena creato.
~4) si esegue gli step del CASO A
int list_size(unrolled_list_t * list) // Parte 1
printf("Numero di elementi nella lista: %d (corretto: 20)\n", list_size(list));
Deletions:
- definire nel file header ##unrolled_linked_list.h## un tipo C, chiamato ##unrolled_list_t##, che rappresenta una lista unrolled (inizialmente senza alcun nodo)
- implementare la funzione di inserimento in coda di un elemento:
L'inserimento in coda (append) di un elemento in un unrolled linked list segue la seguente strategia:
- se nessun nodo è presente nella lista allora:
~2) si inserisce l'elemento nel nodo;
~3) si aggiorna il numero elementi memorizzati nel nodo;
~4) si inizializza il puntatore al nodo successivo.
- se l'ultimo nodo della lista non è pieno (ospita meno di ##q## elementi):
- se l'ultimo nodo della lista è pieno (ospita esattamente ##q## elementi):
~2) si inserisce l'elemento nel nuovo nodo;
~3) si aggiorna il numero di elementi memorizzati nel nodo;
~4) si collega l'ultimo nodo della lista al nodo appena creato;
~5) si inizializza il puntatore al nodo successivo nel nodo appena creato.
Deletions:
In tutti i casi viene ritornato un puntatore al nodo in testa alla lista.