「世界最速のgrep作ってみたよ」

by 新屋 良磨
(twitter:sinya8282)



琉球大学 並列信頼研究室

本当です.


最近...

最近......

そんなこんなでXhago



「よろしい, ならばLTだ.」

大事なので二度.

発表内容

正規表現とは

正規表現とは - 補足

実装はおいといて.

ベンチマーク対象


僕の実装僕の実装
GNU grep (2.7)UNIXコマンドの代表. 10年以上の歴史を持つ(ぽい).
Google RE2 (changeset 43)Google 謹製正規表現エンジン. 2010年リリース.
鬼車 (5.9.2)Ruby 1.9~ 標準搭載の正規表現エンジン.
PCRE (8.12)Perl 標準搭載の正規表現エンジン.

追記 鬼車, RE2は grep frontend(with mmap) を実装しました. -> http://github.com/sinya8282/grep-frontend

性能評価: vs other engine.

ベンチマーク: fixed-string

ベンチマーク: complex-regex

ベンチマーク: http-url-regex

PCREの場合出力だけ3行少なかった(バグ?).

Why?



なんでこんなに速いの?

高速なワケ.

正規表現エンジンの実装

STOP!


詳しくはWebで!卒論で!

第52回プログラミング・シンポジウムでの発表資料.

一気に結論.

Continuation based C

駆け足ですが... まとめ

appendix: GNU grep の(コアな)小ネタ

appendix: UTF-8

appendix: UTF-8