Get Poster

密な演算子呼び出しで実現した内部DSLの
別途処理記述による実行速度改善の試み
東京大学情報理工学系研究科
長田朋久千葉滋
1. 内部DSL (Domain Specific Languages)
5. 演算子の自動リフトアップ
– 特定の領域に特化したプログラミング言語のライブラ
リ
– 自然な表記が可能
–
演算子の一部の引数をリフトアップ
–
リフトアップされた値は別途ユーザ定義された演算子
の式で処理する
個別の内部DSLの固有情報を使用した高速化
手段の提供
–
val lst = 1 :: 2 :: 3 :: Nil
6. Javaによる文字列の結合の例
2. 密な演算子呼び出しによる内部DSL
• plusは文字列を結合するユーザ定義演算子とする
– ユーザ定義演算子を組み合わせて内部DSLを構成
– 擬似的なリテラルを演算子でユーザ定義可能
• 密に演算子呼び出しが発生する
使用例
"Str1" plus "Str2" plus "Str3" //"Str1Str2Str3"
3. 擬似的なリテラルを密な演算子
呼び出しで表現する
–
Stringオブジェクト同士の結合は遅い
• 文字列を 4 個以上結合する場合は、StringBuilder
による結合に書き換えたいとする
– ある演算子について, 指定したオペランドに k 回以上
同じ演算子が出現すれば引数をリフトアップし, リフト
アップ版の演算子を使用する表記を導入する
– 2進数表現の例
オペレータ
オペランド
"0b" _ : Binary -> Int
"0"
"1"
"0"
"1"
単項演算子
定義
_ "plus" _ : String -> String -> String
_ : Binary -> Binary
_ : Binary -> Binary
: Binary
: Binary
String <-> StringBuilder
_(k) "plus" _ : String -> String -> String
無項演算子
_ "plus" _ : StringBuilder -> String -> StringBuilder
(関数)型
0b101 // 5
0b 1
0
1
–
"a" plus "b" plus "c" plus "d"
4回の演算子呼び出しが
密に発生
– 独自言語にて"0b10101"を
4万回評価
time[ms]
4. 密な演算子呼び出しによる
実行時間の低速化
4つのStringを結合する例
• k=2
リフトダウン
(StringBuilder -> String)
plus
400
350
plus
300
dense
operator
calls
250
200
150
native
literals
100
50
plus
a
d
c
b
plus
plus
plus
d
c
a リフトアップ
b
(String -> StringBuilder)
0
mean
evaluation time
_ "plus" _ : StringBuilder -> String -> StringBuilder

Download Report