constexpr を使うべき5の理由 - その5

「constexpr を使うべき5の理由」ひとまず最終回です。
コンパイル時に計算ができると聞いて、誰もがまず思い浮かべる用途は、おそらく、実行時に必要となる値をあらかじめ計算しておくというものでしょう。

5.必要なものをなるべく早く用意しておくために

何度も繰り返し同じような計算を行い、しかも実行速度が要求されるような場合（例えばゲームなど）では、最適化のために
自明な計算をあらかじめ行っておいて結果をテーブルに保持しておくことがしばしばあると思います。

非常にシンプルな例として、度数法で [0 .. 90) の範囲の正弦値を保持するテーブルを考えてみます。

#include <cmath>

double degree_sin_table[90];
void init_table() {
    const double pi = 3.141592653589793238462643383279502884197;
    for (int i = 0; i < 90; ++i) {
        degree_sin_table[i] = std::sin(i * pi / 180);
    }
}

int main() {
    init_table();
    // ...
}

これは見てのとおり C言語的なやり方で実装したコードである。
init_table を実行時に一度だけ呼び出しておく必要があり、非常に煩わしい。

#include <cmath>
#include <array>

std::array<double, 90> calc_table() {
    const double pi = 3.141592653589793238462643383279502884197;
    std::array<double, 90> result;
    for (int i = 0; i < 90; ++i) {
        result[i] = std::sin(i * pi / 180);
    }
    return result;
}
const std::array<double, 90> degree_sin_table = calc_table();

C++ 的に考えれば、degree_sin_table を定数にして、ユーザコードで初期化を呼び出す必要を無くすことはできる。
あるいは degree_sin_table をシングルトンにする実装なども考えられる。

では、この degree_sin_table が初期化されるのはいったいいつの時点だろうか。
通常のグローバル変数（定数）であれば、アプリケーションの起動時である。
シングルトンであれば、最初に値を要求した時点で計算が行われる実装もありうる。

いずれにせよ実際に計算されるのは実行時である。
もちろんこの程度の計算なら速度が問題になることもないだろうが、場合によってはもっと多くの計算を必要とするものもあるだろう。
グローバル変数の場合、初期化順序が問題になるケースもあるかもしれない。

もし『constexpr を使うべき5の理由』を読んできたあなたならば、きっとこう思ったに違いない。

お兄ちゃん、それ実行する前に計算できるよね。なんでランタイムでやってるの？

2012-06-13 18:28:36 via twittbot.net

よろしい、ならば constexpr だ。

#include <sprout/array.hpp>
#include <sprout/range/adaptor.hpp>

constexpr sprout::array<double, 90> degree_sin_table
    = sprout::adaptors::sinusoidal(1. / 360/*周波数*/)
    | sprout::adaptors::copied
    ;

なにやら怪しげな書き方に思えるかもしれないが、ようは constexpr Rangeアダプタでテーブルを生成している。
「Rangeアダプタってなにそれ」という方は "Pstade.Oven" や "Boost.Range" で検索されたし。

ともあれ、ライブラリ化されたものを使えば、constexpr で簡潔に処理を書くことも、様々なパラダイムを扱うこともできることがお分かりになるだろう。
当然ながら、先に挙げた非 constexpr なコードを constexpr に書き直してベタ書きで計算することもできるので、もし興味がある方は試して戴きたい。

ところで、こうしたテーブルを定義する古典的な方法として、何かツールで生成したデータを書き出した CSV ファイルをインクルードするというものがある。

constexpr double degree_sin_table[] = {
#   include "sin.csv"
};

わざわざ constexpr で計算しなくても、これでよいのではないか？

それに対しては、逆にこう質問したい。
・そのツールは、条件分岐や再帰を含む複雑な計算あるいはエラーによるブレークを、必要ならば行えるか？
・そのツールは、C++ のプリプロセッサや型推論のような他の独立した機能との連携を、必要ならば行えるか？
・そのツールは、出力した値を別の計算に再利用するために用いることが、必要ならば行えるか？

