如何減少大型模板的編譯時內存佔用量？

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

（當然，也有可能存在如果你想讓不同的層次具有不同的結構，請將它們分開成小的，大的，巨大的類別，而不是一般的模板