【.NET】軽量・高速・ZeroAllocな数式パーサーを制作

概要

文字列として与えられた数式を評価する、所謂 数式パーサー のライブラリを制作しました。
以前作った『煽られMATH』というゲームで当該ロジックを使っており、「結構有用なのでは？」と思って、最適化・ライブラリにして公開しました。

リンク

GitHub : README から、使い方・インストール方法など公開しています。
NuGet : 同様です。

ダウンロード数

どれほど信憑性があるか分かりませんが、一応こんな感じの数字が出てました。
汎用ライブラリではなく、機能を絞って最適化に特化したものなので、需要はニッチだと思います。
ただ調べた感じ、.NET ライブラリでこのようなものは無かったので、ライブラリ化した意義はあるかな？と。

既存ライブラリとの違い

C# (.NET) で数式パーサーの機能を使うには、いくつかの手段があります。
色々違いがあって面白いのですが、共通してパフォーマンスが悪いかな・・・と思っています（どうしても GC.Alloc が発生してしまう）。
ゲームプログラマーとしては、毎フレーム処理を呼び出す、とかなるとちょっと躊躇してしまう所がありました。

他にどのようなライブラリがあるか、調べたものを以下に述べます。
他ライブラリとの比較 の項でベンチマークを取っているので、併せてご覧ください。

エクセルライブラリの一部機能を使うタイプ

• DataTable.Compute
  .NET の組み込み機能です。最も手軽に数式パースしたい場合、最初に検討するものかと思います。
  データテーブル、つまりエクセルのような構造を作れるライブラリですが、その中のセルを評価する関数を呼び出す感じです。
  手軽に使えていいのですが、機能の一部を無理やり借用している感が否めなく、無駄な処理がオーバーヘッドになってしまいます。戻り値も object なので、浮動小数にキャストするとアンボクシングが発生、GC.Alloc してしまいます。しかも double だったり decimal だったりするので、Convert.ToDouble など使って変換しないといけません。
  お手軽なのはいいですが、総合的にかなり使いにくい感触です。

object resultObject = _table.Compute("数式", null);
double result = Convert.ToDouble(resultObject, CultureInfo.InvariantCulture);

• ClosedXML
  xmlファイル、つまりエクセルを処理するライブラリです。
  基本的に同上で、巨大なライブラリの一部機能を無理やり使っているのが美しくないです。
  戻り値が double でアンボクシングしないのは高評価です。

_cell.FormulaA1 = "数式";
double result = _cell.Value.GetNumber();

他言語を呼び出すタイプ

.NET で無理なら他言語を使ってしまおう、という発想です。

• IronPython
  Python の eval 関数を使います。これは、プログラムを動的に解釈して実行する、という強力な機能です。一方で、内部で手動コンパイルしているのと同義なので、数式パースに特化するよりもパフォーマンスが悪く、 GC.Alloc が発生します。
  戻り値も dynamic なので、アンボクシングが発生します。
  補足として、Python は処理が遅い印象がありますが、ベンチマークを取った感じそれほどの遅さは感じませんでした。確かに Python だけで書くとめっちゃ遅いですが、大体は内部で C/C++/Rust といったネイティブ処理を読んでいる、ラッパー言語の特徴があります。Python はそんなに遅くないぞ、というのを改めて感じました。

dynamic resultDynamic = _engine.Execute($"eval('{"数式"}')")
double result = (double)resutDynamic;

• ExprTk
  C++ の有名な数式パーサーライブラリです。
  DLLにコンパイルして、DLLImport で呼び出しています。
  C++なので、ちゃんと 0 Alloc になっているのが素晴らしい！しかし意外なことに、実行速度は他より圧倒的に（少なくとも10倍ほど）遅かったです。多分ライブラリ自体が巨大なのかな？と思います。
  一方で、プラットフォームに応じてDLLコンパイル → P/Invoke するのがちょっと面倒くさいな〜、という印象です。C++はパッケージシステムがそんなに成熟していないので・・・。
  　
  以下のコードは、macOSで呼び出す例です。
  exprtk.hpp をインクルードしてラッパー関数を作り、.dylib（Windowsでいう.dll）にコンパイルして、C# から P/Invoke します。
  .NET の文字列は UTF16（ワイド文字）で、char は 2 バイトです。
  一方で C++ の文字列の扱いは環境依存な所があって面倒です。数式で使うのはひとまず ASCII 文字のみなので、 C++ では char（1 バイト）として受け取ることにします。
  C# から P/Invoke する際には、char（2 バイト）から byte（1 バイト）に強制的にキャストします。Encoding.GetBytes とかもありますが、char → byte のキャストだけなので、手動でゴリゴリと書いています。