constexpr でデータを生成することの利点の一つは、必要ならば C++ の（少なくともプリプロセスとコンパイル時の）すべての機能が使えることだ。
それは、例えば C++ でパーサを作成するとき yacc+lex よりも Boost.Spirit.Qi を使うのを好むプログラマが存在する理由と同じである。

かの大数学者は言った。「微分のことは微分でせよ」、と。
だからあなたも胸をはってこう言うべきである。

「C++ のことは C++ でせよ」

そしてコンパイル時にできることはコンパイル時にしておきましょう。

constexpr を使うべき5の理由 - その4

「constexpr を使うべき5の理由」ようやく4つめです。
今回は、いわゆるメタプログラミングにおける constexpr について取り上げます。

4.あのうんざりするテンプレートメタプログラミングによる数値計算からはもはや解放された

以下のコードは、[1 .. 5] のリストの各要素を加算するアキュムレートを、古式ゆかしい TMP で書いたものである。

#include <type_traits>
#include <boost/mpl/apply.hpp>
#include <boost/mpl/next.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/vector_c.hpp>
#include <boost/mpl/begin_end.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/lambda.hpp>

template<typename First, typename Last, typename Init, typename BinaryOp, typename = void>
struct meta_accumulate_impl {
public:
    typedef typename meta_accumulate_impl<
        typename boost::mpl::next<First>::type,
        Last,
        typename boost::mpl::apply<BinaryOp, Init, typename boost::mpl::deref<First>::type>::type,
        BinaryOp
     >::type type;
};
template<typename First, typename Last, typename Init, typename BinaryOp>
struct meta_accumulate_impl<
    First, Last, Init, BinaryOp,
    typename std::enable_if<std::is_same<First, Last>::value>::type
> {
public:
    typedef Init type;
};

template<typename First, typename Last, typename Init, typename BinaryOp>
struct meta_accumulate
    : public meta_accumulate_impl<First, Last, Init, BinaryOp>
{};

typedef boost::mpl::vector_c<int, 1, 2, 3, 4, 5> src;
typedef typename meta_accumulate<
    typename boost::mpl::begin<src>::type, typename boost::mpl::end<src>::type,
    boost::mpl::int_<0>, boost::mpl::plus<boost::mpl::_1, boost::mpl::_2>
>::type accumulated;

static_assert(accumulated::value == 15, "");

テンプレートメタプログラミングに慣れたあなたであれば、この程度のコードを読むのはけして苦ではないだろう。
しかしながら、単に数値計算として見た場合、上記のコードはロジックを素直に表現していると言えるだろうか？
そして何より記述量の多さにうんざりせざるをえない。

では、同じ目的のコードを constexpr で書いてみる。

#include <sprout/functional.hpp>

template<typename InputIterator, typename T, typename BinaryOperation>
inline constexpr T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op) {
    return first == last ? init
        : accumulate(first + 1, last, binary_op(init, *first), binary_op)
        ;
}

constexpr int src[] = {1, 2, 3, 4, 5};
constexpr int accumulated = accumulate(
    src, src + 5,
    0, sprout::plus<int>()
    );

static_assert(accumulated == 15, "");

どうだろうか。
非メタプログラマでも普段見慣れているコードとあまり変わらないのではないかと思う。
これは、条件分岐に if でなく条件演算子を、ループの代わりに再帰を用いている点を除けば、std::accumulate の典型的な実装のロジックと同様である。

数値計算のためのコードとしては、TMP と constexpr では後者のほうが読みやすく書きやすいのが見てとれるだろう。
さらに、constexpr であれば浮動小数点型やユーザ定義型（リテラル型）も扱うことが可能だ。

constexpr double src[] = {0.1, 0.2, 0.3, 0.4, 0.5};
constexpr double accumulated = accumulate(
    src, src + 5,
    0, sprout::plus<double>()
    );

