標籤：

如何實現在C++編譯期檢查tuple的空間布局順序是否達到了最省內存的目標？

01-14

我們知道std::tuple之流，由於類型對齊的緣故，他的欄位排列順序會影響到最終這個tuple的sizeof。所以在實現tuple時，優化欄位排列順序是有意義的。

為了簡單化問題，我們先假設每一個欄位大小都是2的冪並且不超過16，並且都按自己的大小來對齊。例如在x64 sizeof(long double)=16, 然後他就按照16位元組來對齊。如果我們把這每個欄位的size都放到一個數組裡a[n]，那麼現在建模後的問題來了：

問題1：

對於tuple size數組S[n], 我們定義

S[0] = a[0];

S[i] = ((S[i-1] +a[i]-1 )(~(a[i] - 1))) + a[i]; //for 0&

求 A1= min(S[n-1])或偏差小於常數的結果？注意a[n]排序未必能得到最優解。不過逆序會是最優解。

求 B1= max(S[n-1])或儘可能精確的B1上界？這個結果對緩衝區預分配是有用的。

說明：

1. S[i]的含義是，假設我們把a[0]放到了地址0處（顯然無條件對齊啦），尋找一個大於或等於已有的size 並且還是a[i]倍數的最小數

((S[i-1] +a[i]-1 )(~(a[i] - 1)))

作為地址放接下來的a[i]。這樣((S[i-1] +a[i]-1 )(~(a[i] - 1))) + a[i] 就是已經消耗的空間數量。i=i+1後依次類推。

2. B1目前我依然還沒有太多思路，手頭只有貪心演算法，讓a[n]的鄰接差的絕對值按從大到小排列， 看不出來是最優的。

問題2：

注意S[n-1]未必是真正的合法的tuple的sizeof。設a[max]是a[n]中的最大值，tuple結尾會需要加上padding, 讓tuple的sizeof能夠被a[max]整除。

求A2 = min( ((S[n-1] +a[max]-1 )(~(a[max] - 1))) )或偏差小於常數的結果？

求 B2= max( ((S[n-1] +a[max]-1 )(~(a[max] - 1))) )或儘可能精確的B2上界？

注意：問題2有一種很trivial的方法，就是問題1的解法得到的a[n]順序下的a[n-1]換成a[max]。這時候結果未必是最優的，當然偏差肯定是在常數範圍啦，不過我們當然期待更優的解法。

問題3：

