Mercurial > hg > Papers > 2019 > anatofuz-prosym
annotate Slide/slide.md @ 88:632f160ccbd0
update
author | Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 10 Jan 2019 21:55:46 +0900 |
parents | 2c38abf2c77d |
children | 1f9baa69dfe0 |
rev | line source |
---|---|
84
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 title: CbCによるPerl6処理系 |
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 author: Takahiro Shimizu, Shinji Kono |
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 profile: 琉球大学 |
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 lang: Japanese |
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 code-engine: coderay |
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 |
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 |
85 | 8 ## 研究目的 |
84
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 - スクリプト言語であるPerl5の後継言語としてPerl6が現在開発されている. |
88 | 10 - 現在主流なPerl6の実装にRakudoがあり, RakudoはNQP(Perl6のサブセット)で記述されたPerl6, NQPで記述されたNQPコンパイラがある |
11 - NQPコンパイラはRakudoのVMであるMoarVM用のバイトコードを生成し, MoarVMはこのバイトコードを解釈, 実行する | |
12 - Continuation based C (CbC)という言語は継続を基本とするC言語であり, 言語処理系に応用出来ると考えられる | |
13 - CbC一部用いてMoarVMの書き換えを行い, 処理を検討する. | |
84
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 |
85 | 15 ## Continuation Based C (CbC) |
16 | |
88 | 17 - Continuation Based C (CbC) はCodeGearを単位として用いたプログラミング言語である. |
85 | 18 - CodeGearはCの通常の関数呼び出しとは異なり,スタックに値を積まず, 次のCodeGearにgoto文によって遷移する. |
19 - このgoto文による遷移を軽量継続と呼ぶ. | |
20 - CodeGearはCの関数宣言の型名の代わりに`__code`と書く事で宣言出来る. | |
21 | |
22 ``` | |
23 extern int printf(const char*,...); | |
24 int main (){ | |
25 int data = 0; | |
26 goto cg1(&data); | |
27 } | |
28 __code cg1(int *datap){ | |
29 (*datap)++; | |
30 goto cg2(datap); | |
31 } | |
32 __code cg2(int *datap){ | |
33 (*datap)++; | |
34 printf("%d\n",*datap); | |
35 } | |
36 ``` | |
37 | |
38 ## CbCの現在の実装 | |
39 | |
86 | 40 - CbCは現在3種類の実装がある. |
85 | 41 - gcc (version 9.0.0) |
42 - llvm/clang (version 7.0.0) | |
86 | 43 - micro-c |
85 | 44 |
45 ## 言語処理系の応用 | |
88 | 46 - スクリプト言語処理系は, バイトコードにコンパイルされ, バイトコードをJITを用いてネイティブに変換する |
47 - JITを使わない場合, バイトコードに対応した, case文や, ラベルのテーブルにgotoすることで処理を実行する | |
48 - CbCを言語処理系に応用した場合, バイトコードに対応するCodeGearを生成することが可能である | |
49 - バイトコードに対応したCodeGearは, CodeGearのテーブルを経由することで実行出来る | |
50 - CodeGearに分割することで, 処理を複数の関数で記述する事が出来, ファイル分割などのモジュール化が可能となる | |
85 | 51 |
52 ## Rakudo | |
53 - Rakudoとは現在のPerl6の主力な実装である. | |
54 - 実行環境のVM, Perl6のサブセットであるNQP(NotQuitPerl), NQPで記述されたPerl6(Rakudo)という構成になっている. | |
88 | 55 - コンパイラは, NQPで記述されたPerl6コンパイラ, NQPで記述されたNQPコンパイラ, MoarVMバイトコードを解釈するMoarVMという構成である |
85 | 56 |
88 | 57 - 現在はMoarVMがRakudoの中でも主流なVM実装となっている. |
85 | 58 |
59 ## MoarVM | |
60 | |
61 - Perl6専用のVMであり, Cで記述されている | |
62 - レジスタマシンとして実装されている. | |
63 - MoarVMはバイトコードインタプリタを `src/core/interp.c` で定義しており, この中の関数 `MVM_interp_run` で命令に応じた処理を実行する | |
64 | |
65 ## MVM_interp_run | |
66 | |
88 | 67 - DISPATCHマクロは次の様に記述されており, この中の `OP` で宣言されたブロックがそれぞれオペコードに対応する処理となっている. |
68 - この中では `GET_REG` などのマクロを用いてMoarVMのレジスタにアクセスする. | |
69 - `cur_op`は次のオペコード列が登録されており, マクロ `NEXT` で決められた方法で次のオペコードに遷移する. | |
70 | |
71 ``` | |
72 DISPATCH(NEXT_OP) { | |
73 OP(const_i64): | |
74 GET_REG(cur_op, 0).i64 = MVM_BC_get_I64(cur_op, 2); | |
75 cur_op += 10; | |
76 goto NEXT; | |
77 } | |
78 | |
79 ``` | |
80 | |
81 ## MVM_interp_run | |
82 | |
85 | 83 - MVM_interp_runでは次のオペコードをフェッチする際に `NEXT_OP` マクロを介して計算を行う. |
84 - オペコードが対応する命令を実行する際は, `MVM_CGOTO` フラグが立っている場合はCのラベルgotoを利用し, 使えない場合はswitch文を利用して遷移する. | |
85 | |
86 | |
87 ``` | |
88 #define NEXT_OP (op = *(MVMuint16 *)(cur_op), cur_op += 2, op) | |
89 | |
90 #if MVM_CGOTO | |
91 #define DISPATCH(op) | |
92 #define OP(name) OP_ ## name | |
93 #define NEXT *LABELS[NEXT_OP] | |
94 #else | |
95 #define DISPATCH(op) switch (op) | |
96 #define OP(name) case MVM_OP_ ## name | |
97 #define NEXT runloop | |
98 #endif | |
99 ``` | |
100 | |
101 ## MVM_interp_run | |
102 | |
103 - ラベル遷移を利用する場合は配列`LABELS`にアクセスし, ラベル情報を取得する | |
104 | |
105 ``` | |
106 static const void * const LABELS[] = { | |
107 &&OP_no_op, | |
108 &&OP_const_i8, | |
109 &&OP_const_i16, | |
110 &&OP_const_i32, | |
111 &&OP_const_i64, | |
112 &&OP_const_n32, | |
113 &&OP_const_n64, | |
114 &&OP_const_s, | |
115 &&OP_set, | |
116 &&OP_extend_u8, | |
117 &&OP_extend_u16, | |
118 &&OP_extend_u32, | |
119 &&OP_extend_i8, | |
120 &&OP_extend_i16, | |
121 ``` | |
122 | |
123 | |
124 ## MVM_interp_run | |
125 | |
126 - Cの実装の場合, switch文に展開される可能性がある為, 命令ディスパッチが書かれているCソース・ファイルの指定の場所にのみ処理を記述せざるを得ない | |
127 - その為, 1ファイルあたりの記述量が膨大になり, 命令のモジュール化ができない | |
128 - Threaded Codeの実装を考えた場合, この命令に対応して大幅に処理系の実装を変更する必要がある. | |
129 - デバッグ時には今どの命令を実行しているか, ラベルテーブルを利用して参照せざるを得ず, 手間がかかる. | |
130 | |
131 | |
132 | |
133 ## CbCMoarVMのバイトコードディスパッチ | |
134 | |
135 - interp.cではマクロを利用した cur_op (現在のオペコード) の計算及び, マクロ遷移かswitch文を利用して次の命令列に遷移していた | |
136 - CbCMoarVMでは, それぞれの命令に対応するCodeGearを生成し, このCodeGearの集合であるテーブルCODESを作成した | |
137 - このテーブルは`cbc_next`というCodeGearから参照し, 以降はこのCodeGearの遷移として処理が継続される. | |
138 | |
139 ``` | |
140 #define NEXT_OP(i) (i->op = *(MVMuint16 *)(i | |
141 ->cur_op), i->cur_op += 2, i->op) | |
142 #define DISPATCH(op) {goto (CODES[op])(i);} | |
143 #define OP(name) OP_ ## name | |
144 #define NEXT(i) CODES[NEXT_OP(i)](i) | |
145 static int tracing_enabled = 0; | |
146 | |
147 _code cbc_next(INTERP i){ | |
148 goto NEXT(i); | |
149 } | |
150 ``` | |
84
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 |
85 | 152 ``` |
153 __code (* CODES[])(INTERP) = { | |
154 cbc_no_op, | |
155 cbc_const_i8, | |
156 cbc_const_i16, | |
157 cbc_const_i32, | |
158 cbc_const_i64, | |
159 cbc_const_n32, | |
160 cbc_const_n64, | |
161 cbc_const_s, | |
162 cbc_set, | |
163 cbc_extend_u8, | |
164 cbc_extend_u16, | |
165 ``` | |
166 | |
167 ## CodeGearの入出力インターフェイス | |
168 | |
169 - MoarVMではレジスタの集合や命令列などをMVM_interp_runのローカル変数として利用し, 各命令実行箇所で参照している | |
170 - CodeGearに書き換えた場合, このローカル変数にはアクセスする事が不可能となる. | |
171 - その為, 入出力としてMoarVMの情報をまとめた構造体interpのポインタであるINTERPを受け渡し, これを利用してアクセスする | |
172 | |
173 | |
174 ``` | |
175 typedef struct interp { | |
176 MVMuint16 op; | |
177 MVMuint8 *cur_op; | |
178 MVMuint8 *bytecode_start; | |
179 MVMRegister *reg_base; | |
180 /* Points to the current compilation unit | |
181 . */ | |
182 MVMCompUnit *cu; | |
183 /* The current call site we’re | |
184 constructing. */ | |
185 MVMCallsite *cur_callsite; | |
186 MVMThreadContext *tc; | |
187 } INTER,*INTERP; | |
188 ``` | |
189 | |
190 ## DataGearへの変換 | |
191 | |
192 - バイトコードに対応する命令をそれぞれCodeGearに変換していく. | |
193 - `OP(.*)`の`(.*)`の部分をCodeGearの名前として先頭に `cbc_` をつけた上で設定する. | |
194 - cur_opなどはINTERPを経由してアクセスする様に修正する. | |
195 - 末尾の `NEXT` を次のCodeGearにアクセスする為に `cbc_next` に修正する. | |
196 - case文で次のcase文に流れる箇所は, 直接その下のcase文に該当するCodeGearに遷移する. | |
88 | 197 - GC対策の為に, CodeGear中のローカル変数をグローバル変数の配列に保存している箇所は,CodeGearに直接処理を書かず, CodeGearから別の関数を呼び出す形に修正する |
198 - その際に, 保存するローカル変数をstatic変数に修正するなどの工夫を行う | |
85 | 199 |
200 | |
201 ``` | |
202 __code cbc_no_op(INTERP i){ | |
203 goto cbc_next(i); | |
204 } | |
205 __code cbc_const_i8(INTERP i){ | |
206 goto cbc_const_i16(i); | |
207 } | |
208 __code cbc_const_i16(INTERP i){ | |
209 goto cbc_const_i32(i); | |
210 } | |
211 __code cbc_const_i32(INTERP i){ | |
212 MVM_exception_throw_adhoc(i->tc, "const_iX NYI"); | |
213 goto cbc_const_i64(i); | |
214 } | |
215 __code cbc_const_i64(INTERP i){ | |
216 GET_REG(i->cur_op, 0,i).i64 = MVM_BC_get_I64(i->cur_op, 2); | |
217 i->cur_op += 10; | |
218 goto cbc_next(i); | |
219 } | |
220 __code cbc_pushcompsc(INTERP i){ | |
221 MVMObject * sc; | |
222 sc = GET_REG(i->cur_op, 0,i).o; | |
223 if (REPR(sc)->ID != MVM_REPR_ID_SCRef) | |
224 MVM_exception_throw_adhoc(i->tc, "Can only push an SCRef with pushcompsc"); | |
225 if (MVM_is_null(i->tc, i->tc->compiling_scs)) { | |
226 MVMROOT(i->tc, sc, { | |
227 i->tc->compiling_scs = MVM_repr_alloc_init(i->tc, i->tc->instance->boot_types.BOOTArray); | |
228 }); | |
229 } | |
230 MVM_repr_unshift_o(i->tc, i->tc->compiling_scs, sc); | |
231 i->cur_op += 2; | |
232 goto cbc_next(i); | |
233 } | |
234 ``` | |
235 | |
88 | 236 ## NQP |
237 - Perl6の機能を制約したプログラミング言語であり, Perl6はNQPで記述されている | |
238 - その為Perl6処理系は, NQPの動作を目的に実装することでPerl6の動作が可能となる | |
239 - NQPコンパイラ自身もNQPで記述されている | |
240 - Perl6と違い, 変数の宣言を `:=` を利用した束縛で行う, `++` 演算子が使用できないなどの違いがある | |
241 - nqpのオペコードを利用する際に,型を指定する事が可能である | |
242 | |
243 ``` | |
244 sub add_test(int $n) { | |
245 my $sum := 0; | |
246 while nqp::isgt_i($n,1) { | |
247 $sum := nqp::add_i($sum,$n); | |
248 $n := nqp::sub_i($n,1); | |
249 } | |
250 return $sum; | |
251 } | |
252 | |
253 say(add_test(10)); | |
254 ``` | |
255 | |
85 | 256 ## MoarVMのデバッグ手法 |
257 | |
258 - MoarVMはバイトコードをランダムに生成する仕様となっている | |
259 - 一旦moarvmバイトコードとして出力したファイルを実行する場合は同じ処理内容となっている | |
260 - そのため, MoarVMのデバッグは同じバイトコードを入力として与え, オリジナルのMoarVMと並列してgdbを用いてトレースを行う. | |
261 - この際, 実行するバイトコードの数が膨大となるので, scriptコマンドを用いて実行するバイトコードの番号を吐き出し, ログファイルを用いて比較する. | |
262 | |
263 ## MoarVMのデバッグ時のbreak point | |
264 | |
265 - CbC側では次のオペコードの遷移は `cbc_next` というCodeGearで行う | |
266 - CodeGearは関数として扱える為, これに直接break pointを設定する | |
84
6c69fdd1716c
add slide.md (template...)
Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
267 |
85 | 268 ``` |
269 (gdb) b cbc_next | |
270 Breakpoint 2 at 0x7ffff7560288: file src/core | |
271 /cbc-interp.cbc, line 61. | |
272 (gdb) command 2 | |
273 Type commands for breakpoint(s) 2, one per | |
274 line. | |
275 End with a line saying just "end". | |
276 >p CODES[*(MVMuint16 *)i->cur_op] | |
277 >p *(MVMuint16 *)i->cur_op | |
278 >c | |
279 >end | |
280 ``` | |
281 - オリジナルの場合マクロである為, dummy関数をマクロに記述し, この関数にbreakpointを設定する | |
282 | |
283 ``` | |
284 dalmore gdb --args ../../MoarVM_Original/ | |
285 MoarVM/moar --libpath=src/vm/moar/stage0 | |
286 gen/moar/stage1/nqp | |
287 (gdb) b dummy | |
288 Function "dummy" not defined. | |
289 Make breakpoint pending on future shared | |
290 library load? (y or [n]) y | |
291 Breakpoint 1 (dummy) pending. | |
292 (gdb) command 1 | |
293 Type commands for breakpoint(s) 1, one per | |
294 line. | |
295 End with a line saying just "end". | |
296 >up | |
297 >p *(MVMuint16 *)(cur_op) | |
298 >c | |
299 >end | |
300 ``` | |
301 | |
302 ## MoarVMのトレース | |
303 | |
304 - トレース時には次の様なデバッグ情報の表示を利用する | |
305 - デバッガに, breakpointで停止した際のcur_opの値を表示する様に設定する. | |
306 | |
307 ``` | |
308 Breakpoint 1, dummy () at src/core/interp.c | |
309 :46 | |
310 46 } | |
311 #1 0x00007ffff75608fe in MVM_interp_run (tc=0 | |
312 x604a20, | |
313 initial_invoke=0x7ffff76c7168 < | |
314 toplevel_initial_invoke>, invoke_data | |
315 =0x67ff10) | |
316 at src/core/interp.c:119 | |
317 119 goto NEXT; | |
318 $1 = 159 | |
319 Breakpoint 1, dummy () at src/core/interp.c | |
320 :46 | |
321 46 } | |
322 #1 0x00007ffff75689da in MVM_interp_run (tc=0 | |
323 x604a20, | |
324 initial_invoke=0x7ffff76c7168 < | |
325 toplevel_initial_invoke>, invoke_data | |
326 =0x67ff10) | |
327 at src/core/interp.c:1169 | |
328 1169 goto NEXT; | |
329 $2 = 162 | |
330 ``` | |
88 | 331 |
332 ## アレ | |
333 | |
334 ``` | |
335 100 MVM_STATIC_INLINE MVMint64 MVM_BC_get_I64(const MVMuint8 *cur_op, int offset) { | |
336 101 const MVMuint8 *const where = cur_op + offset; | |
337 102 #ifdef MVM_CAN_UNALIGNED_INT64 | |
338 103 return *(MVMint64 *)where; | |
339 104 #else | |
340 105 MVMint64 temp; | |
341 106 memmove(&temp, where, sizeof(MVMint64)); | |
342 107 return temp; | |
343 108 #endif | |
344 109 } | |
345 ``` | |
346 | |
85 | 347 ## MoarVMのデバッグ |
348 | |
349 - cur_opのみをPerlスクリプトなどを用いて抜き出し, 並列にログを取得したオリジナルと差分を図る | |
350 - この際に差異が発生したオペコードを確認し, その前の状態で確認していく | |
351 | |
352 ``` | |
353 131 : 131 | |
354 139 : 139 | |
355 140 : 140 | |
356 144 : 144 | |
357 558 : 558 | |
358 391 : 391 | |
359 749 : 749 | |
360 53 : 53 | |
361 *54 : 8 | |
362 ``` | |
363 ## 現在のCbCMoarVM | |
364 | |
365 - 現在はNQP, Rakudoのセルフビルドが達成でき, オリジナルと同等のテスト達成率を持っている | |
366 - moarの起動時のオプションとして `--cbc` を与えることによりCbCで動き, そうでない場合は通常のCで記述された箇所で実行される | |
367 | |
368 ## CbCMoarVMの利点 | |
369 | |
370 - バイトコードインタプリタの箇所をモジュール化する事が可能となり, CodeGearの再利用性や記述生が高まる | |
371 - デバッグ時にラベルではなくCodeGearにbreakpointを設定可能となり,デバッグが安易となる | |
372 - ThreadedCodeを実装する場合, CodeGearを組み合わせることにより実装する事が可能となる | |
373 | |
374 ## CbCMoarVMの欠点 | |
375 | |
376 - CbCコンパイラがバグを発生させやすく, 意図しない挙動を示す事がある | |
88 | 377 - CbCコンパイラ自体のバグも存在する |
85 | 378 - MoarVMのオリジナルの更新頻度が高い為, 追従していく必要がある |
379 - CodeGear側からCに戻る際に手順が複雑となる | |
380 - CodeGearを単位として用いる事で複雑なプログラミングが要求される. | |
381 | |
88 | 382 ## ThreadedCodeの実装 |
383 | |
384 - MoarVM内のオペコードに対応する処理が分離出来たことにより, オペコードに該当するCodeGearを書き連ねることによってThreadedCodeが実装可能となる | |
385 | |
386 | |
85 | 387 ## CbCMoarVMと通常のMoarVMの比較 |
388 | |
389 - CbCMoarVMと通常のMoarVMの速度比較を行った | |
88 | 390 - 対象として, 単純なループで数値をインクリメントする例題と, フィボナッチ数列を求める例題を選択した |
391 - NQPで実装した場合とPerl6で実装した場合の速度を計測した | |
85 | 392 |
393 ``` | |
394 #! nqp | |
88 | 395 |
396 my $count := 100_000_000; | |
85 | 397 |
398 my $i := 0; | |
88 | 399 |
400 while ++$i <= $count { | |
85 | 401 } |
402 ``` | |
403 | |
404 ``` | |
88 | 405 #! nqp |
406 | |
407 sub fib($n) { | |
408 $n < 2 ?? $n !! fib($n-1) + fib($n - 2); | |
409 } | |
85 | 410 |
88 | 411 my $N := 29; |
85 | 412 |
88 | 413 my $t0 := nqp::time_n(); |
414 my $z := fib($N); | |
415 my $t1 := nqp::time_n(); | |
416 | |
417 say("fib($N) = " ~ fib($N)); | |
418 say("time = " ~ ($t1-$t0)); | |
85 | 419 |
420 ``` | |
88 | 421 # フィボナッチの例題 |
422 | |
423 - フィボナッチの例題ではCbCMoarVMが劣る結果となった | |
424 | |
425 | |
426 ## 単純ループ | |
427 | |
428 - オリジナル | |
429 - 7.499 sec | |
430 - 7.844 sec | |
431 - 6.074 sec | |
432 - CbCMoarVM | |
433 - 6.135 sec | |
434 - 6.362 sec | |
435 - 6.074 sec | |
436 | |
437 - 単純ループではCbCMoarVMの方が高速に動作する場合もある | |
438 | |
439 ## まとめ | |
440 | |
441 - 速度を計測した所, 現在はCbCMoarVMの方が僅かに劣る結果となった | |
442 - ただしフィボナッチを求める例題などで, ケースによってはCbCMoarVMの方が高速に動作する場合もある | |
443 | |
444 | |
445 ## まとめと今後の課題 | |
446 - 継続と基本としたC言語 Continuation Based Cを用いてPerl6の処理系の一部を書き直した | |
447 - CbCの持つCodeGearによって, 本来はモジュール化出来ない箇所をモジュール化する事が出来た | |
448 - MoarVMの速度改善にはThreadedCodeが期待でき, CodeGearベースの命令ディスパッチとThreadedCodeは相性が良いと考えられる | |
449 - 今後は実行するバイトコードによりThreadedCode箇所と通常の配列を読み取り, 次のCodeGearを計算する処理を両立させていく | |
450 |