make:
	clang++ -O3 -DNDEBUG -march=native -ffast-math -std=c++17 -fPIC -shared <下記の.cppファイル名>.cpp -o <出力する.dll/.dylibファイル名>.dylib

#include <string>
#include <limits>
#include "exprtk.hpp"

#if defined(_WIN32)
#define DLL_EXPORT extern "C" __declspec(dllexport)
#else
#define DLL_EXPORT extern "C" __attribute__((visibility("default")))
#endif

DLL_EXPORT double Calculate_ExprTk(const char *expression, int length)
{
   if (expression == nullptr || length < 0)
      return std::numeric_limits<double>::quiet_NaN();

   const std::string expression_string(expression, static_cast<std::size_t>(length));

   using T = double;

   exprtk::symbol_table<T> symbol_table;
   symbol_table.add_constants();

   exprtk::expression<T> expression_obj;
   expression_obj.register_symbol_table(symbol_table);

   exprtk::parser<T> parser;
   if (!parser.compile(expression_string, expression_obj))
      return std::numeric_limits<double>::quiet_NaN();

   return expression_obj.value();
}

internal static class Native_ExprTk
{
    [DllImport(".dll/.dylibファイル名", CallingConvention = CallingConvention.Cdecl)]
    private static extern unsafe double Calculate_ExprTk(byte* expression, int length);

    public static unsafe double Calculate(string expression)
    {
        ReadOnlySpan<char> formulaSpan = expression.AsSpan();
        int length = formulaSpan.Length;

        Span<byte> buffer = stackalloc byte[length];
        for (int i = 0; i < length; i++)
        {
            buffer[i] = (byte)formulaSpan[i];
        }

        fixed (byte* p = buffer)
        {
            return Calculate_ExprTk(p, length);
        }
    }
}

// (略)

double result = Native_ExprTk.Calculate("数式");

　
手間がかかりますが、流石にパフォーマンスは良好です。
しかし、個人的な所感で言うと、.NET のライブラリがパフォーマンスを追求できていないだけで、.NET のマネージド環境内のみでも同程度なパフォーマンスは出せるのでは？と思っています。
実際今回作成したライブラリは Pure C# ですが、C++ で再実装したものとベンチマークを取ったところ、C++ の方が一定量だけ遅い、と言う結果になりました。これは、ロジック自体のパフォーマンスはほぼ同じで、呼び出しコスト・マージャリングコストといったものがかかっているのだと思います。
まとめると、C++ はパフォーマンス良く作れるが、.NET のみでも同程度のことは出来る。そうなると、わざわざ手間をかけて C++ を呼び出す意味はない、といった感じです。

数式パーサー特化の .NET ライブラリ

調べた所、.NET でのライブラリ実装がいくつかあるようでした。

• NCalc

シンプルなAPIで呼び出すことが出来ます。
しかし、Expression クラスの作成で GC.Alloc する点は大きなマイナス点で、戻り値が null 許容 object 型なので、アンボクシングのコスト・null チェックの面倒さがあります。
　
事前に AST（構文木）をコンパイルするとか、キャッシュするとかは出来るそうですが、それは数式の形式が静的に決定している場合にしか機能しません。
パフォーマンスは他の手法より若干良好でしたが、GC.Alloc が多め、という感触です。

Expression expression = new Expression("数式");
object? resultObjectOrNull = expression.Evaluate();
double result = (double)resultObjectOrNull!;

• xFunc

こちらも NCalc と似ていますが、Processor クラスをキャッシュしておけるのと、戻り値が double なのが使いやすいです。
パフォーマンスは他の手法と同程度でしたが、GC.Alloc の量はひときわ少ないです。

これも事前コンパイルなど出来ますが、同様に動的な数式のパースにおいては意味をなしません。

Result resultClass = _processor.Solve("数式");
double result = resultClass.Number.Number;

まとめ

・・・ということで、既存ライブラリで 高速 & Zero Alloc で機能するものは意外とありませんでした。そういったわけで、本ライブラリを制作するに至った感じです。
あとは、汎用的なライブラリだと、使わない機能のために余計なオーバーヘッドが出たりしているので、必要な機能のみを厳選した軽量なライブラリとして作ることも意識しました。

実装

ポインタを使って処理

Zero Alloc を実現するために、Span<T> を使って処理していました。
・・・が、その後結局、生ポインタを使ったゴリゴリの Unsafe 処理に変えました。そっちの方が速いので。