static_assert(accumulated == 1.5, "");

(>> id:xxxxxeeeee)さん ×plus ○plus typoでした。指摘ありがとうございます。

これは TMP では書けないコードである。

そして、この constexpr accumulate は、コンパイル時でも実行時でも同じように呼び出すことができる。
だから、同じ目的の計算のためのコードを、実行時のための関数とコンパイル時のためのクラステンプレートとで二重に実装する必要はもはやない。
ただ一つの constexpr 関数で事足りるのだから。

例えば Boost.Math では公約数/公倍数を求めるものとして、ランタイム用の関数とコンパイルタイム用のクラステンプレートの二つを用意している。

boost::math::gcd/lcm (関数)
boost::math::static_gcd/static_lcm (クラステンプレート)

Sprout.Math では、たった一つの constexpr 関数を用意している。

sprout::math::gcd sprout::math::lcm

sprout::math::gcd/lcm のように constexpr である程度複雑な処理を行うコードは、もし初見ならば少しばかり奇妙なコードに思えるかもしれない。
しかしこれはライブラリ化されたものであるから、実装を知らなくても、ユーザコードに使用するぶんには問題ない。

#include <sprout/math/common_factor.hpp>

constexpr int result = sprout::math::gcd(12707, 12319);
static_assert(result == 97, "");

通常の関数と同じように呼び出せばよいだけだ。

Sprout C++ Library では、これだけでなく三角関数をはじめとする各種数学関数、疑似乱数、レイトレーシングなどを constexpr で実装しており、
実装もわりと簡単なので、constexpr のポテンシャルを表しているといえるでしょう。

もちろん、これによって TMP そのものが不要になるわけではない。
型に対する操作については TMP でしかできないのだから。

つまり、型に対するメタプログラミングは TMP、値（オブジェクト）に対するメタプログラミングは constexpr と、分担を明確にできるのが意義である。
そしてそれらはコンパイル時に処理されるもの同士相互に連携することができる。
constexpr によって C++11 におけるメタプログラミング環境はより豊かになったといえるだろう。

constexpr を使うべき5の理由 - その3

相変わらず「constexpr を使うべき5の理由」です。
今回は、関数に対する constexpr 指定のもう一つの意味について取り上げます。

3.副作用がないことを保証する

「ねむらなくてもつかれないくすり」に副作用はあるのでしょうか。疲労をポンと感じなくさせてくれるような気はしますが。
ドラえもんがもし「副作用なんてないよ」と言ったとしてもちょっと信用なりません。
物事にはちゃんとした「保証」が必要です。

関数に対する constexpr 指定は、実装に多くの制限を課すことでもある。
constexpr 関数の中では、ローカル変数の定義や、代入などの操作もできない。
基本的に、同じ引数による呼び出しに対しては同じ値を返すような実装しかできない。
そうした制限は、逆に言えばその関数の参照透明性を保証することでもある。

参照透明でない関数は、以下のようにグローバルな状態を変更する可能性がある。

int something_value(); // 常に同じ値を返すだけの関数。しかしこの宣言では参照透明とは限らない

/* ... */

int something_value() { _C_drive_format(); return 0; } // C:ドライブをフォーマットする

下手をしたらどこかに、上記のように C:ドライブをフォーマットする実装がなされているかもしれない。
もちろんそんなことはまずありえないが、constexpr 関数であれば、副作用がないことを明示的に保証することができる。

constexpr int something_value(); // 参照透明であることを保証する

/* ... */

constexpr int something_value() { return 0; } // Cドライブをフォーマットされることはない

これは例えば、noexcept による無例外保証に似ています。
noexcept 指定は、例外安全において最も強い nothrow 保証を明示的に指定する。
もし指定に反して例外を伝播させようとすれば実行時にプログラムは terminate される。

