Google Chrome、正規表現を独自実装で高速化

後藤大地　 [2009/02/06]

Chromium - News and developments from the open source browser project

開発者向けに公開されたGoogle Chrome 2.0.160.0で、正規表現の実装が新しい実装へ置き換わった。新しい実装はIrregexpと呼ばれている。これはChromeのJavaScript実行速度をさらに高速化するうえで欠かせない取り組みだ。どういった経緯があり正規表現実装を新しくすることになったのか、どういったテクニックを使ったのかがThe Chromium Blog - Irregexp, Google Chrome's New Regexp Implementationにおいて紹介されている。

IrregexpはV8 JavaScriptエンジンをベースに実装された新しい正規表現処理系。主な特徴は次のとおり。

パフォーマンスを引き上げるためにV8 JavaScriptエンジン内部に統合されている
V8インフラストラクチャを活用してメモリ管理機能やネイティブコード生成機能が実装されている
JavaScript Webアプリコーディングでよく使われる正規表現を特に高速に処理するように仕上げられている
100万の有名Webページを対象にして試験を実施し従来の正規表現実装と互換性があることを確認してある

Irregexpは設計思想も特徴的だ。設計の初期の段階で「処理が高速になるならより長い時間をかけてでもコンパイルをする」という設計方針を定め、次の手順で高速化が実施されているという。

正規表現を中間オートマトン形式へ変換する。この形式は正規表現を自然に表現できるうえに扱いやすく、分析や最適化を実施しやすい
最適化する
ネイティブコードへ変換する。バックトラッキングを使っているが、これは時間がかかるため最小限になるように工夫はしてある。このあたりの実装は今後の課題

V8 JavaScriptエンジンの従来の正規表現実装は、すでに広く使われているPCRE系の実装が採用されていた。JSCREがそれだが、これはWebKitプロジェクトがPCREをベースにJavaScript向けに仕上げなおした実装だ。現状使われている正規表現と互換性があり問題も少ない。しかしパフォーマンス改善に取り組み始めると正規表現処理の遅さが目立つようになり、最終的に外部のライブラリを使うのではなく、IrregexpのようにV8エンジンに統合された新しい正規表現実装を開発することになったという。WebKitの高速化に取り組んでいるSquirrelFishのチームも似たような取り組みを実施している。