perl5 issue tracker

本記事の内容は perl5 の gihtub リポジトリに報告してあります。詳しい再現方法等や回避策、修正パッチについても記載してあるので、興味のある方はご覧になってください。5.42 だけではなくて、5.36 からずっと遅かったようです。macOS 15 は 5.34 なので気がつかず、最近 homebrew 版を使うようになってわかったということです。対応は先送りにされたようなので、5.44 でも直りません。

greple の出力が終わらない

greple という Perl 製 grep ライクな検索ツールを長年使っている。10年ほど前「@- と @+ へのアクセスが UTF-8 文字列で異常に遅い」という問題を見つけて記事にしたことがある。

先日、並列化機能を実装してベンチマークを取っていたところ、また様子のおかしい現象に遭遇した。26MB の日本語テキストから、30万行中11万行がマッチするパターンを検索すると、カウントは一瞬で終わるのに、内容を出力させると何分待っても終わらない。

再現方法は簡単で、全行がマッチするような大きめの日本語テキストを作ればいい。

$ perl -e 'print "検索 高速 テキスト 処理\n" x 300000' > big.txt

$ time greple -c 高速 big.txt
300000
real	0m0.985s

$ time greple 高速 big.txt > /dev/null
（15秒経過しても 30万行中 2万行しか出力されない。完走には推定50分）

検索は済んでいるのだから、あとは出力するだけのはずである。それが検索の数千倍かかる。

犯人は substr

macOS の sample コマンドでプロファイルを取ると、一目瞭然だった。

2565 Perl_runops_standard
+ 2549 Perl_pp_substr
+ ! 2549 Perl_sv_pos_u2b_flags
+ !   2549 S_sv_pos_u2b_cached
+ !     2549 S_sv_pos_u2b_midway

時間の 99% が substr の中、それも sv_pos_u2b、つまり文字オフセットからバイトオフセットへの変換に費やされている。

greple はファイル全体を一つの文字列として持ち、マッチしたブロックを substr($text, $start, $len) で切り出しながら出力する。UTF-8 フラグの立った文字列では、文字位置 $start をバイト位置に変換しないと切り出せない。この変換が、呼ぶたびに文字列を先頭付近から線形に歩いているのである。11万ブロックを順に切り出すと O(N²) になり、破滅する。

最小再現コード

greple は関係なく、素の substr だけで再現する。

use Time::HiRes qw(time);
my $s = chr(0x3042) x 20_000_000;   # 「あ」2000万文字
my $n = length $s;
my $t = time;
substr($s, int($n * $_ / 101), 10) for 1 .. 100;
printf "perl %vd: %.3f sec\n", $^V, time - $t;

位置を単調に進めながら、たった 100 回 substr するだけのコードである。これを手元の 2 つの Perl で実行すると：

perl 5.34.1: 0.012 sec
perl 5.42.2: 0.228 sec

19 倍遅い。実ファイル由来の日英混在テキスト（1900万文字）では 0.039 秒 vs 1.05 秒で 27 倍だった。

さらに条件を変えて 1 回あたりの時間を測ると、状況がはっきりする。

条件	5.34.1	5.42.2
多バイト・位置を単調に進める（100回）	0.13 ms/回	2.4 ms/回
多バイト・同一位置（100万文字目）を繰り返す	0.03 µs/回	264 µs/回
ASCII のみ（UTF-8 フラグ付き）単調	0.05 µs/回	0.05 µs/回
ASCII のみ（フラグなし）単調	0.05 µs/回	0.05 µs/回

遅いのは実際に多バイト文字を含む文字列だけ。ASCII なら UTF-8 フラグが立っていても速い
驚くべきことに、まったく同じ位置を繰り返し切り出しても遅い。5.34 では 2 回目以降キャッシュが効いて 0.03 µs なのに、5.42 では毎回 264 µs かかる
間に m//g や pos() への書き込みを挟んでも変わらない。素の substr 単体で遅い

決定的なのは次の測定で、5.42 では substr のコストが文字位置に正確に比例する。

