Mercurial > hg > Papers > 2019 > anatofuz-prosym
diff 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 |
line wrap: on
line diff
--- a/Slide/slide.md Thu Jan 10 10:32:17 2019 +0900 +++ b/Slide/slide.md Thu Jan 10 21:55:46 2019 +0900 @@ -7,26 +7,17 @@ ## 研究目的 - スクリプト言語であるPerl5の後継言語としてPerl6が現在開発されている. -- 現在主流なPerl6はRakudoと言われるプロジェクトである. -- RakudoではPerl6自体をNQP(NotQuitPerl)と言われるPerl6のサブセットで記述し, NQPをVMが解釈するという処理の流れになっている. -- 主に利用されているVMに, Cで書かれたMoarVMが存在する. -- MoarVMは全体的な起動時間及び処理速度が, Perl5と比較し非常に低速である. -- この問題を解決するためにContinuation based C (CbC)という言語を一部用いてMoarVMの書き換えを行う. -- CbCを用いたMoarVMの書き換えを検討し,並列デバッグ方法などについて検討する. +- 現在主流なPerl6の実装にRakudoがあり, RakudoはNQP(Perl6のサブセット)で記述されたPerl6, NQPで記述されたNQPコンパイラがある +- NQPコンパイラはRakudoのVMであるMoarVM用のバイトコードを生成し, MoarVMはこのバイトコードを解釈, 実行する +- Continuation based C (CbC)という言語は継続を基本とするC言語であり, 言語処理系に応用出来ると考えられる +- CbC一部用いてMoarVMの書き換えを行い, 処理を検討する. ## Continuation Based C (CbC) -- Continuation Based C (CbC) はCodeGearとDataGearを単位として用いたプログラミング言語である. +- Continuation Based C (CbC) はCodeGearを単位として用いたプログラミング言語である. - CodeGearはCの通常の関数呼び出しとは異なり,スタックに値を積まず, 次のCodeGearにgoto文によって遷移する. - このgoto文による遷移を軽量継続と呼ぶ. -- CbCは軽量継続を取り入れたCの下位言語であり, C言語のAPIを利用可能なCと互換性のある言語である. - -## CodeGearとDetaGear - -- Cの関数の代わりにCodeGearという単位をCbCでは導入している. - CodeGearはCの関数宣言の型名の代わりに`__code`と書く事で宣言出来る. -- CodeGearの引数を遷移先のCodeGearと揃えることでレジスタに変数を確保した状態で軽量継続可能である. -- その為CodeGearの引数は入出力としての意味があり, DataGearと呼んでいる. ``` extern int printf(const char*,...); @@ -52,32 +43,18 @@ - micro-c ## 言語処理系の応用 -- CbCではCodeGearを処理単位として利用でき, これはコンパイラの基本ブロックに相当する. -- 従来のスクリプト言語などの処理系では, 主にcase文で実装していた命令コードディスパッチの箇所をCodeGearの遷移として記述する事が可能である. -- CodeGearの遷移として記述する事で, 命令処理ごとに分割する事が可能となり, モジュール化が可能となる. -- CodeGearとCodeGearの遷移時に入出力のインターフェイスを揃える事で, レジスタに変数が割り振られたまま軽量継続が可能となり, レジスタレベルの最適化が可能となる. -- これらの検証とPerl6の高速化を行う為に, CbCを用いてPerl6処理系の書き換えを行っていく. - -## Perl6の概要 - -- Perl6とはPerl5の後継言語として当初開発が開始された言語である. -- 仕様と実装が分離しており, 仕様は公式テストスーツであるRoastそのものとなっている. -- 歴史的にHaskellで実装されたPugs, Pythonとの共同基盤を目指したParrotなどの実装が存在する. -- 言語仕様としては漸進的型付け言語であり, 従来のPerl5とは互換性が無い. -- 現在の主要な実装はRakudoと呼ばれる実装である. +- スクリプト言語処理系は, バイトコードにコンパイルされ, バイトコードをJITを用いてネイティブに変換する +- JITを使わない場合, バイトコードに対応した, case文や, ラベルのテーブルにgotoすることで処理を実行する +- CbCを言語処理系に応用した場合, バイトコードに対応するCodeGearを生成することが可能である +- バイトコードに対応したCodeGearは, CodeGearのテーブルを経由することで実行出来る +- CodeGearに分割することで, 処理を複数の関数で記述する事が出来, ファイル分割などのモジュール化が可能となる ## Rakudo - Rakudoとは現在のPerl6の主力な実装である. - 実行環境のVM, Perl6のサブセットであるNQP(NotQuitPerl), NQPで記述されたPerl6(Rakudo)という構成になっている. -- VMはCで書かれたPerl6専用のVMであるMoarVM, JavaVMが選択可能である. -- 現在はMoarVMがRakudoの中でも主流なVM実装となっている. +- コンパイラは, NQPで記述されたPerl6コンパイラ, NQPで記述されたNQPコンパイラ, MoarVMバイトコードを解釈するMoarVMという構成である -## Rakudo -- Rakudoにおけるコンパイラは2種類存在する - - Perl6やNQPのコードをVMのバイトコードに変換するコンパイラ - - NQPが出力したVMのバイトコードをネイティブコードに変換するコンパイラ -- NQPの処理系nqp及び, Perl6のインタプリタである perl6は, それぞれセルフコンパイルしたものを利用する -- Perl6は純粋なNQPではなく, Perl6自身によって拡張され記述されている箇所も存在する +- 現在はMoarVMがRakudoの中でも主流なVM実装となっている. ## MoarVM @@ -87,6 +64,22 @@ ## MVM_interp_run +- DISPATCHマクロは次の様に記述されており, この中の `OP` で宣言されたブロックがそれぞれオペコードに対応する処理となっている. +- この中では `GET_REG` などのマクロを用いてMoarVMのレジスタにアクセスする. +- `cur_op`は次のオペコード列が登録されており, マクロ `NEXT` で決められた方法で次のオペコードに遷移する. + +``` +DISPATCH(NEXT_OP) { + OP(const_i64): + GET_REG(cur_op, 0).i64 = MVM_BC_get_I64(cur_op, 2); + cur_op += 10; + goto NEXT; +} + +``` + +## MVM_interp_run + - MVM_interp_runでは次のオペコードをフェッチする際に `NEXT_OP` マクロを介して計算を行う. - オペコードが対応する命令を実行する際は, `MVM_CGOTO` フラグが立っている場合はCのラベルgotoを利用し, 使えない場合はswitch文を利用して遷移する. @@ -127,40 +120,6 @@ &&OP_extend_i16, ``` -## MVM_interp_run - -- DISPATCHマクロは次の様に記述されており, この中の `OP` で宣言されたブロックがそれぞれオペコードに対応する処理となっている. -- この中では `GET_REG` などのマクロを用いてMoarVMのレジスタにアクセスする. -- `cur_op`は次のオペコードを意味し, マクロ `NEXT` で決められた方法で次のオペコードに遷移する. - -``` -DISPATCH(NEXT_OP) { - OP(no_op): - goto NEXT; - OP(const_i8): - OP(const_i16): - OP(const_i32): - MVM_exception_throw_adhoc(tc, "const_iX NYI"); - OP(const_i64): - GET_REG(cur_op, 0).i64 = MVM_BC_get_I64(cur_op, 2); - cur_op += 10; - goto NEXT; - OP(pushcompsc): { - MVMObject * const sc = GET_REG(cur_op, 0).o; - if (REPR(sc)->ID != MVM_REPR_ID_SCRef) - MVM_exception_throw_adhoc(tc, "Can only push an SCRef with pushcompsc"); - if (MVM_is_null(tc, tc->compiling_scs)) { - MVMROOT(tc, sc, { - tc->compiling_scs = MVM_repr_alloc_init(tc, tc->instance->boot_types.BOOTArray); - }); - } - MVM_repr_unshift_o(tc, tc->compiling_scs, sc); - cur_op += 2; - goto NEXT; - } -} - -``` ## MVM_interp_run @@ -169,33 +128,7 @@ - Threaded Codeの実装を考えた場合, この命令に対応して大幅に処理系の実装を変更する必要がある. - デバッグ時には今どの命令を実行しているか, ラベルテーブルを利用して参照せざるを得ず, 手間がかかる. -## NQP -- MoarVM, JVM上で動作する Perl6のサブセットとなっている. -- NQPの基本文法はPerl6に準拠しているが, 束縛ベースで変数を利用するなどいくつか異なる点が存在する. -- NQPは最終的にブートストラップを行う処理系であるが, 初回のビルド時には, すでに書かれたMoarVM, JVMのバイトコードを必要とする. - - この状態をStage0といい, Stage0を利用してStage1, Stage1を利用してStage2をビルドする事で完成する. -- NQPの実行可能なインタプリタである`nqp`は, MoarVMの実行バイナリ`moar` にライブラリパスなどを設定し, ビルドしたライブラリなどを引数として渡すシェルスクリプトとなっている. -- `nqp` を実行する事でREPLが起動され, NQPスクリプトを `nqp` に入力として与える事で, 通常のスクリプト言語の様に実行する事が可能となる. -- NQPの設計はRoastで定義されているPerl6とは異なり, 今後も変化していく事が公表されている. -``` -#! nqp - -sub fib($n) { - $n < 2 ?? $n !! fib($n-1) + fib($n - 2); -} - -my $N := 29; - -my $z := fib($N); - -say("fib($N) = " ~ fib($N)); -``` - -## CbCによるMoarVM - -- MoarVMの中心部分はバイトコードを解釈するバイトコードインタプリタである. -- その為, CbCを用いてMoarVMのバイトコードインタプリタ部分の書き換えを検討する. ## CbCMoarVMのバイトコードディスパッチ @@ -241,16 +174,8 @@ ``` typedef struct interp { MVMuint16 op; - /* Points to the place in the bytecode - right after the current opcode. */ - /* See the NEXT_OP macro for making sense - of this */ MVMuint8 *cur_op; - /* The current frame’s bytecode start. */ MVMuint8 *bytecode_start; - /* Points to the base of the current - register set for the frame we - * are presently in. */ MVMRegister *reg_base; /* Points to the current compilation unit . */ @@ -269,8 +194,9 @@ - cur_opなどはINTERPを経由してアクセスする様に修正する. - 末尾の `NEXT` を次のCodeGearにアクセスする為に `cbc_next` に修正する. - case文で次のcase文に流れる箇所は, 直接その下のcase文に該当するCodeGearに遷移する. +- GC対策の為に, CodeGear中のローカル変数をグローバル変数の配列に保存している箇所は,CodeGearに直接処理を書かず, CodeGearから別の関数を呼び出す形に修正する + - その際に, 保存するローカル変数をstatic変数に修正するなどの工夫を行う -- 論文執筆時はstaticに修正する必要があったが, その後CbCコンパイラの改良により不要となった. ``` __code cbc_no_op(INTERP i){ @@ -307,6 +233,26 @@ } ``` +## NQP +- Perl6の機能を制約したプログラミング言語であり, Perl6はNQPで記述されている + - その為Perl6処理系は, NQPの動作を目的に実装することでPerl6の動作が可能となる + - NQPコンパイラ自身もNQPで記述されている +- Perl6と違い, 変数の宣言を `:=` を利用した束縛で行う, `++` 演算子が使用できないなどの違いがある +- nqpのオペコードを利用する際に,型を指定する事が可能である + +``` +sub add_test(int $n) { + my $sum := 0; + while nqp::isgt_i($n,1) { + $sum := nqp::add_i($sum,$n); + $n := nqp::sub_i($n,1); + } + return $sum; +} + +say(add_test(10)); +``` + ## MoarVMのデバッグ手法 - MoarVMはバイトコードをランダムに生成する仕様となっている @@ -382,6 +328,22 @@ 1169 goto NEXT; $2 = 162 ``` + +## アレ + +``` +100 MVM_STATIC_INLINE MVMint64 MVM_BC_get_I64(const MVMuint8 *cur_op, int offset) { +101 const MVMuint8 *const where = cur_op + offset; +102 #ifdef MVM_CAN_UNALIGNED_INT64 +103 return *(MVMint64 *)where; +104 #else +105 MVMint64 temp; +106 memmove(&temp, where, sizeof(MVMint64)); +107 return temp; +108 #endif +109 } +``` + ## MoarVMのデバッグ - cur_opのみをPerlスクリプトなどを用いて抜き出し, 並列にログを取得したオリジナルと差分を図る @@ -412,36 +374,77 @@ ## CbCMoarVMの欠点 - CbCコンパイラがバグを発生させやすく, 意図しない挙動を示す事がある + - CbCコンパイラ自体のバグも存在する - MoarVMのオリジナルの更新頻度が高い為, 追従していく必要がある - CodeGear側からCに戻る際に手順が複雑となる - CodeGearを単位として用いる事で複雑なプログラミングが要求される. +## ThreadedCodeの実装 + +- MoarVM内のオペコードに対応する処理が分離出来たことにより, オペコードに該当するCodeGearを書き連ねることによってThreadedCodeが実装可能となる + + ## CbCMoarVMと通常のMoarVMの比較 - CbCMoarVMと通常のMoarVMの速度比較を行った +- 対象として, 単純なループで数値をインクリメントする例題と, フィボナッチ数列を求める例題を選択した +- NQPで実装した場合とPerl6で実装した場合の速度を計測した ``` #! nqp -# Example of a while loop + +my $count := 100_000_000; my $i := 0; -while $i < 10 { - say("i={$i++}"); + +while ++$i <= $count { } ``` ``` -subset Fizz of Int where * %% 3; -subset Buzz of Int where * %% 5; -subset FizzBuzz of Int where Fizz&Buzz; -subset Number of Int where none Fizz|Buzz; +#! nqp + +sub fib($n) { + $n < 2 ?? $n !! fib($n-1) + fib($n - 2); +} -proto sub fizzbuzz ($) { * } -multi sub fizzbuzz (FizzBuzz) { "FuzzBuzz" } -multi sub fizzbuzz (Fizz) { "Fizz" } -multi sub fizzbuzz (Buzz) { "Buzz" } -multi sub fizzbuzz (Number $number) { $number } +my $N := 29; -fizzbuzz($_).say for 1..15; +my $t0 := nqp::time_n(); +my $z := fib($N); +my $t1 := nqp::time_n(); + +say("fib($N) = " ~ fib($N)); +say("time = " ~ ($t1-$t0)); ``` +# フィボナッチの例題 + +- フィボナッチの例題ではCbCMoarVMが劣る結果となった + + +## 単純ループ + +- オリジナル + - 7.499 sec + - 7.844 sec + - 6.074 sec +- CbCMoarVM + - 6.135 sec + - 6.362 sec + - 6.074 sec + +- 単純ループではCbCMoarVMの方が高速に動作する場合もある + +## まとめ + +- 速度を計測した所, 現在はCbCMoarVMの方が僅かに劣る結果となった +- ただしフィボナッチを求める例題などで, ケースによってはCbCMoarVMの方が高速に動作する場合もある + + +## まとめと今後の課題 +- 継続と基本としたC言語 Continuation Based Cを用いてPerl6の処理系の一部を書き直した +- CbCの持つCodeGearによって, 本来はモジュール化出来ない箇所をモジュール化する事が出来た +- MoarVMの速度改善にはThreadedCodeが期待でき, CodeGearベースの命令ディスパッチとThreadedCodeは相性が良いと考えられる +- 今後は実行するバイトコードによりThreadedCode箇所と通常の配列を読み取り, 次のCodeGearを計算する処理を両立させていく +