それと同様に、constexpr 指定は関数に参照透明性を保証する。
もし指定に反して状態を書き換えるようなコードが実行されるならばコンパイル時にエラーになる。

（本当は、実行時にのみ呼び出し可能なコードにおいて副作用を持たせることは実はできるのだが、コンパイル時と同じコードについては確実に参照透明である）

さて、ところで標準ライブラリを見てみよう。
C++11 における標準ライブラリの constexpr の使用は相当保守的であり、constexpr があっておかしくないところに無かったりする。
ところが、一方で驚くほど多くのケースで constexpr が書かれている部分があったりする。デフォルトコンストラクタである。
およそ定数式と縁がないような std::mutex のようなクラスのデフォルトコンストラクタも constexpr だったりする。

デフォルトコンストラクタが constexpr であるとはどういうことか。
それはデフォルトコンストラクタがトリビアルであるか、または、少なくともグローバルな状態を変更しないことを保証している。
これは目的論的にみて、そのクラスがコンパイル時に用いられることを想定するかどうかとは、本質的に無関係である。

このように constexpr 指定は、単にコンパイル時に呼び出すことができるという以上の保証を明示的に表すことができる。
だからあなたは、デフォルトコンストラクタや参照透明であることが自明な関数に対して可能な限り constexpr 指定すべきです。

constexpr を使うべき5の理由 - その1

constexpr を使うべき5の理由

「なぜあなたは constexpr を使うべきか？」

「そもそも constexpr とは何か」という基本的な部分から始めて、
どうして C++er が constexpr を使わなければならないか、日にちを分けて5つのケースを書いてみます。

constexpr を既にバリバリ使っているというあなたにはまったく物足りないかもしれませんが、
改めてのおさらいということで読んでいただくのも一興かと存じます。

1.定数を明示的にコンパイル時定数にする

以下のコードは、定数 x のメンバを配列のサイズに指定している。

struct X { int n; };
int main() {
    const X x = {10};
    int a[x.n] = {1};
}

GCC 4.8 でこのコードは、以下のような警告とエラーになる。

warning: ISO C++ forbids variable length array ‘a’ [-Wvla]
error: variable-sized object ‘a’ may not be initialized

a　が可変長配列になっているため警告が出ている。
また、可変長配列のリスト初期化はできないためエラーになっている。
x.n　はもちろん immutable な定数であるはずだが、なぜこうなるか。

C++ でいうところの「定数」は大きく二つに分けられる。
「コンパイル時定数」と「実行時定数」である。

コンパイル時定数はその名の通りコンパイル時に値が決定されると規格によって定められた定数である。
固定長配列のサイズやテンプレート引数に指定することができるのは、コンパイル時定数のみである。
C++ において、非 constexpr 変数がコンパイル時定数になるのは、const 修飾された整数型（enum を含む）のみである。

実行時定数は、コンパイル時定数以外のすべての定数である。
通常は実行時に計算され、コンパイラの最適化によってはコンパイル時に計算されることもあるが、その場合でもコンパイル時定数とはみなされない。
上記コードにおける x は実行時定数である。
だから x のメンバを固定長配列のサイズとすることはできない。

このコードをコンパイルできるようにするのは簡単だ。
const を constexpr に書き換えるだけである。

struct X { int n; };
int main() {
    constexpr X x = {10}; //　<- コンパイル時定数！
    int a[x.n] = {1};
}

const 修飾された型の変数は、型が整数型であればコンパイル時定数になるし、そうでなければ実行時定数になる。
文脈によって意味が変わってしまう。

しかし constexpr 指定すれば、それは明示的にコンパイル時定数以外の何者でもない。
もしコンパイル時定数がほしいところで非定数式が初期化に使われた場合は、定義時点でエラーにすることができる。

このため C++11 環境において定数を定義したいときは、できるかぎり const 修飾よりも（もちろんマクロよりも） constexpr 指定を使うべきです。

constexpr を使うべき5の理由 - その2