.NET でポインタを使う際の注意点ですが、ガベージコレクションのコンパクション（メモリ上のインスタンスを前に詰めて、断片化を解消する）が起こると、ポインタの指し示す値が変化します。
そのため、fixed スコープで囲むことでポインタをピン留めし、ガベージコレクションが起きてもこのポインタがコンパクションされるのを防止しています。
メソッド内の処理が長くなると、ピン止めされている時間が長くなってメモリが断片化しやすくなるのですが、この程度の実装なら問題ないでしょう。

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static unsafe double Calculate(this ReadOnlySpan<char> formula)
{
    fixed (char* p = formula)
    {
        // ... 処理を行う
    }
}

文字列を前から順に走査する

アルゴリズムは O(N) にしたい拘りがありました。
他のライブラリがそうであるので、このライブラリも妥協はできないかな、と。

ダイクストラの Shunting Yard algorithm があったのですが、これは数式を前から順に走査して、後置記法に置き換えるものです。このようにすることで、数値と演算をスタックに積み、シンプルに処理していくことが出来ます。

従来の AST を構築する手法は GC.Alloc が発生し、AST 構築 → 評価 の 2 パスかかります。
本ライブラリでは、Shunting Yard algorithm で数値と演算をスタックに積むと共に、それらを処理していくのも同時に行います。
こうすることで、ワンパスの単純な処理になり、また配列に順にアクセスしていくので、CPU キャッシュも効きやすくなります。

// Worst case:
// every meaningful character becomes either a value or an operator.
double* values = stackalloc double[len];
char* ops = stackalloc char[len];

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static unsafe bool ApplyTop(double* values, ref int vTop, char* ops, ref int oTop)

検証と処理を分離する

AST 構築をしなくなったことで、数式の形式が適切であるかをチェックする必要が出てきました。
例えば、このような数式は評価することが出来ません。