問題1或者問題2的解法可能不利於c++編譯期計算。設n是編譯期常量，當i是編譯期常量時，a[i](0&<=i&

問題4：

設「每一個欄位大小都是2的冪並且不超過16...」 這堆假設繼續成立，實現一個空間最優化的tuple, 底層存儲能使用A2時的順序，但是訪問時依然能按定義的順序進行獲取。

----------------------------------------------------------------------------------------

顯然不用回答所有問題，對任意一個子問題提出看法亦可。

你可以用模板元編程枚舉類型參數的全排列，挨個求sizeof(tuple&)，然後static_assert看看最小值跟你手上的那個是否一致。

下面的程序可以列印出，給定類型的前提下，tuple尺寸最小的其中一個順序：

main函數：

int main(int argc, char **argv)
{
using candidates = _map_t&&>;
constexpr int min_size = min_of&<_map_t&&>::value;
cout &<&< typeid(head_of&::type&>::type).name() &<&< endl; return 0; }

運行結果：

class std::tuple&

代碼：

#include &
#include &
#include &
#include &

using namespace std;

namespace fuck
{
#define BEGIN_FUNC
template&
struct g;

#define END_FUNC
struct f
{
template&
struct apply
{
using type = typename g&::type;
};
};

// _list, _val, _val_of

template&
struct _list;

template&
struct _val;

template&
struct _val_of;

template&
struct _val_of&<_val&&>
{
static const int value = Value;
};

// _concat_t

template&
struct _concat;

template&
struct _concat&<_list&, _list&&>
{
using type = _list&;
};

template&
using _concat_t = typename _concat&::type;

// _join_t

template&
struct _join;

template&<&>
struct _join&<&>
{
using type = _list&<&>;
};

template&
struct _join&
{
using type = _concat_t&::type&>;
};

template&
using _join_t = typename _join&::type;

// _map_t

template&
struct _map;

template&
struct _map&&>
{
using type = _list&<&>;
};

template&
struct _map&&>
{
using type = _concat_t&<_list&::type&>, typename _map&&>::type&>;
};

template&
using _map_t = typename _map&::type;

// _unpack_t

template& class F, typename Ts&>
struct _unpack;

template& class F, typename ...T&>
struct _unpack&&>
{
using type = F&;
};

template& class F, typename Ts&>
using _unpack_t = typename _unpack&::type;

// _map_join_t

template&
using _map_join_t = _unpack_t&<_join_t, _map_t&&>;

// _pick_to_fronts_t

template&
struct _pick_to_fronts;

template&
struct _pick_to_fronts&&>
{
using type = _list&<&>;
};

template&
struct _pick_to_fronts&&>
{
using type = _concat_t&< _list&<_join_t&<_list&, T, _list&&>&>,
typename _pick_to_fronts&<_concat_t&&>, _list&&>::type
&>;
};

template&
using _pick_to_fronts_t = typename _pick_to_fronts&<_list&<&>, _list&&>::type;

// _perm_of

namespace _head_split
{
BEGIN_FUNC

template&
struct g&<_list&&>
{
using type = _list&&>;
};

END_FUNC
}

namespace _head_merge
{
BEGIN_FUNC

template&
struct g&<_list&&>&>
{
using type = _list&;
};

END_FUNC
}

template&
struct _insert_at_head
{
template&
struct apply
{
using type = _concat_t&<_list&, U&>;
};
};

template&
struct _perm_of;

namespace _partial_perm
{
BEGIN_FUNC

template&
struct g&<_list&&>
{
using perm_of_U_t = typename _perm_of&::type;
using type = _map_t&<_insert_at_head&, perm_of_U_t&>;
};

END_FUNC
}

template&<&>
struct _perm_of&<_list&<&>&>
{
using type = _list&<&>;
};

template&
struct _perm_of&<_list&&>
{
using type = _list&<_list&&>;
};

template&
struct _perm_of&<_list&&>
{
using fronts_t = _pick_to_fronts_t&;
using head_pairs_t = _map_t&<_head_split::f, fronts_t&>;
using type = _map_join_t&<_partial_perm::f, head_pairs_t&>;
};

template&
using _perm_of_t = typename _perm_of&<_list&&>::type;
}

using namespace fuck;

namespace test
{
struct inc
{
template&
struct apply
{
using type = _val&<_val_of&::value + 1&>;
};
};

struct this_and_next
{
template&
struct apply
{
using type = _list&::type&>;
};
};

template&
inline T* same()
{
return static_cast&(nullptr);
}
}

using namespace test;

void Test()
{
same&< _concat_t&<_list&<&>, _list&<&>&>,
_list&<&>
&>();

same&< _concat_t&<_list&<&>, _list&<_val&<1&>, _val&<2&>&>&>,
_list&<_val&<1&>, _val&<2&>&>
&>();

same&< _concat_t&<_list&<&>, _list&<_val&<1&>, _val&<2&>&>&>,
_list&<_val&<1&>, _val&<2&>&>
&>();

same&< _concat_t&<_list&<_val&<1&>, _val&<2&>&>, _list&<&>&>,
_list&<_val&<1&>, _val&<2&>&>
&>();

same&< _concat_t&<_list&<_val&<1&>, _val&<2&>&>, _list&<_val&<3&>, _val&<4&>&>&>,
_list&<_val&<1&>, _val&<2&>, _val&<3&>, _val&<4&>&>
&>();

same&< _join_t&<_list&<&>, _list&<&>, _list&<&>&>,
_list&<&>
&>();

same&< _join_t&<_list&<_val&<1&>&>, _list&<_val&<2&>, _val&<3&>&>, _list&<_val&<4&>, _val&<5&>, _val&<6&>&>&>,
_list&<_val&<1&>, _val&<2&>, _val&<3&>, _val&<4&>, _val&<5&>, _val&<6&>&>
&>();

same&< _map_t&, _val&<2&>, _val&<3&>&>&>,
_list&<_val&<2&>, _val&<3&>, _val&<4&>&>
&>();

same&< _map_join_t&, _val&<2&>, _val&<3&>&>&>,
_list&<_val&<1&>, _val&<2&>, _val&<2&>, _val&<3&>, _val&<3&>, _val&<4&>&>
&>();

same&< _pick_to_fronts_t&<&>,
_list&<&>
&>();

same&< _pick_to_fronts_t&<_val&<1&>&>,
_list&<_list&<_val&<1&>&>&>
&>();

same&< _pick_to_fronts_t&<_val&<1&>, _val&<2&>&>,
_list&<_list&<_val&<1&>, _val&<2&>&>, _list&<_val&<2&>, _val&<1&>&>&>
&>();

same&< _pick_to_fronts_t&<_val&<1&>, _val&<2&>, _val&<3&>&>,
_list&< _list&<_val&<1&>, _val&<2&>, _val&<3&>&>,
_list&<_val&<2&>, _val&<1&>, _val&<3&>&>,
_list&<_val&<3&>, _val&<1&>, _val&<2&>&>
&>
&>();

same&< _perm_of_t&<&>,
_list&<&>
&>();

same&< _perm_of_t&<_val&<1&>&>,
_list&<_list&<_val&<1&>&>&>
&>();

same&< _perm_of_t&<_val&<1&>, _val&<2&>&>,
_list&<_list&<_val&<1&>, _val&<2&>&>, _list&<_val&<2&>, _val&<1&>&>&>
&>();

same&< _perm_of_t&<_val&<1&>, _val&<2&>, _val&<3&>&>,
_list&< _list&<_val&<1&>, _val&<2&>, _val&<3&>&>,
_list&<_val&<1&>, _val&<3&>, _val&<2&>&>,
_list&<_val&<2&>, _val&<1&>, _val&<3&>&>,
_list&<_val&<2&>, _val&<3&>, _val&<1&>&>,
_list&<_val&<3&>, _val&<1&>, _val&<2&>&>,
_list&<_val&<3&>, _val&<2&>, _val&<1&>&>
&>
&>();
}

namespace first
{
BEGIN_FUNC

template&
struct g&<_list&&>
{
using type = T;
};

END_FUNC
}

namespace second
{
BEGIN_FUNC

template&
struct g&<_list&&>
{
using type = U;
};

END_FUNC
}

namespace to_tuple_and_size
{
BEGIN_FUNC

template&
struct g&<_list&&>
{
using type = _list&, _val&)&>&>;
};

END_FUNC
}

