ｃonstexpr関数はコンパイル時処理。これはいい。実行時が霞んで見える。cpuの嬌声が聞こえてきそうだ

constexpr 関数は
コンパイル時処理。
これはいい。実⾏時
が霞んで⾒える。
CPUの嬌声が聞こえ
てきそうだ
ドワンゴC++勉強会 #1
bolero_MURAKAMI
2014/6/28
――『C++らしいライブラリ設計』
の指針としての constexpr――

◆自己紹介
中３⼥⼦です。

◆自己紹介
• 名前 : 村上原野 (むらかみげんや)
@bolero_MURAKAMI, id:boleros
• 棲息地: 大都会岡山
• 仕事 : 猪風来美術館陶芸指導員
・普段はろくろをまわしたり、
縄文土器をつくったりしています
・趣味は constexpr です

◆自己紹介
• 公開しているライブラリ:
Sprout C++ Library (constexpr ライブラリ)
github.com/bolero-MURAKAMI/Sprout
• 過去の発表資料:
Boost.勉強会 #7
【中３⼥⼦でもわかる constexpr】
Boost.勉強会 #8
【中３⼥⼦が狂える本当に気持ちのいい constexpr】
Boost.勉強会 #12
【constexpr 中３⼥⼦テクニック】
江添とボレロ村上の京都C++勉強会
【すごい constexpr たのしくレイトレ！】
www.slideshare.net/GenyaMurakami

◆導入
はよう constexpr
まみれになろうぜ

◆導入
• constexpr とは
– 市⺠の義務
– constexpr を知らないで許されるのは小学生
まで
– C++14 は constexpr の時代
– コンパイル時処理だけじゃない constexpr

◆アジェンダ
• 目標
– constexpr による実装を指針としてモダンな
C++ライブラリ設計について学ぼう！

◆アジェンダ
• 目標
– constexpr による実装を指針としてモダンな
C++ライブラリ設計について学ぼう！
実際こわくない

◆アジェンダ
• constexpr の設計と進化
――C++11 から C++14へ
• 『C++らしさ』と constexpr のカンケイ
――ライブラリ設計ガイド
• 大規模ライブラリの設計
――Sprout の設計を⾒てみよう
• 標準ライブラリにおける constexpr

◆constexpr の設計と進化
• constexpr の超基本
• C++11 constexpr 導入の歴史的経緯
• C++14 constexpr の制限緩和

constexpr の超基本

◆constexpr の超基本
• constexpr とは
– C++11 から新しく導入されたキーワード
– 「定数式」を記述するための指定⼦
– C++14 で大幅な制限緩和がなされた

• constexpr 指定の変数
＝コンパイル時定数
// コンパイル時定数
constexpr unsigned N = 10;
// コンパイル時定数は配列のサイズやテンプレート引数として使用可能
std::array<int, N> arr = {{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }};

• constexpr 指定の関数
＝コンパイル時に呼出可能
• このような、コンパイル時に評価可能な
式を「定数式」という
// constexpr 関数
template<typename T>
constexpr T square(T const& t) {
return t * t;
}
// コンパイル時定数を求めることができる
constexpr int s = square(16);
static_assert(s == 256, “”);

［リテラル型］＝ constexpr で扱えるデータ型
［スカラー型］［リテラル型の配列］
LiteralType [N]
［参照型］
T&
［算術型］
［整数型］ int, unsigned int, char, ...
［浮動小数点型］ float, double, ...
［ポインタ型］
［ポインタ］ int const*, int (*)(void), ...
［メンバポインタ］ int T::*, int (T::*)(void), ...
［列挙型］ enum
特定の条件を満たす
ユーザー定義クラス
void (C++14 以降)

• constexpr の基本について詳細は日経ソ
フトウエア2014年5月号の記事によく纏
まっている。読むべし

C++11 constexpr 導入の歴史的経緯

◆C++11 constexpr 導入の歴史的経緯
• constexpr 導入の動機 1
– 定数を返す関数をコンパイル時評価可能にす
るため
// レガシーなマクロ定数
static_assert(2147483647L <= INT_MAX, “”);
// constexpr が無ければこれはできない
static_assert(2147483647L <= std::numeric_limits<int>::max(), “”);

