Mercurial > hg > Papers > 2010 > jsst-shinya

changeset 17:54987da33049

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
edit slide
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Mon, 13 Sep 2010 08:42:47 +0900
parents 627af8b88d16
children 890d3517870a
files presen/fig.graffle presen/index.html presen/pix/fig.numbers presen/pix/flow.png
diffstat 4 files changed, 147 insertions(+), 47 deletions(-) [+]
line wrap: on
line diff
--- a/presen/fig.graffle	Sun Sep 12 08:57:34 2010 +0900
+++ b/presen/fig.graffle	Mon Sep 13 08:42:47 2010 +0900
@@ -37,13 +37,63 @@
 	<key>GraphicsList</key>
 	<array>
 		<dict>
+			<key>Bounds</key>
+			<string>{{49.75, 243}, {209.5, 46}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>Vertical</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>FontInfo</key>
+			<dict>
+				<key>Font</key>
+				<string>HiraKakuProN-W3</string>
+				<key>Size</key>
+				<real>14</real>
+			</dict>
+			<key>ID</key>
+			<integer>68</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540
+{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural
+
+\f0\fs30 \cf0 \'90\'b3\'8b\'4b\'95\'5c\'8c\'bb\'95\'5d\'89\'bf\'8a\'ed (Python)\
+}</string>
+			</dict>
+		</dict>
+		<dict>
 			<key>Class</key>
 			<string>LineGraphic</string>
 			<key>ID</key>
 			<integer>67</integer>
 			<key>Points</key>
 			<array>
-				<string>{422.5, 250}</string>
+				<string>{410.5, 250}</string>
 				<string>{549.5, 250}</string>
 			</array>
 			<key>Style</key>
@@ -140,7 +190,7 @@
 			<array>
 				<dict>
 					<key>Bounds</key>
-					<string>{{421.5, 228}, {115, 23}}</string>
+					<string>{{406.5, 228}, {145, 23}}</string>
 					<key>Class</key>
 					<string>ShapedGraphic</string>
 					<key>FitText</key>
@@ -177,7 +227,7 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural
 
-\f0\fs30 \cf0 \'90\'b3\'8b\'4b\'95\'5c\'8c\'bb\'95\'5d\'89\'bf\'8a\'ed}</string>
+\f0\fs30 \cf0 \'90\'b3\'8b\'4b\'95\'5c\'8c\'bb\'95\'5d\'83\'7d\'83\'62\'83\'60\'83\'83}</string>
 					</dict>
 					<key>Wrap</key>
 					<string>NO</string>
@@ -891,13 +941,20 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{68, 155}, {173, 24}}</string>
+			<string>{{101.5, 152.5}, {106, 24}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
 			<string>YES</string>
 			<key>Flow</key>
 			<string>Resize</string>
+			<key>FontInfo</key>
+			<dict>
+				<key>Font</key>
+				<string>HiraKakuProN-W3</string>
+				<key>Size</key>
+				<real>16</real>
+			</dict>
 			<key>ID</key>
 			<integer>7</integer>
 			<key>Shape</key>
@@ -928,14 +985,14 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural
 
-\f0\fs32 \cf0 \'83\'52\'81\'5b\'83\'68\'90\'b6\'90\'ac\'8c\'6e(Python)}</string>
+\f0\fs32 \cf0 \'83\'52\'81\'5b\'83\'68\'90\'b6\'90\'ac\'8c\'6e}</string>
 			</dict>
 			<key>Wrap</key>
 			<string>NO</string>
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{168, 59}, {81, 39}}</string>
+			<string>{{169, 11}, {81, 39}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1095,7 +1152,7 @@
 		</dict>
 	</array>
 	<key>ModificationDate</key>
-	<string>2010-09-11 12:17:03 +0900</string>
+	<string>2010-09-13 02:47:50 +0900</string>
 	<key>Modifier</key>
 	<string>ryoma</string>
 	<key>NotesVisible</key>
@@ -1163,7 +1220,7 @@
 		<key>Frame</key>
 		<string>{{134, 39}, {1033, 707}}</string>
 		<key>VisibleRegion</key>
-		<string>{{-244, 0}, {1018, 593}}</string>
+		<string>{{-243, 0}, {1018, 593}}</string>
 		<key>Zoom</key>
 		<real>1</real>
 	</dict>
--- a/presen/index.html	Sun Sep 12 08:57:34 2010 +0900
+++ b/presen/index.html	Mon Sep 13 08:42:47 2010 +0900
@@ -27,6 +27,7 @@
       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>
@@ -52,22 +53,18 @@
       <div class="slide">
         <h1>研究目的と背景 (1)</h1>
         <ul>
-          <li>現在, PythonやRuby等の高度なデータ型を組み込みで備えた, インタプリタ型言語の開発が発達してきている.</li>
-          <li>
-            しかし, 高い性能を必要とされるプログラムは, C言語等のコンパイル型言語による開発が主となっている.<br/>
-            これは, コンパイラの高度に発達した最適化の恩恵を受けれるからである.
-          </li>
-          <li>プログラムの開発は, 可読性・開発効率の高い高級な言語によって行われることが開発者にとって望ましい.</li>
+          <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>
-          <li class="incremental">本研究では生成的プログラミングの有効性を評価するために, 正規表現からC言語等のコードを生成する正規表現評価器の実装を行った.</li>
-          <li class="incremental"></li>
+          <li>生産性の高い言語によって実装したプログラム(生成系)から, 抽象度が低く性能の高い言語のコード生成を行うプログラミング手法がある.</li>
+          <li>この手法では, <blue>性能を保ったまま開発効率に優れるという</blue>利点がある.</li><br/>
+          <li class="incremental">そこで本研究では, 与えられた正規表現を認識するコード(C言語等の)を生成する正規表現評価器の実装を行った.</li><span class="incremental"></span>
         </ul>
       </div>
       <!-- PAGE -->
@@ -75,22 +72,22 @@
         <h1>正規表現とは</h1>
         <ul>
           <li>テキストのパターンマッチング記法.</li>
-          <p>ex: "<blue>(A|B)*C</blue>" -> "A"または"B", の0回以上の繰り返し直後に"C"</p>
-          <li>GNU grep などのテキスト検索ツールや各言語のライブラリで利用されている.</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">状態遷移を関数遷移で表現することで, C言語等のコードに変換を行った.</li>
+          <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> の基本演算に対応.</li>
-          <li>DFAの状態遷移に対応した, 関数遷移を行うコードを生成.</li>
-          <img src="pix/flow.png" style="height: 7em;"/>
-          <li>マルチバイト文字: <strong>UTF-8</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 -->
@@ -107,19 +104,18 @@
       <div class="slide">
         <h1>DFA変換のコスト</h1>
         <ul>
-          <li>変換のコストは, DFAの状態数に比例.</li>
+          <li>DFAへの変換コストを, 正規表現中の単語数で計測.<br/><br/>
+              <span class="incremental">図: N個の単語の集合和からDFAへの変換時間.</span></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>DFAによる状態遷移を<strong>関数遷移</strong>で行うコードを生成.</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 -->
@@ -155,21 +151,50 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-        <h1>コード生成: <a href="code/reg.cbc.txt" target="blank"><red>CbC</red></a></h1>
+        <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>GCC を拡張する形で実装されており, 継続をGCCの末尾呼び出し最適化を強制することで実現している.</li>
+            <li>CbCコンパイラがGCCを拡張する形で実装されている.</li>
           </ul>
-          <li>CbCでも, 前節で紹介したCと同様に生成を行ったが, 関数ではなくコードセグメントを用いている.</li>
-          <li>DFAの遷移は継続的な処理であり, CbCではそれを明示的に記述できる.</li>
+          <li class="incremental">DFAの遷移は継続的な処理であり, CbCではそれを明示的に記述できる.</li>
         </ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-        <h1>コード生成: <a href="code/reg.ll.txt" target="blank"><red>LLVM-IR</red></a> *</h1>
+        <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>
@@ -185,10 +210,15 @@
       <div class="slide">
         <h1>生成系の比較 (1)</h1>
         <ul>
-          <li>コンパイル速度</li>
-          <li><red>テーブル</red></li>
-          <img src="" style="height: 7em;"/>
-          <li>中間表現を直接操作できるLLVMがC言語のコンパイルに比べて10程高速な結果が出た.</li>
+          <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 -->
@@ -201,14 +231,16 @@
             <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>
+        <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>
@@ -217,7 +249,6 @@
             <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;">
@@ -261,15 +292,16 @@
             パターン　: "<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>
+        <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>
+          <li class="incremental">complex-regexでは, 本実装がGNU grepより高速な結果を出した.</li>
         </ul>
       </div>
       <!-- PAGE -->
@@ -278,18 +310,29 @@
         <ul>
           <li>生成系を開発効率に優れた言語であるPythonで実装することで, 少ない記述量で正規表現評価器を実装した.</li>
             <table>
-            <tr><th><blue>本実装 (Python)</blue></th><td>: 3000行 (テスト含む全コード)</td></tr>
+            <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>最終的に得られた正規表現評価器の性能は, GNU grep に勝るテストケースもあり, 性能も良い.</li>
+          <li class="incremental">目的: シンプルで保守性に優れ, かつ性能の高い正規表現マッチャを実装したい.</li>
         </ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
         <h1>今後の課題</h1>
         <ul>
-          <li>固定文字列フィルタリング(Boyer-Moore等)の実装.</li>
-          <li>バックリファレンスの実装.</li>
+          <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>
Binary file presen/pix/fig.numbers has changed
Binary file presen/pix/flow.png has changed