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;}
    </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>現在, PythonやRuby等の高度なデータ型を組み込みで備えた, インタプリタ型言語の開発が発達してきている.</li>
          <li>
            しかし, 高い性能を必要とされるプログラムは, C言語等のコンパイル型言語による開発が主となっている.<br/>
            これは, コンパイラの高度に発達した最適化の恩恵を受けれるからである.
          </li>
          <li>プログラムの開発は, 可読性・開発効率の高い高級な言語によって行われることが開発者にとって望ましい.</li>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>研究目的と背景 (2)</h1>
        <ul>
          <li>開発効率高い言語によって記述した生成系から, より低級な言語のコードを生成するプログラミング手法として生成的プログラミングがある.</li>
          <li>この手法では, 生成系を高級な言語で実装しても, 最終的にはコンパイルされたプログラムとなるので性能を保ったまま<blue>開発効率に優れるという</blue>利点がある.</li>
          <li class="incremental">本研究では生成的プログラミングの有効性を評価するために, 正規表現からC言語等のコードを生成する正規表現評価器の実装を行った.</li>
          <li class="incremental"></li>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>正規表現とは</h1>
        <ul>
          <li>テキストのパターンマッチング記法.</li>
          <p>ex: "<blue>(A|B)*C</blue>" -> "A"または"B", の0回以上の繰り返し直後に"C"</p>
          <li>GNU grep などのテキスト検索ツールや各言語のライブラリで利用されている.</li>
          <br/><br/>
          <li class="incremental">正規表現は等価なDFA(決定性有限オートマトン)に変換可能.</li>
          <li class="incremental">状態遷移を関数遷移で表現することで, C言語等のコードに変換を行った.</li>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>本実装の特徴</h1>
        <ul>
          <li>生成系は<strong>Python</strong>で実装.</li>
          <li>正規表現の<strong>連接</strong>, <strong>集合和</strong>, <strong>閉包</strong> の基本演算に対応.</li>
          <li>DFAの状態遷移に対応した, 関数遷移を行うコードを生成.</li>
          <img src="pix/flow.png" style="height: 7em;"/>
          <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の状態数に比例.</li>
          <img src="pix/bench_translation.png" style="height: 12em;"/>
          <li class="incremental">通常の正規表現の変換では<strong>数十~数百ms</strong>程度.</li>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>DFAからのコード生成</h1>
        <ul>
          <li>DFAによるマッチングを行うコードを生成.</li>
          <li><blue>C</blue>, <blue>CbC</blue>, <blue>LLVM-IR</blue> それぞれのコードを生成する生成系を実装した.</li>
          <img src="pix/flow.png" style="height: 7em;"/>
          <li class="incremental">それぞれ, 最終的に生成されるコードの性能を比較.</li>
        </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(Continuation based C)は</li>
          <ul>
            <li>関数よりも小さなプログラミング単位として<strong>コードセグメント</strong>を持つ.</li>
            <li>コードセグメントによる<strong>継続</strong>を基本としたCの下位言語である.</li>
            <li>GCC を拡張する形で実装されており, 継続をGCCの末尾呼び出し最適化を強制することで実現している.</li>
          </ul>
          <li>CbCでも, 前節で紹介したCと同様に生成を行ったが, 関数ではなくコードセグメントを用いている.</li>
          <li>DFAの遷移は継続的な処理であり, CbCではそれを明示的に記述できる.</li>
        </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>コンパイル速度</li>
          <li><red>テーブル</red></li>
          <img src="" style="height: 7em;"/>
          <li>中間表現を直接操作できるLLVMがC言語のコンパイルに比べて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>
        </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>
            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 class="incremental">ここでいう"複雑さ"とは, DFAに変換した時の分岐の多さで定義する.</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>
        </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">DFAの状態遷移がネックとなる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>: 3000行 (テスト含む全コード)</td></tr>
            <tr><th><blue>GNU grep (C)</blue></th><td>: 15000行 (コアのみ)</td></tr>
            </table>
          <li>最終的に得られた正規表現評価器の性能は, GNU grep に勝る部分もあり, 性能も非常に高いものであった.</li>
        </ul>
      </div>
      <!-- PAGE -->
      <div class="slide">
        <h1>今後の課題</h1>
        <ul>
          <li>固定文字列フィルタリング(Boyer-Moore等)の実装.</li>
          <li>バックリファレンスの実装.</li>
        </ul>
      </div>
    </div>
  </body>
</html>
author	Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date	Sun, 12 Sep 2010 08:57:34 +0900
parents	b3b5bcbba089
children	54987da33049