Puntatori Limitati in Linguaggio C

Un concetto molto importante introdotto nello standard C99 è quello dei puntatori limitati o puntatori restricted.

Attraverso di essi è possibile ottimizzare l'accesso alla memoria, migliorando le prestazioni del programma. In questa lezione vedremo cosa sono i puntatori limitati, come si usano e quando usarli.

Puntatori e Aliasing

Prima di spiegare cosa sono e come si utilizzano i puntatori limitati, è necessario spiegare cos'è il fenomeno dell'aliasing.

Quando abbiamo iniziato lo studio dei puntatori, abbiamo visto che uno dei loro più semplici utilizzi è quello di adoperarli come alias di variabili, ossia come nomi alternativi per accedere a una stessa variabile.

Prendiamo l'esempio che segue:

int a = 10;

int *p = &a;

*p = 20;

printf("%d\n", a); // Stampa 20

In questo caso, p è un puntatore ad intero. Attraverso l'uso dell'operatore indirizzo e dell'operatore di dereferenziazione, p viene utilizzato come alias di a, e quindi la modifica di *p equivale alla modifica di a.

Possiamo, inoltre, usare più puntatori come alias di una stessa variabile:

int a = 10;

int *p = &a;
int *q = &a;

*p = 20;

*q = 30;

printf("%d\n", a); // Stampa 30

In questo caso, p e q sono due puntatori ad intero che puntano alla stessa variabile a. Modificando *p o *q, si modifica a.

Quando si usano più puntatori come alias di una stessa variabile, si parla di aliasing:

Il fenomeno dell'aliasing dei puntatori, di per sé, non rappresenta un problema ma, anzi, viene spesso adoperato proprio per poter accedere a una stessa area di memoria da più punti del programma.

Esiste, tuttavia, un caso in cui l'aliasing può causare problemi. Ma, per capire, dobbiamo analizzare un esempio. Supponiamo di voler realizzare una funzione che prende in ingresso due array, uno di partenza ed uno di destinazione, e copia i valori del primo nell'altro:

