Mercurial > hg > Papers > 2010 > jsst-shinya

<?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>Implimentation 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;}
    </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>Implimentation of Regular Expression Engine with Dynamic Code Generation.</h1>
        <h2>ソフトウェア科学会; 2010/10/14</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>正規表現は, パターンマッチによるテキストの検索等に利用されている.</li>
          <li>シンプルで保守性に優れ, かつ性能の高い正規表現マッチャを実装したい. </li><br/>
          <li class="incremental">プログラムの開発は, 生産性の高い言語によって行われることが開発者にとって望ましい.</li><span class="incremental"></span>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>研究目的と背景 (2)</h1>
        <ul>
          <li>生産性の高い言語によって実装したプログラム(生成系)から, 抽象度が低く性能の高い言語のコード生成を行うプログラミング手法がある.</li>
          <li>この手法では, <blue>性能を保ったまま開発効率に優れるという</blue>利点がある.</li><br/>
          <li class="incremental">そこで本研究では, 与えられた正規表現を認識するコード(C言語等の)を生成する正規表現評価器の実装を行った.</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">正規表現は(NFAを経て)等価なDFA(決定性有限オートマトン)に変換可能.</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</strong>で実装.</li>
          <li>正規表現の<strong>連接</strong>, <strong>集合和</strong>, <strong>閉包</strong> の基本演算に対応.<br/>
          <span class="incremental">"<blue>(A|B)*C</blue>" -> [[[AとBの集合和]の閉包]とCの連接]</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> (1)</a></h1>
        <ul>
          <li>CbC(Continuation based C)は</li>
          <ul>
            <li>関数よりも小さなプログラミング単位として<strong>コードセグメント</strong>を持つ.</li>
            <li>コードセグメントによる<strong>継続</strong>を基本としたCの下位言語である.</li>
            <li>CbCコンパイラがGCCを拡張する形で実装されている.</li>
          </ul>
          <li class="incremental">DFAの遷移は継続的な処理であり, CbCではそれを明示的に記述できる.</li>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>コード生成: <a href="code/reg.cbc.txt" target="blank"><red>CbC</red></a> (2)</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>
          <img src="" style="height: 7em;"/>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>生成系の比較 (1)</h1>
        <ul>
          <li>コンパイル速度<br/>
          表: N個の単語の集合和から生成されたコードのコンパイル時間 (<blue>最適化有り(O3)</blue>).</li>
          <table id="tbcom">
            <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>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>生成系の比較 (2)</h1>
        <ul>
          <li>コンパイルされたプログラムの実行速度</li>
          <ul>
            <li>C/CbC/LLVM-IRをコンパイルしたプログラムの実行速度に, あまり差がでなかった.</li>
            <li class="incremental">3つの生成系は, 生成する言語が違うが, 生成するコードの処理内容は同じ.</li>
          </ul>
          <li class="incremental">生成されたコードは, 関数呼び出しとswitch文によるシンプルなプログラムなので, 最適化によって性能の等しいネイティブコードが生成されたためと思われる.</li>
          <li class="incremental">CbCでは, 関数呼び出しより軽量な状態遷移である継続を用いて実装しているため, コンパイラの最適化に依らず性能の高いコードが保証されている.</li>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>性能評価: vs GNU grep.</h1>
        <ul>
          <li>本実装により生成したCコードとGNU grep 2.6.3/2.5.4 の検索時間を計測(変換/コンパイル時間も含む).</li>
          <li>生成コード, GNU grep は共にGCC 4.4.1(-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>simple-regex</blue></th><td>: 単純な正規表現</td></tr>
            <tr><th><blue>complex-regex</blue></th><td>: 複雑な正規表現</td></tr>
            </table>
          </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>テストケース</h1>
        <ul>
          <li>
            <strong>fixed-string</strong> - 固定文字列でのマッチング<br/>
            パターン　: "<blue>Wikipedia</blue>"<br/>
            マッチ行数: 348936行
          </li>
          <li>
            <strong>simple-regex</strong> - 単純な正規表現でのマッチング<br/>
            <span class="incremental">Wikipediaの記事のカテゴリタグ記述にマッチ</span><br/>
            パターン　: "<blue>^\*+ \[\[</blue>"<br/>
            マッチ行数: 1503行
          </li>
          <li>
            <strong>complex-regex</strong> - 複雑な正規表現でのマッチング<br/>
            パターン　: "<blue>(Python|Perl|Pascall|Prolog|PHP|Ruby|Haskell|Lisp|Scheme)</blue>"<br/>
            マッチ行数: 3439028行
          </li>
          <li class="incremental">"複雑さ" = DFAに変換時の分岐の多さ.</li>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>性能評価: 結果</h1>
        <img src="pix/bench_grep.png" style="height: 11em;"/>
        <ul>
          <li class="incremental">fixed-stringでは, 固定文字列フィルタの差が大きい.</li>
          <li class="incremental">complex-regexでは, 本実装がGNU grepより高速な結果を出した.</li>
        </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>GNU grep (C)</blue></th><td>: 15000行 (コアのみ)</td></tr>
            </table>
          <li>最終的に得られた正規表現評価器の性能は, GNU grep に勝るテストケースもあり, 性能も良い.</li>
          <li class="incremental">目的: シンプルで保守性に優れ, かつ性能の高い正規表現マッチャを実装したい.</li>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>今後の課題</h1>
        <ul>
          <li>正規表現評価器の機能強化</li>
          <ul>
            <li>固定文字列フィルタリング(Boyer-Moore等)や後方参照の実装等.</li>
            <li>後方参照: "(A*)B\1" -> "\1"は(A*)でマッチした文字列.</li>
            <li class="incremental">本実装は関数遷移によるマッチングを行うので, バックトラック処理を容易に記述できる.</li>
          </ul>
          <li>grep 以外のソフトウェアへの応用</li>
          <ul>
            <li>一度コンパイルすればマッチングを行うネイティブコードが得られる.</li>
            <li>同様のパターンで何度もマッチングを行うプログラムと相性が良い.</li>
            <li class="incremental">スパムフィルタの単語検索など.</li>
          </ul>
        </ul>
      </div>
    </div>
  </body>
</html>
author	Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date	Mon, 13 Sep 2010 08:42:47 +0900
parents	627af8b88d16
children	890d3517870a