[C/C++] Allineamento di una struttura

[Lazy Bit]

Ciao a tutti! In alcuni codici sorgenti ho trovato dei commenti che avvisavano riguardo all'aggiunta di strutture con un corretto allineamento, in modo tale da permettere al compilatore di non eseguire il padding per tutti i sistemi supportati.

Cosa significa il concetto di allineamento di strutture? Cosa sarebbe il padding in questo caso? Se dovessi aggiungere alcune strutture al codice per estenderlo, dovrei stare attento a come progettarle per seguire "l'allineamento"?

Cercando su internet, ho trovato qualche spiegazione, ma non riesco bene a capire. Potreste gentilmente spiegarmi? Grazie in anticipo!

Allineamento strutture dati (???):
- http://en.wikipedia.org/wiki/Data_structure_alignment
- http://msdn.microsoft.com/it-it/library/71kf49f1(v=vs.80).aspx

[WarDuck]

Non vorrei sbagliarmi ma è un problema relativo alla dimensione della struttura stessa, che dovrebbe essere un multiplo della parola del calcolatore (32bit o 64bit rispettivamente).

In pratica sarebbe meglio che la struttura avesse dimensione pari a multipli di 4 o 8 bytes.

Questo perché, supponendo di avere una architettura a 32bit, le letture in memoria vengono effettuate a gruppi di 4 bytes... ciò significa che se hai una struttura ad esempio di 5 o 6 bytes dovrai effettuare 2 letture anziché una sola, "sprecando", per così dire, cicli di clock.

Spero di non aver detto castronerie.

[sottovento]

Alcuni processori (per esempio, la famiglia Motorola) "allineano" le parole su indirizzi pari/multipli di 4 a seconda della lunghezza della parola stessa. Per esempio, gli interi a 32 bit cominceranno ad un indirizzo multiplo di 4. I processori Intel in genere non hanno questo problema.
Il motivo e' (era) per problemi di performance e di semplicita' (non sono un elettronico, non sono sicuro al 100% che fossero questi i motivi). Ad ogni modo, e' chiaro che questo fa si che il bus (ammesso che sia a 32 bit) possa essere utilizzato "in pieno" per trasferire una singola parola a 32 bit, in maniera piu' semplice.

E' molto importante da tenere in considerazione il fattore allineamento quando si definiscono le strutture. Per semplicita', occorre sempre pensare che partano dall'indirizzo zero.

Per esempio:


struct MyStruct
{
char a;
int b;
};


Un processore Intel ritornera' sizeof(MyStruct) = 5 mentre un Motorola ritornera' sizeof(MyStruct) = 8.
Il compilatore aggiungera' dei riempitivi, piu' o meno cosi:


struct MyStruct
{
char a;
char dummy[3];
int b;
}


E' molto importante tenere questa cosa in mente, soprattutto se si scrive codice che deve girare su processori diversi, oppure se si intende spedire/memorizzare una struttura. Questo problema puo' causare diverse sorprese (pensa se trasferisci la struttura fra due computer con allineamenti diversi).

Esistono ovviamente altri tipi di allineamento. Alcuni processori allineano su indirizzi pari, per cui sizeof(MyStruct) = 6, e cosi' via.

In Visual Studio e' possibile cambiare l'allineamento mediante le proprieta' del progetto o mediante keyword speciali:


__declspec (align(8)) volatile MyVar;



Questo ti permette di fare dei "giochi" interessanti: per esempio, la variabile verra' trasferita utilizzando l'intero bus a 32 bit, pertanto se utilizzi la variabile tra vari thread, potresti ben sperare che non si debba sincronizzare l'accesso (sai, sincronizzare con un semaforo l'accesso ad una singola variabile risulterebbe terribilmente lento. Questo puo' drammaticamente incrementare le prestazioni del tuo software).

Sfruttando questo meccanismo, Win32 mette a disposizione le funzioni InterlockedXXX (per es: InterlockedExchange()) che ti garantiscono che la scrittura in quella variabile e' fatta in mutua esclusione SENZA DOVER SINCRONIZZARE, quindi restando in "User mode" con grande risparmio di tempo

[cdimauro]

Aggiungo qualche informazione e considerazione.

Alcuni processori richiedono che l'accesso a determinate informazioni siano allineate secondo alcune regole, pena il sollevamento di eccezioni o il malfunzionamento.

Un esempio sono i vecchi Motorola 68000/010/012, che per quantità maggiori di un byte (word, longword) richiedevano un allineamento a 16 bit.

La stessa cosa capita con alcuni processori RISC, che richiedono l'allineamento a 32 bit (ad esempio i vecchi ARM).

