C++ 使用分治減小模板遞歸深度
起因
C++14 引入 STL 的 make_index_sequence 可以生成一個類型為 std::size_t，0 到 N-1 的編譯期序列，我們可以這樣使用它：
代碼
//利用函數參數推導提取序列
template<std::size_t... Seq>
void foo(std::index_sequence<Seq...>)
{
//使用Seq
}
//利用模板特化提取序列
template<typename>
struct extract_sequence;
template<std::size_t... Seq>
struct extract_sequence<std::index_sequence<Seq...>>
{
//使用Seq
};
foo(std::make_index_sequence<5>{});//foo內部得到 {0, 1, 2, 3, 4}
extract_sequence<std::make_index_sequence<3>>;//extract_sequence內部得到 {0, 1, 2}
可是在我的程序中，我想創建一個等差數列，std::make_index_sequence 無法直接拿來使用（其實可以間接使用，后文會提到）。于是我編寫了一個自己的版本：
代碼
//主模板，遞歸實例化
template<std::size_t Base,std::size_t Step, std::size_t Count, std::size_t... Seq>
struct make_arithmetic_progression : make_arithmetic_progression<Base + Step, Step, Count-1, Seq..., Base>
{
};
//遞歸終點特化版本
template<std::size_t Base, std::size_t Step, std::size_t... Seq>
struct make_arithmetic_progression<Base, Step, 0, Seq...>
{
using type = std::index_sequence<Seq...>;
};
template<std::size_t Base, std::size_t Step, std::size_t Count>
using arithmetic_progression = typename make_arithmetic_progression<Base, Step, Count>::type;
foo(arithmetic_progression<1, 2, 3>{});//foo內部得到 {1, 3, 5}
extract_sequence<arithmetic_progression<3, 3, 3>>;//extract_sequence內部得到 {3, 6, 9}
問題
這個實現看起來沒什么問題，可以正確地生成任意指定的等差數列。但是在一個偶然的情況下，我在創建一個很長的數列時，遇到以下錯誤：
模板遞歸實例化深度超過限制了，查閱了一下資料，獲知各家編譯器都對這個深度有一個默認限制，GCC 和 clang 都是 1024，MSVC 是 499。
可以使用編譯參數來指定這個限制：
代碼
-ftemplate-depth=N //GCC 和 clang
/Zc:templateDepth=N //MSVC
但這顯然是下策，每次編譯這個模板都需要在編譯時加上額外的指令，非常麻煩。
解決
自定義方式
我們知道有個排序算法叫歸并排序，將長列表不斷拆分成最小單元后合并。我們的這個數列實現也可以直接借鑒這個思路，拆分數組后合并：
代碼
//list拼接類主模板
template<typename, typename>
struct index_list_concat;
//list拼接類特化版本
template<std::size_t... Seq1, std::size_t... Seq2>
struct index_list_concat<std::index_sequence<Seq1...>, std::index_sequence<Seq2...>>
{
using type = std::index_sequence<Seq1..., Seq2...>;
};
//輔助分割主模板
template<std::size_t Base, std::size_t Step, std::size_t Count>
class make_arithmetic_progression
{
static constexpr std::size_t HalfCount = Count / 2;
static constexpr std::size_t HalfBase = Base + HalfCount * Step;
public:
using type = typename index_list_concat<typename make_arithmetic_progression<Base, Step, HalfCount>::type,
typename make_arithmetic_progression<HalfBase, Step, Count - HalfCount>::type>::type;
};
//拆分為1個元素特化版本
template<std::size_t Base, std::size_t Step>
class make_arithmetic_progression<Base, Step, 1>
{
public:
using type = index_list<Base>;
};
//拆分為2個元素特化版本
template<std::size_t Base, std::size_t Step>
class make_arithmetic_progression<Base, Step, 2>
{
public:
using type = index_list<Base, Base + Step>;
};
template<std::size_t Base, std::size_t Step, std::size_t Count>
using arithmetic_progression = typename make_arithmetic_progression<Base, Step, Count>::type;
這樣對于長度為 Count 的序列，模板遞歸實例化的深度變為 $log_2Count$，按照 MSVC 的默認最大深度 499 來算，也能支持到 $2^{499}$ 長度的序列，這無論如何都夠用了，更別說 GCC 和 clang 的 1024 了。
借用標準庫
上文說到可以間接使用標準庫來實現這個等差數列模板。在我們初中的時候就知道，可以用公差為 1 的等差數列生成任意的其他等差數列：
$$ \begin{aligned} a_n&=n (n=0,1,2,...)\\\\ b_n&=a_n*d+k (n=0,1,2,...)//d為公差，k為首項 \end{aligned} $$ 結合 C++17 的折疊表達式，我們可以構建這樣的模板：
代碼
//輔助推導函數
template<std::size_t Base, std::size_t Step, std::size_t... Seq>
std::index_sequence<(Base + Step * Seq)...> arithmetic_progression_helper(std::index_sequence<Seq...>);
template<std::size_t Base, std::size_t Step, std::size_t Count>
using arithmetic_progression = decltype(arithmetic_progression_helper<Base, Step>(std::make_index_sequence<Count>{}));
這個模板只是在 STL 的 index_sequence 上做了一次包裝，更加簡潔。
優劣
在我對上述兩種實現進行測試時，發現在實例化超長的數列時，使用 STL 的版本無論在速度上還是內存消耗上都顯著優于自定義版本。
比如在我的電腦上使用 clang 編譯，實例化一個長度為 100000 的數列。STL 版本的實現編譯耗時 1 秒左右，內存僅占用數十 MB；而自定義版本的編譯卻需要 10 秒左右，內存占用超過 1.2GB。
為什么相差如此懸殊？我于是很好奇 STL 是如何實現 make_index_sequence 的，找到源碼后跟進去一瞧，它其實是 __make_integer_seq<std::size_t, N>。大家都知道，前導兩個下劃線的 STL 模板是內部實現版本，它們要么由編譯器支持沒有源碼，要么有源碼但不建議直接使用，這個 __make_integer_seq 屬于前者。這些由編譯器支持的模板大部分屬于用戶端不可能實現或者實現極為復雜，而在編譯器端實現會相對簡單并且高效的。
這提醒我們，對于標準庫能夠直接或間接支持的模塊，應該優先選擇使用標準庫來實現，它們會幫我們最大化地利用資源。不過在學習過程中，編寫自己的版本也是很有價值的，能夠讓我們深入細節，接觸優秀的編碼思想和優化策略。
總結
使用分治來降低模板遞歸實例化深度這一策略，是我以前從沒考慮過的，雖然它在本次編碼中被最終舍棄，但是日后說不定有用武之地。本篇學習記錄梳理了我在逐步實現和改進等差數列模板的思路，總結如下：
1. 學習過程中不斷造輪子加驗證是獲取和掌握知識的有效途徑；
2. 在實際項目中，盡量使用經過大眾檢驗的庫有助于項目的穩定高效。
對于第二條，如果為了一個模塊而引入一整個大型庫的依賴，仍須仔細斟酌。這與本篇筆記的內容無關，但在實際工作中，如果每個人都為了實現一個簡單模塊而肆無忌憚的引入三方依賴，造成團隊項目倉庫中一大半是三方庫內容的情況還是很讓人不舒服的。
浙公網安備 33010602011771號