Mercurial > hg > Papers > 2011 > prosym-shinya
view presen/index.html @ 13:db808a9e7df9 default tip
typo: Implimentation -> Implementation.
| author | Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 19 Feb 2011 10:47:40 +0900 |
| parents | 107d09e097d8 |
| children |
line wrap: on
line source
<?xml version="1.0" encoding="utf-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" lang="ja" xml:lang="ja"> <head> <title>Implementation of Regular Expression Engine with Dynamic Code Generation.</title> <!-- metadata --> <meta name="generator" content="S5" /> <meta name="version" content="S5 1.1" /> <meta name="presdate" content="20101014" /> <meta name="author" content="Ryoma SHINYA" /> <meta name="company" content="University of the Ryukyu" /> <!-- configuration parameters --> <meta name="defaultView" content="slideshow" /> <meta name="controlVis" content="hidden" /> <!-- style sheet links --> <link rel="stylesheet" href="ui/default/slides.css" type="text/css" media="projection" id="slideProj" /> <link rel="stylesheet" href="ui/default/outline.css" type="text/css" media="screen" id="outlineStyle" /> <link rel="stylesheet" href="ui/default/print.css" type="text/css" media="print" id="slidePrint" /> <link rel="stylesheet" href="ui/default/opera.css" type="text/css" media="projection" id="operaFix" /> <!-- embedded styles --> <style type="text/css" media="all"> .imgcon {width: 525px; margin: 0 auto; padding: 0; text-align: center;} #anim {width: 270px; height: 320px; position: relative; margin-top: 0.5em;} #anim img {position: absolute; top: 42px; left: 24px;} img#me01 {top: 0; left: 0;} img#me02 {left: 23px;} img#me04 {top: 44px;} img#me05 {top: 43px;left: 36px;} #tbcom td, #tbcom th, #tbcom {border: 1px solid black; padding: 2px;} .tbl td, .tbl th, .tbl {border: 1px solid black; padding: 2px;} </style> <!-- S5 JS --> <script src="ui/default/slides.js" type="text/javascript"></script> </head> <body> <div class="layout"> <div id="controls"><!-- DO NOT EDIT --></div> <div id="currentSlide"><!-- DO NOT EDIT --></div> <div id="header"></div> <div id="footer"> <h1>Implementation of Regular Expression Engine with Dynamic Code Generation.</h1> <h2>プログラミングシンポジウム; 2011/ 1/ 9</h2> </div> </div> <div class="presentation"> <div class="slide"> <h1>動的なコード生成を用いた<br/>正規表現マッチャの実装</h1> <h3>新屋 良磨, 河野 真治</h3> <h4><a href="http://ie.u-ryukyu.ac.jp/" rel="external">琉球大学 並列信頼研究室</a></h4> <div class="handout"></div> </div> <!-- PAGE --> <div class="slide"> <h1>研究目的と背景 (1)</h1> <ul> <li>当研究室では, 継続を基本としたプログラミング言語 Continuation based C (CbC)を開発している.</li> <li>この言語は, Cから関数呼び出しや for ループ制御などを」覗き, 同等の動作はすべて継続でを用いて実現することで, Cよりも細かい動作を可能にしている. </li><br/> <li class="incremental">本研究では, CbC の特徴を生かす例題として, 正規表現エンジンに着目した.</li><span class="incremental"></span> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>研究目的と背景 (2)</h1> <ul> <li>シンプルで保守性に優れ, かつ性能の高い正規表現エンジンの実装が望ましい. </li><br/> <li>生産性の高い言語によって実装したプログラム(生成系)から, 抽象度が低く性能の高い言語(CbC/C/Assembly)のコード生成を行うプログラミング手法がある.</li> <li>この手法では, <blue>性能を保ったまま開発効率に優れるという</blue>利点がある.</li><br/> <li class="incremental">そこで本研究では, 与えられた正規表現を認識するCbCによって記述されたソースコードを生成する正規表現エンジンの実装を行った.</li><span class="incremental"></span> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>発表内容</h1> <ol> <li>CbC の紹介</li> <li>コード生成による正規表現エンジンの実装法</li> <li>比較検証(grep)</li> <li>まとめ</li> </ol> </div> <!-- PAGE --> <div class="slide"> <h1>Continuation based C (1)</h1> <h2><b>状態遷移記述をベースとした、より細かい単位でのプログラミングを実現する.</b></h2><br/> <ul> <li>環境を保持しない継続、軽量継続を導入. 軽量継続で状態遷移が明確になる.</li> <li>C言語などの関数よりも小さなプログラミング単位として, コードセグメントを持つ.</li> <li>関数 > コードセグメント > ステートメント</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>Continuation based C (2)</h1> <h2><b>継続</b></h2> <ul> <li>現在の処理を続行するための情報.</li> <ul> <li>Cならば続く命令のアドレスや,</li> <li>命令に必要な値,</li> <li>スタックなど, その環境すべてを含む.</li> </ul> </ul><br/> <h2><b>CbCの軽量継続</b></h2> <ul> <li>継続からスタックに関する情報を落とす.</li> <li>続く命令とデータのみのシンプルな継続.</li> <li class="incremental">軽量継続によって, より高度に最適化された状態遷移によるプログラミングが可能. -> <b>正規表現</b></li><span class="incremental"></span> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>正規表現とは</h1> <ul> <li>テキストのパターンマッチング記法.</li> <p>ex: "<blue>(A|B)*C</blue>" -> "A"または"B", の0回以上の繰り返し直後に"C"<span class="incremental">: "C","ABC","ABBBBC"</span></p> <li>GNU grep などのテキスト検索ツール等で利用されている.</li> <br/><br/> <li class="incremental">正規表現は等価なDFA(決定性有限オートマトン)に変換可能.</li> <li class="incremental">主張: DFAによる状態遷移は, CbCによる記述が適している.</li><span class="incremental"></span> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>正規表現マッチャの実装</h1> <ul> <li>DFAの状態遷移に対応した, <strong>関数遷移</strong>を行うコードを生成.</li> <img src="pix/flow.png" style="height: 7em;"/> <li>生成系は<strong>Python, CbC</strong>で実装.</li> <li>正規表現の<strong>連接</strong>, <strong>集合和</strong>, <strong>閉包</strong> の基本演算及びいくつかの拡張記法に対応. <span class="incremental">例: "<blue>(A|B)*CD+[0-9]?</blue>"</span></li> <li>マルチバイト文字: <strong>UTF-8</strong> に対応(内部コード).</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>正規表現からDFAへの変換</h1> <ul> <li>正規表現を等価な<red>NFA</red>に変換.</li> <li>NFAを部分集合構成法を用いて<red>DFA</red>に変換.</li> <p>図: 正規表現"<blue>(A|B)*C</blue>"と等価なDFA</p> <img src="pix/dfa.png" style="height: 7em;"/> </ul> </div> <!-- PAGE --> <!-- <div class="slide"> <h1>DFA変換のコスト</h1> <ul> <li>DFAへの変換コストを, 正規表現中の単語数で計測.<br/><br/> <span class="incremental">図: N個の単語の集合和からDFAへの変換時間.</span></li> <img src="pix/bench_translation.png" style="height: 12em;"/> </ul> </div> --> <!-- PAGE --> <div class="slide"> <h1>DFAからのコード生成</h1> <ul> <li>DFAによる状態遷移を<strong>関数遷移</strong>で行うコードを生成.</li> <li><blue>C</blue>, <blue>CbC</blue>, <blue>LLVM-IR</blue> それぞれのコードを生成する生成系を実装した.</li> <img src="pix/flow.png" style="height: 7em;"/> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>コード生成: <a href="code/reg.c.txt" target="blank"><red>C</red></a></h1> <ul> <li>DFAによる状態遷移を, 関数遷移として表現.</li> <li>入力文字列による分岐は<strong>switch文</strong>, 状態遷移は<strong>関数遷移</strong>.<br/> <pre style="font-size: 0.6em;"> /* "<blue>(A|B)*C</blue>"に対応するCコード. /* int state_1(unsigned char* s) { switch(*s++) { case 0: /* match */ return accept(s); default: return reject(s); } } int state_0(unsigned char* s) { switch(*s++) { case 65: /* match A */ return state_0(s); case 66: /* match B */ return state_0(s); case 67: /* match C */ return state_1(s); default: return reject(s); } } </pre> </li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>コード生成: <a href="code/reg.cbc.txt" target="blank"><red>CbC</red></a></h1> <ul> <li>CbCでも, 前節で紹介したCと同様に生成を行ったが, 関数ではなくコードセグメントを用いている.</li> <pre style="font-size: 0.6em;"> /* "<blue>(A|B)*C</blue>"に対応するCコード. /* __code state_1(unsigned char *s) { switch(*s++) { case 0: /* match */ goto accept(s); default: goto reject(s); } } __code state_0(unsigned char *s) { switch(*s++) { case 65: /* match A */ goto state_0(s); case 66: /* match B */ goto state_0(s); case 67: /* match C */ goto state_1(s); default: goto reject(s); } } </pre> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>コード生成: <a href="code/reg.ll.txt" target="blank"><red>LLVM-IR</red></a></h1> <ul> <li>LLVM(Low Level Virtual Machine)は</li> <ul> <li>構文解析やコード生成など, 機能単位で再利用可能なコンパイラ基盤.</li> <li>様々な最適化が実装されている.</li> <li>LLVM内部表現であるLLVM-IRを, 直接操作するAPIが提供されている.</li> </ul> <li>Cと同様な処理を行うコードを, LLVM-IRを直接操作して生成.</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>生成系の比較 (1)</h1> <ul> <li>コンパイル速度<br/> 表: N個の単語の集合和から生成されたコードのコンパイル時間 (<blue>最適化有り(O3)</blue>).</li> <table class="tbl"> <tr><th>N (単語数)</th><td>1</td><td>10</td><td>100</td></td> <tr><th><strong>C (GCC)</strong></th><td>0.34s</td><td>0.78s</td><td>4.27s</td></td> <tr><th><strong>CbC (GCC)</strong></th><td>0.75s</td><td>1.03s</td><td>9.43s</td></td> <tr><th><strong>LLVM-IR (LLVM)</strong></th><td>0.044s</td><td>0.08s</td><td>0.47s</td></td> </table> <li>LLVMによるコンパイルが, GCCによるコンパイルに比べ10倍程高速な結果がでた.</li> <li class="incremental">主張: コンパイル速度はあまり重要でない.</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>生成系の比較 (2)</h1> <ul> <li>コンパイルされたプログラムの実行速度</li> <ul> <li>C/CbC/LLVM-IRをコンパイルしたプログラムの実行速度に, あまり差がでなかった.</li> <li>3つの生成系は, 生成する言語が違うが, 生成するコードの処理内容は同じ.</li> </ul> <li class="incremental">生成されたコードは, 関数呼び出しとswitch文によるシンプルなプログラムなので, 最適化によって性能の等しいネイティブコードが生成されたためと思われる.</li> <li class="incremental">CbCでは, 関数呼び出しより軽量な状態遷移である継続を用いて実装しているため, コンパイラの最適化に依らず性能の高いコードが保証されている -> 生成コードとして最適.</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>性能評価: vs other grep.</h1> <ul> <li>本実装により生成したCbCコードとGNU grep 2.7, Google RE2, cgrep との検索時間を計測(変換/コンパイル時間も含む).</li> <li>生成コード, GNU grep は共にGCC 4.5.0(-O3) でコンパイル.</li> <li>検索テキスト: Wikipedia 日本語版全記事 (UTF-8, 8000万行) </li> <li> 3つのパターンによるベンチマーク.<br/> <table> <tr><th><blue>fixed-string</blue></th><td>: 固定文字列</td></tr> <tr><th><blue>complex-regex</blue></th><td>: 複雑な正規表現</td></tr> <tr><th><blue>http-url-regex</blue></th><td>: RFC定義のURL正規表現</td></tr> </table> <p class="incremental">"複雑さ" = 変換されたDFAの状態数/遷移規則の多さ.</p> </li> <!-- <li>実験環境.</li><br/> <table style="border: solid black 1px;"> <tr> <th style="border: solid black 1px;">CPU</th> <td style="border: solid black 1px;">Intel Core i7 950 @3.0GHz</td> </tr> <tr style="border: solid black 1px;"> <th style="border: solid black 1px;">Memory</th> <td style="border: solid black 1px;">16GB</td> </tr> <tr style="border: solid black 1px;"> <th style="border: solid black 1px;">Compiler</th> <td style="border: solid black 1px;">GCC 4.4.1</td> </tr> <tr style="border: solid black 1px;"> <th style="border: solid black 1px;">Text</th> <td style="border: solid black 1px;">Wikipedia 日本語版全記事<br/>XML, UTF-8, 4.7GB (8000万行)</td> </tr> </table> --> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>ベンチマーク: fixed-string</h1> <ul> <li> <strong>fixed-string</strong> - 固定文字列でのマッチング<br/> パターン : "<blue>Wikipedia</blue>" - <a href="pix/fixed-string.png" target="blank">図</a><br/> マッチ行数: 348936行<br/><br/><br/><br/><br/><br/> マッチ時間: </li> <table class="tbl" style="margin: auto;"> <tr> <th>本実装</th><th>GNU grep</th><th> cgrep </th><th>Google RE2</th> </tr> <tr> <td>1.57(+0.12) s</td><td>2.59 s</td><td>1.89 s</td><td>30.10 s</td> </tr> </table> </ul> </div> <div class="slide"> <h1>ベンチマーク: complex-regex</h1> <ul> <li> <strong>complex-regex</strong> - 複雑な正規表現でのマッチング<br/> パターン : "<blue style='font-size: 80%;'>(Python|Perl|Pascall|Prolog|PHP|Ruby|Haskell|Lisp|Scheme)</blue>" - <a href="pix/complex-regex.png" target="blank">図</a><br/> マッチ行数: 15030行<br/><br/><br/><br/><br/><br/> マッチ時間 </li> <table class="tbl" style="margin: auto;"> <tr> <th>本実装</th><th>GNU grep</th><th> cgrep </th><th>Google RE2</th> </tr> <tr> <td>4.51(+0.41) s</td><td>15.48 s</td><td>6.42 s</td><td>16.83 s</td> </tr> </table> </ul> </div> <div class="slide"> <h1>ベンチマーク: http-url-regex</h1> <ul> <li> <strong>http-url-regex</strong> - RFC定義のURL正規表現<br/> パターン : "<blue style='font-size: 70%;'>http://((([a-zA-Z0-9]|[a-zA-Z0-9][-a-zA-Z0-9]*[a-zA-Z0-9])\.)*([a-zA-Z]|[a-zA-Z][-a-zA-Z0-9]*[a-zA-Z0-9])\.?|[0-9]+\.[0-9]+\.[0-9]+\.[0-9]+)(:[0-9]*)?(/([-_.!~*'()a-zA-Z0-9:@&=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*(;([-_.!~*'()a-zA-Z0-9:@&=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*)*(/([-_.!~*'()a-zA-Z0-9:@&=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*(;([-_.!~*'()a-zA-Z0-9:@&=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*)*)*(\?([-_.!~*'()a-zA-Z0-9;/?:@&=+$,]|%[0-9A-Fa-f][0-9A-Fa-f])*)?)?</blue>"<br/> マッチ行数: 110411行<br/><br/> マッチ時間: </li> <table id="tbcom" style="margin: auto;"> <tr> <th>本実装</th><th>GNU grep</th><th> cgrep </th><th>Google RE2</th> </tr> <tr> <td>2.20(+0.40) s</td><td>51.43 s</td><td>2.62 s</td><td>85.12 s</td> </tr> </table> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>まとめ</h1> <ul> <li>生成系を開発効率に優れた言語であるPythonで実装することで, 少ない記述量で正規表現評価器を実装した.</li> <table> <tr><th><blue>本実装 (Python)</blue></th><td>: 1500行 (C生成系: テストコード含む)</td></tr> <tr><th><blue>本実装 (CbC)</blue></th><td>: 1400行 (C生成系,最小実装)</td></tr> <tr><th><blue>GNU grep (C)</blue></th><td>: 15000行 (コアのみ)</td></tr> </table> <li>最終的に得られた正規表現評価器の性能は, どのテストケースにおいても 他のgrep より 2~20倍, ほど高速な結果がでており, 性能は非常に高い.</li> <li class="incremental">目的: シンプルで保守性に優れ, かつ性能の高い正規表現マッチャを実装したい.</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>展望</h1> <ul> <li>grep 以外のソフトウェアへの応用</li> <ul> <li>正規表現に対して, 検索対象の規模が大きいプログラムと相性が良い.</li> <li>一度コンパイルすればマッチングを行うネイティブコードが得られる.</li> <li>同様のパターンで何度もマッチングを行うプログラムと相性が良い.</li> <li class="incremental">スパムフィルタの単語検索など.</li> </ul> <strong class="incremental">ご清聴ありがとうございました.</strong> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>appendix: 色々な高速化</h1> <ul> <li>生成系自身の高速化 (CbCで書きなおし)</li> <li>スレディッドコード (thanks Mr. Sasada)</li> <li>固定文字列フィルタリング(BMH, Quick-Search, 簡易フィルタ).</li> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>appendix: UTF-8</h1> <ul> <li>Unicodeの符号化形式 -> マルチバイト文字に対応.</li> <li>符号単位は8bit.</li> <li>ASCIIとの互換性を持っている.</li> <li>プログラムでのバイト操作が非常に容易な, 素晴らしい符号化形式.</li> <ul> <li>文字の先頭1ByteでByteが分かる</li> <li>先頭Byteと中間Byteは先頭2bitで判別可能.</li> </ul> </ul> </div> <!-- PAGE --> <div class="slide"> <h1>正規表現: UTF-8</h1> <ul> <li>入力の最小単位として, Unicode文字単位でNFA,DFAを構築すれば良い.</li> <img src="pix/utf-dfa.png" stye="height: 11em;"/> <li class="incremental">GNU grep 2.5.X では, DFAの遷移毎に入力文字に対して mbrtowc() を用いてwchar型への変換を行っている -> ボトルネック (90%以上)</li> <li class="incremental">GNU grep 2.5.X の場合, テストケースcoplex-regex において 190[s] 程かかる(!!) -> 2.6/ 2.7 を使いましょう.</li> </ul> </div> </div> </body> </html>