template&
struct min_of;

template&
struct min_of&<_list&<_val&&>&>
{
static const int value = Value;
};

template&
struct min_of&<_list&<_val&, T...&>&>
{
static const int min_of_the_rest = min_of&<_list&&>::value;
static const int value = Value &< min_of_the_rest ? Value : min_of_the_rest; }; template&
struct filter_tuple;

template&
struct filter_tuple&&>
{
using type = _list&<&>;
};

template&
struct filter_tuple&&>, Ts...&>&>
{
using type = _concat_t&<_list&, typename filter_tuple&&>::type&>;
};

template&
struct filter_tuple&&>, Ts...&>&>
{
using type = typename filter_tuple&&>::type;
};

template&
struct head_of;

template&
struct head_of&<_list&&>
{
using type = T;
};

int main(int argc, char **argv)
{
using candidates = _map_t&&>;
constexpr int min_size = min_of&<_map_t&&>::value;
cout &<&< typeid(head_of&::type&>::type).name() &<&< endl; return 0; }

tuple一般是個便捷的臨時存在。

就像ls說的， 不是臨時處理的話，直接再聲明個 struct 用名字來訪問， 而不是用tuple的序號。

為什麼排序得不到 A1/A2 的最優解？

按對齊從大到小排序放置不就沒有中間填充，只有末尾填充位元組了嗎？

實際上align值都是16，8，4，2，1位元組，所以數據按照align值從大到小排序就行了，沒有縫隙。當然tuple實際sizeof必須是最大align值的倍數，所以sizeof比把自己加起來略大。

我是不是理解錯問題了？因為略簡單。

很好玩，但感覺追求這個 sizeof 感覺沒啥意義。如果是欄位多到節省內存很重要的話為什麼不定義個 struct 呢。。再說為了節省內存而改變布局，還可能訪問效率還變低呢？

推薦閱讀：

※玩模板元編程走火入魔是一種怎樣的體驗？
※如何用c++ template 解決這個需求？

TAG:演算法 | STL | C | 元編程 | 演算法與數據結構 |