void copia_array(int *dest, int *src, int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

L'implementazione è molto semplice: si scorre l'array di partenza src e si copiano i valori nell'array di destinazione dest.

Scritto così, il codice funziona correttamente ma non è ottimale. Infatti, i processori moderni sono in grado di accedere alla memoria, e quindi ai due array, in modo parallelo. Cioè, piuttosto che leggere la memoria byte a byte, come facevano i processori di un tempo, i processori moderni leggono la memoria a blocchi, ovvero leggono più byte alla volta.

Alla luce di ciò, i compilatori moderni possono ottimizzare il codice di sopra in modo da leggere e scrivere in memoria a blocchi, migliorando le prestazioni del programma. Quindi, anziché leggere un intero alla volta e poi scriverlo, il compilatore potrebbe leggere e scrivere blocchi di più di un intero alla volta. Ad esempio, potrebbe leggerli a due a due, oppure a quattro a quattro, a seconda dell'architettura del processore.

Questa ottimizzazione funzionerebbe in teoria. Nella pratica, purtroppo, i compilatori C non applicano tale ottimizzazione a causa del fenomeno dell'aliasing. Infatti, i compilatori non possono fare assunzioni sui due puntatori in ingresso, nel senso che essi potrebbero a locazioni di memoria qualunque: sia aree di memoria diverse, sia aree di memoria sovrapposte.

Il problema si presenta nel secondo caso: se i due array si sovrappongono, l'ottimizzazione non può essere applicata.

Per chiarire, supponiamo di avere due array da 8 elementi che si sovrappongono parzialmente come mostra la figura:

In questo caso, src punta all'inizio del primo array e dest punta all'inizio del secondo array. I due array si sovrappongono esclusi i primi due elementi.

Se chiamiamo la funzione copia_array con src e dest che puntano alle due locazioni di memoria sovrapposte, e il compilatore non applica alcuna ottimizzazione, il risultato sarà il seguente:

1. Copia del primo intero:

   

2. Copia del secondo intero:

   

3. Copia del terzo intero:

   

E così via.

Alla fine, il risultato sarà il seguente:

Mettiamo il caso, invece, che il processore su cui eseguiamo questa funzione sia in grado di leggere e scrivere in memoria a blocchi di quattro interi alla volta. Inoltre, supponiamo che il compilatore abbia ottimizzato la funzione copia_array in modo da leggere e scrivere in memoria a blocchi di quattro interi alla volta. Cosa accade?

1. Per prima cosa viene copiato il primo blocco di quattro interi:

   

   Dopo la copia il risultato sarà:

   

2. Successivamente, viene copiato il secondo e ultimo blocco:

   

   Dopo la copia il risultato sarà:

   

Come si può osservare, il risultato è completamente differente rispetto al caso non ottimizzato. Tuttavia, il compilatore deve sempre rispettare le intenzioni del programmatore, quindi deve garantire che il risultato finale sia lo stesso, indipendentemente dalle ottimizzazioni che applica.

Il problema è che il compilatore non è in grado di determinare se c'è effettivamente aliasing oppure no. Si tratta di un problema di difficile soluzione perché ad ogni chiamata della funzione il compilatore dovrebbe verificare se i due puntatori in ingresso si sovrappongono o meno. Questo è un problema computazionalmente molto oneroso e che rallenterebbe l'esecuzione del programma.

Morale della favola: In presenza di possibile aliasing i compilatori per il linguaggio C disattivano le ottimizzazioni che riguardano l'accesso alla memoria. Da notare che abbiamo usato il termine possibile, infatti il compilatore non può sapere se due puntatori puntano effettivamente alla stessa locazione di memoria. Ma proprio per questo, si deve premunire contro il possibile aliasing disattivando le ottimizzazioni.

Puntatori Limitati o Puntatori Restricted

La questione dell'aliasing e della disattivazione delle ottimizzazioni è un problema particolarmente sentito quando si scrivono programmi di calcolo numerico in cui si fanno operazioni su array di dati, specialmente su vettori e matrici. In questi casi, l'ottimizzazione dell'accesso alla memoria è fondamentale per ottenere prestazioni elevate.

Per risolvere questo problema, a partire dallo standard C99 sono stati introdotti i puntatori limitati o puntatori restricted.

Per definire un puntatore limitato, si usa la parola chiave restrict:

int * restrict p;

Quando definiamo un puntatore in questo modo, stiamo dicendo al compilatore che il puntatore p è l'unico puntatore che può accedere alla locazione di memoria a cui punta e, soprattutto, che non vi saranno altri puntatori che accederanno alla stessa locazione di memoria o porzioni di essa.

Torniamo all'esempio della funzione copia_array. Possiamo riscriverla utilizzando puntatori limitati:

void copia_array(int * restrict dest, int * restrict src, int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

In questo modo, stiamo sostanzialmente dicendo al compilatore che src e dest non si sovrappongono, e quindi può applicare le ottimizzazioni che ritiene opportune. In questo modo la funzione copia_array sarà più veloce ed efficiente.

Ovviamente c'è una controindicazione. Quando usiamo restrict stiamo facendo una promessa al compilatore che non useremo altri puntatori per accedere alla stessa locazione di memoria. Ma, la responsabilità di mantenere questa promessa è tutta a carico dello sviluppatore: il compilatore prenderà questa informazione per buona e non farà alcun controllo.

Inoltre, l'uso di restrict è pur sempre un suggerimento per il compilatore. Questo significa che il compilatore potrebbe non applicare le ottimizzazioni che ritiene opportune, anche se noi abbiamo usato restrict.

Ricapitolando:

tipo * restrict nome_puntatore;

Abbiamo detto che è compito del programmatore garantire che non vi siano sovrapposizioni tra le locazioni di memoria puntate da puntatori limitati e che il compilatore non farà alcun controllo. Ma cosa accade se il programmatore non mantiene la promessa? Cosa accade se si viola la regola dell'unicità del puntatore?

Vediamo un esempio senza l'uso di restrict:

int n = 10;
int *p;
int *q;

p = (int *) malloc(sizeof(int) * n);

q = p;

q[0] = 20;

Questo esempio è perfettamente legale. Abbiamo allocato un blocco di memoria di n interi e abbiamo assegnato a q l'indirizzo di memoria di p. Quindi, p e q puntano alla stessa locazione di memoria. Poi abbiamo modificato il primo elemento dell'array puntato da q. In pratica, abbiamo sfruttato l'aliasing per accedere alla stessa locazione di memoria da due punti diversi.

Modifichiamo il programma usando restrict:

int n = 10;
int * restrict p;
int * restrict q;

p = (int *) malloc(sizeof(int) * n);

q = p;

q[0] = 20;

In questo caso, abbiamo dichiarato p e q come puntatori limitati. Questo significa che p e q non possono accedere alla stessa locazione di memoria. Tuttavia, abbiamo violato la regola dell'unicità del puntatore, in quanto p e q puntano alla stessa locazione di memoria. Cosa accade?

Il compilatore non effettua nessun controllo, per cui il codice di sopra compila tranquillamente. Tuttavia, il comportamento del programma è indefinito. Potrebbe accadere che non succeda nulla, oppure che il programma vada in crash, oppure che il risultato sia imprevedibile.

Conclusioni

In questa lezione abbiamo studiato una serie di concetti avanzati riguardanti i puntatori in Linguaggio C:

• Abbiamo visto che l'aliasing è il fenomeno per cui si accede ad una stessa locazione di memoria attraverso più nomi (variabili o puntatori).
• L'aliasing può essere un fenomeno voluto o indesiderato. Nel secondo caso, può causare problemi di prestazioni.
• Abbiamo visto come i compilatori disattivino le ottimizzazioni che riguardano l'accesso alla memoria in possibile presenza di aliasing.
• Abbiamo introdotto i puntatori limitati o puntatori restricted, che permettono di dichiarare al compilatore che un puntatore è l'unico mezzo per accedere a una determinata locazione di memoria.
• Abbiamo visto che l'uso di restrict è un'ottimizzazione che va usata con cautela e solo se necessario.