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