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