Skip to content

Come si organizzano i membri di una struttura per sprecare il minor spazio possibile nell'allineamento?

Abbiamo la risposta a questo conflitto, almeno lo speriamo. Se hai ancora domande, faccelo sapere e ti risponderemo con piacere.

Soluzione:

(Non applicate queste regole senza riflettere. Si veda il punto di ESR sulla localizzazione nella cache dei membri che si usano insieme. E nei programmi multi-thread, fate attenzione alla falsa condivisione di membri scritti da thread diversi. Generalmente non si vogliono dati per thread in una singola struct per questo motivo, a meno che non lo si faccia per controllare la separazione con un grande alignas(128). Questo vale per atomic e alle barre non atomiche; ciò che conta è che i thread scrivano sulle linee di cache, indipendentemente dal modo in cui lo fanno).


Regola empirica: dal più grande al più piccolo alignof(). Non si può fare nulla che sia perfetto ovunque, ma il caso di gran lunga più comune al giorno d'oggi è un'implementazione sana e "normale" del C++ per una normale CPU a 32 o 64 bit. Tutti i tipi primitivi hanno dimensioni power-of-2.

La maggior parte dei tipi ha alignof(T) = sizeof(T), o alignof(T) con un limite massimo pari alla larghezza del registro dell'implementazione. Quindi i tipi più grandi sono solitamente più allineati di quelli più piccoli.

Le regole di impacchettamento delle strutture nella maggior parte delle ABI attribuiscono ai membri delle struct il loro valore assoluto di alignof(T) assoluto rispetto all'inizio della struttura, e la struttura stessa eredita il più grande allineamento alignof() .alignof()di ogni suo membro.

  • Mettere prima i membri sempre a 64 bit (come double, long longe int64_t). ISO C++ ovviamente non fissa questi tipi a 64 bit / 8 byte, ma in pratica su tutte le CPU che vi interessano lo sono. Chi esegue il porting del codice su CPU esotiche può modificare il layout delle strutture per ottimizzarlo, se necessario.

  • poi i puntatori e interi con larghezza di puntatore: size_t, intptr_te ptrdiff_t (che possono essere a 32 o 64 bit). Questi sono tutti della stessa larghezza nelle normali implementazioni moderne del C++ per CPU con un modello di memoria piatto.

    Considerate la possibilità di mettere i puntatori a destra e a sinistra degli elenchi collegati e degli alberi per primi, se vi interessano le CPU x86 e Intel. La ricerca di puntatori attraverso i nodi di un albero o di una lista collegata comporta delle penalità quando l'indirizzo iniziale della struct si trova in una pagina 4k diversa da quella del membro a cui si sta accedendo. Metterli per primi garantisce che ciò non accada.

  • allora long (che a volte è a 32 bit anche quando i puntatori sono a 64 bit, in ABI LLP64 come Windows x64). Ma è garantita almeno la stessa larghezza di int.

  • quindi 32-bit int32_t, int, float, enum. (Opzionalmente separare int32_t e float prima di int se ci si preoccupa di eventuali sistemi a 8 / 16 bit che ancora imbottiscono questi tipi a 32 bit, o che fanno meglio con loro naturalmente allineati. La maggior parte dei sistemi di questo tipo non ha carichi più ampi (FPU o SIMD), quindi i tipi più ampi devono essere sempre gestiti come pezzi multipli separati).

    ISO C++ consente int di essere stretto fino a 16 bit o largo arbitrariamente, ma in pratica è un tipo a 32 bit anche su CPU a 64 bit. I progettisti dell'ABI hanno riscontrato che i programmi progettati per funzionare con i tipi a 32-bit int sprecano solo memoria (e ingombro della cache) se int fosse più ampio. Non fate ipotesi che causerebbero problemi di correttezza, ma per le "prestazioni portatili" dovete avere ragione nel caso normale.

    Le persone che mettono a punto il codice per piattaforme esotiche possono modificarlo se necessario. Se una certa disposizione delle strutture è critica dal punto di vista delle prestazioni, magari commentate le vostre ipotesi e il vostro ragionamento nell'intestazione.

  • allora short / int16_t

  • allora char / int8_t / bool

  • (per più bool soprattutto se di lettura o se vengono modificati tutti insieme, si consideri la possibilità di impacchettarli con campi di bit a 1 bit).

(Per i tipi interi senza segno, trovare il tipo firmato corrispondente nel mio elenco).

Un byte multiplo di 8 array di tipi più stretti può andare prima, se lo si desidera. Ma se non si conoscono le dimensioni esatte dei tipi, non si può garantire che int i + char buf[4] riempirà uno slot allineato a 8 byte tra due array di tipi doubles. Ma non è un'ipotesi sbagliata, quindi lo farei comunque se ci fosse qualche ragione (come la localizzazione spaziale dei membri a cui si accede insieme) per metterli insieme invece che alla fine.

Tipi esotici Il sistema V x86-64 ha alignof(long double) = 16ma il sistema V i386 ha solo alignof(long double) = 4, sizeof(long double) = 12. È il tipo x87 a 80 bit, che è in realtà 10 byte ma imbottito a 12 o 16 in modo da essere un multiplo del suo alignof, rendendo possibili gli array senza violare la garanzia di allineamento.

E in generale diventa più complicato quando i membri della struct sono essi stessi degli aggregati (struct o union) con un sizeof(x) != alignof(x).