• constexpr 導入の動機 2
– テンプレートメタプログラミングでやってい
たコンパイル時計算を自然な関数で書けるよ
うにするため
// TMP で (16^2)^2
typedef Square<Square<int_<16> >::type>::type Result;
static_assert(Result::value == 65536, “”);
// constexpr で (16^2)^2
constexpr auto result = square(square(16));
static_assert(result == 65536, “”);

• C++11 constexpr 関数のつらい点
– ローカル変数宣言ができない
– あらゆる副作用が許されない
• （もちろん変数書き換えもダメ）
– ループ文や if, switch 等の構文が使えない
• （関数の再帰はできる）
– 処理を実質 return 文ひとつで記述しなけれ
ばならない

• 最初は関数の再帰さえ許可されない予定
だった
– 再帰ダメだよ派
• コンパイラの実装が面倒になる
• 絶対濫用するヤツが出てくる
– 再帰いいでしょ派
• たいした処理が書けなくなる
• TMP によるコンパイル時計算の代替にならない

• 関数の再帰が許可された結果
コンパイル時レイトレーシング

• 関数の再帰が許可された結果
– ほか、標準アルゴリズムや疑似乱数、パーサ
コンピネータや波形処理など、たいていの処
理は（頑張れば）書けるようになった

C++14 constexpr の制限緩和

◆C++14 constexpr の制限緩和
• C++14 constexpr の制限緩和
– ローカル変数宣言の許可
– 変数書き換えの許可
– ループ文や if, switch 等の構文の許可
– 文をいくらでも記述できるようになった

邪神改変

• find アルゴリズム実装例(非constexpr)
template<typename Iter, typename T>
Iter find(Iter first, Iter last, T const& value) {
while (first != last) {
if (*first == value) return first;
++first;
}
return last;
}

• find アルゴリズム実装例(C++11 constexpr)
constexpr Iter find_impl(
Iter first, Iter last, T const& value,
typename iterator_traits<Iter>::difference_type pivot, Iter found)
{
return found != first ? found
: pivot == 0 ? (*first == value ? first : last)
: find_impl(
next(first, pivot), last, value,
(distance(first, last) - pivot) / 2,
find_impl(
first, next(first, pivot), value,
pivot / 2, first)
);
constexpr Iter find(Iter first, Iter last, T const& value) {
return first == last ? last
: find_impl(first, last, value, distance(first, last) / 2, first);
}

constexpr Iter find_impl(
Iter first, Iter last, T const& value,
typename iterator_traits<Iter>::difference_type pivot, Iter found)
{
return found != first ? found
: pivot == 0 ? (*first == value ? first : last)
: find_impl(
next(first, pivot), last, value,
(distance(first, last) - pivot) / 2,
find_impl(
first, next(first, pivot), value,
pivot / 2, first)
);
return first == last ? last
: find_impl(first, last, value, distance(first, last) / 2, first);
}
再帰深度オーダーを抑える工
夫が必要
ループも if もインクリメント
も書けない
実装用関数を分けたり
色々とつらい

◆再帰深度のオーダー
• 再帰深度のオーダー(線形再帰の場合)
+
+
+
+
+
+
+
a0 a1 a3 a4 a5 a6 a7a2各項
1
2
6
5
4
3
7再帰深度
オーダー：
比較回数 = Ο(N)
再帰深度 = Ο(N)

a3 a4 a5 a6 a7a2
◆再帰深度のオーダー
• 再帰深度のオーダー(二分再帰の場合)
a0 a1各項
1 1 1 1
2 2
3再帰深度
オーダー：
比較回数 = Ο(N)
再帰深度 = Ο(logN)
+ + + +
+ +
+

++first;
}
return last;
}

++first;
}
return last;
}
宣言に constexpr 指定を追加
しただけ
実際明快でわかりやすい

• merge アルゴリズム実装例(非constexpr)
template<typename Iter1, typename Iter2, typename OutIter>
OutIter
merge(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, OutIter result) {
for (; ; ) {
if (first1 == last1) {
return copy(first2, last2, result);
}
}
*result++ = *first2 < *first1
? *first2++ : *first1++;
}
}

• merge アルゴリズム実装例(C++11
constexpr)
– (同じシグネチャでは不可能)

