Allineamento bit per aumenti di spazio e prestazioni

Question

Nel libro Game Coding Complete, 3rd Edition, l'autore cita una tecnica per ridurre le dimensioni della struttura dati e aumentare le prestazioni di accesso. In sostanza si basa sul fatto che ottieni prestazioni quando le variabili membro sono allineate in memoria. Si tratta di un'eventuale potenziale ottimizzazione da cui i compilatori potrebbero trarre vantaggio, ma assicurandosi che ogni variabile sia allineata finiscono per gonfiare le dimensioni della struttura dei dati.

O quella era la sua richiesta almeno.

Il vero aumento delle prestazioni, afferma, è utilizzando il cervello e assicurando che la struttura sia progettata correttamente per sfruttare gli aumenti di velocità e impedire al compilatore di gonfiarsi. Egli fornisce il seguente frammento di codice:

#pragma pack(push, 1) 

struct SlowStruct 
{ 
    char c; 
    __int64 a; 
    int b; 
    char d; 
}; 

struct FastStruct 
{ 
    __int64 a; 
    int b; 
    char c; 
    char d; 
    char unused[ 2 ]; // fill to 8-byte boundary for array use 
}; 

#pragma pack(pop) 

Utilizzando i suddetti struct oggetti in un test non specificato che segnala un aumento delle prestazioni di 15.6% (222ms rispetto al 192ms) ed una dimensione più piccola per il FastStruct. Questo rende ogni senso su carta per me, ma non riesce a tenere sotto il mio test:

stesso tempo risulta e dimensioni (contando per il char unused[ 2 ])!

Ora, se il #pragma pack(push, 1) è isolato solo per FastStruct (o rimossi del tutto) facciamo vedere una differenza:

Così, finalmente, qui sta il problema: Do compilatori moderni (VS2010 in particolare) già ottimizzare per l'allineamento dei bit, quindi la mancanza di aumento delle prestazioni (ma aumentare le dimensioni della struttura come un effetto collaterale, come affermato da Mike Mcshaffry)? Oppure il mio test non è abbastanza intenso/inconcludente per restituire risultati significativi?

Per i test ho eseguito una serie di attività da operazioni matematiche, allineamento/controllo di array multidimensionali su colonna principale, operazioni con matrici, ecc. Sul membro non allineato __int64. Nessuno dei quali ha prodotto risultati diversi per entrambe le strutture.

Alla fine, anche se il loro è stato un aumento delle prestazioni, questo è ancora un bocconcino utile da tenere a mente per mantenere l'utilizzo della memoria al minimo. Ma mi piacerebbe se ci fosse un aumento delle prestazioni (non importa quanto minore) che io non sto vedendo.

Answer 1

È altamente dipendente dall'hardware.

Lasciatemi mostrare:

#pragma pack(push, 1) 

struct SlowStruct 
{ 
    char c; 
    __int64 a; 
    int b; 
    char d; 
}; 

struct FastStruct 
{ 
    __int64 a; 
    int b; 
    char c; 
    char d; 
    char unused[ 2 ]; // fill to 8-byte boundary for array use 
}; 

#pragma pack(pop) 

int main (void){ 

    int x = 1000; 
    int iterations = 10000000; 

    SlowStruct *slow = new SlowStruct[x]; 
    FastStruct *fast = new FastStruct[x]; 



    // Warm the cache. 
    memset(slow,0,x * sizeof(SlowStruct)); 
    clock_t time0 = clock(); 
    for (int c = 0; c < iterations; c++){ 
     for (int i = 0; i < x; i++){ 
      slow[i].a += c; 
     } 
    } 
    clock_t time1 = clock(); 
    cout << "slow = " << (double)(time1 - time0)/CLOCKS_PER_SEC << endl; 

    // Warm the cache. 
    memset(fast,0,x * sizeof(FastStruct)); 
    time1 = clock(); 
    for (int c = 0; c < iterations; c++){ 
     for (int i = 0; i < x; i++){ 
      fast[i].a += c; 
     } 
    } 
    clock_t time2 = clock(); 
    cout << "fast = " << (double)(time2 - time1)/CLOCKS_PER_SEC << endl; 



    // Print to avoid Dead Code Elimination 
    __int64 sum = 0; 
    for (int c = 0; c < x; c++){ 
     sum += slow[c].a; 
     sum += fast[c].a; 
    } 
    cout << "sum = " << sum << endl; 


    return 0; 
} 

