Newsgroup: it.comp.lang.c
Titolo: allineamento dei dati nello heap

ciao a tutti,
ho molti dubbi sull'allineamento dei dati, in particolare ai dati
allocati nello heap.
Da quello che ho letto, per ragioni legate all'architettura hardware e
alle performance, le strutture dati vengono "allienate", e questo in
alcuni casi potrebbe costringere il compilatore ad aggiundere dei byte
in più.
Esempio:
typedef struct
{
   int a;
   char b;
} str_test_t;
probabilmente il valore restituito da sizeof(str_test_t) sarà 8:
4(int) + 1(char) + 3(padding).
Non mi è chiaro invece se l'indirizzo che punta ad una variabile di
tipo str_test_t deve essere multiplo di 4. Non posso mettere la
vaiabile in questo indirizzo: 0x00000001?
Cosa succede se forzo il processore a lavorare con dati che non sono
contenuti in indirizzi multipli di 4?
Ad esempio:
void* ptr = malloc(1000); // <-- mi sembra di aver letto che malloc
restituisca sempre indirizzi allienati multipli di 4 ( ovviamende
dipende dall'architettura )
str_test_t* ptrStr = (str_test_t*)(ptr+1); // <-- faccio in modo che
una istanza di str_test_t inizi ad un indirizzo dispari
Benche compili e non dia errori di segmentazione a runtime che tipo di
errore commetto? Problemi di performance perchè costringo il
processore ad eseguire piu cicli per recuperare i dati?
Questi dubbi nascono dal fatto che di solito alloco sempre una
quantita di heap all'inizio del programma, in cui poi metto dati
eterogenei. Il vantaggio è che faccio solo una chiamata a malloc e non
ho problemi di memomy leack. Però mi chiedo se devo tener conto anche
del fatto che i miei dati dovrebbero risiedere in indirizzi multipli
di 4.
Grazie mille
Alessio


Dipende molto dal processore che stai usando.
Su un'architettura x86 un elemento non allineato causa solo una 
perdita di performance proprio perché devi fare un doppio accesso. 
Inoltre l'allineamento, in genere, favorisce la gestione della cache.
C'è anche la possibilità di forzare un'eccezione settando una flag del 
processore (AC = Alignment Check) ma credo che sia raramente usata.
Altre architetture potrebbero causare eccezioni proprio perché il 
processore non accetta indirizzi che abbiano l'allineamento corretto. 
  In quei casi ho visto aggirare il problema usando l'accesso byte a 
byte per ricostruire il dato in un registro. con evidente 
peggioramento delle prestazioni.
Ciao
Giovanni
-- 
   A computer is like an air conditioner,
   it stops working when you open Windows.
   < 
http://giovanni.homelinux.net/
 >

 processore non accetta indirizzi che abbiano l'allineamento corretto.
Naturalmente intendevo:
Altre architetture potrebbero causare eccezioni proprio perché il
processore accetta solo indirizzi che abbiano l'allineamento corretto.


 perdita di performance proprio perché devi fare un doppio accesso.
Grazie mille per la rapida risposta.
In effetti ho sempre, ed erroneamente, pensato che fosse importante
solo che una struttura avesse lunghezza multipla dal piu grande dei
sui elementi (sto un po approssimando), ma non ho mai attribuito
importanza all'indirizzo a cui si trova fisicamente una variabile di
questa struttura. La scelta di allocare tutto subito puo andare bene,
ma bisogna stare attenti a rispettare l'allineamento, atrimenti i
vantaggi di avere una unica allocazione si perdono in incrementi di
cicli del bus per leggere i dati.
Ciao
   Alessio

 processore non accetta indirizzi che abbiano l'allineamento corretto.
Intendevi "scorretto"?


Mi ero già "corretto" :-)


 in piů.
 > [...]
 > Non mi č chiaro invece se l'indirizzo che punta ad una variabile di
 > tipo str_test_t deve essere multiplo di 4. Non posso mettere la
 > vaiabile in questo indirizzo: 0x00000001?
Se ne č parlato proprio poco tempo fa su questo ng. Sono stato io l'OP 
di quel thread, prova a cercare.
I miei dubbi nascevano dal fatto che lavoravo con protocolli di 
comunicazione dove i pacchetti dati non erano stabiliti da me, ma da 
altri. Insomma, un intero a 16 bit poteva tranquillamente trovarsi ad un 
indirizzo dispari.
Con il mio processore riesco a fare accessi non allineati, con 
diminuzione delle performance. Ma si tratta di qualche colpo di clock in 
piů, cosě ho deciso di scrivere nel modo piů portabile possibile e cioč 
costruendomi l'intero a partire dai byte.
Se quell'intero č "allocato" ad un indirizzo allineato nel pacchetto 
dati, comunque me ne frego :-)
Nel tuo caso, sembra che tu abbia bisogno di allocare una volta per 
tutte un certo spazio in RAM per risparmiare il tempo speso da tante 
malloc() successive.
Perň se decidi di allocare 1000 byte, allora forse č meglio un bel 
vettorone ad allocazione statica, anzichč una malloc():
   unsigned char heap[1000];
