遅いッ！遅すぎるッ！Java の正規表現のお話。 - Cybozu Inside Out | サイボウズエンジニアのブログ

こんにちは、ミドルウェア開発チームの青木です。 先日、アプリケーションサーバーが応答を返さなくなるトラブルに遭遇しました。 今回はその時のトラブルの原因と対策の顛末についてお話しようと思います。 現象 アプリケーションサーバーが突如応答を返さなくなりました。 現象が発生したアプリケーションサーバーのスタックトレースを見ると、あるスレッドの先頭が上記のようになっていました。 "qtp258153142-514386" prio=10 tid=0x00007f40b8dbf000 nid=0x7b4e runnable [0x00007f415ccb0000] java.lang.Thread.State: RUNNABLE at java.util.regex.Pattern$Loop.match(Pattern.java:4692) at java.util.regex.Pattern$G

[kits]

最初から (|) を避けて [0-9A-Za-z-\\%_+!/=.] のように書くかなあ。

[miyakawa_taku]

文中の水島さんのコメントの通り、後方参照を使うような、有限オートマトンで表せないパターンは、原理的に線形時間ではマッチできないので、不正確な記述と思われます。たぶん内部的にエンジンを切り替えてる。

[kmizushima]

（コメント欄に書いた者と同一人物です）コメント参照：

[ext3]

後ろに.入ってるやん？それはいいのか？　Javaだとエスケープする必要ないのか？

[m-naze]

ああそうかORだから入力一文字ごとにバックトラック（不一致が発生したときに備えて保存しておくべき状態）が倍々に増えていくのか…。

[hs_hachi]

昔メールアドレスチェックの正規表現書いて、ものすごい長いアドレスが来た時に落としたのはいい思い出(よくない

[zilog80]

javaのAPIってどうも垢抜けないんだよなあ。使い勝手や完成度などの面で。Javaをあまり好きになれない理由の一つ。

[yujiorama]

対数で増えていく時間…怖いな

[dekasasaki]

Javaが対処してくれるのが一番楽だよなあ、と思ってみたりする。

[w1234567]

これぐらいだったら外部ライブラリ使うより自前で解析したほうがいいよね

[uskey]

RE2/Jよいな。用途によって使い分けるのが良さそう。

[decoy2004]

Google 製の RE2/J はバックトラッキングしない。 『マッチにかかる時間が入力文字列に対して線形で済むことを保証してくれており、今回のようにマッチ時間が倍々で増えていくことが無いとしています。』

[masa8aurum]

内容がよく理解できなかったので、また調べながら読む。

[ymori76]

ほーう。。メモメモ。

[naga_sawa]

Javaの正規表現エンジンはパターンによってはバックトラック走って重くなる場合がある

[mas-higa]

本の宣伝だった!!

[airj12]

「バックトラッキングを用いた正規表現エンジンはほとんどの場合にはうまく動きますが、稀に今回のようにマッチに膨大な時間がかかってしまうことがあります。」その辺をもうちょっと詳しく…(自分で考えろ

[kimutansk]

単にマッチングさせるだけなら、後方参照は不要ですからね。最初からそれがオミットされているなら納得な結果ではあります。

[waman]

『結論から言うと、今回の現象の原因はアンダースコアでした。』『RE2/J』

[kuxttoba]

良い正規表現ライフ…

[rryu]

\wはロケールとかで内容が変わるから[a-zA-Z]の代わりに使うのは不適切な気がする。

[stealthinu]

javaの正規表現で遅くなる場合の話。そういう場合でもGoogleのRE2/Jだと速いんだそうな。

[kabochatori]

本筋とずれるかもだけど、"@"で分割してからマッチングしたほうがいいと思う。

[tsekine]

https://github.com/google/re2/blob/master/doc/syntax.txt RE2J も多分一緒。

[papiro]

単語区切りの表現とアンダースコア_に注意

[easy-breezy]

欲しいとこを取る、ってことばかりでパフォーマンスを意識したことがなかった...

[t-murachi]

Java って PCRE 使ってるんじゃなかったっけ? 後読みアサーションで解決できないん? あと \w って Unicode 環境だと半角英数字以外のあらゆる言語のアルファベットにマッチしそうな悪寒が… (調べずに書いてます)

[ginzi009]

遅いッ！遅すぎるッ！Java の正規表現のお話。

[surume000]

googleありがとう

[kotesaki]

正規表現もライブラリによりこれだけ実行時間が違うんだなー

[jewel12]

("______________________________")

[babydaemons]

さすが、Google先生！ "In the worst case, the java.util.regex matcher may run forever, or exceed the available stack space and fail; this will never happen with RE2/J."

[a2ikm]

\wが_を含むの初めて知った。見慣れないからだいたい\w使わずに[]で列挙してた

[raimon49]

RE2/J　もともとの原因は、標準ライブラリの正規表現パターン\wの中にアンダースコアも含めれていることだった

[tachesimazzoca]

https://swtch.com/~rsc/regexp/regexp1.html

[clavier]

遅いッ！遅すぎるッ！Java の正規表現のお話。 | Cybozu Inside Out | サイボウズエンジニアのブログ