Mercurial > hg > Papers > 2019 > anatofuz-thesis
view presen/slide.html @ 94:19df48819b8d
update
| author | anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 19 Feb 2019 15:02:16 +0900 |
| parents | 9c5bf7231557 |
| children | 77fb6e9e3c08 |
line wrap: on
line source
<!DOCTYPE html> <html> <head> <meta http-equiv="content-type" content="text/html;charset=utf-8"> <title>CbCによるPerl6処理系</title> <meta name="generator" content="Slide Show (S9) v4.0.1 on Ruby 2.5.1 (2018-03-29) [x86_64-darwin17]"> <meta name="author" content="Takahiro Shimizu, Shinji Kono" > <!-- style sheet links --> <link rel="stylesheet" href="s6/themes/projection.css" media="screen,projection"> <link rel="stylesheet" href="s6/themes/screen.css" media="screen"> <link rel="stylesheet" href="s6/themes/print.css" media="print"> <link rel="stylesheet" href="s6/themes/blank.css" media="screen,projection"> <!-- JS --> <script src="s6/js/jquery-1.11.3.min.js"></script> <script src="s6/js/jquery.slideshow.js"></script> <script src="s6/js/jquery.slideshow.counter.js"></script> <script src="s6/js/jquery.slideshow.controls.js"></script> <script src="s6/js/jquery.slideshow.footer.js"></script> <script src="s6/js/jquery.slideshow.autoplay.js"></script> <!-- prettify --> <link rel="stylesheet" href="scripts/prettify.css"> <script src="scripts/prettify.js"></script> <script> $(document).ready( function() { Slideshow.init(); $('code').each(function(_, el) { if (!el.classList.contains('noprettyprint')) { el.classList.add('prettyprint'); } }); prettyPrint(); } ); </script> <!-- Better Browser Banner for Microsoft Internet Explorer (IE) --> <!--[if IE]> <script src="s6/js/jquery.microsoft.js"></script> <![endif]--> </head> <body> <div class="layout"> <div id="header"></div> <div id="footer"> <div align="right"> <img src="s6/images/logo.svg" width="200px"> </div> </div> </div> <div class="presentation"> <div class='slide cover'> <table width="90%" height="90%" border="0" align="center"> <tr> <td> <div align="center"> <h1><font color="#808db5">CbCによるPerl6処理系</font></h1> </div> </td> </tr> <tr> <td> <div align="left"> Takahiro Shimizu, Shinji Kono 琉球大学 <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;"> </div> </td> </tr> </table> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="研究目的">研究目的</h2> <ul> <li>現在開発されているPerl6の実装にRakudoがあり, RakudoはNQP(Perl6のサブセット)で記述されたPerl6, NQPで記述されたNQPコンパイラ, NQPを解釈するVMで構成されている</li> <li>NQPコンパイラはRakudoのVMであるMoarVM用のバイトコードを生成する</li> <li>MoarVMはこのバイトコードを解釈, 実行する</li> </ul> <img src="fig/perl6nqp.svg" alt="" /> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="研究目的-1">研究目的</h2> <ul> <li>Continuation based C (CbC)という言語は継続を基本とするC言語であり, 言語処理系に応用出来ると考えられる</li> <li>スクリプト言語などは, バイトコードを扱うが, この実行にcae文や, ラベルgotoなどを利用している。 <ul> <li>この部分はCbCの機能で書き換える事が可能である</li> </ul> </li> <li>命令実行処理部分をモジュール化することで、各命令ごとの最適化や、 命令ディスパッチ部分の最適化を行う事が可能であると考える。</li> <li>従って, CbC一部用いてPerl6にC処理系であるMoarVMの書き換えを行い, 処理を検討する．</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="continuation-based-c-cbc">Continuation Based C (CbC)</h2> <ul> <li>Continuation Based C (CbC) はCodeGearを単位として用いたプログラミング言語である.</li> <li>CodeGearはCの通常の関数呼び出しとは異なり，スタックに値を積まず, 次のCodeGearにgoto文によって遷移する.</li> <li>CodeGear同士の移動は、 状態遷移として捉える事が出来る</li> <li>(図をいれる)</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="continuation-based-c-cbc-1">Continuation Based C (CbC)</h2> <ul> <li>CodeGearはCの関数宣言の型名の代わりに<code>__code</code>と書く事で宣言出来る</li> <li>CodeGearの引数は, 各CodeGearの入出力として利用する</li> <li>gotoしてしまうと、元のCodeGearに戻る事が出来ない</li> </ul> <pre><code>__code cg1(TEST testin){ TEST testout; testout.number = testin.number + 1; testout.string = "Hello"; goto cg2(testout); } __code cg2(TEST testin){ printf("number = %d\t string= %s\n",testin.number,testin.string); } int main(){ TEST test = {0,0}; goto cg1(test); } </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="言語処理系の応用">言語処理系の応用</h2> <ul> <li>スクリプト言語は入力として与えられたソースコードを、 直接評価せずにバイトコードにコンパイルする形式が主流となっている</li> <li>その為スクリプト言語の実装は大きく2つで構成されている <ul> <li>バイトコードに変換するフロントエンド部分</li> <li>バイトコードを解釈する仮想機械</li> </ul> </li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="rakudo">Rakudo</h2> <ul> <li>Rakudoとは現在のPerl6の主力な実装である．</li> <li>Rakudoは次の構成になっている <ul> <li>実行環境のVM</li> <li>Perl6のサブセットであるNQP(NotQuitPerl)</li> <li>NQPで記述されたPerl6(Rakudo)</li> </ul> </li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="moarvm">MoarVM</h2> <ul> <li>Perl6専用のVMであり, Cで記述されている</li> <li>レジスタマシンとして実装されている．</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="moarvmのバイトコード">MoarVMのバイトコード</h2> <ul> <li>MoarVMは16ビットのバイナリを命令バイトコードとして利用している</li> <li>命令にはその後に16ビットごとにオペランド(引数)を取るものがある</li> </ul> <pre><code>add_i loc_3_int, loc_0_int, loc_1_int set loc_2_obj, loc_3_obj </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="moarvmのバイトコードインタプリタ">MoarVMのバイトコードインタプリタ</h2> <ul> <li>バイトコードは連続したメモリに確保されている</li> <li>その為次の処理を繰り返す必要がある <ul> <li>16ビットごとで読み込み</li> <li>読み込んだビットから、命令に対応する処理を呼び出し</li> <li>その処理を実行する</li> </ul> </li> <li>この処理をバイトコードディスパッチと呼び、 実行する部分をバイトコードインタプリタと呼ぶ</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="moarvmのバイトコードインタプリタ-1">MoarVMのバイトコードインタプリタ</h2> <ul> <li>MoarVMは関数 <code>MVM_interp_run</code> でバイトコードに応じた処理を実行する</li> <li>マクロDISPATCHで, ラベルgotoかcase文に変換が行われる <ul> <li>バイトコードは数値として見る事が出来る為、 case文に対応する事が出来る</li> <li>この中の <code>OP</code> で宣言されたブロックがそれぞれバイトコードに対応する処理となっている．</li> </ul> </li> <li><code>cur_op</code>は次のバイトコード列が登録されており, マクロ <code>NEXT</code> で決められた方法で次のバイトコードに対応した処理に遷移する．</li> </ul> <pre><code>DISPATCH(NEXT_OP) { OP(const_i64): GET_REG(cur_op, 0).i64 = MVM_BC_get_I64(cur_op, 2); cur_op += 10; goto NEXT; } </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="mvm_interp_runで使用されているマクロ">MVM_interp_runで使用されているマクロ</h2> <pre><code>DISPATCH(NEXT_OP) { OP(const_i64): </code></pre> <ul> <li>マクロ <code>OP</code> 及び <code>NEXT</code> は次の様に定義している</li> </ul> <pre><code> #define OP(name) OP_ ## name #define NEXT *LABELS[NEXT_OP] </code></pre> <ul> <li>マクロ<code>DISPATCH</code>は, ラベルgotoが利用できる場合は無視される</li> <li>マクロ <code>OP</code> が, 対応するバイトコード命令を, ラベル列に変換する</li> </ul> <pre><code> OP_const_i16: OP_const_i32: MVM_exception_throw_adhoc(tc, "const_iX NYI"); OP_const_i64: </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="mvm_interp_runで使用されているマクロ-1">MVM_interp_runで使用されているマクロ</h2> <ul> <li>次のバイトコード命令に遷移するマクロ <code>NEXT</code> は, ラベルgotoが使用可能な場合次の様に記述されている</li> <li><code>NEXT</code>自体はラベルテーブルにアクセスし, ラベルを取り出す</li> <li>次のバイトコードを取り出すのは, <code>NEXT_OP</code> というマクロが担っている</li> </ul> <pre><code>#define NEXT_OP (op = *(MVMuint16 *)(cur_op), cur_op += 2, op) #define NEXT *LABELS[NEXT_OP] </code></pre> <ul> <li>マクロ <code>NEXT</code> は次の様に展開される</li> </ul> <pre><code>goto *LABELS[(op = *(MVMuint16 *)(cur_op), cur_op += 2, op)]; </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="mvm_interp_runのラベルテーブル">MVM_interp_runのラベルテーブル</h2> <ul> <li>利用するCコンパイラが、ラベルgotoをサポートしている場合に実行される</li> <li>配列<code>LABELS</code>にアクセスし, ラベル情報を取得する</li> <li>ラベル情報を取得出来ると、 そのラベルに対してラベルgotoを利用する</li> </ul> <pre><code>static const void * const LABELS[] = { &&OP_no_op, &&OP_const_i8, &&OP_const_i16, &&OP_const_i32, &&OP_const_i64, &&OP_const_n32, &&OP_const_n64, &&OP_const_s, &&OP_set, &&OP_extend_u8, &&OP_extend_u16, &&OP_extend_u32, &&OP_extend_i8, &&OP_extend_i16, </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="mvm_interp_run">MVM_interp_run</h2> <ul> <li>Cの実装の場合, switch文に展開される可能性がある <ul> <li>命令ディスパッチが書かれているCソース・ファイルの指定の場所にのみ処理を記述せざるを得ない</li> <li>1ファイルあたりの記述量が膨大になり, 命令のモジュール化ができない</li> </ul> </li> <li>高速化手法の、 Threaded Codeの実装を考えた場合, この命令に対応して大幅に処理系の実装を変更する必要がある．</li> <li>デバッグ時には今どの命令を実行しているか, ラベルテーブルを利用して参照せざるを得ず, 手間がかかる．</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="cbcmoarvmのバイトコードディスパッチ">CbCMoarVMのバイトコードディスパッチ</h2> <ul> <li>CbCのCodeGearは関数よりも小さな単位である</li> <li>その為、 従来は関数化出来なかった単位をCodeGearに変換する事が出来る</li> <li>CbCをMoarVMに適応すると, ラベルなどで制御していた命令に対応する処理をCodeGearで記述する事が可能である</li> <li>オリジナルでは, マクロ <code>NEXT</code> が担当していた, 次のバイトコードへの移動は, NEXT相当のCodeGear <code>cbc_next</code>で処理を行う</li> <li>CodeGearの入出力として, MoarVMなどの情報をまとめた構造体を利用する</li> </ul> <pre><code>__code cbc_next(INTERP i){ __code (*c)(INTERP) c = CODES[(i->op = *(MVMuint16 *)(i->cur_op), i->cur_op += 2, i->op)]; // c = NEXT(i) goto c(i); } __code cbc_const_i64(INTERP i){ GET_REG(i->cur_op, 0,i).i64 = MVM_BC_get_I64(i->cur_op, 2); i->cur_op += 10; goto cbc_next(i); } </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="codegearの入出力インターフェイス">CodeGearの入出力インターフェイス</h2> <ul> <li>MoarVMではレジスタの集合や命令列などをMVM_interp_runのローカル変数として利用し, 各命令実行箇所で参照している</li> <li>CodeGearに書き換えた場合, このローカル変数にはアクセスする事が不可能となる．</li> <li>その為, 入出力としてMoarVMの情報をまとめた構造体interpのポインタであるINTERPを受け渡し, これを利用してアクセスする</li> </ul> <pre><code>typedef struct interp { MVMuint16 op; MVMuint8 *cur_op; MVMuint8 *bytecode_start; MVMRegister *reg_base; /* Points to the current compilation unit . */ MVMCompUnit *cu; /* The current call site we’re constructing. */ MVMCallsite *cur_callsite; MVMThreadContext *tc; } INTER,*INTERP; </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="cbcmoarvmのcodegearテーブル">CbCMoarVMのCodeGearテーブル</h2> <ul> <li>CodeGearテーブルは引数としてINTERを受け取るCodeGearの配列として定義する</li> <li>テーブルとして宣言することで、 バイトコードの数をそのままテーブルに反映させる事が可能である</li> </ul> <pre><code>__code (* CODES[])(INTERP) = { cbc_no_op, cbc_const_i8, cbc_const_i16, cbc_const_i32, cbc_const_i64, cbc_const_n32, cbc_const_n64, cbc_const_s, cbc_set, cbc_extend_u8, cbc_extend_u16, </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="cbcmoarvmの利点">CbCMoarVMの利点</h2> <ul> <li>バイトコードインタプリタの箇所をモジュール化する事が可能となった <ul> <li>CodeGearの再利用性や記述生が高まる</li> <li>CodeGearは関数の様に扱えるの為、 命令ディスパッチの最適化につながる実装が可能となった</li> </ul> </li> <li>デバッグ時にラベルではなくCodeGearにbreakpointを設定可能となった <ul> <li>デバッグが安易となる</li> </ul> </li> <li>CPUがキャッシュに収まる範囲の命令の場合、 通常のMoarVMよりも高速に動作する</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="cbcmoarvmの欠点">CbCMoarVMの欠点</h2> <ul> <li>MoarVMのオリジナルの更新頻度が高い為, 追従していく必要がある</li> <li>CodeGear側からCに戻る際に手順が複雑となる</li> <li>CodeGearを単位として用いる事で複雑なプログラミングが要求される.</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="moarvmのトレース">MoarVMのトレース</h2> <ul> <li>トレース時には次の様なデバッグ情報の表示を利用する</li> <li>デバッガに, breakpointで停止した際のcur_opの値を表示する様に設定する．</li> </ul> <pre><code>Breakpoint 1, dummy () at src/core/interp.c:46 46 } #1 0x00007ffff75608fe in MVM_interp_run (tc=0x604a20, initial_invoke=0x7ffff76c7168 <toplevel_initial_invoke>, invoke_data=0x67ff10) at src/core/interp.c:119 119 goto NEXT; $1 = 159 Breakpoint 1, dummy () at src/core/interp.c:46 46 } #1 0x00007ffff75689da in MVM_interp_run (tc=0x604a20, initial_invoke=0x7ffff76c7168 <toplevel_initial_invoke>, invoke_data=0x67ff10) at src/core/interp.c:1169 1169 goto NEXT; $2 = 162 </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="cbcmoarvmのデバッグ">CbCMoarVMのデバッグ</h2> <pre><code>Breakpoint 2, cbc_next (i=0x7fffffffdc30) at src/core/cbc-interp.cbc:61 61 goto NEXT(i); $1 = (void (*)(INTERP)) 0x7ffff7566f53 <cbc_takeclosure> $2 = 162 Breakpoint 2, cbc_next (i=0x7fffffffdc30) at src/core/cbc-interp.cbc:61 61 goto NEXT(i); $3 = (void (*)(INTERP)) 0x7ffff7565f86 <cbc_checkarity> $4 = 140 Breakpoint 2, cbc_next (i=0x7fffffffdc30) at src/core/cbc-interp.cbc:61 61 goto NEXT(i); $5 = (void (*)(INTERP)) 0x7ffff7579d06 <cbc_paramnamesused> $6 = 558 </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="moarvmのデバッグ">MoarVMのデバッグ</h2> <ul> <li>cur_opのみをPerlスクリプトなどを用いて抜き出し, 並列にログを取得したオリジナルと差分を図る</li> <li>この際に差異が発生したバイトコードを確認し, その前の状態で確認していく</li> </ul> <pre><code>25 : 25 : cbc_unless_i 247 : 247 : cbc_null 54 : 54 : cbc_return_o 140 : 140 : cbc_checkarity 558 : 558 : cbc_paramnamesused 159 : 159 : cbc_getcode 391 : 391 : cbc_decont 127 : 127 : cbc_prepargs *139 : 162 cbc_invoke_o:cbc_takeclosure </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="現在のcbcmoarvm">現在のCbCMoarVM</h2> <ul> <li>現在はNQP, Rakudoのセルフビルドが達成でき, オリジナルと同等のテスト達成率を持っている</li> <li>moarの起動時のオプションとして <code>--cbc</code> を与えることによりCbCで動き, そうでない場合は通常のCで記述された箇所で実行される</li> <li>Perl6の実行バイナリperl6, NQPの実行バイナリnqp は, それぞれmoarを起動するシェルスクリプトである為, <code>--cbc</code> オプションをシェルスクリプト内に書き加えることで, Perl6, NQPがそれぞれCbCで起動する</li> </ul> <pre><code>#!/bin/sh exec /mnt/dalmore-home/one/src/Perl6/Optimize/llvm/build_perl6/bin/moar --cbc \ --libpath=/mnt/dalmore-home/one/src/Perl6/Optimize/llvm/build_perl6/share/nqp/lib \ /mnt/dalmore-home/one/src/Perl6/Optimize/llvm/build_perl6/share/nqp/lib/nqp.moarvm "$@" </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="threadedcodeの実装">ThreadedCodeの実装</h2> <ul> <li>MoarVM内のバイトコードに対応する処理が分離出来たことにより, バイトコードに該当するCodeGearを書き連ねることによってThreadedCodeが実装可能となる</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="cbcmoarvmと通常のmoarvmの比較">CbCMoarVMと通常のMoarVMの比較</h2> <ul> <li>CbCMoarVMと通常のMoarVMの速度比較を行った</li> <li>対象として, 単純なループで数値をインクリメントする例題と, フィボナッチ数列を求める例題を選択した</li> <li>NQPで実装し, 速度を計測した</li> </ul> <pre><code>#! nqp my $count := 100_000_000; my $i := 0; while ++$i <= $count { } </code></pre> <pre><code>#! nqp sub fib($n) { $n < 2 ?? $n !! fib($n-1) + fib($n - 2); } my $N := 30; my $z := fib($N); say("fib($N) = " ~ fib($N)); </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="フィボナッチの例題">フィボナッチの例題</h2> <ul> <li>オリジナル <ul> <li>1.379 sec</li> <li>1.350 sec</li> <li>1.346 sec</li> </ul> </li> <li>CbCMoarVM <ul> <li>1.636 sec</li> <li>1.804 sec</li> <li>1.787 sec</li> </ul> </li> <li>フィボナッチの例題ではCbCMoarVMが劣る結果となった</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="単純ループ">単純ループ</h2> <ul> <li>オリジナル <ul> <li>7.499 sec</li> <li>7.844 sec</li> <li>6.746 sec</li> </ul> </li> <li>CbCMoarVM <ul> <li>6.135 sec</li> <li>6.362 sec</li> <li>6.074 sec</li> </ul> </li> <li>単純ループではCbCMoarVMの方が高速に動作する場合もある</li> </ul> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="基本ブロックとcodegear">基本ブロックとCodeGear</h2> <ul> <li>コンパイラなどでは, 関数あるいはループの先頭から, 別の関数呼び出し, あるいはジャンプするまでの間のコードを基本ブロックと呼ぶ</li> <li>基本ブロックは入力に影響を受けず, 基本ブロックが決定したタイミングである決定的な処理を行う</li> <li>予め実行する基本ブロックが確定していれば, その部分のみ抜き出してコンパイルする事が可能である</li> <li>CbCのCodeGearは, この基本ブロックとみなす事が可能である</li> <li>その為, NQPの例題の様に, 予め実行する基本ブロックが確定すれば, その部分の処理が可能となる</li> <li>これを行うことで, CbCを用いてMoarVMのThreadedCode実装が可能となる</li> </ul> <pre><code>__code cbc_const_i64(INTERP i,__code cbc_next(INTERP i)){ GET_REG(i->cur_op, 0,i).i64 = MVM_BC_get_I64(i->cur_op, 2); i->cur_op += 10; goto cbc_next(i); } goto cbc_const_i64_16(i,cbc_gt_i_01); __code cbc_gt_i_01(INTERP i){ goto cbc_gt_i(i,cbc_unless_i_01); } __code cbc_unless_i_01(INTERP i){ goto cbc_unless_i(i,cbc_osrpoint_01); } </code></pre> </div> <div class='slide'> <!-- _S9SLIDE_ --> <h2 id="まとめと今後の課題">まとめと今後の課題</h2> <ul> <li>継続と基本としたC言語 Continuation Based Cを用いてPerl6の処理系の一部を書き直した</li> <li>CbCの持つCodeGearによって, 本来はモジュール化出来ない箇所をモジュール化する事が出来た</li> <li>MoarVMの速度改善にはThreadedCodeが期待でき, CodeGearベースの命令ディスパッチとThreadedCodeは相性が良いと考えられる</li> <li>今後は実行するバイトコードによりThreadedCode箇所と通常の配列を読み取り, 次のCodeGearを計算する処理を両立させていく</li> </ul> </div> </div><!-- presentation --> </body> </html>