---

Core i7 920 @ 3,5 GHz

slow = 4.578 
fast = 4.434 
sum = 99999990000000000 

Va bene, non molta differenza. Ma è ancora coerente su più esecuzioni.
Quindi l'allineamento fa una piccola differenza su Nehalem Core i7.

---

Intel Xeon X5482 Harpertown @ 3,2 GHz (Core 2 - generazione Xeon)

slow = 22.803 
fast = 3.669 
sum = 99999990000000000 

Ora date un'occhiata ...

6.2x più veloce !!!

---

Conclusione:

si vedono i risultati. Decidi se valga la pena o meno il tuo tempo per fare queste ottimizzazioni.

---

EDIT:

stessi parametri di riferimento, ma senza la #pragma pack:

Core i7 920 @ 3,5 GHz

slow = 4.49 
fast = 4.442 
sum = 99999990000000000 

Intel Xeon X5482 Harpertown @ 3,2 GHz

slow = 3.684 
fast = 3.717 
sum = 99999990000000000 

• I numeri Core i7 non è cambiata. Apparentemente può gestire il disallineamento senza problemi per questo benchmark.
• Il Core 2 Xeon ora mostra gli stessi orari per entrambe le versioni.Ciò conferma che il disallineamento è un problema nell'architettura Core 2.

Tratto da mio commento:

Se si lascia la #pragma pack, il compilatore tenere tutto allineato in modo che non si vede questo problema. Quindi questo è in realtà un esempio di cosa potrebbe accadere se si utilizza errato#pragma pack.

Answer 2

Tali ottimizzazioni manuali sono generalmente lunghe. L'allineamento è solo una considerazione seria se stai facendo i bagagli per lo spazio, o se hai un tipo di allineamento forzato come i tipi SSE. Le regole di allineamento e imballaggio predefinite del compilatore sono intenzionalmente progettate per massimizzare le prestazioni, ovviamente, e mentre la messa a punto manuale può essere utile, in genere non ne vale la pena.

Probabilmente, nel programma di test, il compilatore non ha mai memorizzato alcuna struttura nello stack e ha semplicemente mantenuto i membri nei registri, che non hanno allineamento, il che significa che è abbastanza irrilevante quale sia la dimensione o l'allineamento della struttura.

Ecco la cosa: ci possono essere aliasing e altri fastidi con accesso alla parola secondaria, e non è più lento accedere a una parola intera piuttosto che accedere a una parola secondaria. Quindi, in generale, non è più efficiente, nel tempo, confezionare più strettamente della dimensione della parola se si accede solo, ad esempio, a un membro.

Answer 3

Visual Studio è un ottimo compilatore per quanto riguarda l'ottimizzazione. Tuttavia, tieni presente che l'attuale "guerra di ottimizzazione" nello sviluppo del gioco non è nell'arena dei PC. Mentre tali ottimizzazioni potrebbero benissimo essere morte sul PC, sulle piattaforme della console è un paio di scarpe completamente diverso.

Detto questo, potresti voler ripubblicare questa domanda sullo specializzato gamedev stackexchange site, potresti ottenere alcune risposte direttamente dal "campo".

Infine, i risultati sono esattamente gli stessi fino al microsecondo che è morto impossibile su un sistema multithreaded moderno - Sono abbastanza sicuro che sia di utilizzare un timer risoluzione molto bassa, o il vostro codice di temporizzazione è rotto.

Answer 4

I compilatori moderni allineano i membri su contorni di byte diversi a seconda della dimensione del membro. Vedere la parte inferiore di this.

Normalmente non dovresti preoccuparti del riempimento della struttura, ma se hai un oggetto che avrà 1000000 istanze o qualcosa del genere, la regola del pollice è semplicemente ordinare i membri dal più grande al più piccolo. Non consiglierei di fare scherzi con il padding con le direttive #pragma.

