6

テンプレート パラメーターから取得した型の 4 つのフィールドの構造体があります。

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;
};

各型T1、T2、T3、およびT4は、プリミティブ型または型であることが保証されていますfour_tuple<...>::payload。保証は再帰的です。構造体は、葉ノードがプリミティブ型である四分木をエンコードしていると考えることができます。

sizeof私の目標は、すべての葉ノードが適切に配置されているという条件に従って、構造体が可能な限り最小になることです。最適化に使用できるツールは、以下を使用したクラス テンプレートの特殊化です。

  • フィールドの並べ替えt1、t2、t3、t4
  • フィラー フィールドの追加
  • gcc 属性packedオンpayload
  • 多分他の人？

enable_ifSFINAEを使用すると、この問題に対する賢い解決策があるように感じます。誰でも見つけることができますか？

問題を説明するために、上記の実装をそのまま使用するusing Foo = four_tuple<char,double,char,double>と、ペイロードと全体のサイズが 32 になります。単純にペイロードを宣言するとpacked、doubleが適切に配置されません。フィールドを降順に並べ替えるテンプレートの特殊化 (ここではdouble, double, char, char) は、ペイロードと全体のサイズを 24 にしますusing Bar = four_tuple<Foo::payload,int,int,int>。最適なパッキングではBar32 バイトに収まる可能性がありますが、このスキームでは 40 バイトが必要になります。packedintBar

一般に、構造体のフィールドのメモリ レイアウトを再構築すると、キャッシュの考慮事項が原因でパフォーマンスに影響する可能性があり、一般に、これらの影響は、少なくともより良いパッキングによる潜在的な利益と同じくらい重要であることを知っています。ただし、トレードオフを検討したいのですが、この問題を解決しない限り、私のコンテキストでは適切にそれを行うことはできません。

4

1 に答える 1

1

入れ子になったタプルの場合の大きな問題は、 type のフィールドを であるかのfour_tuple<char,double,char,double>::payloadように整列させたいfour_tuple<char,double,char,double>が、コンテナー型がその整列を継承する必要がないことです。これは複雑です。これを行うことは可能ですが、コードを GCC 以外に非常に移植しにくくなります。質問で既に GCC 拡張機能を提案しているので、それで問題ないと思います。基本的な考え方は、ビットフィールドを使用してパディングを挿入し、整列を確保できるというものです。

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もちろん、非常に特定のアラインメントを持つ非常に特定のタイプであり、動的に決定されるアラインメントが必要です。幸いなことに、GCC では、通常はバイト アラインメントのみを強制する 型のビット フィールドcharを と組み合わせてalignas、任意のアラインメントを保証することができます。

これが完了すると、24 の可能なフィールド順序をすべて確認し、合計サイズが最小になるペイロードを選択できます。ペイロードをグローバル タイプにし、フィールドの順序を示す追加のテンプレート パラメーターを指定しました。これにより、、 などを順番tuple4<T1, T2, T3, T4>にチェックして、最適なものを選択できます。tuple4_payload<T1, T2, T3, T4, 1234>tuple4_payload<T1, T2, T3, T4, 1243>

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

あなたの場合、これを として使用しますtuple4<int, tuple4<char, double, char, double>, int, int>。t2ペイロード タイプはここでは明示的に言及されていませんが、メンバーには引き続き使用されることに注意してください。

于 2016-01-08T23:35:24.523 に答える