Crea il tuo forum GRATIS su GlobalFreeForum.com.

Strutture in C, memoria e allineamento.

In questa sezione avverranno le discussioni sulla scienza e sulle arti. Si possono chiedere pareri e spiegazioni o postare i propri pensieri a riguardo di un argomento. Qui potete postare spiegazioni su un qualsiasi argomento: matematica, chimica, lingue etc...

Moderatori: Gruppo Admin, Gruppo Mod

Strutture in C, memoria e allineamento.

Messaggioda Flame_Alchemist » 22/09/2012 - 19:03

- Hey, Prof! Che cosa facciamo questa sera?
Quello che facciamo tutte le sere, Mignolo: tentare di conquistare il mondo!

L'altro giorno in IRC io e Style parlavamo delle struct in C, e di quanta memoria effettivamente occupassero. Li' per li' abbiamo tentato di rispondere come secondo noi le cose funzionassero per essere piu' efficienti, speculando un po'.
Oggi mi sono messo a fare un paio di ricerche/calcoli e ho scoperto un paio di cose interessanti.

Iniziamo dalle brutte notizie: tipicamente un programmatore vede la memoria come blocchi della dimensione di un byte ciascuno. Ecco, non e' cosi'.
La maggior parte dei processori odierni permette di accedere alla memoria in blocchi da 4 byte per volta (anche se ci sono istruzioni per leggere anche 1 byte, 8, o addirittura 16). Quindi questo vuol dire che l'indirizzo da cui la CPU puo' iniziare a leggere deve essere multiplo di 4 (questi indirizzi sono detti allineati a 4 byte).
Quando questo non avviene la maggior parte delle CPU generano un errore. Una delle poche CPU che riesce a leggere anche indirizzi non allineati e' l'x86, cioe' quella che viene usata di solito nei computer desktop. Anche con questa CPU comunque, un accesso ad indirizzo di memoria non allineato e' molto lento (perche' devono essere letti piu' blocchi da 4 byte e una parte del risultato deve essere scartato).

(Articolo con numeri/calcoli basati su architettura a 32 bit, con GCC versione 4.7.1, i vostri numeri potrebbero essere diversi)

Cominciamo dal caso piu' semplice.
Codice: Seleziona tutto
typedef struct {
    int a;
    int b;
} A;

Questa struct usa 4 + 4 = 8 byte. Semplice, non si puo' fare altrimenti. sizeof(A) restituisce proprio 8, infatti non si incorre in problemi di allineamento.
Codice: Seleziona tutto
typedef struct {
    char a;
    int b;
} B;

B dovrebbe occupare 5 (1 byte per il char, 4 per l'intero) byte. Come abbiamo visto sopra, pero', 5 byte non e' una dimensione comoda. Il char puo' risiedere a qualunque indirizzo in memoria, mentre l'intero deve essere salvato ad un indirizzo multiplo di 4. Il compilatore quindi fa in modo di aggiungere dello spazio in piu' dopo il char per garantire l'allineamento necessario. La struttura viene riscritta in questo modo:
Codice: Seleziona tutto
typedef struct {
    char a;
    char padding_a[3];
    int b;
} Bc;

(tranne che il padding non ha nome). Lo standard del C da' al compilatore liberta' su quanto padding aggiungere (anche 7 byte andrebbero bene), ma non credo che qualche compilatore aggiunga piu' spazio del necessario.
Codice: Seleziona tutto
typedef struct {
    char a;
    int b;
    char c;
} C;

Qui siamo nello stesso caso di prima, quindi vengono aggiunti 3 byte di padding dopo a, e 3 dopo c, in modo che anche la struttura abbia l'allineamento necessario. La struttura occupera' quindi 1 + 3 + 4 + 1 + 3 = 12 byte, esattamente il doppio di quanto dovrebbe occupare. E' giunto il momento di ridurre questo problema. Si puo' abbassare lo spazio utilizzato semplicemente riordinando gli elementi della struct.
Se spostiamo in questo modo:
Codice: Seleziona tutto
typedef struct {
    char a;
    char c;
    int b;
} C2;

il compilatore aggiungera' solo 2 byte di padding dopo c, e la dimensione scende ad 8.
Sembrerebbe una ottimizzazione che puo' fare anche il compilatore, ma lo standard C lo proibisce (dice esplicitamente che l'ordine di dichiarazione in una struct conta), anche se al programmatore l'ordine degli elementi non interessa piu' di tanto.

