ottimale confezionamento di una struct in modo ricorsivo su modelli senza perdita di allineamento

Question

ho una struct di 4 campi di tipi che provengono da parametri di modello:

template <typename T1, typename T2, typename T3, typename T4> 
struct __attribute__((aligned(8))) four_tuple { 
    typedef struct { 
    T1 t1; 
    T2 t2; 
    T3 t3; 
    T4 t4; 
    } payload; 
    payload p; 
}; 

Ogni tipo T1, T2, T3, e T4, è garantito per essere un tipo primitivo o un tipo four_tuple<...>::payload. Le garanzie sono ricorsive: si può pensare alla struct come codifica a quadtree i cui nodi foglia sono tipi primitivi.

Il mio obiettivo è che la struttura abbia il minimo possibile sizeof, a condizione che tutti i nodi foglia siano allineati correttamente. Gli strumenti consentiti per l'ottimizzazione sono specializzazioni modello di classe che utilizzano:

• riordino dei campi t1, t2, t3, t4
• aggiunta di campi di riempimento
• attributi gcc packed su payload
• forse altri?

Mi sento come se ci fosse una soluzione intelligente a questo problema utilizzando enable_if e SFINAE. Qualcuno può trovarlo?

Per illustrare il problema, se utilizziamo l'implementazione di cui sopra come using Foo = four_tuple<char,double,char,double>, avremo una dimensione di 32 per il carico utile e nel complesso. Se dichiariamo semplicemente il carico utile packed, gli double non saranno ben allineati. Una specializzazione di modello che riordina i campi in ordine decrescente (qui, double, double, char, char) darà un carico utile e una dimensione complessiva di 24. Ma i 6 byte aggiuntivi che utilizza sono dispendiosi, come si può vedere considerando using Bar = four_tuple<Foo::payload,int,int,int>. Con l'imballaggio ottimale Bar è possibile inserire 32 byte, ma con questo schema ne occorrerebbero 40. L'applicazione semplice del riordino del campo con packed comporterà un disallineamento di int in Bar - è necessario un riempimento.

So che in generale la ristrutturazione del layout di memoria dei campi di una struct può avere implicazioni sulle prestazioni a causa di considerazioni sulla cache, e che in generale tali implicazioni saranno almeno altrettanto significative di qualsiasi potenziale guadagno derivante da un migliore imballaggio. Mi piacerebbe esplorare i compromessi, però, e non posso davvero farlo correttamente nel mio contesto senza risolvere questo problema.

Answer 1

Il grosso problema nella tua tupla nidificata è che si desidera avere un campo di tipo four_tuple<char,double,char,double>::payload, allineato come se fosse un four_tuple<char,double,char,double>, ma senza richiedere che il tipo di contenitore erediti il ​​suo allineamento. Questo è complicato Ciò è possibile, ma rende il tuo codice altamente non portabile a qualsiasi cosa diversa da GCC. Immagino che va bene dato che suggerisci già un'estensione GCC nella tua domanda. L'idea di base è che i bit-campi possono essere utilizzati per inserire imbottitura per garantire un allineamento:

struct __attribute__((packed)) S { 
    char c; // at offset 0 
    int i; // at offset 1, not aligned 
    int : 0; 
    int j; // at offset 8, aligned 
    int : 0; 
    int k; // at offset 12, no extra padding between j and k 
}; 

int è, naturalmente, un tipo molto specifico con un allineamento molto specifico, e avete bisogno di un allineamento determinata in modo dinamico. Fortunatamente, GCC consente i campi di bit di tipo char, che generalmente applicano solo l'allineamento dei byte, da combinare con alignas, garantendo l'allineamento arbitrario.

A tal fine, è possibile controllare tutti i 24 ordini possibili sul campo e selezionare il carico utile che fornisce la dimensione totale più bassa. Ho reso il carico utile un tipo globale e gli ho fornito un parametro di modello aggiuntivo per indicare l'ordine dei campi. Ciò consente a tuple4<T1, T2, T3, T4> di verificare tuple4_payload<T1, T2, T3, T4, 1234>, tuple4_payload<T1, T2, T3, T4, 1243>, ecc. In ordine e scegliere quale sia il migliore.

template <typename...> struct smallest; 
template <typename...T> using smallest_t = typename smallest<T...>::type; 

template <typename T> struct smallest<T> { using type = T; }; 
template <typename T, typename...Ts> struct smallest<T, Ts...> { using type = std::conditional_t<sizeof(T) <= sizeof(smallest_t<Ts...>), T, smallest_t<Ts...>>; }; 

template <typename T1, typename T2, typename T3, typename T4> struct tuple4; 
template <typename T1, typename T2, typename T3, typename T4, int fieldOrder> struct tuple4_payload; 
template <typename T1, typename T2, typename T3, typename T4> struct tuple4_simple { T1 t1; T2 t2; T3 t3; T4 t4; }; 

template <typename T> struct extract_payload { using type = T; }; 
template <typename...T> struct extract_payload<tuple4<T...>> { using type = typename tuple4<T...>::payload; }; 
template <typename T> using extract_payload_t = typename extract_payload<T>::type; 

#define PERMS \ 
    PERM(1,2,3,4) PERM(1,2,4,3) PERM(1,3,2,4) PERM(1,3,4,2) PERM(1,4,2,3) PERM(1,4,3,2) \ 
    PERM(2,1,3,4) PERM(2,1,4,3) PERM(2,3,1,4) PERM(2,3,4,1) PERM(2,4,1,3) PERM(2,4,3,1) \ 
    PERM(3,1,2,4) PERM(3,1,4,2) PERM(3,2,1,4) PERM(3,2,4,1) PERM(3,4,1,2) PERM(3,4,2,1) \ 
    PERM(4,1,2,3) PERM(4,1,3,2) PERM(4,2,1,3) PERM(4,2,3,1) PERM(4,3,1,2) PERM(4,3,2,1) 

#define PERM(a,b,c,d) \ 
    template <typename T1, typename T2, typename T3, typename T4> \ 
    struct __attribute__((packed)) tuple4_payload<T1, T2, T3, T4, a##b##c##d> { \ 
    char : 0 alignas(T##a); extract_payload_t<T##a> t##a; \ 
    char : 0 alignas(T##b); extract_payload_t<T##b> t##b; \ 
    char : 0 alignas(T##c); extract_payload_t<T##c> t##c; \ 
    char : 0 alignas(T##d); extract_payload_t<T##d> t##d; \ 
    }; 
PERMS 
#undef PERM 

#define PERM(a,b,c,d) , tuple4_payload<T1, T2, T3, T4, a##b##c##d> 
template <typename, typename...T> using tuple4_smallest_payload_t = smallest_t<T...>; 
template <typename T1, typename T2, typename T3, typename T4> 
struct alignas(tuple4_simple<T1, T2, T3, T4>) tuple4 : tuple4_smallest_payload_t<void PERMS> { 
    using payload = tuple4_smallest_payload_t<void PERMS>; 
}; 
#undef PERM 

Nel tuo caso, lo utilizzeresti come tuple4<int, tuple4<char, double, char, double>, int, int>. Si noti che anche se il tipo di payload non è menzionato esplicitamente qui, verrà comunque utilizzato per il membro t2.