my $s = chr(0x3042) x 20_000_000;
for my $pos (1_000, 100_000, 1_000_000, 10_000_000) {
    my $t = time;
    substr($s, $pos, 10) for 1 .. 1000;
    printf "位置 %8d: %8.2f µs/回\n", $pos, (time-$t)/1000*1e6;
}

位置     1000:     3.64 µs/回
位置   100000:    34.44 µs/回
位置  1000000:   332.47 µs/回
位置 10000000:  2896.55 µs/回

つまり毎回、文字列の先頭から目的の位置まで歩き直している。

何が起きているのか

Perl は UTF-8 文字列の「文字位置/バイト位置」変換を高速化するため、SV に MAGIC として位置キャッシュ（${^UTF8CACHE}）を付けている。直前の変換結果が残っていれば差分だけ歩けば済むはずで、実際 5.34 まではそう動いていた。

5.42 では ${^UTF8CACHE} が 1（有効）にもかかわらず、上の測定が示す通りキャッシュはまったく機能しておらず、コストは常に位置に比例する。プロファイルで S_sv_pos_u2b_midway（キャッシュ済み位置の中間から歩く関数）に時間が張り付いていることから、キャッシュ機構のコード自体は通っているのに、有効なキャッシュエントリが参照できていない（保存されていないか、無効化されている）ように見える。

10年前の @-/@+ の問題は、バイト→文字方向（sv_pos_b2u）の変換が遅いという話だった。今回はその逆方向（sv_pos_u2b）である。ただし決定的な違いがある。@-/@+ は少なくとも 5.12 の昔から一貫して遅かったのに対し、substr は 5.34 では速かった。5.36 から 5.42 のどこかで退行したことになる。

対策：unpack で一括切り出し

greple での対策として、「ブロックごとに substr」をやめて、全ブロックを unpack 一発で切り出すことにした。

# @blocks = ([from, to], [from, to], ...)  昇順・非重複であること
my $template = do {
    my $pos = 0;
    join '', map {
        my($s, $e) = @$_;
        my $t = 'x' . ($s - $pos) . 'a' . ($e - $s);
        $pos = $e;
        $t;
    } @blocks;
};
my @pieces = unpack $template, $text;

a10 は 10 文字取り出す、x20 は 20 文字読み飛ばす、という unpack のテンプレートを全ブロック分連結して一度に適用する。unpack は文字列を先頭から一度だけ走査するので、ブロック数によらず O(N) である。

効果は劇的で、1900万文字の文字列から 10 万ブロックを切り出すのに：

substr 方式：1回平均 10ms × 10万 = 推定 1000 秒超
unpack 方式：0.05 秒

この修正を入れた greple 10.05 では、冒頭の「終わらない出力」が 1.5 秒で完走するようになった。行番号計算（これも切り出した gap 部分を数えるだけにした）を含めても 2.2 秒である。

なお、検索フェーズが元々速いのは、10年前の教訓で @-/@+ を避けて pos() と ${^MATCH} を使っているからで、この方式は 5.42 でも速いままだった。回避してきた地雷原の隣に、新しい地雷が埋まっていた格好である。

おまけ：5.42 で壊れたもうひとつの話

ついでに、以前別の記事に書いた「親プロセスが STDIN を読み切ったあと fork した子プロセスが入力を読めない」問題も 5.42 で確認してみた。当時「不思議だが動く」と書いた @_ に読み込むトリックは、5.42 では動かなくなっている。

@_ = <>;
if (open(CHLD, '|-') == 0) {
    print <>;    # 5.34 では読める。5.42 では何も読めない
    exit;
}
print CHLD @_;

一方、当時「最善」と判断した fdopen 方式は 5.42 でも問題なく動く。

open STDIN, '<&', 0 if eof STDIN;

原理を理解して選んだ回避策は生き残り、偶然動いていたものは偶然壊れた。

環境と今後

macOS 15.7.7 (Apple Silicon)
perl 5.34.1（システム標準）/ perl 5.42.2（Homebrew）

どのバージョンで退行したのか、より新しいバージョンで直っているかは不明。

とりあえず greple 利用者や、substr を利用する同様なプログラムが急に遅くなった、という人のために先に書いておく。