Perň non mi convince quando dici che devi gestire delle variabili 
nell'heap. Come fai ad allocare dinamicamente le varie variabili 
nell'heap? Hai un tuo gestore di memoria? Gestisci la "frammentazione"? 
Oppure lo schema di allocamento č di tipo statico, cioč sai a priori 
quali e quante sono le variabili che vorrai mettere nell'heap?
In questo caso avrei due proposte.
Puoi definire qualcosa del genere:
   typedef struct {
     struct MiaStruct1 str1;
     struct MiaStruct2 str2;
     ...
   } HeapLayout;
   HeapLayout heap;
   struct MiaStruct1 *ms1 = &heap.str1;
   struct MiaStruct2 *ms2 = &heap.str2;
Perň a questo punto fare anche un semplicissimo:
   struct MiaStruct ms1;
   struct MiaStruct ms2;
   ...
Insomma, non mi viene in mente un'applicazione dove sia meglio il tuo 
approccio. Ti va di spiegarne i dettagli?

 approccio. Ti va di spiegarne i dettagli?
Ciao,
grazie mille per l'interessamento.
Sto scrivendo, più per divertimento che per fini pratici, un gestore
della memoria dinamica, quindi dello heap.
L'approccio che sto utilizzando è quello di preallocare allo startup
una certa quantità di RAM e ogni richiesta successiva di allocazione
viene fatta in questa area.
Come dicevo il vantaggio è che non avrò mai memory leak oltre a
limitare le malloc.
Cerco di gestire la frammentazione di quest'area cerando una lista
linkata degli spazi vuoti. E gestisco anche la coesione di questi
spazi in fase di deallocazione.
Il problema di utilizzare un array statico è che a priori non so
quanta ram avrò mi servirà. Quindi sono in questa situazione:
- non conosco la quantità massima di memoria che mi servirà a run time
- le mie strutture dati non hanno una dimensione prestabilita, l'idea
è di creare un gestore il piu possible generico. Cosi lo riutilizzo
per altre applicazioni
Facendo questo lavoro però ho purtroppo trascurato gli aspetti legati
all'allineamento dei dati, e non avendo mai eccezioni a run time non
mi sono mai accorto di questo errore.
Nel mio gestore ogni volta che dovrò allocare dei dati dovrò essere
sicuro di restituire un puntatore ad un indirizzo multiplo di 4.
Premetto che le mie indagini su questo aspetto sono ancora all'inizio.
Ciao
   Alessio

 di 4.
Questo è quello che normalmente fa la malloc().  Restituisce sempre 
puntatori allineati alla dimensione del bus.  Anche la dimensione 
dell'area allocata è normalmente a multipli della stessa.
Per es. se chiedi 14 byte in realtà l'allocazione è di 16.  Questo 
allineamento delle dimensioni è utile anche per mantenere 
l'allineamento dei puntatori.


    Alessio
Per "divertimento" te lo consiglio, anche io ho scritto più di un
allocatore :-)
Per "fini pratici" lascia perdere: quello che stai facendo è già
implementato a livello di kernel/libc, che sicuramente sanno svolgere
meglio questo lavoro (non solo ovviamente per gli anni di esperienza,
ma anche perché possono tenere in conto tanti altri fattori che per un
singolo programma utente sono nascosti).
Ciao!

 Premetto che le mie indagini su questo aspetto sono ancora all'inizio.
Questo sicuramente sì...

Creare un proprio algoritmo di allocazione della memoria è sicuramente
un ottima sfida su cui mettersi alla prova, però secondo me non serve
a nulla contro i memory leak.
Semplicemente perchè se usi la tua funzione di allocazione e poi da
qualche parte dimentichi di chiamare la tua funzione di deallocazione,
il memory leak si crea ugualmente.
Per evitare i memory leak potresti invece concentrarti nella creazione
di un garbage collector.
Ne esistono diversi con tecniche anche molto raffinate e sofisticate
da cui imparare.
Ma per gli scopi "quotidiani" direi che la tecnica del "reference
counting" è una ottima soluzione, semplice da implementare e
facilmente comprensibile da chiunque.
saluti
P.S. in realtà neanche il ref.counting ti evita i memory leak, infatti
se una volta referenziato una struttura ti dimentichi di
dereferenziarla, questa sopravvivrà im memoria per sempre...
ti liberà però dell'incombenza di decidere a priori in che parte del
programma verrà liberata tale struttura, cosa che non sempre è così
scontata.