[C++] Loop Unrolling Using Metaprogramming

Loop unrolling (迴圈展開) 是 compiler 在編譯過程中基本常用的優化方式。然而， compiler 到底會不會採用 loop unrolling 其實完全由 compiler 決定，換言之，你可以預期 compiler 會做，但事實上 compiler 不一定會做，因此這邊介紹利用 metapromming 的方式，強迫使用 loop unrolling 的技巧。

Loop unrolling 是把編譯期就已知迴圈次數的迴圈展開，變成許多重複的程式碼，藉此去除迴圈的 overhead：判斷迴圈是否達到終止條件。舉例來說

int dot_product (const int dim, const int* a, const int* b)
{
	int result = 0;
	for (int i=0; i<dim; ++i) {
		result += a[i] * b[i];
	}
	return result;
}

假設我們可以在編譯期就確定 dim 的值是 3，那麼 dot_product 的 loop 經過 unrolling 會變成

int dot_product (const int* a, const int* b)
{
	return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
}

雖然 loop unrolling 的好處顯而易見，然而你無法控制 compiler 要不要採用 loop unrolling，因此這篇要介紹的是利用 metaprogramming 來強迫使用 loop unrolling。

關於 metaprogramming 的介紹可以參考這篇 wiki，他的範例是 factorial。metaprogramming 在 C++ 中因為是利用 template 來實現的，因此最大的優點在於所有的計算均在編譯期完成。已該文章的 factorial 為例，factorial<4>::value 是可以在編譯期就得知其數值是 24。因此 metaprogramming 的優點很明顯：把運算移到 compile time，因此有機會可以做更多的最佳化 (因為都會是已知)、可以減少程式的執行時間 (因為移到編譯期了)；缺點也很明顯：編譯時間會增加、能派上用場的地方會比較受限。

回到主題，假設今天想強制上面的那個 loop 做 unrolling，但又不想人工完成的話，可以這樣做：

// general template for loop unrolling
template <int N>
int dot_product (const int* a, const int* b)
{
	return ((*a) * (*b)) + dot_product<N-1> (a + 1, b + 1);
}

// template specialization
template <>
int dot_product<1> (const int* a, const int* b)
{
	return (*a) * (*b);
}

// usage
dot_product<3>(a, b);

這個做法既可達到 loop unrolling 的效果，又可免去人工 unroll 的麻煩與維護的困擾。

值得注意的是，他確實做了 unrolling，但是 unroll 後的結果是遞迴的函式呼叫，雖然這樣的遞迴呼叫基本上也是可已經過優化後轉變成最純粹的運算 (g++ 4.8 的話用 -O1 就可以了，而 g++ 4.8 的 loop unrolling 要在 -O2 才會做)，因此是好是壞很難說，端看使用的時機與場合。