[#uses=1] + ret i32 %0 +} diff -r b3b5bcbba089 -r 627af8b88d16 presen/index.html --- 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 @@

研究目的と背景 *

研究目的と背景 (1)

現在C言語のような静的な言語では, 実行中に内部表現となるデータを生成し, それを操作していくデータ主導のプログラミング手法が基本である.
データである内部表現をコードに変換して再度コンパイルすることで, コード主導のプログラミング手法が取れる.
この手法では, 生成系を高級な言語で実装しても最終的にはコンパイルされたプログラムとなるので性能を保ったまま開発効率に優れるという利点がある.
現在, PythonやRuby等の高度なデータ型を組み込みで備えた, インタプリタ型言語の開発が発達してきている.
+ しかし, 高い性能を必要とされるプログラムは, C言語等のコンパイル型言語による開発が主となっている.
+ これは, コンパイラの高度に発達した最適化の恩恵を受けれるからである. +
プログラムの開発は, 可読性・開発効率の高い高級な言語によって行われることが開発者にとって望ましい.

研究目的と背景 **

研究目的と背景 (2)

本研究では生成的プログラミングの有効性を示す例題として, 正規表現をコードに変換し, コンパイルして実行する正規表現評価器を実装した.
開発効率高い言語によって記述した生成系から, より低級な言語のコードを生成するプログラミング手法として生成的プログラミングがある.
この手法では, 生成系を高級な言語で実装しても, 最終的にはコンパイルされたプログラムとなるので性能を保ったまま開発効率に優れるという利点がある.
本研究では生成的プログラミングの有効性を評価するために, 正規表現からC言語等のコードを生成する正規表現評価器の実装を行った.

例題: 正規表現

正規表現とは

テキストのパターンマッチング記法.

ex: "(A|B)*C" -> "A"または"B", の0回以上の繰り返し直後に"C"

GNU grep などのテキスト検索ツールや各言語のライブラリで利用されている.

正規表現は等価な有限オートマトンに変換可能.
状態遷移を関数遷移に変換することで, コード主導のプログラムとなる..
正規表現は等価なDFA(決定性有限オートマトン)に変換可能.
状態遷移を関数遷移で表現することで, C言語等のコードに変換を行った.

@@ -81,7 +87,7 @@

本実装の特徴

生成系はPythonで実装.
連接, 集合和, 閉包の基本演算に対応.
正規表現の連接, 集合和, 閉包の基本演算に対応.
DFAの状態遷移に対応した, 関数遷移を行うコードを生成.

マルチバイト文字: UTF-8 に対応.

コード生成: CbC *

DFAからのコード生成

DFAによるマッチングを行うコードを生成.
C, CbC, LLVM-IR それぞれのコードを生成する生成系を実装した.

それぞれ, 最終的に生成されるコードの性能を比較.

コード生成: C

DFAによる状態遷移を, 関数遷移として表現.

入力文字列による分岐はswitch文, 状態遷移は関数遷移.
+

+/* "(A|B)*C"に対応する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);
+  }
+}
+

コード生成: CbC **

コード生成: CbC

DFAの状態遷移をCbCのコードセグメントによる軽量継続で表現.

コード: 正規表現"(A|B)*C"から生成されたCbCコード

-__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);
-}
-

CbC(Continuation based C)は

関数よりも小さなプログラミング単位としてコードセグメントを持つ.
コードセグメントによる継続を基本としたCの下位言語である.
GCC を拡張する形で実装されており, 継続をGCCの末尾呼び出し最適化を強制することで実現している.

CbCでも, 前節で紹介したCと同様に生成を行ったが, 関数ではなくコードセグメントを用いている.
DFAの遷移は継続的な処理であり, CbCではそれを明示的に記述できる.

比較対象: GNU grep

コード生成: LLVM-IR *

LLVM(Low Level Virtual Machine)は

構文解析やコード生成など, 機能単位で再利用可能なコンパイラ基盤.
様々な最適化が実装されている.
LLVM内部表現であるLLVM-IRを, 直接操作するAPIが提供されている.

Cと同様な処理を行うコードを, LLVM-IRを直接操作して生成.

生成系の比較 (1)

本実装と同様にDFAベースのマッチングを行う.
C言語による実装 -> DFAを構造体で構築.
コンパイル速度
テーブル

中間表現を直接操作できるLLVMがC言語のコンパイルに比べて10程高速な結果が出た.

生成系の比較 (2)

コンパイルされたプログラムの実行速度

C/CbC/LLVM-IRをコンパイルしたプログラムの実行速度に, あまり差がでなかった.
3つの生成系は, 生成する言語が違うが, 生成するコードの処理内容は同じ.

生成されたコードは, 関数呼び出しとswitch文によるシンプルなプログラムなので, 最適化によって性能の等しいネイティブコードが生成されたためと思われる.

ベンチマーク: vs GNU grep.

本実装により生成したCコードとGNU grep 2.6.3/2.5.4 の検索時間を計測.
本実装により生成したCコードとGNU grep 2.6.3/2.5.4 の検索時間を計測(変換/コンパイル時間も含む).
生成コード, GNU grep は共にGCC 4.4.1(-O3) でコンパイル.
3つのパターンによるベンチマーク.
@@ -211,9 +266,10 @@
ベンチマーク: 結果
- +
- は
- fixed-stringでは, 固定文字列フィルタの差が大きい.
- DFAの状態遷移がネックとなるcomplex-regexでは, 本実装がGNU grepより高速な結果を出した.
@@ -236,14 +292,6 @@
バックリファレンスの実装.

予想される質問

CbCコード生成の利点(Cでは? 他の静的言語では?)
正規表現->DFA変換のオーバーヘッド
コンパイルのオーバーヘッド