c++ - 如何减少大型模板的编译时内存占用？

Question

假设我有一个包含 大量 个其他类声明的类。是否有可能以某种方式分散这些成本，以便编译时内存消耗不会为嵌套类型二次增长？如果需要，我愿意减少编译时间，如果可以的话，我很乐意将其划分为不同的翻译单元。

为了尝试提出解决方案，我编写了以下程序，说明了导致这些井喷的代码的简化版本:

// Add T to the list of args of SeqWithArgs N number of times:
template <int N, typename T, typename SeqWithArgs>
struct Append;

template <int N, typename T, template <typename...> class Seq, typename... Args>   
struct Append<N, T, Seq<Args...>>                                                  
{                                                                                  
    using type = typename Append<N-1, T, Seq<Args..., T>>::type;                   
};                                                                                 

template <typename T, template<typename...> class Seq, typename... Args>           
struct Append<0, T, Seq<Args...>>                                                  
{                                                                                  
    using type = Seq<Args...>;                                                     
};                                                                                 

static constexpr const int N = 10;                                              

// Tuple containing N instances of int
using Small = typename Append<N, int, std::tuple<>>::type;

// Tuple containing N instances of Small
using Big = typename Append<N, Small, std::tuple<>>::type;

// Tuple containing N instances of Big
using Huge = typename Append<N, Big, std::tuple<>>::type;

int main()
{                                                                               
    Huge h;                                                                     
    return 0;                                                                   
}

正如 Yakk 所指出的，这些 Append 操作效率极低。但是，在此代码的真实版本中，修改这些将需要对代码进行根本性的重组。

我将 N 从 10 更改为 70，并使用 GCC 4.8.1 编译我的程序得到了这个结果。我还运行了 time -v make 以获得峰值驻留内存使用率。以下是仅使用默认标志的结果:

这个结果对我来说似乎太过分了，不是因为形状(预计是 O(N^3) 并且似乎遵循那个形状)，而是因为幅度。几乎看起来 Small 正在为 Big 的 每个 实例进行扩展，而 Big 又依次为Huge 的每个实例化。在模板较少的代码中，通常会使用 extern 关键字声明某种类型的泛型特化，因此会避免这种“嵌套扩展”，但这些是 types，而不是值(value)观;这种构造是否存在类似的东西？

内存爆裂的原因是什么，我可以做些什么来减少这种内存占用不改变 Small、Big 的类型> 和 巨大的？

Answer 1

Append生成 Seq<T> Seq<T,T> ... Seq<T,...,T> .这比它生成 Append<n-1, T, Seq<T>> 的问题要少。 ，它是每个 N 的独特且唯一的类型和每个递归。

它会生成 N总名称长度的唯一类型 O(n^2*|T|) ，输出类型的大小为 O(n*|T|) .

然后我们将其链接起来。

Big 生成总大小的类型 O(n^2*O(n*|int|)) , 结束类型大小 O(n^2|int|) .巨款O(n^2*O(n^2|int|))=O(n^4|int|) .

生成的类型很多。

70^4=5000^2=O(2500 万) 总类型长度。

我们可以通过减少脑死亡的 Append 做得更好。分三步完成。

transcribe需要 t<Ts...>和 template<class...>class Seq并复制 Ts...结束了。

template<class...>struct t{using type=t;};
template<class src, template<class...>class dest>
struct transcribe;
template<class...Ts, template<class...>class dest>
struct transcribe<t<Ts...>,dest>{
  using type=dest<Ts...>;
};
template<class src, template<class...>class dest>
using transcribe_t=typename transcribe<src, dest>::type;

append接受任意数量的 t<...> s 并附加它们。

template<class... ts>
struct append;
template<>struct append<>{using type=t<>;};
template<class...Ts>struct append<t<Ts...>>{using type=t<Ts...>;};

template<class... Ts, class... Us, class... Zs>
struct append<t<Ts...>,t<Us...>,Zs....>:
  append<t<Ts...,Us...>,Zs...>
{};
template<class...ts>
using append_t=typename append<ts...>::type;

breaker取无符号值 N并将其分解为 2 的幂，输出 v<0,1,3,4> ( 2^0+2^1+2^3+2^4 ) 为 26 .

template<unsigned...>struct v{using type=v;};
template<unsigned X, class V=v<>, unsigned B=0, class=void>
struct breaker;
template<unsigned X, unsigned...vs, unsigned B>
struct breaker<X, v<vs...>, B, typename std::enable_if<
  X&(1<<B)
>::type>:breaker<X&~(1<<B), v<vs...,B>, B+1>
{};
template<unsigned X, unsigned...vs, unsigned B>
struct breaker<X, v<vs...>, B, typename std::enable_if<
  !(X&(1<<B))
>::type>:breaker<X&~(1<<B), v<vs...>, B+1>
{};
template<unsigned X, unsigned...vs, unsigned B>
struct breaker<0, v<vs...>, B, void>
{
  using type=v<vs...>;
};
template<unsigned X>
using breaker_t=typename breaker<X>::type;

Build 采用无符号值 N和 T .它Break s N .然后我们将二的幂构建为t<T,T,T,...,T> s。然后我们追加它们。

然后我们将输出转写为 Seq<...> .

这会生成 O(N*logN*logN)类型。所以对于大N可能会更好。另外生成的大多数类型都小而简单，这是一个优点。

这最多可以将您的负载减少 10 倍。值得一试。