[C++]自称世界最速の文字列数式計算ライブラリを作った。

更新情報

2021年1月

  • C++標準への要求をC++14からC++17に変更しました。
  • ベクトル、行列をadapt::Vector<double>、adapt::Matrix<double>からEigenのVectorXd、MatrixXdに、文字列をadapt::Stringからstd::stringに変更しました。
  • 上の変更に伴い、線形代数ライブラリEigenを要求するようになりました。

動機

C++で文字列式を計算したいと考えたことはないだろうか。例えば"2 * a + b ^ 2"みたいな適当な式を文字列で定義しておいて、aやbに任意の値を与えることで計算結果を出力させたい、というような話だ。pythonでいうところのevalみたいなもの。
これを実現するようなライブラリは、実は多数存在する。現存する中で最速のものはExprTkのようで、似たライブラリを集めたベンチマークで最高成績を収めている。

ただしExprTkには欠点がある。基本的に浮動小数点しか扱えないのだ。いや正確には複素数なども扱えるが、基本的に予めテンプレートパラメータに与えた一つの型しか扱えない。浮動小数点と決めたなら整数も複素数も扱えないのだ。もちろんベクトルや行列、文字列などを扱うことはできないし、増して同時に扱うことも不可能である。多数の型に対応しつつも高速なライブラリは、残念ながら見つからなかった。私はこれらの型をすべて同時に、自由に扱いたいのだ。

そこで、これらの型を一つの式の中で同時に扱うことのできる文字列式パーサーライブラリを自作しようと考えた。そしてどうせなら、ExprTkを上回る世界最速のライブラリにしてやろうと思った。

というわけで試作してみたのがADAPT-FMPである。要求するバージョンはC++14で、ヘッダーオンリーで使える2021年1月現在のバージョンでは線形代数ライブラリEigenとC++17が必要であるが、一応ヘッダーオンリーではある。開発したのは2020年1月ごろで、その後自作のデータ解析用ライブラリに組み込もうとしたのだが、そちらの作業を行う時間がなかなか取れずに放置されていた。折角作ったのに勿体ないのでここで公開してみる。 github.com

ADAPT-FMPの使い方

現在対応している型は整数(int64_t)、浮動小数点(double)、ベクトル(adapt::Vector<double>Eigen::VectorXd)、行列(adapt::Matrix<double>Eigen::MatrixXd)、文字列(adapt::Stringstd::string)である。とはいえ、ベクトルや行列、文字列の関数や演算子などは十分には定義されていない。そのうち気が向いたら用意する。 定義済み演算子、関数はGitHubのREADMEFMPFunction.hあたりを参照されたい。

#include <ADAPT/FMP/FastMathParser.h>

using namespace adapt;
using namespace adapt::fmp;
using namespace adapt::fmp::lit;

int main()
{
    {
        std::string expr = "25*x^5 - 35*x^4 - 15*x^3 + 40*x^2 - 15*x + 1";
        double x;
        double r0 = 0;
        double r1 = 1;
        double delta = 1 / 100.0;
        FastMathParser f(expr, { "x"_a = &x });
        for (x = r0; x <= r1; x += delta)
        {
            printf("%19.15f\t%19.15f\n", x, f.Flt());
        }
    }
    {
        std::string expr1 = "sqrt(dot(xy, xy))";
        std::string expr2 = "atan2(xy[1], xy[0])";
        Eigen::VectorXd xy(2); xy << 1., 1.;
        FastMathParser r(expr1, { "xy"_a = &xy });
        FastMathParser t(expr2, { "xy"_a = &xy });
        for (double theta = 0; theta < 1.; theta += 0.01)
        {
            xy[0] = cos(theta);
            xy[1] = sin(theta);
            printf("r = %lf, t = %lf\n", r.Flt(), t.Flt());
        }
    }
    {
        std::string expr = "mat2(vec2(cos(pi * t), -sin(pi * t)), vec2(sin(pi * t), cos(pi * t)))*v + vec2(0.1, 0.5)";
        double theta;
        Eigen::VectorXd v(2);
        FastMathParser aff(expr, { "t"_a = &theta, "v"_a = &v }, { "pi"_c = 3.1415926535897932});
        for (double x = 0; x < 1; x += 0.1)
        {
            for (double y = 0; y < 1; y += 0.1)
            {
                for (theta = 0; theta < 1; theta += 0.05)
                {
                    v[0] = x, v[1] = y;
                    const Eigen::VectorXd& res = aff.Vec();
                    printf("(%8.5lf, %8.5lf) -> (%8.5lf, %8.5lf)\n", x, y, res[0], res[1]);
                }
            }
        }
    }
    return 0;
}

使い方は上記の通り。FastMathParserのコンストラクタに式と引数を与え、計算用関数を呼び出せば良い。ただし式の戻り値の型によって呼び出すべき関数が異なる。

  • int64_t -> Int()
  • double -> Flt()
  • std::string -> Str()
  • Eigen::VectorXd -> Vec()
  • Eigen::MatrixXd -> Mat()

戻り値の型が分からない場合、FastMathParser::GetResultType()を呼べば教えてくれる。

余談

このライブラリの開発は実はかなり難航した。最初私はテンプレートを駆使してこれの構造を纏め上げようとしたのだが、それはうまく行かなかった。完全にテンプレートメタプログラミングのみで実装したところ、複雑化しすぎてコンパイルができなかったのだ。あの巨大すぎるテンプレートライブラリをコンパイルできるほど現代のPCやコンパイラの性能は高くないようだ。デバッグ情報を捨てれば一時間くらいかけてコンパイルできることは分かったが、ファイルサイズが悲惨なことになったため断念した。
仕方ないので、Pythonを使ったコード生成を行うことにした。テンプレートに担わせようとしたジェネリクスを代わりにPythonスクリプトに全部書き下させることで、テンプレートを排除しつつ高速化することができた。……いや、まあ、すごい力技なんだけど、これ以外に方法がなかったのだ。ExprTkはdoubleなどの1種類の型に対してだけ実装すればいいが、こちらは現時点で5種類もの型を同時に扱うので、手作業で書き下すなんて到底不可能なのである。

適当に数式を入力してExprTkと速度比較をしてみると、状況によりけりではあるが、ADAPT-FMPの方が数%程度だが速いことが多かったので、世界最速を自称している。詳細なベンチマークなどは行っていないので確証はないし、ExprTkの方が高速な場合もあるちょっとしたベンチマークもやってみたところ、実行速度では概ねExprTkを上回っているらしいことが分かった。もちろん式によってどちらに有利かという差異はあるので一概に言えないが、世界最速を名乗っても不自然ではないと思っている。 また実行速度と多数の型の扱いを両立する代償としてコンパイルは遅い。

ちなみに、パーサージェネレータにLemonを、レキサージェネレータにre2cを使っている。使いやすいのだが、どちらも基本的にC言語用であることが不便だった。C++でこれを使うにはちょっと工夫が必要だった。特にLemon。何でもかんでも共用体にぶっ込まれるととても困る。しかもLemonによって生成されたコードから消しようのない警告が多数出てくる。もっと便利なジェネレータがあればいいのだが、私が探した限りでは見つからなかった。

最近GitHubで公開していたとあるリポジトリに初めて星が付いて気が大きくなり、以前から公開するか悩んでいたこちらも踏み切った。他にSlack過去ログビューアもいずれ公開しようと思っているが、まだメッセージ検索機能が実装できていないこと、Qtに依存しているためオープンソース化にちょっと手間取っていることが原因で保留している。