In genere il programmatore non si deve occupare di allineare le strutture in qualche modo (anche perché non saprebbe se allineare a 16, 32, 64, 128 bit, ecc.), perché è compito del compilatore.

Sicuramente con delle buone conoscenze di basso livello è possibile ottimizzare l'accesso ed eventualmente anche lo spazio, organizzando opportunamente i campi delle strutture.

E' comunque difficile, a causa delle differenze fra le architetture. Ad esempio ci sono architetture per cui i puntatori sono a 32 bit, e altre a 64 bit. Alcune architetture più vecchie hanno puntatori a 16 bit. Insomma, è un casino.:stordita:

[sottovento]

Come sempre hai ragione, caro mio!

L'unica precauzione, quando possibile, e' quella di scrivere la struttura mettendo i campi piu' lunghi all'inizio, per esempio:


struct MyStruct
{
int a;
char b;
};


funziona indipendentemente dall'allineamento del processore :D

[Lazy Bit]

Grazie per le risposte! Quindi, se ho capito bene, con alcuni processori l'accesso dei dati avviene prelevando una word che abbia le variabili allineate secondo uno specifico criterio, per semplificare il processo. Corretto? Come ottimizzare quindi una struttura, conoscendo l'allineamento che il compilatore andrà ad eseguire?

#include <iostream>
using namespace std;

int main()
{
typedef struct
{
char a;
int b;
}struttura;

cout << "Dimensione struttura: " << sizeof(struttura) << " bytes" << endl;
}

Sto eseguendo il codice su architettura x86-32 con un AMD Athlon 64 (Windows 7 a 32 bit) e la struttura ha dimensione 8 byte. In questo caso, anche invertendo l'ordine dei campi la dimensione non cambia. Quindi esegue un allineamento di 4 bytes...? Ma se l'architettura x86 non eseguiva alcun allineamento, perché la precedente struttura ha dimensione 8 bytes? Sto diventando matto... :D


Infine (scusate se approfitto del vostro aiuto), perché la seguente struttura viene allineata in quel modo (con un allineamento di 4 bytes)?

http://i.msdn.microsoft.com/dynimg/IC66193.png

Nel primo byte viene inserita la variabile "a", il secondo byte viene riempito, mentre il terzo e il quarto byte contengono la variabile "b" e nel quinto viene collocata "c".

Il software che sto estendendo deve esser eseguito solo su architetture x86-32 e x86-64 con i sistemi operativi Windows, Linux e MacOS. I compilatori che utilizzo sono Visual Studio 2010 e GCC 4.6.0. Come mi conviene creare le strutture? I compilatori supportano le istruzioni instrinseche SSE/SSE2/SSE3 per ottimizzare il programma. Nella pagina di Wikipedia che tratta l'allineamento delle strutture dati (allegato nel primo post), c'è scritto che SSE2 richiede un allineamento di 16 bytes, mentre le architetture x86 non utilizzano alcun allineamento (almeno in teoria, perché sembra proprio che utilizzino un allineamento di 4 byte). Quindi come fare per ottimizzare?

[Lazy Bit]

(Messaggio vuoto: per errore è stato copiato due volte il messaggio precedente)

[cdimauro]

Grazie per le risposte! Quindi, se ho capito bene, con alcuni processori l'accesso dei dati avviene prelevando una word che abbia le variabili allineate secondo uno specifico criterio, per semplificare il processo. Corretto?
Sì, ma, come dicevo, in genere è il compilatore che se ne occupa. E si vede anche dagli esempi che hai fornito.
Come ottimizzare quindi una struttura, conoscendo l'allineamento che il compilatore andrà ad eseguire?
Come ha suggerito sottovento. Tra l'altro il suo esempio calza perfettamente con la struct del tuo primo esempio.
#include <iostream>
using namespace std;

int main()
{
typedef struct
{
char a;
int b;
}struttura;

cout << "Dimensione struttura: " << sizeof(struttura) << " bytes" << endl;
}

Sto eseguendo il codice su architettura x86-32 con un AMD Athlon 64 (Windows 7 a 32 bit) e la struttura ha dimensione 8 byte. In questo caso, anche invertendo l'ordine dei campi la dimensione non cambia.
Quindi esegue un allineamento di 4 bytes...?
Sì, il compilatore esegue comunque un padding, in modo che la struttura finale occupi sempre un multiplo di 4 byte.

Nel caso che hai esposto, aggiunge 3 byte dopo char a, in modo che int b risulti allineata a 32 bit / 4 byte.
Ma se l'architettura x86 non eseguiva alcun allineamento, perché la precedente struttura ha dimensione 8 bytes? Sto diventando matto... :D
E' "colpa" del compilatore, che ottimizza per la velocità, quindi esegue il padding di cui sopra.

