# HG changeset patch
# User Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
# Date 1294378616 -32400
# Node ID 107d09e097d8c927759a1fce487ff52ba4360e45
# Parent  59d695a30f5ed9877cdf5a1ea90873bb696cc5fb
add appendix.

diff -r 59d695a30f5e -r 107d09e097d8 presen/index.html
--- a/presen/index.html	Thu Jan 06 23:49:31 2011 +0900
+++ b/presen/index.html	Fri Jan 07 14:36:56 2011 +0900
@@ -28,6 +28,7 @@
       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>
@@ -39,12 +40,12 @@
       <div id="header"></div>
       <div id="footer">
         <h1>Implimentation of Regular Expression Engine with Dynamic Code Generation.</h1>
-        <h2>ソフトウェア科学会; 2010/10/14</h2>
+        <h2>プログラミングシンポジウム; 2011/ 1/ 9</h2>
       </div>
     </div>
     <div class="presentation">
       <div class="slide">
-        <h1>動的なコード生成を用いた<br/>正規表現評価器の実装</h1>
+        <h1>動的なコード生成を用いた<br/>正規表現マッチャの実装</h1>
         <h3>新屋 良磨, 河野 真治</h3>
         <h4><a href="http://ie.u-ryukyu.ac.jp/" rel="external">琉球大学 並列信頼研究室</a></h4>
         <div class="handout"></div>
@@ -53,42 +54,81 @@
       <div class="slide">
         <h1>研究目的と背景 (1)</h1>
         <ul>
-          <li>正規表現は, パターンマッチによるテキストの検索等に利用されている.</li>
-          <li>シンプルで保守性に優れ, かつ性能の高い正規表現マッチャを実装したい. </li><br/>
-          <li class="incremental">プログラムの開発は, 生産性の高い言語によって行われることが開発者にとって望ましい.</li>
-          <li class="incremental">開発効率 or 実行効率 ?</li><span class="incremental"></span>
+          <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>
+          <li>シンプルで保守性に優れ, かつ性能の高い正規表現エンジンの実装が望ましい. </li><br/>
+          <li>生産性の高い言語によって実装したプログラム(生成系)から, 抽象度が低く性能の高い言語(CbC/C/Assembly)のコード生成を行うプログラミング手法がある.</li>
           <li>この手法では, <blue>性能を保ったまま開発効率に優れるという</blue>利点がある.</li><br/>
-          <li class="incremental">そこで本研究では, 与えられた正規表現を認識するコード(C言語等の)を生成する正規表現評価器の実装を行った.</li><span class="incremental"></span>
+          <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">正規表現は(NFAを経て)等価なDFA(決定性有限オートマトン)に変換可能.</li>
-          <li class="incremental">主張: DFAは直接コードで表現できる.</li><span class="incremental"></span>
+          <li class="incremental">正規表現は等価なDFA(決定性有限オートマトン)に変換可能.</li>
+          <li class="incremental">主張: DFAによる状態遷移は, CbCによる記述が適している.</li><span class="incremental"></span>
         </ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-        <h1>本実装の特徴</h1>
+        <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>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>
@@ -103,6 +143,7 @@
         </ul>
       </div>
       <!-- PAGE -->
+      <!--
       <div class="slide">
         <h1>DFA変換のコスト</h1>
         <ul>
@@ -111,6 +152,7 @@
           <img src="pix/bench_translation.png" style="height: 12em;"/>
         </ul>
       </div>
+      -->
       <!-- PAGE -->
       <div class="slide">
         <h1>DFAからのコード生成</h1>
@@ -153,20 +195,7 @@
       </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>
+        <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;">
@@ -213,7 +242,7 @@
         <ul>
           <li>コンパイル速度<br/>
           表: N個の単語の集合和から生成されたコードのコンパイル時間 (<blue>最適化有り(O3)</blue>).</li>
-          <table id="tbcom">
+          <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>
@@ -247,8 +276,8 @@
             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>
+            <tr><th><blue>http-url-regex</blue></th><td>: RFC定義のURL正規表現</td></tr>
             </table>
             <p class="incremental">"複雑さ" = 変換されたDFAの状態数/遷移規則の多さ.</p>
           </li>
@@ -282,12 +311,12 @@
           <li>
             <strong>fixed-string</strong> - 固定文字列でのマッチング<br/>
             パターン　: "<blue>Wikipedia</blue>" - <a href="pix/fixed-string.png" target="blank">図</a><br/>
-            マッチ行数: 348936行<br/><br/>
+            マッチ行数: 348936行<br/><br/><br/><br/><br/><br/>
             マッチ時間:
           </li>
-          <table id="tbcom" style="margin: auto;">
+          <table class="tbl" style="margin: auto;">
             <tr>
-              <th>本実装</th><th>GNU grep</th><th>cgrep</th><th>Google RE2</th>
+              <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>
@@ -296,36 +325,36 @@
         </ul>
       </div>
       <div class="slide">
-        <h1>ベンチマーク: simple-regex</h1>
-        <ul>
-          <li>
-            <strong>simple-regex</strong> - 単純な正規表現でのマッチング<br/>
-            パターン　: "<blue style='font-size: 70%;'>(Python|Perl|Pascall|Prolog|PHP|Ruby|Haskell|Lisp|Scheme)</blue>" - <a href="pix/complex-regex.png" target="blank">図</a><br/>
-            マッチ行数: 15030行<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>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>ベンチマーク: complex-regex</h1>
         <ul>
           <li>
             <strong>complex-regex</strong> - 複雑な正規表現でのマッチング<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>" - <a href="pix/complex-regex.png" target="blank">図</a><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>
+              <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>
@@ -340,27 +369,15 @@
           <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>最終的に得られた正規表現評価器の性能は, GNU grep に勝るテストケースもあり, 性能も良い.</li>
+          <li>最終的に得られた正規表現評価器の性能は, どのテストケースにおいても 他のgrep より 2~20倍, ほど高速な結果がでており, 性能は非常に高い.</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>コード生成の最適化, 生成手法の評価.</li>
-        </ul>
-      </div>
-      <!-- PAGE -->
-      <div class="slide">
         <h1>展望</h1>
         <ul>
           <li>grep 以外のソフトウェアへの応用</li>
@@ -375,7 +392,16 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-        <h1>付録: UTF-8</h1>
+        <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>
@@ -394,6 +420,7 @@
           <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>