引き続き、「constexpr を使うべき5の理由」です。
ここでは、できるかぎり関数に constexpr を付けることが如何に C++er の義務であるかを示します。

2.定数を返す関数をコンパイル時定数にする

#include <limits>

constexpr auto v = std::numeric_limits<double>::max();

std::numeric_limits は、標準ライブラリで constexpr が使われた例として最も有名なものの一つでしょう。

C++03 では浮動小数点型の定数を定義することできなかったため、numeric_limits::min/max を関数として定義せざるをえず、
関数であるがゆえその値をコンパイル時定数として使うことができなかった。
C++11 では関数が constexpr 指定されたため、返値をコンパイル時定数として使うことができるようになった。

このことはよく知られている C++03 の「失敗」であり、constexpr がそれを完全に補っている。
あなたは、自明な定数値を返すような関数については、それがフリー関数であれメンバ関数であれ、constexpr 指定すべきです。

template<typename T, size_t N>
struct MyArray {
    T elem[N];
    size_t size() { return N; }
};

例えば以上のようなメンバ関数を見たら、C++er であるあなたは必ずこう言うでしょう。
「！！！const が付いてないぞ！！！」と。

template<typename T, size_t N>
struct MyArray {
    T elem[N];
    size_t size() const { return N; }
};

あなたが原理主義的な const 教徒であるかそうでないかにかかわらず、このような関数には必ず const をつけるべきです。
理由はここで述べるまでもありませんが、それが C++ プログラムとしての「正しさ」です。

template<typename T, size_t N>
struct MyArray {
    T elem[N];
    constexpr size_t size() const { return N; }
};

メンバ関数に（可能な限り） const を付けるのが正しいのと全く同じく、メンバ関数に constexpr を付けることは正しい。
コードの挙動をまったく変えることなく、それをコンパイル時に実行できるようにする。
少なくともこのようなケースにおいて、プログラムの意図が明確になり、それを必要とする者にとってより便利になり、そしてデメリットはおよそ無いからである。

なるほど、世の中にはひょっとして（考えたくもないことだが）ある関数が read-only や immutable であることの言語による強制など窮屈なだけで必要としないという罪深い人間がいるかもしれない。
ちょうど、どんな国にもアナーキストや売国奴が少なからず存在するように。

であっても、少なくとも国家はアナーキストや売国奴のために存在するものではない。
関数が read-only かつ immutable であるという安全保障を必要とする善良な市民がいることを慮って const を書くように、
それをコンパイル時に必要とする善良な市民がいることを想像すれば、constexpr を書くことが正しい義務であると理解できるはずです。

「市民、あなたは constexpr ですか」
「もちろんです、C++。constexpr であることは市民の義務です」

コンパイル時離散フーリエ変換(DFT)

コンパイル時離散フーリエ変換(DFT)

Sprout.Numeric.DFT は、constexpr DFT アルゴリズムを提供します。
https://github.com/bolero-MURAKAMI/Sprout/tree/master/sprout/numeric/dft

DFT は周波数解析などに用いられますが、ここでは詳しくは述べません。
とりあえずサンプルコードを見てください。

• • 単純な正弦波の DFT

#include <iostream>
#include <fstream>
#include <sprout/array.hpp>
#include <sprout/pit.hpp>
#include <sprout/complex.hpp>
#include <sprout/numeric/dft.hpp>
#include <sprout/range/adaptor.hpp>
#include <sprout/functional.hpp>

template<typename Elem, typename Traits, typename InputRange>
std::basic_ostream<Elem, Traits>& output_plot(std::basic_ostream<Elem, Traits>& os, InputRange const& range) {
    os << std::fixed;
    int x = 0;
    for (auto const& e : range) {
        os << x++ << ',' << e << '\n';
    }
    return os;
}
template<typename Elem, typename Traits, typename InputRange>
std::basic_ostream<Elem, Traits>& output_plot_real(std::basic_ostream<Elem, Traits>& os, InputRange const& range) {
    os << std::fixed;
    int x = 0;
    for (auto const& e : range) {
        os << x++ << ',' << real(e) << '\n';
    }
    return os;
}

