Article

2017年10月10日
今日も楽しくC++しているみなさま、こんにちは!C++勉強会を開催したり、wandboxのスポンサーになったり、もちろん業務でも使ったりと、日頃からC++に触れることの多いフィックスターズですが、今日はそんなC++の高速化(?)技法を一つ紹介したいと思います。それは記事題の通り部分特殊化された非型引数においても、部分特殊化のテンプレート引数を使った演算できるようにする方法です。

TL;DR:非型引数をラップする型を使えば良い

問題の要約は以下の通りです(wandboxでの実行結果)。

// こんなテンプレートがあった時に
template<int V1, int V2>
struct Foo;

// 部分特殊化したい場合、
template<int V>       // 部分特殊化のテンプレート引数を
struct Foo<V, V+1>{}; // 使って部分特殊化の非型引数を演算してはいけない

これを回避する方法は以下の通りです(wandboxでの実行結果)。

// 非型引数をラップする型を作って
template<int I>
struct Int{};

// 型引数をとるテンプレートにして
template<typename I1, typename I2>
struct Foo;

// 型引数にラップしてやる
template<int V>
struct Foo<Int&ltV>, Int&ltV+1>>{};

解説

なぜ問題なのか

C++のテンプレートで部分特殊化する時は、色々と制約がありますが、この問題もそんな制約のひとつです。

今回の制約の詳細は、C++規格書(C++14最終ドラフト版)の§14.5.5の(8.1)に見ることができます。

14 Template [temp]
14.5 Template declarations [temp.decls]
14.5.5 Class template partial specializations [temp.class.spec]

(8.1) — A partially specialized non-type argument expression shall not involve a template parameter of the partial specialization except when the argument expression is a simple identifier. [ Example:

template <int I, int J> struct A {};
template <int I> struct A<I+5, I*2> {}; // error

template <int I, int J> struct B {};
template <int I> struct B<I, I> {}; // OK

— end example ]

愚直に翻訳すると「部分特殊化された非型実引数式に、部分特殊化のテンプレート仮引数を含めてはいけない(単純に名前を使うだけは除く)」という制約です。

もう少し噛み砕くと、以下のような条件の時はC++規格としての制約にひっかかるということになります。

  • テンプレート引数に型以外(整数など)をとる
  • そのテンプレートを部分特殊化する
  • 部分特殊化で入力として受け取る仮引数を、部分特殊化するための実引数に使う時、演算してはいけない

上記のExampleで言うと、仮引数の部分はtemplate <int I> struct AIのことで、実引数の部分はstruct A<I+5, I*2>I+5I*2のことです。

どう解決したのか

上記の問題は「非型」であることが問題だったので、引数に型を入力すれば解決できる、ということになります。
ということで、先の解決策の再掲になりますが

// 非型引数をラップする型を作って
template<int I>
struct Int{};

// 型引数をとるテンプレートにして
template<typename I1, typename I2>
struct Foo;

// 型引数にラップしてやる
template<int V>
struct Foo<Int&ltV>, Int&ltV+1>>{};

とすれば、良いのです。こうすると、実引数は型を受け取るので、制約にはひっかからないのです!

という、C++でよくありがちな「本質的ではない(ほぼ同等のことができる回避策がある)制約」の話がまたひとつ生まれました。

そもそもなぜ必要になったのか?

この問題は、フィックスターズの得意とする高速化業務で最もよく使われる手法のひとつである「ループ展開」をしたい時に当たったものでした。

例えば、以下のような関数があった時

double Sum(const double src[], const std::size_t x, const std::size_t width)
{
	const auto half = static_cast<std::make_signed_t<std::remove_const_t<decltype(width)>>>(width/2);

	auto sum = decltype(src[0])(0);
	for(auto dx = -half; dx <= half; dx++)
	{
		sum += src[x + dx];
	}
	return sum;
}

widthがほとんど固定値なので以下のように展開したい、ということが多くあります。

double Sum3(const double src[], const std::size_t x) // width=3特化
{
	auto sum = decltype(src[0])(0);
	sum += src[x - 1];
	sum += src[x + 0];
	sum += src[x + 1];
	return sum;
}
double Sum5(const double src[], const std::size_t x) // width=5特化
{
	auto sum = decltype(src[0])(0);
	sum += src[x - 2];
	sum += src[x - 1];
	sum += src[x + 0];
	sum += src[x + 1];
	sum += src[x + 2];
	return sum;
}
double Sum7(const double src[], const std::size_t x) // width=7特化
{
	auto sum = decltype(src[0])(0);
	sum += src[x - 3];
	sum += src[x - 2];
	sum += src[x - 1];
	sum += src[x + 0];
	sum += src[x + 1];
	sum += src[x + 2];
	sum += src[x + 3];
	return sum;
}
// 以下延々と続く・・・

