Mercurial > hg > Papers > 2010 > jsst-shinya

changeset 16:627af8b88d16

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 Sun, 12 Sep 2010 08:57:34 +0900
parents b3b5bcbba089
children 54987da33049
files presen/code/reg.c.txt presen/code/reg.cbc.txt presen/code/reg.ll.txt presen/index.html presen/pix/bench_grep.png presen/pix/fig.numbers
diffstat 6 files changed, 217 insertions(+), 48 deletions(-) [+]
line wrap: on
line diff
Binary file presen/code/reg.c.txt has changed
Binary file presen/code/reg.cbc.txt has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presen/code/reg.ll.txt	Sun Sep 12 08:57:34 2010 +0900
@@ -0,0 +1,121 @@
+; ModuleID = 'DFA'
+global [4 x i8] c"ABC\00"		; <[4 x i8]*>:0 [#uses=4]
+global [28 x i8] c"state: %s, arg: %c(int %d)\0A\00"		; <[28 x i8]*>:1 [#uses=0]
+
+define i32 @accept(i32 %index) {
+entry:
+	ret i32 1
+}
+
+define i32 @reject(i32 %index) {
+entry:
+	ret i32 0
+}
+
+define i32 @"8"(i32 %index) {
+entry:
+	%0 = getelementptr [4 x i8]* @0, i32 0, i32 %index		; <i8*> [#uses=1]
+	%1 = add i32 %index, 1		; <i32> [#uses=2]
+	%2 = load i8* %0		; <i8> [#uses=1]
+	switch i8 %2, label %default [
+		i8 0, label %case0
+	]
+
+default:		; preds = %entry
+	%3 = call i32 @reject(i32 %1)		; <i32> [#uses=1]
+	ret i32 %3
+
+case0:		; preds = %entry
+	%4 = call i32 @accept(i32 %1)		; <i32> [#uses=1]
+	ret i32 %4
+}
+
+define i32 @"1_3_5_6_7"(i32 %index) {
+entry:
+	%0 = getelementptr [4 x i8]* @0, i32 0, i32 %index		; <i8*> [#uses=1]
+	%1 = add i32 %index, 1		; <i32> [#uses=4]
+	%2 = load i8* %0		; <i8> [#uses=1]
+	switch i8 %2, label %default [
+		i8 65, label %case0
+		i8 67, label %case1
+		i8 66, label %case2
+	]
+
+default:		; preds = %entry
+	%3 = call i32 @reject(i32 %1)		; <i32> [#uses=1]
+	ret i32 %3
+
+case0:		; preds = %entry
+	%4 = call i32 @"1_2_3_5_7"(i32 %1)		; <i32> [#uses=1]
+	ret i32 %4
+
+case1:		; preds = %entry
+	%5 = call i32 @"8"(i32 %1)		; <i32> [#uses=1]
+	ret i32 %5
+
+case2:		; preds = %entry
+	%6 = call i32 @"1_3_4_5_7"(i32 %1)		; <i32> [#uses=1]
+	ret i32 %6
+}
+
+define i32 @"1_3_4_5_7"(i32 %index) {
+entry:
+	%0 = getelementptr [4 x i8]* @0, i32 0, i32 %index		; <i8*> [#uses=1]
+	%1 = add i32 %index, 1		; <i32> [#uses=4]
+	%2 = load i8* %0		; <i8> [#uses=1]
+	switch i8 %2, label %default [
+		i8 65, label %case0
+		i8 67, label %case1
+		i8 66, label %case2
+	]
+
+default:		; preds = %entry
+	%3 = call i32 @reject(i32 %1)		; <i32> [#uses=1]
+	ret i32 %3
+
+case0:		; preds = %entry
+	%4 = call i32 @"1_2_3_5_7"(i32 %1)		; <i32> [#uses=1]
+	ret i32 %4
+
+case1:		; preds = %entry
+	%5 = call i32 @"8"(i32 %1)		; <i32> [#uses=1]
+	ret i32 %5
+
+case2:		; preds = %entry
+	%6 = call i32 @"1_3_4_5_7"(i32 %1)		; <i32> [#uses=1]
+	ret i32 %6
+}
+
+define i32 @"1_2_3_5_7"(i32 %index) {
+entry:
+	%0 = getelementptr [4 x i8]* @0, i32 0, i32 %index		; <i8*> [#uses=1]
+	%1 = add i32 %index, 1		; <i32> [#uses=4]
+	%2 = load i8* %0		; <i8> [#uses=1]
+	switch i8 %2, label %default [
+		i8 65, label %case0
+		i8 67, label %case1
+		i8 66, label %case2
+	]
+
+default:		; preds = %entry
+	%3 = call i32 @reject(i32 %1)		; <i32> [#uses=1]
+	ret i32 %3
+
+case0:		; preds = %entry
+	%4 = call i32 @"1_2_3_5_7"(i32 %1)		; <i32> [#uses=1]
+	ret i32 %4
+
+case1:		; preds = %entry
+	%5 = call i32 @"8"(i32 %1)		; <i32> [#uses=1]
+	ret i32 %5
+
+case2:		; preds = %entry
+	%6 = call i32 @"1_3_4_5_7"(i32 %1)		; <i32> [#uses=1]
+	ret i32 %6
+}
+
+define i32 @unitmain(i32 %index) {
+entry:
+	%0 = call i32 @"1_3_5_6_7"(i32 %index)		; <i32> [#uses=1]
+	ret i32 %0
+}
--- a/presen/index.html	Sat Sep 11 23:46:30 2010 +0900
+++ b/presen/index.html	Sun Sep 12 08:57:34 2010 +0900
@@ -50,30 +50,36 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-        <h1>研究目的と背景 *</h1>
+        <h1>研究目的と背景 (1)</h1>
         <ul>
-          <li>現在C言語のような静的な言語では, 実行中に内部表現となるデータを生成し, それを操作していくデータ主導のプログラミング手法が基本である.</li>
-          <li>データである内部表現をコードに変換して再度コンパイルすることで, コード主導のプログラミング手法が取れる.</li>
-          <li>この手法では, 生成系を高級な言語で実装しても最終的にはコンパイルされたプログラムとなるので性能を保ったまま<blue>開発効率に優れるという</blue>利点がある.</li>
+          <li>現在, PythonやRuby等の高度なデータ型を組み込みで備えた, インタプリタ型言語の開発が発達してきている.</li>
+          <li>
+            しかし, 高い性能を必要とされるプログラムは, C言語等のコンパイル型言語による開発が主となっている.<br/>
+            これは, コンパイラの高度に発達した最適化の恩恵を受けれるからである.
+          </li>
+          <li>プログラムの開発は, 可読性・開発効率の高い高級な言語によって行われることが開発者にとって望ましい.</li>
         </ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-        <h1>研究目的と背景 **</h1>
+        <h1>研究目的と背景 (2)</h1>
         <ul>
-          <li>本研究では生成的プログラミングの有効性を示す例題として, 正規表現をコードに変換し, コンパイルして実行する正規表現評価器を実装した.</li>
+          <li>開発効率高い言語によって記述した生成系から, より低級な言語のコードを生成するプログラミング手法として生成的プログラミングがある.</li>
+          <li>この手法では, 生成系を高級な言語で実装しても, 最終的にはコンパイルされたプログラムとなるので性能を保ったまま<blue>開発効率に優れるという</blue>利点がある.</li>
+          <li class="incremental">本研究では生成的プログラミングの有効性を評価するために, 正規表現からC言語等のコードを生成する正規表現評価器の実装を行った.</li>
+          <li class="incremental"></li>
         </ul>
       </div>
       <!-- PAGE -->
       <div class="slide">
-        <h1>例題: 正規表現</h1>
+        <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">正規表現は等価な有限オートマトンに変換可能.</li>
-          <li class="incremental">状態遷移を関数遷移に変換することで, コード主導のプログラムとなる..</li>
+          <li class="incremental">正規表現は等価なDFA(決定性有限オートマトン)に変換可能.</li>
+          <li class="incremental">状態遷移を関数遷移で表現することで, C言語等のコードに変換を行った.</li>
         </ul>
       </div>
       <!-- PAGE -->
@@ -81,7 +87,7 @@
         <h1>本実装の特徴</h1>
         <ul>
           <li>生成系は<strong>Python</strong>で実装.</li>
-          <li><strong>連接</strong>, <strong>集合和</strong>, <strong>閉包</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>
@@ -108,51 +114,100 @@
       </div>
       <!-- PAGE -->
       <div class="slide">
-        <h1>コード生成: <red>CbC</red> *</h1>
+        <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></li>
+          <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>コード生成: <red>CbC</red> **</h1>
+        <h1>コード生成: <a href="code/reg.cbc.txt" target="blank"><red>CbC</red></a></h1>
         <ul>
-          <li>DFAの状態遷移をCbCのコードセグメントによる軽量継続で表現.</li>
-          <p>コード: 正規表現"<blue>(A|B)*C</blue>"から生成されたCbCコード</p>
-          <pre style="font-size: 0.6em;">
-__code state_0(unsigned char *s, unsigned char* cur,\
-  unsigned char* buf, FILE *f, char* filename) {
-  switch(*s++) {
-    case 'A':
-      goto state_0(s, cur, buf, f, filename);
-    case 'B':
-      goto state_0(s, cur, buf, f, filename);
-    case 'C':
-      goto state_1(s, cur, buf, f, filename);
-    default: goto reject(s, cur, buf, f, filename);
-  }
-}
-
-__code state_1(unsigned char *s, unsigned char* cur,\
-  unsigned char* buf, FILE *f, char* filename) {
-  goto accept(s, cur, buf, f, filename);
-}
-          </pre>
+          <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>比較対象: GNU grep</h1>
+        <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>本実装と同様にDFAベースのマッチングを行う.</li>
-          <li>C言語による実装 -> DFAを構造体で構築.</li>
+          <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>本実装により生成したCコードとGNU grep 2.6.3/2.5.4 の検索時間を計測(変換/コンパイル時間も含む).</li>
           <li>生成コード, GNU grep は共にGCC 4.4.1(-O3) でコンパイル.</li>
           <li>
             3つのパターンによるベンチマーク.<br/>
@@ -211,9 +266,10 @@
       <!-- PAGE -->
       <div class="slide">
         <h1>ベンチマーク: 結果</h1>
-        <img src="pix/bench_grep.png" style="height: 12em;"/>
+        <img src="pix/bench_grep.png" style="height: 11em;"/>
         <ul>
-          <li>は</li>
+          <li class="incremental">fixed-stringでは, 固定文字列フィルタの差が大きい.</li>
+          <li class="incremental">DFAの状態遷移がネックとなるcomplex-regexでは, 本実装がGNU grepより高速な結果を出した.</li>
         </ul>
       </div>
       <!-- PAGE -->
@@ -236,14 +292,6 @@
           <li>バックリファレンスの実装.</li>
         </ul>
       </div>
-      <div class="slide">
-        <h1>予想される質問</h1>
-        <ul>
-          <li>CbCコード生成の利点(Cでは? 他の静的言語では?)</li>
-          <li>正規表現->DFA変換のオーバーヘッド</li>
-          <li>コンパイルのオーバーヘッド</li>
-        </ul>
-      </div>
     </div>
   </body>
 </html>
Binary file presen/pix/bench_grep.png has changed
Binary file presen/pix/fig.numbers has changed