• merge アルゴリズム実装例(C++14
constexpr)
template<typename Iter1, typename Iter2, typename OutIter>
constexpr OutIter
merge(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, OutIter result) {
for (; ; ) {
}
}
*result++ = *first2 < *first1
? *first2++ : *first1++;
}
}

• C++14 constexpr であっても許可され
ない制限(例)
– I/O
– 動的メモリ（new/delete）
– 例外処理（try-catch）
– RAII（デストラクタを使った後処理）
– ラムダ式
– グローバル変数の参照

• 抽象マシンモデルの採用
• C++11 constexpr 関数の評価は、関数呼び出
しの置換(function invocation substitution)と
いう規則で定義されていた
– 関数の評価を、呼び出し先の関数の式の評価と置換
することで、関数呼び出しをエミュレートする
– 式変形の最適化に近い
• C++14 constexpr では、定数式の評価はC++
抽象マシンのサブセットとして再定義される

◆処理系の constexpr 対応状況
• C++11 constexpr 対応
– GCC 4.7.0 以降
– Clang 3.2 以降
• C++14 constexpr 対応
– Clang 3.3 以降

• GCC
– C++11 constexpr にはよく対応している
– C++14 constexpr 対応はまだ
– 数学関数など有用な組み込み関数あり
– メモ化のおかげで⾼速だがメモリ⾺⿅⾷い

• Clang
– C++11 constexpr に対応
– 唯一 C++14 constexpr 対応が進んでいる
– constexpr 関係の大きなバグが残っている
• 相互再帰する constexpr 関数がコンパイルエラー

• ICC (Intel C++ Compiler)
– ICC 11 で C++11 constexpr を使える
• が、バグが多くて constexpr 実用はまだ難しい
• 今後に期待する

• VC++ (Microsoft Visual C++)
– November 2013 CTPで C++11 constexpr
を使える
• と発表されたが、constexpr メンバ関数に未対応
なので複雑な処理はまったく書けない
• 今後に期待できるのだろうか？

◆『C++らしさ』と constexpr のカンケイ
C++ らしいライブラリ設計とは？

◆C++ らしいライブラリ設計とは
C++ のライブラリといえば Boost

• Boost ライブラリの特徴（独断）
– とにかくテンプレート
• 静的ダックタイピング
• 機能の非メンバ関数化
• 疎結合な機能群
– 機能分割がしっかりしている
– 『C++ らしい』と思う
• STLから以降の標準ライブラリの流れでもある

• Q. どうすれば『C++ らしい』ライブラ
リ設計ができるか？
• A. なるべく constexpr 関数になるよう実
装してみよう
– （ほんとか？）

constexpr 関数の制限を満たすよう
心掛ければ『C++ らしい』設計を
せざるをえなくなる。

◆ライブラリを constexpr 化しよう
• ポリモーフィズムの例(仮想関数版)
– 関数 foo を constexpr 化するには？
struct Base {
virtual int f() const = 0;
};
int foo(Base const& t) {
return t.f();
}

• ポリモーフィズムの例(テンプレート版)
– 動的ポリモーフィズムから静的ポリモーフィズムへ
constexpr auto foo(T const& t)
-> decltype(t.f()) {
return t.f();
}
constexpr で仮想関数は使え
ないのでテンプレートにする

• コンテナ操作の例(コンテナ決め打ち版)
– 関数 remove_erase を constexpr 化するには？
void remove_erase(vector<T>& c, T const& val) {
c.erase(remove(begin(c), end(c), val), end(c));
}
vector<int> c = { 1, 1, 2, 2, 3, 3 };
remove_erase(c, 1);

• コンテナ操作の例(テンプレート版)
– 型の決め打ちを排除する
template<typename Container, typename T>
constexpr void remove_erase(Container& c, T const& val) {
c.erase(remove(begin(c), end(c), val), end(c));
}
deque<int> c = { 1, 1, 2, 2, 3, 3 };
remove_erase(c, 1);
std::vector は非リテラル型な
のでテンプレートにする
vector 以外の
コンテナでも使える

• コンテナ操作の例(Rangeアダプタ版)
–Rangeアダプタ版ならば C++11
constexpr でも使える
deque<int> c = { 1, 1, 2, 2, 3, 3 };
auto c2 = c | sprout::adaptors::removed(1);
Rangeアダプタは
元のコンテナを変更しない
「処理後の範囲」が欲しいだけ
ならこれでOK