int main() {
    using namespace sprout;

    constexpr std::size_t size = 256;
    typedef array<complex<double>, size> container_t;
    typedef array<double, size> spectrum_t;

    // 周波数 10 の正弦波を生成
    constexpr container_t src_data = adaptors::sinusoidal(10. / size, 10000.) | adaptors::copied;
    {
        std::ofstream os("src.txt");
        output_plot_real(os, src_data);
    }

    // DFT(離散フーリエ変換)
    constexpr auto dft_data = sprout::dft(begin(src_data), end(src_data), pit<container_t>());

    // IDFT(逆離散フーリエ変換)
    constexpr auto idft_data = sprout::idft(begin(dft_data), end(dft_data), pit<container_t>());
    {
        std::ofstream os("dft_idft.txt");
        output_plot_real(os, idft_data);
    }

    // 周波数スペクトルに変換
    constexpr auto spec_data = sprout::spectrum(begin(dft_data), end(dft_data), pit<spectrum_t>());
    {
        std::ofstream os("spec.txt");
        output_plot(os, spec_data);
    }
}

• • 出力を gnuplot でグラフ化
    • src.txt (入力ソース)

• • • dft_idft.txt ([DFT→IDFT]で変換→逆変換したもの)

• • • spec.txt (周波数スペクトル)

周波数スペクトルのピークが X 軸上の 10 のところにあるので、周波数 10 の正弦波であることがわかります。
変換→逆変換の結果が入力ソースと等しくなっているので、正しく相互変換されていることも確かめられました。

主な機能は、
　　　sprout::dft →DFT
　　　sprout::idft →IDFT(逆変換)
　　　sprout::spectrum →周波数スペクトルに変換

また、正弦波の生成のところで使っているのは、最近 Sprout に追加された Range アダプタです。
　　　adaptors::sinusoidal →正弦波を返す Range アダプタ。そのものを Range として扱うこともできる。
　　　adaptors::copied →他のコンテナへ暗黙の変換をする Range アダプタ。Pstade.Oven の copied と同じ。

もうすこし複雑な例も。

• • 重ね合わせた正弦波の DFT

#include <iostream>
#include <fstream>
#include <sprout/array.hpp>
#include <sprout/pit.hpp>
#include <sprout/complex.hpp>
#include <sprout/numeric/dft.hpp>
#include <sprout/range/adaptor.hpp>

template<typename Elem, typename Traits, typename InputRange>
std::basic_ostream<Elem, Traits>& output_plot(std::basic_ostream<Elem, Traits>& os, InputRange const& range) {
    os << std::fixed;
    int x = 0;
    for (auto const& e : range) {
        os << x++ << ',' << e << '\n';
    }
    return os;
}
template<typename Elem, typename Traits, typename InputRange>
std::basic_ostream<Elem, Traits>& output_plot_real(std::basic_ostream<Elem, Traits>& os, InputRange const& range) {
    os << std::fixed;
    int x = 0;
    for (auto const& e : range) {
        os << x++ << ',' << real(e) << '\n';
    }
    return os;
}

int main() {
    using namespace sprout;

    constexpr std::size_t size = 256;
    typedef array<complex<double>, size> container_t;
    typedef array<double, size> spectrum_t;

    // 周波数 10, 25, 35 の正弦波の重ね合わせを生成
    constexpr container_t src_data
        = adaptors::sinusoidal(10. / size, 10000.)
        | adaptors::transformed(adaptors::sinusoidal(25. / size, 5000.), plus<double>())
        | adaptors::transformed(adaptors::sinusoidal(35. / size, 7500.), plus<double>())
        | adaptors::copied
        ;
    {
        std::ofstream os("src.txt");
        output_plot_real(os, src_data);
    }

    // DFT(離散フーリエ変換)
    constexpr auto dft_data = sprout::dft(begin(src_data), end(src_data), pit<container_t>());

    // IDFT(逆離散フーリエ変換)
    constexpr auto idft_data = sprout::idft(begin(dft_data), end(dft_data), pit<container_t>());
    {
        std::ofstream os("dft_idft.txt");
        output_plot_real(os, idft_data);
    }

    // 周波数スペクトルに変換
    constexpr auto spec_data = sprout::spectrum(begin(dft_data), end(dft_data), pit<spectrum_t>());
    {
        std::ofstream os("spec.txt");
        output_plot(os, spec_data);
    }
}