Non sono sicuro, ma probabilmente forzando il compilatore a ottimizzare per lo spazio, la struct di cui sopra potrebbe occupare 5 byte anziché 8.
Infine (scusate se approfitto del vostro aiuto), perché la seguente struttura viene allineata in quel modo (con un allineamento di 4 bytes)?

http://i.msdn.microsoft.com/dynimg/IC66193.png

Nel primo byte viene inserita la variabile "a", il secondo byte viene riempito, mentre il terzo e il quarto byte contengono la variabile "b"
Il secondo byte viene riempito perché la seconda variabile è di tipo short, e occupa 2 byte. In questo modo, grazie al padding, sarà sempre allineata a 16 bit / 2 byte, per cui quando il processore accederà al secondo campo, lo farà a piena velocità.
e nel quinto viene collocata "c".
Che, essendo char, occupa un solo byte e non ha problemi di allineamento.

Dopo c vengono aggiunti 3 byte, per far sì che d risulti allineata a 32 bit / 4 byte.
Il software che sto estendendo deve esser eseguito solo su architetture x86-32 e x86-64 con i sistemi operativi Windows, Linux e MacOS. I compilatori che utilizzo sono Visual Studio 2010 e GCC 4.6.0. Come mi conviene creare le strutture?
Come ha suggerito sottovento: piazzando i campi con tipo più grande prima.

L'ordine in genere è il seguente:
- double;
- puntatori; *
- long; *
- int; *
- float;
- short;
- char.

Dove ho messo i 3 * è perché sono da prendere con le pinze. Potrebbe succedere, infatti, che un puntatore occupi 4 byte, mentre un long 8.

Comunque in generale sono da prendere tutti con le pinze. :D
I compilatori supportano le istruzioni instrinseche SSE/SSE2/SSE3 per ottimizzare il programma. Nella pagina di Wikipedia che tratta l'allineamento delle strutture dati (allegato nel primo post), c'è scritto che SSE2 richiede un allineamento di 16 bytes,
Sì, per un loro limite implementativo. Successivamente (SSE3, se non ricordo male) sono state aggiunte istruzioni per il load (non so se anche per lo store; purtroppo ci sono così tanti dettagli che non riesco a tenerli a mente tutti) disallineato dalla memoria.

E le AVX prediligono i 32 byte (hanno registri a 256 bit), ma non dovrebbero avere il vincolo di accedere sempre a multipli di questa quantità.
mentre le architetture x86 non utilizzano alcun allineamento (almeno in teoria, perché sembra proprio che utilizzino un allineamento di 4 byte).
Come dicevo sopra, è il compilatore che in ogni caso ottimizza per la velocità.

Per il resto sono perfettamente in grado di lavorare con dati disallineati.
Quindi come fare per ottimizzare?
Visto che hai le SSE2 da usare, queste in genere operano su array di dati omogenei (ad esempio tutti float o int) , quindi non dovresti aver bisogno di allineare alcunché perché dovrebbe farlo il compilatore.

Il problema è: ma il compilatore lo fa? :D

Se non lo fa, cerca di aggiungere tanti elementi all'array in modo che la sua dimensione finale sia sempre un multiplo di 16 byte.

Esempio: anziché un array di 30 elementi float, allocane uno da 32 elementi.

E' probabile che ci siano delle specifiche direttive per allineare (e allocare) un array opportunamente per le unità SIMD.

[ingframin]

Puo' influire il fatto che con le memorie DDR e i nuovi processori si leggono 128byte per ciclo di clock?

[cdimauro]

Questo dipende dalla dimensione del bus. Le DDR sono a 64 bit, quindi trasferiscono 8 byte alla volta, per un burst che può arrivare 4 trasferimenti. Quindi in totale 32 byte per un burst. In dual channel il valore raddoppia, arrivando a 64 byte trasferiti.

Comunque ci sono differenze fra le memorie. Le DDR possono leggere una qualunque locazione di memoria (anche un solo byte volendo), e fermarsi sì.

Con le DDR2 invece un accesso implica l'inizio di un ciclo di burst che dev'essere completato, quindi nel caso peggiore se inizi dalla prima locazione, devi completare il burst di 4 locazioni.

Con le DDR3 è ancora peggio, perché lavorano con un burst completo.

In ogni caso tutto ciò è utile per riempire le cache, ma questo non sempre è un vantaggio. Pensa agli accessi random a singole locazioni di memoria, ad esempio.