読者です 読者をやめる 読者になる 読者になる

ボレロ村上 - ENiyGmaA Code

中3女子です。

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 ならばここで二つの疑問が湧いていることでしょう。
  1.なぜ Expression Template で実装したのか。
  2.なぜ出力がユーザ指定の固定長なのか。可変長のほうが良いのではないか。


1.については、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 のイディオムを組み合わせることで、
文字列連結を一手順で処理するように実装しています。
このため、長い文字列であっても現実的なメモリと時間で処理できるようになっています。


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


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


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


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


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