15

私はコンパイラに取り組んでおり、そのパフォーマンスを改善したいと考えています。時間の約 50% がソース ファイルの解析に費やされていることがわかりました。ソースファイルは非常に小さく、その後かなり多くの変換を行っているため、完璧にできるように思えます。

私のパーサーはレクサー (lexer::pos_iterator を使用) を備えたブースト スピリット パーサーであり、中規模の文法を使用しています。ソースを AST に解析しています。

私の問題は、解析中に何が最も時間がかかるのかわからないことです: AST ノード、レクサー、パーサー ルール、またはメモリのコピーです。

私はSSDで作業していて、最初にファイル全体を読み込んでからメモリバージョンのみを使用しているので、I / Oの問題ではないと思います。

プロファイラーを使ってみたのですが、時間のかかるメソッドは何百文字もあるBoostのメソッドで、何をするのかよくわかりません...

では、Boost Spirit Parser とその文法をベンチマークする好ましい方法はありますか? または、特定のポイントで効率を検証するために使用できるルールはありますか?

ありがとう

興味のある人のための情報源:

4

1 に答える 1

13

私は物事を簡単にスキャンしました。

私のプロファイラーはすぐに、文法と (特に) lexer オブジェクトの構築にかなりのリソースを必要とすることを教えてくれました。

実際、SpiritParser.cpp の 1 行を変更するだけで、実行時間が 40%短縮されました1 (~28 秒から~17 秒):

    lexer::Lexer lexer;

の中へ

    static const lexer::Lexer lexer;

今、

  • 文法を静的にすることには、ステートレスにすることが含まれます。私はこれを実現させました

    • （を使用して）に移動position_beginし、qi::_aqi::locals

    • 適切なタイミングで継承属性として渡す

      • と文法、EDDIGrammar例えばValueGrammar

        start %= qi::eps [ qi::_a = qi::_r1 ] >> program;

      • 外部ValueGrammarで使用されている個々のルールと同様に)。

    これにはいくつかの最適ではない副作用がありました。

    • lexer::pos_iterator_typeにはデフォルトの出力ストリーミング オーバーロードがないため、ルールのデバッグはコメント アウトされています。

    • 式は、qi::position(position_begin)かなり手の込んだ置換で「偽造」されています。

      auto local_pos = qi::lazy (
        boost::phoenix::construct<qi::position>(qi::_a)
    );

      それは理想的ではないようです。(理想的には、qi::locals (?) から get begin_position を取得する方法を知っているqi::position変更されたカスタム パーサー ディレクティブに置き換えて、パーサー式を遅延して呼び出す必要がないようにすることをお勧めします。)

とにかく、これらの追加の変更2 を実装すると、実行時間がさらに 15% 短縮されました。

static const lexer::Lexer lexer;
static const parser::EddiGrammar grammar(lexer); 

try {
    bool r = spirit::lex::tokenize_and_parse(
            position_begin, position_end,
            lexer, 
            grammar(boost::phoenix::cref(position_begin)),
            program);

緩いアイデア:

  • 静的レクサーの生成を検討しましたか (静的アナライザーの生成)
  • バックトラッキングの量を潜在的に削減するために期待値を使用することを検討しましたか (注: 私はその分野では何も測定していません)
  • と の代替案を検討しましたPosition::fileかPosition::theLine? 文字列のコピーは、必要以上に重いようです。保管したいconst char *です。Boost Flyweightも参照してください。
  • qi::positionディレクティブ内で事前スキップが本当に必要ですか?
  • (あまり深刻ではありません: Spirit X3への移植を検討したことがありますか?移動のセマンティクスの形で潜在的な利点が約束されているようです。)

お役に立てれば。

[1]すべてのテスト ケースをtest/cases/*.eddi100 回解析する場合(github) :

for (int i=0; i<100; i++)
    for (auto& fname : argv)
{
    eddic::ast::SourceFile program;
    std::cout << fname << ": " << std::boolalpha << parser.parse(fname, program, nullptr) << "\n";
}

シンプルなタイミングで

time ./test ../../test/cases/*.eddi | md5sum

md5sum健全性チェックとして機能します。

[2] https://github.com/wichtounet/eddic/pull/52の概念実証リファクタリングでプル リクエストを作成しました

于 2013-06-05T03:32:41.120 に答える