• • 出力を gnuplot でグラフ化
    • src.txt (入力ソース)

• • • dft_idft.txt ([DFT→IDFT]で変換→逆変換したもの)

• • • spec.txt (周波数スペクトル)

これもやはりピークが 10, 25, 35 のところにあり、正しく変換されています。

ここでは、正弦波の合成に transformed Range アダプタを使っています。
　　　adaptors::transformed →Range の各要素をファンクタで変換する。1引数版と2引数版がある。

もし Range アダプタを使わなければ、一々テンポラリのコンテナを生成しなければならず非効率なので、
Range アダプタの有用性を示すケースであるとも言えます。

sprout::dft の実装は、離散フーリエ変換の数学的定義を素直にコードに落としたものです。
最初は FFT(高速フーリエ変換) のアルゴリズムを実装しようと思ったのですが、
FFT アルゴリズムは空間の再利用とループを必要とするため、constexpr で同様の実装をすることは、
不可能であるかまたは却って非効率な処理にならざるをえず断念しました。

以上のサンプルではコードによって生成した波形を解析していますが、
例のごとく #include でテキストを取り込めば外部のソースを解析することもできるでしょう。

さて、コンパイル時に DFT を走らせて何の役に立つかと言えば、
あなたのコーヒータイムが伸びることで人生にほんの少しゆとりが生まれるかもしれません。
もっと楽しそうな使い方があればぜひ教えてください。

Sprout.Io - とりあえず文字列へ変換／コンパイル時のパフォーマンスとバッファサイズの話

Github - Sprout　https://github.com/bolero-MURAKAMI/Sprout

Sprout.Io は、コンパイル時に文字列をソース/シンクとした入出力を行うことを目指すライブラリです。
基本的に iostream ライクな記法です。

• • Sprout.Io で文字列へ変換する

#include <iostream>
#include <sprout/io.hpp>

int main() {
    namespace io = sprout::io;
    constexpr auto v = io::output<1023>(
        io::root << "[pai = " << (3.14159265 | io::scientific) << "]"
        );
    std::cout << v << std::endl;
}

• • 出力

[pai = 3.141592]

io::root を開始として、iostream のように operator<<() でオペランドを繋げていきます。
なお、Sprout.Io は Expression Template ベースの実装になっています。
そのため式を書いた時点ではまだ文字列化は行われていません。

実際に文字列化を実行するには io::output() に式を渡します。
N は文字列バッファの長さです。出力がはみ出ないように適切な長さを指定してやる必要があります。

上記コード中の io::scientific は書式指定です。
std::scientific と同じ意味ですが、Sprout.Io では iostream と異なり、ストリームでなく値に対して書式指定を行います。
書式指定は operator|() で行います。後置していくつも繋げることが出来ます。

• • iostream

out << std::scientific << val;

• • Sprout.Io

out << (val | io::scientific);

ちなみに、上記で scientific を指定しているのに出力がそうなっていないのは、書式指定に従った出力がまだ未実装だからです。

ユーザ定義型も出力することが出来ます。

• • Sprout.Io でユーザ定義型から文字列へ変換する

#include <iostream>
#include <utility>
#include <sprout/io.hpp>
#include <sprout/complex.hpp>