1 + 2 -* 3
2 - (3 * 4

しかしながら、これをチェックするためにメインロジックが肥大化するのは、軽量なライブラリとは言えないと思いました。
そこで、「数式の形式が適切かチェックする」「数式を評価する」処理を、別々の API として切り分けました。

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static unsafe double Calculate(this ReadOnlySpan<char> formula)

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static unsafe bool IsValidFormula(this ReadOnlySpan<char> formula)

Calculate では、数式の形式が正しいと信じて処理を行います。
実行時でないと評価できない問題（0除算など）の場合は、double.NaN を返却します。
ユーザー入力から計算するなどの場合は、IsValidFormula と組み合わせて使用してください。

ReadOnlySpan<char> formula = "数式".AsSpan();

if (!formula.IsValidFormula())
{
    return;
}

double result = formula.Calculate();

仕様

プログラムで使われる数式というよりは、自然言語の文脈で使われる数式を解析したかったので、例えば以下のような制約を設けています。

単項演算子を二項演算子の右辺に置くときは、カッコで囲むこと

OK: 23 + (-2)
NG: 23 + -2

累乗において、底と指数が共に整数の場合、底は非負整数でなければならない

OK: 3 ^ 4
NG: (-2) ^ 6

テストコードを作っており、これらルールを仕様として厳密にチェックしています。
AI の助力を借りるときも、明文化された仕様（＝テスト）があると効果的でした。

ちなみに、剰余（余り）演算子 % だけは特例として追加しています。
あると便利かなと思ったので、エコ贔屓しました。

NuGet, UPM 公開

.NET Standard 2.1 で制作し、NuGet公開しています。
一方で Unity の場合は、Unity Package Manager (UPM) を用いるのが一般的なので、Unity 側のラッパークラスを作成して Assembly Definition に包みました。
実装で用いたテストコードも、そのまま Unity の Test Runner で動かすことが出来ます。

NuGet

dotnet add package foriver4725.FormulaCalculator

UPM

https://github.com/foriver4725/FormulaCalculator.git?path=Unity/Assets/foriver4725/FormulaCalculator

機能の限定

本ライブラリでは、以下のような演算を意図的にサポート対象外としています。

sin(), cos(), tan(), asin(), acos(), atan(), sinh(), cosh(), tanh(),
abs(), floor(), ceil(), round(), deg(), rad(), sqrt(), exp(), log(), ln(),

... (その他たくさんの関数)

電卓とかではこういう機能がよくありますが、こういう膨大な数の関数をサポートし始めると、ライブラリが一気に肥大化し始めて嫌だな、と思いました。
設計思想として「軽量」であることは大事にしたいので、バッサリと消してしまうことにしました。
sqrt とかも実装していないですが、x ^ 0.5 で代用できるのでいいかな、と感じています。

また、これらの演算はプログラムの関数呼び出しみたいな感じで、自然言語としての数式に機能を外付けしている印象があります。
その点もあり、本ライブラリのコア機能としてサポートするよりは、ユーザー側で必要な分、機能を外付けするのがいいと思いました。

以下は sin のパース処理を外付けする例です。
適当な作りで GC.Alloc も出ていますが、そこらへんはいい感じに最適化をお願いします。
Dictionary<string, Func<double, double>> とかで "sin" - Math.Sin の連想配列を作ることも考えましたが、関数ポインタとかやり始めるとかなり処理が肥大化しますし、インライン化も出来ないので最適化されにくくなってしまいます。
こういう技術的な事情もあり、まあ・・・いいかなと。力不足ですみません🙇

using System;
using System.Globalization;
using foriver4725.FormulaCalculator;

static string PreprocessSin(ReadOnlySpan<char> formula)
{
    const string functionName = "sin(";

    int index = formula.IndexOf(functionName, StringComparison.OrdinalIgnoreCase);
    if (index < 0)
    {
        return formula.ToString();
    }

    int argumentStart = index + functionName.Length;

    int depth = 0;
    int argumentEnd = -1;

    for (int i = argumentStart; i < formula.Length; i++)
    {
        char c = formula[i];

        if (c == '(')
        {
            depth++;
        }
        else if (c == ')')
        {
            if (depth == 0)
            {
                argumentEnd = i;
                break;
            }

            depth--;
        }
    }

    if (argumentEnd < 0)
    {
        throw new FormatException("Missing closing parenthesis for sin().");
    }

    ReadOnlySpan<char> inner = formula.Slice(argumentStart, argumentEnd - argumentStart);

    // recursive preprocessing
    string processedInner = PreprocessSin(inner);

    double value = processedInner.AsSpan().Calculate();
    string replacement = Math.Sin(value).ToString(CultureInfo.InvariantCulture);

    string before = formula.Slice(0, index).ToString();
    string after = formula.Slice(argumentEnd + 1).ToString();

    string combined = before + replacement + after;

    // continue processing remaining string
    return PreprocessSin(combined.AsSpan());
}

string formula = "sin(1+sin(2*3))*2";
string preprocessed = PreprocessSin(formula.AsSpan());
double result = preprocessed.AsSpan().Calculate();

ベンチマーク

本ライブラリ

実行時間

時間計算量は O(n) です。
特に、従来の手法で行われていたAST構築をバッサリと切ったので、計算の固定コストが最小限に抑えられています。
そのため、特に短い長さの数式において、顕著に実行時間が短く顕れています。
50文字とかあっても、sin() 1回分程度の計算で済んでいます。（式の中にどんな演算があるかによりますが・・・）

また、数式の形式チェック (IsValidFormula) も、メインの計算に対して 50% ほどの計算量となっており、バリデーションを挟んでも十分速く動作するという印象です。

ヒープアロケーション

Zero Alloc です。
本ライブラリの設計要件なので、当然達成するべき結果ではあるのですが、それでも清々しい結果です。

先に紹介した通り、.NET のライブラリはパフォーマンスを軽視しがちな所があります。
昔の .NET はパフォーマンスより生産性を重視していましたが、近年ではパフォーマンスの追求も大きなファクターになっています。
しかしながら、老舗のサードパーティーライブラリは、昔のままで未だその流れに追いつけていないものが多い、という現状があります。

従って .NET の純正ライブラリで Zero Alloc を達成しているということ、それだけで本ライブラリには大きな価値があると考えています。
きっと今後、上位互換のライブラリが登場する予感はしていますが、いずれにせよ本記事で述べた考え方がもっと広まってほしいと思っています。

ゲームでも、何の気兼ねもなく毎フレーム実行することが出来ますよ！

他ライブラリとの比較

※ ライブラリによって値が大きく異なるので、グラフの値軸を対数軸にしています。

実行時間

他ライブラリより圧倒的に短い計算時間を達成しています。
大体10倍くらい本ライブラリの方が速いです。

先ほども述べましたが、計算の固定コストをなるべく取り除いているので、特に短い長さの数式で、顕著に高速演算することが出来ています。
（グラフの左下がグイッと下向きに曲がっています。）

ヒープアロケーション

対数軸は 0 をプロット出来ないので、本ライブラリ・ExprTk は描画されていません。
他ライブラリでは GC.Alloc が発生する一方で、本ライブラリでは完全な Zero Alloc を実現できています。

まとめ

必要な機能以外を削ぎ落とし、ワンパスで数式を走査する、Zero Alloc な数式パーサーライブラリを制作しました。
.NET 開発環境からは NuGet で、Unity からは UPM でインストール出来ます。
提供しているメソッドも2つだけ、Calculate(), IsValidFormula() だけです。

感想・要望・その他フィードバックも気兼ねなく！