◆型制約について
• Rangeアダプタとは？
– Range はイテレータの組
• begin(Rng) と end(Rng) で始端と終端を取得
＝型制約
– Rng | Adaptor が Range を返すものが
Rangeアダプタ
• Rng | reversed
• Rng | sorted など

• Range アダプタは通常副作用を持たない
– Rng | reversed
-> [
reverse_iterator( end(Rng) ),
reverse_iterator( begin(Rng) )
)

• Range アダプタは通常副作用を持たない
– Rng | reversed
-> [
reverse_iterator( end(Rng) ),
reverse_iterator( begin(Rng) )
)
元の要素を書き換えるのではなく、
イテレータアダプタの範囲を生成する

• ジェネリックプログラミングでは型
制約が大事
• できるだけ最小の制約を考える
–RandomAccessIterator よりも
ForwardIterator や InputIterator を
–コンテナよりも Range を

• 型制約の例
– イテレータ
– Range
– Rangeアダプタ
– タプル
– ビジター
– 関数オプジェクト

◆非メンバ関数のススメ
• 機能はメンバ関数よりも非メンバ関数と
して追い出したほうがよい
– Rng.size() よりも size(Rng)

◆非メンバ関数のススメ
• 機能はメンバ関数よりも非メンバ関数と
して追い出したほうがよい
– Rng.size() よりも size(Rng)
– より小さな型制約で済む
– クラスの肥大化を避けられる
– より疎結合な設計になる
template<typename Range>
constexpr auto size(Range const& rng)
-> decltype(distance(begin(rng), end(rng))) {
return distance(begin(rng), end(rng));
}
非メンバ関数の size(Rng) は
begin と end だけ
あれば実装できる

◆疎結合とは
• 疎結合な設計
– 機能同⼠の結合度が低い（互いに依存しない）
– 継承関係などが結合にあたる
• constexpr 実装にすると抽象クラスの継承関係などを排除
しなければならない → 疎結合化

◆Sprout ライブラリ
• とくに大規模なライブラリ
– Sprout.Darkroom
• レイトレーシング
– Sprout.Weed
• パーサコンビネータ
– Sprout.Compost
• 波形処理

◆Sprout.Darkroom
• コンパイル時レイトレーシング

◆Sprout.Darkroom の機能階層
データアクセスインタフェース
(access)
基本データ定義／演算の提供
(coord:座標, colors:色)
組合せデータ定義／演算の提供
(rays:光線, materials:材質, intersects:衝突情報)
各種配置オブジェクトの提供
(objects:物体, lights:光源, cameras:カメラ)
トップレベル演算の提供
(renderers:レンダラ, pixels:出力画像)
低
←
レ
ベ
ル
→
高

データアクセスインタフェース
(access)
基本データ定義／演算の提供
(coord:座標, colors:色)
組合せデータ定義／演算の提供
(rays:光線, materials:材質, intersects:衝突情報)
各種配置オブジェクトの提供
(objects:物体, lights:光源, cameras:カメラ)
トップレベル演算の提供
(renderers:レンダラ, pixels:出力画像)
低
←
レ
ベ
ル
→
高
基本データ型は
すべてタプル
配置物はほとんど
関数オブジェクト

• 大概のデータはタプルの組合せで表
現できる
– ベクトル { x, y, z }
– 色 { R, G, B }
– 光線 { 始点ベクトル, 方向ベクトル }
– 材質 { 色, 反射率, 透過率, ... }
– 衝突情報 { 距離, 位置ベクトル, 法線
ベクトル, ... }

• 大概の配置物は関数オブジェクトまたは
そのタプルで表現できる
– マテリアル Mat(u, v) -> Color
• UV座標に対して値を返すもの
– オブジェクト Obj(Ray) -> Intersection
• 光線と衝突判定できるもの
– 光源 Light(Inter, Obj) -> Color
• 衝突情報から色を取得できるもの
– カメラ Cam(x, y, w, h) -> Ray
• 画角から光線を求められるもの