Ora veniamo all'esempio che ha fatto partire tutto:
Codice: Seleziona tutto
typedef struct {
    unsigned a : 2; //a occupa 2 bit
    unsigned b : 3; //b occupa 3 bit
} D;

Secondo quello che abbiamo visto fin'ora questa struct dovrebbe occupare 2 + 3 bit = 5 bit => 1 byte. Invece sizeof ritorna 4 byte: in realta' non dovrebbe stupire molto, ma cerchiamo di capire perche', e se si puo' fare qualcosa di interessante.
La ragione e' molto semplice: se si dichiarano gli elementi di un bitfield come unsigned, il bitfield deve essere allineato a 4 byte; se si dichiarassero come char questa limitazione verrebbe meno, e sizeof ritornerebbe 1.
I campi di un bitfield (in questo caso a e b) pero' non hanno questa limitazione, infatti i 27 bit mancanti vengono aggiunti tutti alla fine della struttura (e non 6 bit dopo a e 21 dopo b, come si potrebbe pensare). Quindi a e b vengono salvati uno di seguito all'altro.
Codice: Seleziona tutto
int main(int argc, char *argv[]) {
    D test;
    test.a = 3;
    test.b = 4;
    return 0;
}


Compilandolo con l'opzione -g e usando un debugger si ottiene qualcosa di simile a questo:
Codice: Seleziona tutto
[flame@archbox c]$ gcc d.c -o d -g
[flame@archbox c]$ gdb d
...
(gdb) b 10
Breakpoint 1 at 0x80483d2: file d.c, line 10
(gdb) run
Starting program: /media/experimental/c/d.c
Breakpoint 1, main (argc=1, argv=0xbffffb64) at d.c:10
10          test.a = 3;
(gdb) p &test;
$1 = (D *) 0xbffffac4
(gdb) x 0xbffffac4
0xbffffac4:     0x00000000
(gdb) n
11          test.b = 4;
(gdb) x 0xbffffac4
0xbffffac4:     0x00000003
(gdb) n
26          return 0;
(gdb) x 0xbffffac4
0xbffffac4:     0x00000013


(il vostro risultato potrebbe cambiare se usate un processore che salva i numeri in little-endian).

0x13 in binario e' 10011 (cioe' il decimale 19). Casualmente (o no?), noi abbiamo salvato in quell'indirizzo di memoria il numero 3 (in binario 11) e 4 (in binario 100).
a e b vengono salvati nello stesso blocco, senza distinzione, e' poi il compilatore ad estrarre il numero richiesto tramite mashere binarie (compilando con -S si puo vedere il codice -- come Neo -- e quindi capire la tecnica utilizzata).
La domanda spontanea e': visto che a e b vengono salvati assieme, possiamo modificare b accedendo solo ad a?
Per non saper ne' leggere ne' scrivere proviamo cosi':
Codice: Seleziona tutto
int main(int argc, char *argv[]) {
    D test;
    test.b = 0;
    test.a = 31; //il valore massimo che puo' essere salvato in a e' 3, in b invece posso salvare al massimo 7.
    printf("a = %d, b = %d\n", test.a, test.b);
    return 0;
}

Compilando il codice otteniamo un warning per overflow ("warning: large integer implicitly truncated ..."). Il compilatore ha implicitamente troncato il 31 al valore massimo che puo' essere salvato in a. Eseguendo, infatti, si ottiene:

a = 3, b = 0

Non e' quello che volevamo. Probabilmente c'e' una opzione del compilatore da modificare per ottenere il risultato voluto (che non conosco, aspetto suggerimenti), ma c'e' anche un'altra via.
Codice: Seleziona tutto
int main(int argc, char *argv[]) {
    D test;
    test.a = 0;
    test.b = 0;
    *(int *)&test = (2 << 5) - 1; //malvagio hack per dire al compilatore di trattare test come se fosse un int
    //scriviamo 31 nella cella di memoria in cui e' salvato test.
    printf("a = %d, b = %d\n", test.a, test.b);
    return 0;
}

Ricompiliamo e rieseguiamo, si ottiene:

a = 3, b = 7

Ok, abbastanza interessante, ma gli utilizzi pratici sono limitati. Comunque il compilatore genera del codice molto simile da solo anche compilando il primo programma (basta vedere l'assembly), quindi non stiamo facendo niente di particolare.

- Mignolo, stai ponderando quello che sto ponderando io?
Credo di si', Prof, ma dove troviamo un'anatra e un tubo di gomma, a quest'ora?
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Torna a Il Pozzo della conoscenza

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron