Get Slide

密な演算子呼び出しで実現した
内部DSLの前処理による
実行速度改善の試み
東京大学情報理工学系研究科
長田朋久千葉滋
Osada Tomohisa
1
内部DSL (Domain Specific Languages)
• 特定の領域に特化したプログラミング言語の
ライブラリ
• 自然な表記が可能
– 例: ScalaのList
val lst = 1 :: 2 :: 3 :: Nil
Osada Tomohisa
2
内部DSL (Domain Specific Languages)
• 特定の領域に特化したプログラミング言語の
ライブラリ
• 自然な表記が可能
– 例: ScalaのList
val lst = ((Nil.::(3)).::(2)).::(1)
"::" はListクラスのメソッド
組み込み演算子ではない
• ホスト言語の文法的制約を受ける
Osada Tomohisa
3
密な演算子呼び出しによる内部DSL
• Scala
1.+(2) = 1 + 2
– 二項演算子に見えるメソッドを定義可能
– ドットと括弧を省略できるが空白が必要
– 可能な演算子名に制限がある
• メソッド名であるため
• ProteaJ
[Ichikawa et al, Modluarity'14]
– n項演算子を定義可能, 空白不要, メソッド名に
制限がない
– 擬似的なリテラルを演算子で定義可能
• 密な演算子呼び出しになりやすい
Osada Tomohisa
4
擬似的なリテラルを密な演算子呼び出しで
表現する
0b101 // 5
"0b" _ : Binary -> Int
"0"
"1"
"0"
"1"
Osada Tomohisa
_ : Binary -> Binary
_ : Binary -> Binary
: Binary
: Binary
5
擬似的なリテラルを密な演算子呼び出しで
表現する
オペレータ
0b101 // 5
単項演算子
オペランド
"0b" _ : Binary -> Int
"0"
"1"
"0"
"1"
_ : Binary -> Binary
_ : Binary -> Binary
: Binary
: Binary
無項演算子
(関数)型
Osada Tomohisa
6
擬似的なリテラルを密な演算子呼び出しで
表現する
Expect Binary value
Return Int value
0b101 // 5
"0b" _ : Binary -> Int
"0"
"1"
"0"
"1"
Osada Tomohisa
_ : Binary -> Binary
_ : Binary -> Binary
: Binary
: Binary
7
擬似的なリテラルを密な演算子呼び出しで
表現する
Expect Binary value
Return Int value
0b101 // 5
0b
"0b" _ : Binary -> Int
"0"
"1"
"0"
"1"
Osada Tomohisa
_ : Binary -> Binary
_ : Binary -> Binary
: Binary
: Binary
8
擬似的なリテラルを密な演算子呼び出しで
表現する
Expect Binary value
Return Int value
0b101 // 5
0b 1
"0b" _ : Binary -> Int
"0"
"1"
"0"
"1"
Osada Tomohisa
_ : Binary -> Binary
_ : Binary -> Binary
: Binary
: Binary
9
擬似的なリテラルを密な演算子呼び出しで
表現する
Expect Binary value
Return Int value
0b101 // 5
0b 1
0
"0b" _ : Binary -> Int
"0"
"1"
"0"
"1"
Osada Tomohisa
_ : Binary -> Binary
_ : Binary -> Binary
: Binary
: Binary
10
擬似的なリテラルを密な演算子呼び出しで
表現する
Expect Binary value
Return Int value
0b101 // 5
0b 1
0
1
"0b" _ : Binary -> Int
"0"
"1"
"0"
"1"
_ : Binary -> Binary
_ : Binary -> Binary
: Binary
: Binary
4回の演算子呼び出しが密に発
生
Osada Tomohisa
11
密な演算子呼び出しによる実行時間の低速化
• 独自に作成した言語にて実験
• 2進数リテラルの評価時間を
計測
350
300
time[ms]
– "0b10101" を4万回評価
400
250
200
• 通常のリテラル
150
100
– コンパイル時に意味解析
50
• 密な演算子呼び出し
0
– 遅い. 実行時に意味解析(=演算子実行)
mean
しているようなもの
evaluation time
Osada Tomohisa
dense
operator
calls
native
literals
14
密な演算子呼び出し部分の構文木変換
• 目標
– 密な演算子呼び出しによる内部DSLの実行時間を
削減する
• 方法
– 内部DSL使用部分の構文木をコンパイル時に
前処理で変換する
• 同一内部DSLの命令は一箇所にまとまって
存在する
Osada Tomohisa
15
実験に用いた独自言語
• 密な演算子呼び出しによる内部DSLを
構成可能な言語を作成
operators TupleInt {
"0" () = 0 -> 1;
"1" () = 1 -> 1;
[r] "0" _ (TupleInt pair) =
(first pair) -> ((second pair) + 1);
[r] "1" _ (TupleInt pair) = ((first pair) + (1 <<
(second pair))) -> ((second pair) + 1);
};
operators Int {
[r] "0b" _ (TupleInt pair) = first pair;
};
Osada Tomohisa
16
実装した構文木の変換
• まず, 演算子のインライン展開を実装した
– 例: 0b10 のインライン展開
Call
Call(Var("0b"),
Call(Var("1"),
Call(Var("0"),Tuple(0,1))))
Var
Call
Var
Call
Var Tuple
構文木の文字列表現
First(Tuple(Plus(First(Tuple(0,1)),
LeftShift(1,Second(Tuple(0,1)))),
Plus(Second(Tuple(0,1)),1)))
Osada Tomohisa
17
インライン展開実装版の実行時間
• 独自に作成した言語にて実験
• 2進数リテラルの実行時間を
計測
– インライン展開により大幅に
速度が低下した
• 理由は調査中
2000
time[ms]
– "0b10101" を4万回評価
2500
dense
operator
calls
1500
native
literals
1000
500
inlining
0
mean
evaluation
time
Osada Tomohisa
18
関連研究
• 書き換え規則
– CodeBoost (C++):
• http://codeboost.org/
– GHC/Haskell rewrite rules (Haskell):
• https://downloads.haskell.org/~ghc/7.0.1/docs/html/u
sers_guide/rewrite-rules.html
{-# RULES
"map/map" forall f g xs.
map f (map g xs) = map (f.g) xs
#-}
Osada Tomohisa
19
今後の予定
• 具体的な前処理の内容を考案する
– 特定のDSLに特化した構文木の変換
• 実用的な言語で実装する
– Java(ProteaJ)上
Osada Tomohisa
20

Download Report