◆光源の定義
• 例： point_light 光源のインタフェース
template<typename Position, typename Color>
class basic_point_light {
public:
constexpr basic_point_light(position_type const& pos, color_type const&
col);
template<typename Intersection, typename Objects>
constexpr color_type
operator() (Intersection const& inter, Objects const& objs) const;
};

◆光源の定義
• 例： point_light 光源のインタフェース
template<typename Position, typename Color>
class basic_point_light {
public:
constexpr basic_point_light(position_type const& pos, color_type const&
col);
template<typename Intersection, typename Objects>
constexpr color_type
operator() (Intersection const& inter, Objects const& objs) const;
};
operator() メンバ関数
第 2 引数のオブジェクトは
遮蔽判定のために使われる
位置、輝度
の情報を保持する

◆Sprout.Darkroom の設計
• ほとんどの部品がタプルと関数オブジェ
クトとしてコンセプト化されている
– ジェネリックかつ疎結合
– 細かく単純な処理に切り分けられているから
constexpr 関数として実装できている

◆Sprout.Darkroom
• コンパイル時間？
例：
8196×8196px
→約160時間（7日）

◆Sprout.Weed
• コンパイル時パーサコンビネータ
constexpr auto unbracket_uuid_p
= repeat[lim<16>(hex8f)]
| repeat[lim<4>(hex8f)]
>> '-' >> repeat[lim<2>(hex8f)] >> '-' >> repeat[lim<2>(hex8f)]
>> '-' >> repeat[lim<2>(hex8f)] >> '-' >> repeat[lim<6>(hex8f)];
constexpr auto uuid_p
= (unbracket_uuid_p | '{' >> unbracket_uuid_p >> '}') >> eoi;
constexpr auto parsed = parse_range(
to_string( "{550E8400-E29B-41D4-A716-446655440000}“ ),
uuid_p
);

◆Sprout.Weed
• コンパイル時パーサコンビネータ
constexpr auto unbracket_uuid_p
= repeat[lim<16>(hex8f)]
| repeat[lim<4>(hex8f)]
>> '-' >> repeat[lim<2>(hex8f)] >> '-' >> repeat[lim<2>(hex8f)]
>> '-' >> repeat[lim<2>(hex8f)] >> '-' >> repeat[lim<6>(hex8f)];
constexpr auto uuid_p
= (unbracket_uuid_p | '{' >> unbracket_uuid_p >> '}') >> eoi;
constexpr auto parsed = parse_range(
to_string( "{550E8400-E29B-41D4-A716-446655440000}“ ),
uuid_p
);
Expression Template

◆ Sprout.Weed
• 典型的なExpression Template (ET)
–大体 Boost.Spirit (v2) に倣っている
•ET のスケルトンは相当カジュアルに書き
直している
–ET は一時変数の使用を抑制するために
発明された
• C++11 constexpr と相性バツグン

◆ Sprout.Weed
• 典型的なExpression Template (ET)
–ET の詳細について解説は省く
•余白が狭すぎる

◆Sprout.Compost
• コンパイル時波形処理
– twinkle.wav
– vowel.wav

◆Sprout.Compost の機能階層
基本波形生成
(waves)
基本的なRangeアダプタ
(ranges)
シンセサイザーエフェクト
(effects)
チャンネル／複素数の分離合成
(formats)
フーリエ変換・スペクトル
(analyses)
Range以外のユーティリティ
(utility)

基本波形生成
(waves)
基本的なRangeアダプタ
(ranges)
シンセサイザーエフェクト
(effects)
チャンネル／複素数の分離合成
(formats)
フーリエ変換・スペクトル
(analyses)
Range以外のユーティリティ
(utility)
Range
Rangeアダプタ

• ほぼ全部 Range と Range アダプタ
で表現している

• 基本波形
– blanked （空白）
– sinusoidal （正弦波）
– sawtooth_wave （ノコギリ波）
– square_wave （矩形波）
– triangle_wave （三角波）
– white_noise （ホワイトノイズ）

• sinusoidal （正弦波）

• sinusoidal （正弦波）
–sinusoidal(freq, amp, phase)
-> sinusoid_range を返す
– sinusoid_iterator の組
– インデックス i に対して
• amp * sin(2 * pi * freq * i + phase)

• シンセサイザーエフェクト
– reverbed （リバーブ）
– distorted （ディストーション）
– overdriven （オーバードライヴ）
– tremolo （トレモロ）
– vibrato （ビブラート）
– chorus （コーラス）
– superposed （重ね合わせ） etc...

• distorted （ディストーション）
–distortion.wav

–Rng | disorted(gain, level)
-> Rng
| changed_volume(gain)
| clipped()
| changed_volume(level)

–Rng | disorted(gain, level)
-> Rng
| changed_volume(gain)
| clipped()
| changed_volume(level)
振幅を上げる
100%を越えた部分
をクリップする
レベル調節

◆ Sprout.Compost の機能階層
複雑な処理の Range アダプタ
であっても、いくつかの
アダプタの組合せで表現できる

• Range アダプタのデメリット
–エフェクトをふたつ重ねてみる
decltype(begin( sinusoidal(1.) | distorted(2., .5) | reverbed(1., 1.) ))

–生成されるイテレータの型
sprout::transform_iterator<sprout::compost::reverb_outdirected_value<doubl
e, int>,
sprout::counting_iterator<sprout::indexed_iterator<sprout::transform_iterator
<sprout::binder2nd<sprout::multiplies<void>, double>,
sprout::clamp_iterator<sprout::transform_iterator<sprout::binder2nd<sprout::
multiplies<void>, double>, sprout::sinusoid_iterator<double>, void>,
sprout::less<double> >, void> > >, void>

–生成されるイテレータの型
sprout::transform_iterator<sprout::compost::reverb_outdirected_value<doubl
e, int>,
sprout::counting_iterator<sprout::indexed_iterator<sprout::transform_iterator
<sprout::binder2nd<sprout::multiplies<void>, double>,
sprout::clamp_iterator<sprout::transform_iterator<sprout::binder2nd<sprout::
multiplies<void>, double>, sprout::sinusoid_iterator<double>, void>,
sprout::less<double> >, void> > >, void>
とても明快でわかりやすい

◆ Sprout.Compost の機能階層
あまり Range アダプタ
を重ねると型が複雑になりすぎたり
コンパイル時間が爆発する

◆標準ライブラリの constexpr 対応状況
C++14 に向けて
constexpr 対応を進めるべく
多くの提案が消化されている
ワーキングドラフト(N3936)
を確認のこと

• C++14 標準ライブラリでの
constexpr 対応
– C++11 constexpr の制限を満たす関
数はほとんど constexpr 指定された
•イテレータ周りを除く

• std::array::operator[] の例
reference
operator[](size_type i) {
return elems[ i ] ;
}
constexpr const_reference
operator[](size_type i) const {
return elems[ i ] ;
}

• std::array::operator[] の例
reference
operator[](size_type i) {
return elems[ i ] ;
}
constexpr const_reference
operator[](size_type i) const {
return elems[ i ] ;
}
非const版
いまだ constexpr 指定されない
const版
新たに constexpr 指定される

◆C++1z constexpr 化の検討
• C++1z に向けて constexpr 対応で
きそうな機能を検討してみた
– gist.github.com/bolero-MURAKAMI/9283758

• C++1z に向けて constexpr 対応で
きそうな機能を検討してみた
– gist.github.com/bolero-MURAKAMI/9283758
– 約350 の constexpr 化可能な関数を
ピックアップ
–うち約200 が直ちに constexpr 指定
できる（すべきである）
•もちろん個別具体的な議論が必要

• 直ちに constexpr 指定できる例
–リテラル型のコピー/ムーブ代入演算⼦
•tuple, complex など
–小さなユーティリティ関数
•swap, rel_ops など
–getterの非const版オーバーロード
•array::front, array::at など

こういう提案を
日本の C++標準化委員会WG
から出していきたい

◆まとめ
• constexpr は C++11 での導入から
C++14 へと進化を続けている
• constexpr の制限を指針にすること
で C++ らしいジェネリックな設計
を講じることができる
• C++1z へ向けて標準ライブラリの整
備を進めるべき

ご清聴ありがとう
ございました

ｃonstexpr関数はコンパイル時処理。これはいい。実行時が霞んで見える。cpuの嬌声が聞こえてきそうだ

More Related Content

ｃonstexpr関数はコンパイル時処理。これはいい。実行時が霞んで見える。cpuの嬌声が聞こえてきそうだ