Un altro problema è che in alcune ABI (ad esempio Windows a 32 bit, se ricordo bene) i membri delle struct sono allineati alla loro dimensione (fino a 8 byte) rispetto all'inizio della struttura anche se alignof(T) è ancora solo 4 per double e int64_t.
Questo serve a ottimizzare il caso comune di allocazione separata di memoria allineata a 8 byte per una singola struct, senza fornire un allineamento garanzia Anche il sistema V i386 ha la stessa alignof(T) = 4 per la maggior parte dei tipi primitivi (ma malloc fornisce ancora memoria allineata a 8 byte perché alignof(maxalign_t) = 8). Ma in ogni caso, il sistema V i386 non ha questa regola di impacchettamento delle strutture, quindi (se non si dispone la struttura dal più grande al più piccolo) si può finire con membri a 8 byte sotto-allineati rispetto all'inizio della struttura.


La maggior parte delle CPU ha modalità di indirizzamento che, dato un puntatore in un registro, consentono l'accesso a qualsiasi offset di byte. L'offset massimo è di solito molto grande, ma su x86 si risparmia la dimensione del codice se l'offset del byte si inserisce in un byte firmato ([-128 .. +127]). Quindi, se si ha un array di grandi dimensioni di qualsiasi tipo, si preferisce metterlo più avanti nella struct dopo i membri utilizzati più di frequente. Anche se questo costa un po' di imbottitura.

Il vostro compilatore farà quasi sempre codice che ha l'indirizzo della struttura in un registro e non in un indirizzo al centro della struttura per sfruttare i brevi spostamenti negativi.


Eric S. Raymond ha scritto l'articolo The Lost Art of Structure Packing. In particolare, la sezione sul riordino delle strutture è sostanzialmente una risposta a questa domanda.

Fa anche un altro punto importante:

9. Leggibilità e località della cache

Mentre il riordino per dimensione è il modo più semplice per eliminare lo slop, non è necessariamente la cosa giusta. Ci sono altri due problemi: la leggibilità e la localizzazione nella cache.

In un grande che può essere facilmente divisa su una linea di cache, ha senso mettere due cose vicine se vengono sempre usate insieme. O anche contigue, per consentire il coalescenza del carico e della memorizzazione, ad esempio copiando 8 o 16 byte con un intero (non allineato) o caricando e memorizzando SIMD invece di caricare separatamente i membri più piccoli.

Le linee di cache sono tipicamente di 32 o 64 byte sulle CPU moderne. (Sui moderni x86, sempre 64 byte. E la famiglia Sandybridge ha un prefetcher spaziale di linee adiacenti nella cache L2 che cerca di completare coppie di linee da 128 byte, separato dal principale streamer HW di prefetch pattern e dal prefetching L1d).


Curiosità: Rust permette al compilatore di riordinare le strutture per migliorare l'impacchettamento o per altre ragioni. Non so se qualche compilatore lo faccia davvero. Probabilmente è possibile solo con l'ottimizzazione dell'intero programma al momento del collegamento, se si vuole che la scelta sia basata su come la struttura viene effettivamente utilizzata. Altrimenti le parti del programma compilate separatamente non potrebbero accordarsi sul layout.


(@alexis ha postato una risposta solo linkata che rimanda all'articolo di ESR, quindi grazie per questo punto di partenza).

gcc ha il -Wpadded che avverte quando viene aggiunto del padding a una struttura:

https://godbolt.org/z/iwO5Q3:

:4:12: warning: padding struct to align 'X::b' [-Wpadded]
    4 |     double b;
      |            ^

:1:8: warning: padding struct size to alignment boundary [-Wpadded]
    1 | struct X
      |        ^

È possibile riorganizzare manualmente i membri in modo che ci sia meno o nessun padding. Ma questa non è una soluzione trasversale alle piattaforme, perché tipi diversi possono avere dimensioni/allineamenti diversi su sistemi diversi (in particolare i puntatori sono a 4 o 8 byte su architetture diverse). La regola generale è quella di andare dall'allineamento più grande a quello più piccolo quando si dichiarano i membri e, se si è ancora preoccupati, compilare il codice con -Wpadded una volta (ma non lo terrei sempre attivo, perché a volte il padding è necessario).

Il motivo per cui il compilatore non può farlo automaticamente è lo standard ([class.mem]/19). Lo garantisce, perché si tratta di una semplice struttura con solo membri pubblici, &x.a < &x.c (per alcuni X x;), quindi non possono essere riorganizzati.

Non c'è una soluzione portatile nel caso generico. A parte i requisiti minimi che lo standard impone, i tipi possono essere di qualsiasi dimensione l'implementazione voglia farli.

Inoltre, il compilatore non può riordinare i membri della classe per renderla più efficiente. Lo standard impone che gli oggetti siano disposti nel loro ordine dichiarato (per modificatore di accesso), quindi anche questo è escluso.

È possibile utilizzare tipi a larghezza fissa come

struct foo
{
    int64_t a;
    int16_t b;
    int8_t c;
    int8_t d;
};

e questo sarà uguale su tutte le piattaforme, a patto che forniscano questi tipi, ma funziona solo con i tipi interi. Non esistono tipi in virgola mobile a larghezza fissa e molti oggetti/contenitori standard possono avere dimensioni diverse su piattaforme diverse.

Pubblica recensioni e valutazioni

Se il nostro articolo ti è stato utile, vorremmo che lo condividessi con più programmatori e ci aiutassi a diffondere queste informazioni.



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.