Cosa considerare per quanto riguarda l'allineamento durante la progettazione di un pool di memoria?

Question

Sto lavorando a un pool di memoria per un piccolo motore di gioco.

L'utilizzo principale sarà come deposito separato; un pool contiene oggetti di un tipo e una dimensione specifici. Attualmente i pool possono essere utilizzati per archiviare qualsiasi cosa, ma le allocazioni verranno eseguite in blocchi di una dimensione specifica. La maggior parte del fabbisogno di memoria verrà allocata contemporaneamente, ma la "crescita eccessiva" può essere abilitata se necessario per facilitare l'ottimizzazione (dimensioni quasi fisse).

Il problema è che ho iniziato a diventare un po 'paranoico quando si esamina l'allineamento della memoria. Sono abituato solo alla gestione della memoria grezza su processori a 8 bit in cui tutto è allineato in byte.

Sto lasciando che l'utente (me) specifichi la dimensione desiderata dei blocchi, che nel caso di archiviazione segregata sarebbe la dimensione degli oggetti che sto per memorizzare in esso.

L'approccio attuale è di allocare un grosso della memoria blocks * (desired_size + header_size) grande e posizionare gli oggetti in esso, con un'intestazione per ogni blocco; gli oggetti sarebbero ovviamente posizionati direttamente dietro questa intestazione.

Che cosa devo considerare per quanto riguarda l'allineamento della memoria nel mio scenario?

La risposta che ho trovato finora è che finchè desired_size rappresenta n -byte dati allineati; l'intestazione è correttamente allineata e impacchettata dal compilatore, così come i dati effettivi, tutto ciò che è memorizzato nel blocco sarà n- -byte allineato.

n è qualsiasi limite richiesto dalla piattaforma. Per il momento sto prendendo di mira x86, ma non mi piace fare supposizioni sulla piattaforma nel mio codice.

Alcune delle risorse che ho usato:

• http://www.ibm.com/developerworks/library/pa-dalign/
• http://en.wikipedia.org/wiki/Data_structure_alignment
• Memory alignment on a 32-bit Intel processor
• documentazione Boost Pool per l'ispirazione al disegno generale. Vorrei evitare di trascinare la spinta in questo progetto; e sto vedendo anche questa come un'opportunità di apprendimento.

Modifica

codice Uploaded piccolo campione che può utile a nessuno confuso quanto me in futuro here.

Answer 1

Le allocazioni con malloc sono garantite per essere allineate per qualsiasi tipo fornito dal compilatore e quindi qualsiasi oggetto [*].

Il pericolo è quando l'intestazione ha un requisito di allineamento inferiore rispetto al requisito di allineamento massimo per l'implementazione. Quindi la sua dimensione potrebbe non essere un multiplo del massimo. allineamento, e quindi quando provi a lanciare/usare buf + header_size come puntatore a qualcosa che fa ha il massimo. allineamento, è disallineato. Per quanto riguarda una C, questo è un comportamento indefinito. Su Intel funziona ma è più lento. Su alcuni ARM causa un'eccezione hardware. Su alcuni ARM dà in silenzio la risposta sbagliata. Quindi se non vuoi fare supposizioni sulla piattaforma nel tuo codice, devi affrontarlo.

Ci sono fondamentalmente tre trucchi che io sappia per garantire che il colpo di testa non causa disallineamento:

• Usa un allineamento pragma specifico dell'implementazione per forzare la questione.
• Utilizzare la conoscenza specifica della piattaforma per il layout della struttura e l'allineamento per assicurarsi che le sue dimensioni siano un multiplo del requisito di allineamento massimo sul sistema. In genere ciò significa "aggiungi un ulteriore int come padding, se necessario, per renderlo un 8-multiplo anziché solo un 4-multiplo".
• Imposta l'intestazione a union di ogni tipo standard, insieme alla struttura che si desidera effettivamente utilizzare. Funziona bene in C, ma avresti problemi in C++ se la tua intestazione non è valida per l'adesione ai sindacati.

In alternativa, si può solo definire header_size non essere sizeof(header), ma per essere quelle dimensioni arrotondato a un multiplo di un certo potere di grosso 2 che è "abbastanza buono". Se si spreca un po 'di memoria, così sia, e si può sempre avere una "intestazione di portabilità" che definisce questo genere di cose in un modo che non è puramente indipendente dalla piattaforma, ma rende facile adattarsi alle nuove piattaforme.

[*] con un'eccezione comune ai tipi di SIMD sovradimensionati. Dal momento che sono non standard, e sarebbe dispendioso 16 allineare ogni allocazione solo per loro, vengono messi da parte a mano, e hai bisogno di speciali funzioni di allocazione per loro.

Answer 2

Il compilatore allinea già i membri di oggetti e strutture che verranno memorizzati nel pool. Utilizzando l'imballaggio predefinito appropriato per la propria architettura, in genere 8 per un core a 32 bit. Devi solo assicurarti che l'indirizzo che generi dal tuo pool sia allineato di conseguenza. Quale su un sistema operativo a 32 bit dovrebbe essere un multiplo di 8 byte.

L'allineamento errato degli oggetti può essere molto costoso quando attraversano un limite della linea della cache della CPU. Un doppio che si trova a cavallo di due linee di cache richiede un tempo tre volte superiore per essere letto o scritto.

Answer 3

Utilizzare http://msdn.microsoft.com/en-us/library/bb982233.aspx - std :: alignment_of. Questo assicura che per ogni T che alleni nel tuo pool, conoscerai l'allineamento e potrai assicurarti che si adatti. Non ho intenzione di fingere di conoscere/comprendere la logica effettiva che useresti per rendere queste informazioni in garanzia di allineamento, ma esiste ed è disponibile per l'uso.

Answer 4

Per quanto ne so, boost :: pool si basa su "allocator of small objects" di alexandrescu spiegato nel suo libro "design moderno C++". Devo leggere il libro (visto che stai scrivendo questa roba anche per l'apprendimento)

Answer 5

Anche io ho manipolato l'allineamento della memoria. La prima cosa da capire è che ogni oggetto ha i propri requisiti di allineamento della memoria, che è (al massimo) la dimensione dell'oggetto stesso. Fortunatamente è spesso più piccolo.

Ci sono strutture di due tipi per aiutare a scrivere ripartitori di memoria corretti (C++ 0x, che può essere trovato in std::tr1 nella maggior parte STL):

• std::alignment_of dà l'allineamento come un valore in fase di compilazione
• std::aligned_storage dà una memoria allineato secondo i suoi parametri

Lavorare con i due di loro, si otterrà quello che ti serve.

Tuttavia, il design è leggermente off-base, non per la mente, perché l'intestazione non avrà lo stesso requisito di allineamento (in generale) rispetto agli oggetti memorizzati.

template <class T, size_t N> 
struct Block 
{ 
    // Header bits 

    typedef std::aligned_storage< 
     N*sizeof(T), 
     std::alignment_of<T>::value 
    >::type buffer_type; 
    buffer_type mBuffer; 
}; 

Due note:

• Block si potrebbe avere un allineamento diverso, ma non importa
• Si potrebbe utilizzare sizeof per l'allineamento, è garantito per funzionare, anche se un po ' sprecato

Infine, è possibile anche riuscire senza tutti questi, e alcuni aritmetica puntatore, ma dal momento che è offerto ....