Answer 5

Il compilatore sta per ottimizzare per dimensione o velocità e se non lo dici esplicitamente non sai cosa ottieni. Ma se segui il consiglio di quel libro vincerai la maggior parte dei compilatori. Metti le cose più grandi, allineate, prima nella tua struct, poi le cose a mezza misura, poi le cose a byte singolo, se ce ne sono, aggiungi alcune variabili dummy da allineare. Utilizzare byte per cose che non devono essere comunque può essere un successo in termini di prestazioni, poiché un compromesso usa gli inte per tutto (devi conoscere i pro e i contro di farlo)

L'x86 ha fatto un sacco di programmatori cattivi e compilatori perché consente accessi non allineati. Rendere difficile a molte persone trasferirsi su altre piattaforme (che stanno subentrando). Sebbene gli accessi non allineati funzionino su un x86, si ottiene un grave calo di prestazioni. Ecco perché è importante sapere come i compilatori funzionano sia in generale che in quello specifico che si sta utilizzando.

con cache, e come con le moderne piattaforme di computer basate su cache per ottenere qualsiasi tipo di prestazioni, si desidera che siano allineate e impacchettate. La semplice regola che viene insegnata ti dà sia ... in generale. È un ottimo consiglio L'aggiunta di pragmi specifici del compilatore non è altrettanto buona, rende il codice non-portatile e non richiede molta ricerca tramite SO o googling per scoprire quante volte il compilatore ignora il pragma o non fa quello che volevi veramente.

Answer 6

Su alcune piattaforme il compilatore non ha un'opzione: gli oggetti di tipi più grandi di char hanno spesso requisiti rigorosi per essere in un indirizzo adeguatamente allineato. In genere i requisiti di allineamento sono identici alla dimensione dell'oggetto fino alla dimensione della parola più grande supportata dalla CPU in modo nativo. Questo è short in genere richiede di essere a un indirizzo pari, long in genere richiede di essere a un indirizzo divisibile per 4, double a un indirizzo divisibile per 8, e ad es. Vettori SIMD a un indirizzo divisibile per 16.

Poiché C e C++ richiedono l'ordine dei membri nell'ordine in cui sono dichiarati, la dimensione delle strutture sarà molto diversa sulle piattaforme corrispondenti. Dal momento che le strutture più grandi causano più errori di cache, mancate pagine, ecc., Si verificherà un notevole peggioramento delle prestazioni durante la creazione di strutture più grandi.

Da quando ho visto un reclamo che non ha importanza: è importante per la maggior parte (se non tutti) i sistemi che sto usando. C'è un semplice esempio di mostrare diverse dimensioni.Quanto influisce sulla performance dipende ovviamente da come le strutture devono essere utilizzate.

#include <iostream> 

struct A 
{ 
    char a; 
    double b; 
    char c; 
    double d; 
}; 

struct B 
{ 
    double b; 
    double d; 
    char a; 
    char c; 
}; 

int main() 
{ 
    std::cout << "sizeof(A) = " << sizeof(A) << "\n"; 
    std::cout << "sizeof(B) = " << sizeof(B) << "\n"; 
} 

./alignment.tsk 
sizeof(A) = 32 
sizeof(B) = 24 

Answer 7

Lo standard C specifica che i campi all'interno di una struct devono essere allocati ad indirizzi crescenti. Una struct che ha otto variabili di tipo 'int8' e sette variabili di tipo 'int64', memorizzate in tale ordine, richiederà 64 byte (praticamente indipendentemente dai requisiti di allineamento di una macchina). Se i campi fossero ordinati 'int8', 'int64', 'int8', ... 'int64', 'int8', la struct impiegherebbe 120 byte su una piattaforma dove i campi 'int64' sono allineati sui confini di 8 byte. Riordinare i campi da soli permetterà loro di essere imballati più strettamente. I compilatori, tuttavia, non riordineranno i campi all'interno di una struttura senza permesso esplicito per farlo, poiché così facendo potrebbe cambiare la semantica del programma.