ご覧の通り、反復回数が増えるに従って延々と同じような行をコピペしてまごころを込めて量産していくことになります。これを回避するためによく使われる手法は、

  • 展開したコードを生成するシェルスクリプト等を作成する
  • プリプロセッサマクロを使う
  • #pragma unrollを使う

などがありますが、スクリプトを作る方法は外部で生成することになるので管理が大変になりますし、プリプロセッサは型安全ではないですし、#pragma unrollはコンパイラの拡張機能なので標準的ではありません。

と、どれも欠点があるのですが、これに対して、以下のようにテンプレートを用いる実装はこれらの問題を解決します。

namespace detail
{
	using DIFF = std::make_signed_t<std::remove_const_t<std::size_t>>;

	template<std::size_t WIDTH, DIFF DX>
	struct Sum
	{
		static auto sum(const double src[], const std::size_t x)
		{
			return src[x+DX] + Sum<WIDTH, DX+1>::sum(src, x);
		}
	};

	template<std::size_t WIDTH>
	struct Sum<WIDTH, WIDTH/2>
	{
		static auto sum(const double src[], const std::size_t x)
		{
			return src[x+WIDTH/2];
		}
	};
}

namespace
{
	template<std::size_t WIDTH>
	auto Sum(const double src[], const std::size_t x)
	{
		return detail::Sum<WIDTH, -static_cast<detail::DIFF>(WIDTH/2)>::sum(src, x);
	}
}

ただし、このコードは、実際には動きません(コンパイルエラー)。
その理由が、今回紹介した制約である「部分特殊化された非型引数における、部分特殊化のテンプレート引数を使った演算」です。
実際、17-18行目でtemplate<std::size_t WIDTH> struct Sum<WIDTH, WIDTH/2>としている部分が、該当していて、WIDTHという非型な仮引数を使ってWIDTH/2演算した結果を実引数にしようとしています。

このコード、実はなぜかclangだと通るという面白い現象があって、最初は発見できずにいたのですが、gccやVC++で動かそうとしてエラーになって発覚しました。

ということで、ちゃんとclang以外でも実行できるように、先述のようなラップする関数を使うことで解決できたのでした。

namespace detail
{
	using DIFF = std::make_signed_t<std::remove_const_t<std::size_t>>;
	
	template<std::size_t V>
	struct WRAPPER_SIZE_T
	{};
	template<DIFF V>
	struct WRAPPER_DIFF
	{};
	
	template<typename T1, typename T2>
	struct Sum;

	template<std::size_t WIDTH, DIFF DX>
	struct Sum<WRAPPER_SIZE_T<WIDTH>, WRAPPER_DIFF<DX>>
	{
		static auto sum(const double src[], const std::size_t x)
		{
			return src[x+DX] + Sum<WRAPPER_SIZE_T<WIDTH>, WRAPPER_DIFF<DX+1>>::sum(src, x);
		}
	};

	template<std::size_t WIDTH>
	struct Sum<WRAPPER_SIZE_T<WIDTH>, WRAPPER_DIFF<WIDTH/2>>
	{
		static auto sum(const double src[], const std::size_t x)
		{
			return src[x+WIDTH/2];
		}
	};
}

namespace
{
	template<std::size_t WIDTH>
	auto Sum(const double src[], const std::size_t x)
	{
		return detail::Sum<detail::WRAPPER_SIZE_T<WIDTH>, detail::WRAPPER_DIFF<-static_cast<detail::DIFF>(WIDTH/2)>>::sum(src, x);
	}
}

めでたし、めでたし。

まとめ

ということで、「部分特殊化された非型引数においても、部分特殊化のテンプレート引数を使った演算できるようにするには、非型引数をラップする型を使えば良い」という技法の紹介でした。

この手法は特に高速化以外でもよく現れるところですが、今回のように安全かつ標準的な手法を使ってループ展開したい時にも使うことができます。毎朝まごころ込めて職人がループ展開しているのをどうにかしたい方、ぜひ試してみてください。

謝辞

なお、この問題の発見・解決には、インターン今泉良紀さんの成果が含まれています。彼の今後のC++界での活躍を期待すると共に、ここに謝辞を記しておきたいと思います。

Tags

About Author

YOSHIFUJI Naoki

yoshifujiです。計算力学的なプログラムを高速化することが得意です。プログラミング自体はチョットダケワカリマス。 Twitter: https://twitter.com/LWisteria

Leave a Comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

Recent Comments

Social Media