⛳

[Rust] 再帰下降パーサの落とし穴

2024/09/25に公開

Rust

Mascal 最適化

Rust で作るプログラミング言語シリーズです。

https://www.amazon.co.jp/dp/4297141922

Mascal プロジェクトで、パーサが異様に遅い現象がありました。
しかも、次のようなシンプルなコードでです。

var a = array([[[1]]]);

print(a, type(a));

こんな素朴なコードのパースに、 Rust のリリースビルドでも 2 秒もかかりました。

real    0m2.447s
user    0m2.446s
sys     0m0.001s

この遅さは配列のネストの深さを増すと急速に増大します。もう一段ネストしただけで...

var a = [[[[1]]]];

...非合理的なほど遅くなりました。

real    0m28.689s
user    0m28.689s
sys     0m0.000s

原因

知っている人は良く知っていると思いますが、再帰下降パーサ(あるいは一般に LL(k) パーサ)は複数の構文の候補があった場合、バックトラックによって候補を決定します。それにしてもこんな簡単な構文でここまで遅くなるとは予想していませんでした。

Mascal は配列を操作することを目的とした言語なので、 3 段か 4 段のネストした配列はよく出てきます。これのパースにここまで時間がかかっては実用的ではありません。

ここでパーサのコードを見直すと、次のようなパターンが頻出することに気づきました。

fn array_rows(i: Span) -> IResult<Span, Vec<Vec<Expression>>> {
    let (r, (mut val, last)) = pair(
        many0(terminated(array_row, ws(tag(";")))), opt(array_row)
    )(i)?;

    if let Some(last) = last {
        val.push(last);
    }
    Ok((r, val))
}

このパーサ関数の意味は、複数の array_row でパースした結果をセミコロンで区切り、最後のセミコロンは任意であるということで、例えば [1; 2] と [1; 2; ] の両方を受け付けます。ところが、入力にセミコロンがなかった場合、この関数は入力をもう一度読み直します。これだけなら入力のスキャンを 2 回するだけに思えますが、配列をネストするとこのバックトラックが指数的に増えていきます。

修正方法は簡単です。 <array_row> ; のパースを試みて、次に <array_row> を試みる代わりに、 <array_row> をパースして、最後に ; を付け加えればよいです。

fn array_rows(i: Span) -> IResult<Span, Vec<Vec<Expression>>> {
    terminated(separated_list0(char(';'), array_row), opt(ws(char(';'))))(i)
}

コードはむしろシンプルになりましたが、この効果は後で見るように絶大です。

関数呼び出し回数の評価

効果を測定するために、次のようなコードを各関数に挿入し、関数の呼び出し回数をカウントしました^[1]。 nom はパーサに渡せるコンテキスト変数のようなメカニズムを持たないので、関数の呼び出し回数をカウントするにはグローバル変数を使う必要があります。 Rust は可変なグローバル変数を毛嫌いしていますが、アトミック変数ならしぶしぶ受け入れてくれます ^[2]。

static ARRAY_LIT: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);

pub(crate) fn array_literal(i: Span) -> IResult<Span, Expression> {
    ARRAY_LIT.fetch_add(1, Relaxed);
    // ...
    Ok((r, Expression::new(ExprEnum::ArrLiteral(val), span)))
}

array_rows 関数を改善する前：

    array_rows: 225888
    array_literal_calls: 112968
    primary_expression_calls: 5421384
    postfix_expression_calls: 1807132
    fn_invoke_arg: 4
    cmp_expr: 903566
    expr_calls: 451783

後：

    array_rows: 28848
    array_literal_calls: 28872
    primary_expression_calls: 692424
    postfix_expression_calls: 230812
    fn_invoke_arg: 4
    cmp_expr: 115406
    expr_calls: 57703

評価回数が一気に1/10近くに減りました。

ここで同じような最適化を array_row にも適用してみます。これは array_rows とほぼ同じロジックで、 , を区切り文字とするパーサです。

    array_rows: 7536
    array_literal_calls: 7560
    primary_expression_calls: 90504
    postfix_expression_calls: 30172
    fn_invoke_arg: 4
    cmp_expr: 15086
    expr_calls: 7543

さらに比較演算のパーサ cmp_expr で expr を繰り返さないように修正します。

    array_rows: 516
    array_literal_calls: 540
    primary_expression_calls: 3132
    postfix_expression_calls: 1048
    fn_invoke_arg: 4
    fn_invoke: 1048
    cmp_expr: 1048
    expr_calls: 524

また、式の末尾のパーサ postfix_expression (a.b などを解析する) および代入式 assign_expr にも似たような最適化を施すと、最終的に次のようになりました。

    array_rows: 3
    array_literal_calls: 5
    primary_expression_calls: 6
    postfix_expression_calls: 7
    fn_invoke_arg: 1
    fn_invoke: 7
    cmp_expr: 7
    assign_expr_calls: 7

結論

バックトラックの無駄は一つ一つが小さくても、再帰呼び出しによって指数的に増大します。今回は array_rows が array_row を呼び出し、それが一般の式 expr を呼び出し、さらに巡って array_row を呼び出し…という形で相互再帰しているため、少ないネストの階数でも非常に多くの無駄に増大しました。

前の記事では再帰下降パーサのバックトラックの無駄が現実的な問題になることはないなどと書いてしまいましたが、思いっきり現実的な問題になりました。ただし、原因が分かってしまえば繰り返し同じパースをしないように書き直すことで取り除くことができます。

LR パーサジェネレータがしばしば好まれるのは、このような無駄はツールが防いでくれるから、という理由もあるようです。究極的には、構文の曖昧さという問題に人間が対処するか、ツールが対処するかというだけで、能力的には同じです^[3]。

今回は影響が指数的に増大していったのですぐに気づけましたが、もしかしたら、気づかないうちにあなたのパーサも遅くなっているかもしれないので、お気を付けください。

[2024/10/07 追記] rusty-parser プロジェクトを Mascal に改名したのに追従しました。

脚注

perf や callgrind などのプロファイリングツールを使っても良いですが、ここではごく特定の関数の呼び出し階数をカウントしたいだけなので、そのようなツールをインストール・セットアップするよりもコードにカウンタを導入する方が楽です。 ↩︎
thread_local! でもよいですが、結局 Cell か RefCell に包む必要があるのでコード量的なメリットはあまりありません。 ↩︎
他にも Packrat parsing などのメモリ使用量を犠牲にして繰り返しを防ぐ方法もありますが、どのように書き直せば無駄が取り除けるかがわかってしまえば、それが一番効率が良いので優先したいですね。 ↩︎

GitHubで編集を提案

Mascal 最適化

原因

関数呼び出し回数の評価

結論

Discussion