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

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

作为righly通过指出雅克，这些操作是非常低效的。但是，在修改这些代码的实际版本中，需要对代码进行基本的重构。

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

这个结果似乎它没有形状的，因为过多的对我来说，（预计是O（N^3），似乎遵循形状） ，但由于数量巨大。它看起来很像Small正在扩大对每实例化大，反过来大被扩大了的巨大每一个实例。在模板较少的代码中，通常会使用关键字extern来声明某种类型的泛型，并因此会避免这种“嵌套扩展”，但这些是类型而不是值;这种构造是否存在类似的东西？

这是什么井喷内存的原因，我能做些什么来减少这种内存占用没有改变Small，Big和Huge类型？

Answer 1

Append生成Seq<T>Seq<T,T> ... Seq<T,...,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万）总类型长度。

我们可以做得更好，减少脑死附加。分三步做。

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; 

生成需要一个无符号值N和T。它是Break的N。然后，我们建立两个力量到t<T,T,T,...,T> s。然后我们追加它们。

然后我们取出输出并抄录到Seq<...>。

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

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

Answer 2

同意 - 看代码，它似乎有N^3复杂性。

我不认为有一个足够聪明的编译器能够发现“巨大”的“基础”类将与Small相同。编译器实际上必须解决这个问题，从“自下而上”开始，以某种方式说明，找出巨大的内容。它会发现，一旦完成，基类将会是相同的，但我不认为这些智慧将会在那里发现，从此开始。所以，它必须烧毁内存和CPU，才能达到这个结论。

该图似乎显示至少O（N^2），如果不是O（N^3）复杂度。其中一些无疑是与模板相关的。当涉及到模板时，编译器几乎没有余地。如果您要绘制编译N与N * 2普通类声明所需的时间和内存，我敢打赌，观察到的复杂性不会是2^3，而是线性的。

Answer 3

在编辑之后进行编辑：整个问题的执行定义的性质让我回想起来。其实，我只能看到下面提到的改进铿锵声。我只是用g ++ 4.8.2试过同样的东西，编译时间和内存使用率与使用clang的改进值相当（不管我是使用继承还是使用原始类型定义）。例如，N = 70只需要大约3GB的内存，而不像OP的情况那样需要12GB。所以，对于g ++，我的建议实际上并不是一个改进。

编辑：从我原来的回答下面，很明显，可以通过在每个级别引入一个新的类，其中下一个嵌套级别只有一个成员变量可以防止完整的嵌套扩展。但我发现同样的东西也适用于继承。类型Small,Big和Huge并未完全保留。你失去了类型标识，但是你保留了功能（运行时间）等价。所以，这与OP所希望的要比下面的成员技巧更接近。使用clang，它将编译时间缩短了约7倍。不确定它是否会改变缩放比例。下面是代码：

template<typename T> 
struct MyType : Append<N, T, std::tuple<>>::type { 
    typedef typename Append<N, T, std::tuple<>>::type Base; 
    using Base::Base; 
    using Base::operator=; 
}; 

int main() 
{ 

    MyType<MyType<MyType<int>>> huge; 

    //You can work with this the same way as with the nested tuples: 
    std::get<0>(std::get<0>(std::get<0>(huge))); 

    return 0; 
} 

的基本思想是一样的成员如下技巧：通过给东西在每个级别需要不是一个新的名称/不能向下展开来的最低水平（相到简单的typedef或使用声明），“嵌套”被降低。

---

原来的答复：

所以，很显然，编译器为确定内部各类一遍又一遍（相对于我的意见最初说），否则，以下是行不通的：如果您将“不改变Small，Big，Huge类型”的条件放宽到“不改变Small，Big，Huge的逻辑结构”的条件，那么可以通过拥有类的嵌套类型一个成员，而不是只是嵌套类型本身。我想这是因为，在这种情况下，编译器实际上并不需要嵌套类型。在每个级别上，元组成员只包含一些“嵌套的<”类型，编译器不能进一步扩展。当然，这是有代价的：初始化特殊的方式，访问级别的特殊方式（基本上追加“成员”给每个呼叫），等等

#include <tuple> 

// 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 = 40; 

template<typename T> 
struct Nested { 
    typename Append<N, T, std::tuple<>>::type member; 
}; 

int main() 
{ 
    Nested<Nested<Nested<int>>> huge; 

    //Access is a little verbose, but could probably 
    //be reduced by defining clever template 
    //"access classes/functions" 

    std::get<0>(std::get<0>(std::get<0>(huge.member).member).member); 

    return 0; 
} 

（当然，也有可能存在如果你想让不同的层次具有不同的结构，请将它们分开成小的，大的，巨大的类别，而不是一般的模板