|
81
|
1 title: CbCによるPerl6処理系
|
|
100
|
2 author: 清水隆博
|
|
|
3 profile: 並列信頼研
|
|
81
|
4 lang: Japanese
|
|
|
5 code-engine: coderay
|
|
|
6
|
|
|
7
|
|
|
8 ## 研究目的
|
|
|
9 - 現在開発されているPerl6の実装にRakudoがあり, RakudoはNQP(Perl6のサブセット)で記述されたPerl6, NQPで記述されたNQPコンパイラ, NQPを解釈するVMで構成されている
|
|
92
|
10 - NQPコンパイラはRakudoのVMであるMoarVM用のバイトコードを生成する
|
|
|
11 - MoarVMはこのバイトコードを解釈, 実行する
|
|
|
12
|
|
|
13 
|
|
|
14
|
|
|
15 ## 研究目的
|
|
81
|
16 - Continuation based C (CbC)という言語は継続を基本とするC言語であり, 言語処理系に応用出来ると考えられる
|
|
92
|
17 - スクリプト言語などは, バイトコードを扱うが, この実行にcae文や, ラベルgotoなどを利用している。
|
|
|
18 - この部分はCbCの機能で書き換える事が可能である
|
|
|
19 - 命令実行処理部分をモジュール化することで、各命令ごとの最適化や、 命令ディスパッチ部分の最適化を行う事が可能であると考える。
|
|
81
|
20 - 従って, CbC一部用いてPerl6にC処理系であるMoarVMの書き換えを行い, 処理を検討する．
|
|
92
|
21
|
|
81
|
22
|
|
|
23 ## Continuation Based C (CbC)
|
|
|
24 - Continuation Based C (CbC) はCodeGearを単位として用いたプログラミング言語である.
|
|
|
25 - CodeGearはCの通常の関数呼び出しとは異なり，スタックに値を積まず, 次のCodeGearにgoto文によって遷移する.
|
|
85
|
26 - CodeGear同士の移動は、 状態遷移として捉える事が出来る
|
|
100
|
27
|
|
|
28 <img src="fig/cbc_sample.svg" >
|
|
|
29
|
|
85
|
30
|
|
|
31 ## Continuation Based C (CbC)
|
|
|
32
|
|
|
33 - CodeGearはCの関数宣言の型名の代わりに`__code`と書く事で宣言出来る
|
|
|
34 - CodeGearの引数は, 各CodeGearの入出力として利用する
|
|
92
|
35 - gotoしてしまうと、元のCodeGearに戻る事が出来ない
|
|
81
|
36
|
|
|
37 ```
|
|
|
38 __code cg1(TEST testin){
|
|
|
39 TEST testout;
|
|
|
40 testout.number = testin.number + 1;
|
|
|
41 testout.string = "Hello";
|
|
|
42 goto cg2(testout);
|
|
|
43 }
|
|
|
44
|
|
|
45 __code cg2(TEST testin){
|
|
|
46 printf("number = %d\t string= %s\n",testin.number,testin.string);
|
|
|
47 }
|
|
|
48
|
|
|
49 int main(){
|
|
|
50 TEST test = {0,0};
|
|
|
51 goto cg1(test);
|
|
|
52 }
|
|
|
53 ```
|
|
|
54
|
|
|
55 ## 言語処理系の応用
|
|
92
|
56 - スクリプト言語は入力として与えられたソースコードを、 直接評価せずにバイトコードにコンパイルする形式が主流となっている
|
|
|
57 - その為スクリプト言語の実装は大きく2つで構成されている
|
|
|
58 - バイトコードに変換するフロントエンド部分
|
|
|
59 - バイトコードを解釈する仮想機械
|
|
81
|
60
|
|
100
|
61 <img src="fig/bytecode_sample_generally_lang.svg" width="80%">
|
|
|
62
|
|
|
63
|
|
81
|
64 ## Rakudo
|
|
|
65 - Rakudoとは現在のPerl6の主力な実装である．
|
|
93
|
66 - Rakudoは次の構成になっている
|
|
|
67 - 実行環境のVM
|
|
|
68 - Perl6のサブセットであるNQP(NotQuitPerl)
|
|
|
69 - NQPで記述されたPerl6(Rakudo)
|
|
81
|
70
|
|
|
71 ## MoarVM
|
|
|
72
|
|
|
73 - Perl6専用のVMであり, Cで記述されている
|
|
|
74 - レジスタマシンとして実装されている．
|
|
92
|
75
|
|
|
76
|
|
|
77 ## MoarVMのバイトコード
|
|
|
78
|
|
|
79 - MoarVMは16ビットのバイナリを命令バイトコードとして利用している
|
|
|
80 - 命令にはその後に16ビットごとにオペランド(引数)を取るものがある
|
|
|
81
|
|
|
82 ```
|
|
|
83 add_i loc_3_int, loc_0_int, loc_1_int
|
|
|
84 set loc_2_obj, loc_3_obj
|
|
|
85 ```
|
|
|
86
|
|
93
|
87 ## MoarVMのバイトコードインタプリタ
|
|
|
88 - バイトコードは連続したメモリに確保されている
|
|
|
89 - その為次の処理を繰り返す必要がある
|
|
|
90 - 16ビットごとで読み込み
|
|
|
91 - 読み込んだビットから、命令に対応する処理を呼び出し
|
|
|
92 - その処理を実行する
|
|
|
93 - この処理をバイトコードディスパッチと呼び、 実行する部分をバイトコードインタプリタと呼ぶ
|
|
92
|
94
|
|
|
95 ## MoarVMのバイトコードインタプリタ
|
|
|
96
|
|
93
|
97 - MoarVMは関数 `MVM_interp_run` でバイトコードに応じた処理を実行する
|
|
|
98 - マクロDISPATCHで, ラベルgotoかcase文に変換が行われる
|
|
|
99 - バイトコードは数値として見る事が出来る為、 case文に対応する事が出来る
|
|
81
|
100 - この中の `OP` で宣言されたブロックがそれぞれバイトコードに対応する処理となっている．
|
|
|
101 - `cur_op`は次のバイトコード列が登録されており, マクロ `NEXT` で決められた方法で次のバイトコードに対応した処理に遷移する．
|
|
|
102
|
|
|
103 ```
|
|
|
104 DISPATCH(NEXT_OP) {
|
|
|
105 OP(const_i64):
|
|
|
106 GET_REG(cur_op, 0).i64 = MVM_BC_get_I64(cur_op, 2);
|
|
|
107 cur_op += 10;
|
|
|
108 goto NEXT;
|
|
|
109 }
|
|
|
110
|
|
|
111 ```
|
|
|
112
|
|
|
113 ## MVM_interp_runで使用されているマクロ
|
|
|
114
|
|
|
115 ```
|
|
|
116 DISPATCH(NEXT_OP) {
|
|
|
117 OP(const_i64):
|
|
|
118 ```
|
|
|
119
|
|
93
|
120 - マクロ `OP` 及び `NEXT` は次の様に定義している
|
|
81
|
121
|
|
|
122 ```
|
|
|
123 #define OP(name) OP_ ## name
|
|
|
124 #define NEXT *LABELS[NEXT_OP]
|
|
|
125 ```
|
|
|
126
|
|
|
127 - マクロ`DISPATCH`は, ラベルgotoが利用できる場合は無視される
|
|
102
|
128 - マクロ `OP` が, バイトコードの名前をC言語のラベルに変換する
|
|
81
|
129
|
|
|
130
|
|
|
131 ```
|
|
|
132 OP_const_i16:
|
|
102
|
133 ```
|
|
|
134
|
|
|
135 ```
|
|
|
136 #OP_const_i16
|
|
81
|
137 ```
|
|
|
138
|
|
|
139 ## MVM_interp_runで使用されているマクロ
|
|
|
140
|
|
|
141 - `NEXT`自体はラベルテーブルにアクセスし, ラベルを取り出す
|
|
102
|
142 - 取り出したNEXTはラベルなので、 ラベルgotoの拡張が実装されている場合はgoto文でジャンプ出来る
|
|
|
143 - 次の命令を計算する処理は, `NEXT_OP` というマクロが担っている
|
|
81
|
144
|
|
|
145 ```
|
|
|
146 #define NEXT_OP (op = *(MVMuint16 *)(cur_op), cur_op += 2, op)
|
|
|
147 #define NEXT *LABELS[NEXT_OP]
|
|
|
148
|
|
|
149 ```
|
|
|
150 - マクロ `NEXT` は次の様に展開される
|
|
102
|
151 - これは現在のバイトコードを指すポインタをインクリメントし、 命令に対応する変数に代入をする
|
|
81
|
152
|
|
|
153 ```
|
|
|
154 goto *LABELS[(op = *(MVMuint16 *)(cur_op), cur_op += 2, op)];
|
|
|
155 ```
|
|
|
156
|
|
|
157
|
|
|
158 ## MVM_interp_runのラベルテーブル
|
|
|
159
|
|
93
|
160 - 利用するCコンパイラが、ラベルgotoをサポートしている場合に実行される
|
|
|
161 - 配列`LABELS`にアクセスし, ラベル情報を取得する
|
|
|
162 - ラベル情報を取得出来ると、 そのラベルに対してラベルgotoを利用する
|
|
81
|
163
|
|
|
164 ```
|
|
|
165 static const void * const LABELS[] = {
|
|
|
166 &&OP_no_op,
|
|
|
167 &&OP_const_i8,
|
|
|
168 &&OP_const_i16,
|
|
|
169 &&OP_const_i32,
|
|
|
170 &&OP_const_i64,
|
|
|
171 &&OP_const_n32,
|
|
|
172 &&OP_const_n64,
|
|
|
173 &&OP_const_s,
|
|
|
174 &&OP_set,
|
|
|
175 &&OP_extend_u8,
|
|
|
176 &&OP_extend_u16,
|
|
|
177 &&OP_extend_u32,
|
|
|
178 &&OP_extend_i8,
|
|
|
179 &&OP_extend_i16,
|
|
|
180 ```
|
|
|
181
|
|
|
182
|
|
|
183 ## MVM_interp_run
|
|
|
184
|
|
93
|
185 - Cの実装の場合, switch文に展開される可能性がある
|
|
102
|
186 - 命令ディスパッチが書かれているCソースファイルの指定の場所にのみ処理を記述せざるを得ない
|
|
93
|
187 - 1ファイルあたりの記述量が膨大になり, 命令のモジュール化ができない
|
|
|
188 - 高速化手法の、 Threaded Codeの実装を考えた場合, この命令に対応して大幅に処理系の実装を変更する必要がある．
|
|
81
|
189 - デバッグ時には今どの命令を実行しているか, ラベルテーブルを利用して参照せざるを得ず, 手間がかかる．
|
|
|
190
|
|
|
191
|
|
|
192
|
|
95
|
193 ## CbCでの変換
|
|
81
|
194
|
|
93
|
195 - CbCのCodeGearは関数よりも小さな単位である
|
|
|
196 - その為、 従来は関数化出来なかった単位をCodeGearに変換する事が出来る
|
|
81
|
197 - CbCをMoarVMに適応すると, ラベルなどで制御していた命令に対応する処理をCodeGearで記述する事が可能である
|
|
95
|
198
|
|
|
199 ## CbCMoarVMのバイトコードディスパッチ
|
|
|
200
|
|
81
|
201 - オリジナルでは, マクロ `NEXT` が担当していた, 次のバイトコードへの移動は, NEXT相当のCodeGear `cbc_next`で処理を行う
|
|
|
202 - CodeGearの入出力として, MoarVMなどの情報をまとめた構造体を利用する
|
|
|
203
|
|
|
204 ```
|
|
|
205 __code cbc_next(INTERP i){
|
|
|
206 __code (*c)(INTERP)
|
|
|
207 c = CODES[(i->op = *(MVMuint16 *)(i->cur_op), i->cur_op += 2, i->op)]; // c = NEXT(i)
|
|
|
208 goto c(i);
|
|
|
209 }
|
|
|
210
|
|
|
211 __code cbc_const_i64(INTERP i){
|
|
|
212 GET_REG(i->cur_op, 0,i).i64 = MVM_BC_get_I64(i->cur_op, 2);
|
|
|
213 i->cur_op += 10;
|
|
|
214 goto cbc_next(i);
|
|
|
215 }
|
|
|
216
|
|
|
217 ```
|
|
|
218
|
|
|
219 ## CodeGearの入出力インターフェイス
|
|
|
220
|
|
|
221 - MoarVMではレジスタの集合や命令列などをMVM_interp_runのローカル変数として利用し, 各命令実行箇所で参照している
|
|
|
222 - CodeGearに書き換えた場合, このローカル変数にはアクセスする事が不可能となる．
|
|
|
223 - その為, 入出力としてMoarVMの情報をまとめた構造体interpのポインタであるINTERPを受け渡し, これを利用してアクセスする
|
|
|
224
|
|
|
225
|
|
|
226 ```
|
|
|
227 typedef struct interp {
|
|
|
228 MVMuint16 op;
|
|
|
229 MVMuint8 *cur_op;
|
|
|
230 MVMuint8 *bytecode_start;
|
|
|
231 MVMRegister *reg_base;
|
|
|
232 /* Points to the current compilation unit
|
|
|
233 . */
|
|
|
234 MVMCompUnit *cu;
|
|
|
235 /* The current call site we’re
|
|
|
236 constructing. */
|
|
|
237 MVMCallsite *cur_callsite;
|
|
|
238 MVMThreadContext *tc;
|
|
|
239 } INTER,*INTERP;
|
|
|
240 ```
|
|
|
241
|
|
|
242 ## CbCMoarVMのCodeGearテーブル
|
|
|
243
|
|
|
244 - CodeGearテーブルは引数としてINTERを受け取るCodeGearの配列として定義する
|
|
95
|
245 - テーブルとして宣言することで、 バイトコードの値をそのままテーブルに反映させる事が可能である
|
|
81
|
246
|
|
|
247 ```
|
|
|
248 __code (* CODES[])(INTERP) = {
|
|
|
249 cbc_no_op,
|
|
|
250 cbc_const_i8,
|
|
|
251 cbc_const_i16,
|
|
|
252 cbc_const_i32,
|
|
|
253 cbc_const_i64,
|
|
|
254 cbc_const_n32,
|
|
|
255 cbc_const_n64,
|
|
|
256 cbc_const_s,
|
|
|
257 cbc_set,
|
|
|
258 cbc_extend_u8,
|
|
|
259 cbc_extend_u16,
|
|
|
260 ```
|
|
|
261
|
|
|
262
|
|
|
263
|
|
96
|
264 ## MoarVMとCbCMoarVMのトレース
|
|
81
|
265
|
|
96
|
266 - MoarVMのデバッグ時には、 次の命令が何であるかは直接は判断出来なかった
|
|
81
|
267
|
|
|
268 ```
|
|
|
269 Breakpoint 1, dummy () at src/core/interp.c:46
|
|
|
270 46 }
|
|
|
271 #1 0x00007ffff75689da in MVM_interp_run (tc=0x604a20,
|
|
|
272 initial_invoke=0x7ffff76c7168 <toplevel_initial_invoke>, invoke_data=0x67ff10)
|
|
|
273 at src/core/interp.c:1169
|
|
|
274 1169 goto NEXT;
|
|
|
275 $2 = 162
|
|
|
276 ```
|
|
96
|
277 - CbCMoarVMの場合は、 次に実行する命令名を確認する事が出来る
|
|
81
|
278
|
|
|
279 ```
|
|
|
280 Breakpoint 2, cbc_next (i=0x7fffffffdc30) at src/core/cbc-interp.cbc:61
|
|
|
281 61 goto NEXT(i);
|
|
|
282 $1 = (void (*)(INTERP)) 0x7ffff7566f53 <cbc_takeclosure>
|
|
|
283 $2 = 162
|
|
|
284 ```
|
|
|
285
|
|
|
286 ## MoarVMのデバッグ
|
|
|
287
|
|
|
288 - cur_opのみをPerlスクリプトなどを用いて抜き出し, 並列にログを取得したオリジナルと差分を図る
|
|
|
289 - この際に差異が発生したバイトコードを確認し, その前の状態で確認していく
|
|
|
290
|
|
|
291 ```
|
|
|
292 25 : 25 : cbc_unless_i
|
|
|
293 247 : 247 : cbc_null
|
|
|
294 54 : 54 : cbc_return_o
|
|
|
295 140 : 140 : cbc_checkarity
|
|
|
296 558 : 558 : cbc_paramnamesused
|
|
|
297 159 : 159 : cbc_getcode
|
|
|
298 391 : 391 : cbc_decont
|
|
|
299 127 : 127 : cbc_prepargs
|
|
|
300 *139 : 162
|
|
|
301 cbc_invoke_o:cbc_takeclosure
|
|
|
302 ```
|
|
|
303
|
|
|
304 ## 現在のCbCMoarVM
|
|
|
305
|
|
|
306 - 現在はNQP, Rakudoのセルフビルドが達成でき, オリジナルと同等のテスト達成率を持っている
|
|
95
|
307 - その為、 NQP, Rakudoの実行コマンドであるnqp perl6が起動する様になった
|
|
|
308 - moarの起動時のオプションとして `--cbc` を与えることによりCbCかオリジナルを選択可能である
|
|
|
309 - Perl6の実行バイナリperl6, NQPの実行バイナリnqp は, それぞれmoarを起動するシェルスクリプトである
|
|
|
310 - `--cbc` オプションをシェルスクリプト内に書き加えることで, Perl6, NQPがそれぞれCbCで起動する
|
|
81
|
311
|
|
|
312 ```
|
|
|
313 #!/bin/sh
|
|
|
314 exec /mnt/dalmore-home/one/src/Perl6/Optimize/llvm/build_perl6/bin/moar --cbc \
|
|
|
315 --libpath=/mnt/dalmore-home/one/src/Perl6/Optimize/llvm/build_perl6/share/nqp/lib \
|
|
|
316 /mnt/dalmore-home/one/src/Perl6/Optimize/llvm/build_perl6/share/nqp/lib/nqp.moarvm "$@"
|
|
|
317 ```
|
|
|
318
|
|
|
319 ## ThreadedCodeの実装
|
|
|
320
|
|
|
321 - MoarVM内のバイトコードに対応する処理が分離出来たことにより, バイトコードに該当するCodeGearを書き連ねることによってThreadedCodeが実装可能となる
|
|
|
322
|
|
|
323
|
|
|
324 ## CbCMoarVMと通常のMoarVMの比較
|
|
|
325
|
|
|
326 - CbCMoarVMと通常のMoarVMの速度比較を行った
|
|
102
|
327 - NQPで実装した2種類の例題を用いた
|
|
|
328 - 単純なループで数値をインクリメントする例題
|
|
|
329 - 再帰呼び出しを用いてフィボナッチ数列を求める例題
|
|
|
330
|
|
|
331
|
|
|
332 ## フィボナッチの例題
|
|
|
333
|
|
|
334 ```
|
|
|
335 #! nqp
|
|
|
336
|
|
|
337 sub fib($n) {
|
|
|
338 $n < 2 ?? $n !! fib($n-1) + fib($n - 2);
|
|
|
339 }
|
|
|
340
|
|
|
341 my $N := 30;
|
|
|
342 my $z := fib($N);
|
|
|
343 say("fib($N) = " ~ fib($N));
|
|
|
344 ```
|
|
|
345
|
|
|
346
|
|
|
347 - フィボナッチの例題ではCbCMoarVMが劣る結果となった
|
|
|
348
|
|
|
349 <table>
|
|
|
350 <tbody>
|
|
|
351 <tr>
|
|
|
352 <td>[単位 sec]</td>
|
|
|
353 <td></td>
|
|
|
354 <td></td>
|
|
|
355 <td></td>
|
|
|
356 </tr>
|
|
|
357 <tr>
|
|
|
358 <td>MoarVM</td>
|
|
|
359 <td>1.379</td>
|
|
|
360 <td>1.350</td>
|
|
|
361 <td>1.346</td>
|
|
|
362 </tr>
|
|
|
363 <tr>
|
|
|
364 <td>CbCMoarVM</td>
|
|
|
365 <td>1.636</td>
|
|
|
366 <td>1.804</td>
|
|
|
367 <td>1.787</td>
|
|
|
368 </tr>
|
|
|
369 </tbody>
|
|
|
370 </table>
|
|
|
371
|
|
|
372 ## 単純ループ
|
|
81
|
373
|
|
|
374 ```
|
|
|
375 #! nqp
|
|
|
376
|
|
|
377 my $count := 100_000_000;
|
|
|
378
|
|
|
379 my $i := 0;
|
|
|
380
|
|
|
381 while ++$i <= $count {
|
|
|
382 }
|
|
|
383 ```
|
|
|
384
|
|
102
|
385 <style type="text/css">
|
|
|
386 table , td, th {
|
|
|
387 border: 2px solid #595959;
|
|
|
388 border-collapse: collapse;
|
|
|
389 }
|
|
|
390 td, th {
|
|
|
391 padding: 12px;
|
|
|
392 width: 120px;
|
|
|
393 height: 40px;
|
|
81
|
394 }
|
|
102
|
395 th {
|
|
|
396 background: #f0e6cc;
|
|
|
397 }
|
|
|
398 .even {
|
|
|
399 background: #fbf8f0;
|
|
|
400 }
|
|
|
401 .odd {
|
|
|
402 background: #fefcf9;
|
|
|
403 }
|
|
|
404 </style>
|
|
81
|
405
|
|
102
|
406 - 単純ループの場合は1.5secほど高速化した
|
|
|
407 - これは実行する命令コードが、 CPUのキャッシュに収まった為であると考えられる
|
|
81
|
408
|
|
102
|
409 <table>
|
|
|
410 <tbody>
|
|
|
411 <tr>
|
|
|
412 <td>[単位 sec]</td>
|
|
|
413 <td></td>
|
|
|
414 <td></td>
|
|
|
415 <td></td>
|
|
|
416 </tr>
|
|
|
417 <tr>
|
|
|
418 <td>MoarVM</td>
|
|
|
419 <td>7.499</td>
|
|
|
420 <td>7.844</td>
|
|
|
421 <td>7.822</td>
|
|
|
422 </tr>
|
|
|
423 <tr>
|
|
|
424 <td>CbCMoarVM</td>
|
|
|
425 <td>6.135</td>
|
|
|
426 <td>6.362</td>
|
|
|
427 <td>6.074</td>
|
|
|
428 </tr>
|
|
|
429 </tbody>
|
|
|
430 </table>
|
|
81
|
431
|
|
95
|
432 ## CbCMoarVMの利点
|
|
|
433 - バイトコードインタプリタの箇所をモジュール化する事が可能となった
|
|
|
434 - CodeGearの再利用性や記述生が高まる
|
|
|
435 - CodeGearは関数の様に扱える為、 命令ディスパッチの最適化につながる実装が可能となった
|
|
|
436 - デバッグ時にラベルではなくCodeGearにbreakpointを設定可能となった
|
|
|
437 - デバッグが安易となる
|
|
|
438 - CPUがキャッシュに収まる範囲の命令の場合、 通常のMoarVMよりも高速に動作する
|
|
|
439
|
|
|
440 ## CbCMoarVMの欠点
|
|
|
441
|
|
|
442 - MoarVMのオリジナルの更新頻度が高い為, 追従していく必要がある
|
|
|
443 - CodeGear側からCに戻る際に手順が複雑となる
|
|
|
444 - CodeGearを単位として用いる事で複雑なプログラミングが要求される.
|
|
|
445
|
|
81
|
446
|
|
102
|
447 ## まとめ
|
|
81
|
448 - 継続と基本としたC言語 Continuation Based Cを用いてPerl6の処理系の一部を書き直した
|
|
102
|
449 - Cの持つCodeGearによって, 本来はモジュール化出来ない箇所をモジュール化が可能となった
|
|
|
450 - CPUキャッシュに収まるループなどの命令の場合は、 通常のMoarVMよりも高速に動作する
|
|
|
451 - 今後はCodeGearの特性を活用し、 直接次の命令を実行する処理を実装する
|