namespace sprout {
    template<typename Left, typename Right, typename T>
    inline SPROUT_CONSTEXPR auto
    operator<<(sprout::io::format_expression<Left, Right> const& lhs, sprout::complex<T> const& rhs)
        -> decltype(lhs << '(' << rhs.real() << ',' << rhs.imag() << ')')
    {
        return lhs << '(' << rhs.real() << ',' << rhs.imag() << ')';
    }
}   // namespace sprout

int main() {
    namespace io = sprout::io;
    constexpr auto v = io::output<1023>(
        io::root << "[complex = " << (sprout::complex<double>(1.41421356, 1.7320508) | io::scientific) << "]"
        );
    std::cout << v << std::endl;
}

• • 出力

[complex = (1.414213,1.732050)]

ここでは、複素数クラス sprout::complex の出力を定義しています。
iostream のように、ADL で選択されるよう operator<<() を定義してやります。

左辺のオペランドに io::format_expression、右辺のオペランドにユーザ定義型をとります。
注意すべき点は、返値の型は式テンプレート構築のため自動推論が行われるので、decltype(式) で書いてやる必要があることです。

ところで、あなたが C++er ならばここで二つの疑問が湧いていることでしょう。
　　１．なぜ Expression Template で実装したのか。
　　２．なぜ出力がユーザ指定の固定長なのか。可変長のほうが良いのではないか。

１．については、constexpr における切実なパフォーマンス（メモリと速度）の問題によるものです。
例えば10個の文字列 a, b, c,... を連結する場合を考えます。

• • 実行時の場合（ストリームを使う）

std::ostringstream os;
os << a << b << c << ...;

コピーは常に ostringstream の管理領域に対して行われ、必要に応じて再確保されます。

• • 実行時の場合（酷い例）

std::string s = a + b + c + ...;

operator+() 毎に新しい string のインスタンスが作成され、メモリの面でも速度の面でもオーバーヘッドになります。
こんなコードを平気で書くプログラマがいたら窓から投げ捨てるべきでしょう。

しかしながら、constexpr の文脈においては、代入や書き替えができないため、『普通に書くと』上の酷い例のように書くしかないわけです。
特に、長いバッファのコピーをコンパイル時に行うのは、コードの見かけ上以上にメモリを消費します。
例えば GCC4.7 で、1000文字くらいの文字列を10数回 operator+() で連結すると、数GiBくらいは軽くいきます。

そのため、Sprout.Io の io::output では、ExpressionTemplate と IndexTuple のイディオムを組み合わせることで、
文字列連結を一手順で処理するように実装しています。
このため、長い文字列であっても現実的なメモリと時間で処理できるようになっています。

２．については、これはコンパイル時という制限のためです。
sprout::string を見れば解るように、コンパイル時に完全に可変長なバッファを扱うことは出来ません。
そのため、constexpr コンテナ等は要素数をあらかじめ型の一部として持っていなければなりません。

この制限を回避するには、二つの方法が考えられます。
　　A．ちょうど必要なサイズを自動推論して型レベルでサイズを調節する。
　　B．最大限必要なサイズを推論して、それを統一的に使う。
A．は sprout::string の operator+() で、B．は sprout::to_string などの数値変換において行われています。
しかしながら、これは入力の型や書式がかなり固定的な場合においてのみ考えられることです。

一般に、ある書式での文字列の変換に必要な最大サイズを推論するのは、不可能であるか、あるいは非常に大きなサイズになってしまいます。
例えば long double の固定小数点表記に必要な最大サイズは numeric_limits::max_exponent10 + α になり、
これはコンパイラによっては4000以上の値になります。（たかだか浮動小数点数一つに！）

こうした現実的な問題を踏まえて、Sprout.Io では出力サイズをユーザ側が固定長で指定する仕様になっています。

なお、Sprout.Io はまだまだ開発途上であり、ここで書いたような仕様や識別子のネーミングも、これから破壊的変更がなされる可能性があります。