# HG changeset patch # User Takahiro SHIMIZU # Date 1541758506 -32400 # Node ID 443de29ac3490eeced4b7f229973ec62e0265fdb # Parent 6fc015dd380b10c9f78109f2b10bc1a143905551 fix section names diff -r 6fc015dd380b -r 443de29ac349 Paper/anatofuz.pdf Binary file Paper/anatofuz.pdf has changed diff -r 6fc015dd380b -r 443de29ac349 Paper/anatofuz.tex --- a/Paper/anatofuz.tex Fri Nov 09 18:44:58 2018 +0900 +++ b/Paper/anatofuz.tex Fri Nov 09 19:15:06 2018 +0900 @@ -1,40 +1,40 @@ % withpage: ページ番号をつける (著者確認用) % english: 英語原稿用フォーマット \documentclass{ipsjprosym} -%\documentclass[withpage,english]{ipsjprosym} +%\documentclass[withpage, english]{ipsjprosym} \usepackage[dvipdfmx]{graphicx} \usepackage{latexsym} \usepackage{comment} \usepackage{listings} \lstset{ - language=C, - tabsize=2, - frame=single, - basicstyle={\ttfamily\footnotesize},% - identifierstyle={\footnotesize},% - commentstyle={\footnotesize\itshape},% - keywordstyle={\footnotesize\bfseries},% - ndkeywordstyle={\footnotesize},% - stringstyle={\footnotesize\ttfamily}, - breaklines=true, - captionpos=b, - columns=[l]{fullflexible},% - xrightmargin=0zw,% - xleftmargin=1zw,% - aboveskip=1zw, - numberstyle={\scriptsize},% - stepnumber=1, - numbersep=0.5zw,% - lineskip=-0.5ex, + language=C, + tabsize=2, + frame=single, + basicstyle={\ttfamily\footnotesize}, % + identifierstyle={\footnotesize}, % + commentstyle={\footnotesize\itshape}, % + keywordstyle={\footnotesize\bfseries}, % + ndkeywordstyle={\footnotesize}, % + stringstyle={\footnotesize\ttfamily}, + breaklines=true, + captionpos=b, + columns=[l]{fullflexible}, % + xrightmargin=0zw, % + xleftmargin=1zw, % + aboveskip=1zw, + numberstyle={\scriptsize}, % + stepnumber=1, + numbersep=0.5zw, % + lineskip=-0.5ex, } \renewcommand{\lstlistingname}{Code} \usepackage{caption} -\captionsetup[lstlisting]{font={small,tt}} +\captionsetup[lstlisting]{font={small, tt}} \usepackage{url} \begin{document} -% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{CbCを用いたPerl6処理系} %\affiliate{IPSJ}{情報処理学会} @@ -47,105 +47,104 @@ \begin{abstract} スクリプト言語であるPerl5の後継言語としてPerl6が現在開発されている． Perl6は設計と実装が区分されており様々な処理系が開発されている．現在主流なPerl6はRakudoと言われるプロジェクトである． -RakudoではPerl6自体をNQP(NotQuitPerl)と言われるPerl6のサブセットで記述し,NQPをVMが解釈するという処理流れになっている． -このVMは任意のVMが選択できるようになっており,現在はMoarVM,JavaVM,Javascriptが動作環境として選択可能である． +RakudoではPerl6自体をNQP(NotQuitPerl)と言われるPerl6のサブセットで記述し, NQPをVMが解釈するという処理流れになっている． +このVMは任意のVMが選択できるようになっており, 現在はMoarVM,JavaVM,Javascriptが動作環境として選択可能である． 主に利用されているVMにCで書かれたMoarVMが存在する． -MoarVMはJITコンパイルなどをサポートしているが,全体的な起動時間及び処理速度がPerl5と比較し非常に低速である． +MoarVMはJITコンパイルなどをサポートしているが, 全体的な起動時間及び処理速度がPerl5と比較し非常に低速である． この問題を解決するためにContinuation based C (CbC)という言語を一部用いてMoarVMの書き換えを行う． -本論文ではCbCを用いたMoarVMの書き換えを検討し,得られた知見について述べる． +本論文ではCbCを用いたMoarVMの書き換えを検討し, 得られた知見について述べる． \end{abstract} \begin{jkeyword} -プログラミング言語, コンパイラ, CbC, Perl6, MoarVM +プログラミング言語, コンパイラ, CbC, Perl6, MoarVM \end{jkeyword} \maketitle % Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\section{研究目的} -現在も広く使われているスクリプト言語PerlことPerl5の後継言語としてPerl6が開発されている． -Perl6は設計と実装が区分されており,現在広く使われている実装はRakudoと呼ばれるプロジェクトである． -Rakudoの実装はPerl6コンパイラ開発者用のサブセットであるNQP(NotQuitPerl)で実装されているPerl6の事を指す． -現在RakudoはNQPを解釈できる実行環境として,C言語で実装されたMoarVM,JVM,Javascript上で動作する様に開発されている． -Rakudoとして主に使われている処理系はMoarVMであるが,MoarVMの処理時間がPerl5などの多くのスクリプト言語と比較し非常に低速である． +\section{CbCを用いた言語処理系の実装} +当研究室ではContinuation Based C(以下CbC)という言語を開発している． +CbCはCよりきめ細やかな単位で実装する事が可能である為, 言語処理系に応用すれば効率的な開発，実行が出来ると期待される． +現在活発に開発が進んでいる言語にPerl6がある． +Perl6はMoarVMと呼ばれるVMを中心としたRakudoと呼ばれる実装が現在の主流となっている． +Rakudoは処理速度が他のプログラミング言語と比較しても非常に低速である． その為現在日本国内ではPerl6を実務として利用するケースは概ね存在しない． Perl6の持つ言語機能や型システムは非常に柔軟かつ強力であるため実用的な処理速度に達すれば言語の利用件数が向上することが期待される． -この問題を解決するために現在当研究室で開発しているContinuation Based C(以下CbC)を用いて改良を行う． -CbCはCよりさらにきめ細やかな記述が可能であるためスクリプト言語などのプログラミング言語の記述と親和性が高い事が推測される． -本研究はCbCをスクリプト言語の実装に適応した場合,どのような利点やプログラミング上の問題点に遭遇するかCbCの応用としての側面でも行う． -本稿ではまずCbC,Perl6の特徴及び現在の実装について述べ,本研究で行ったCbCで書き換えたMoarVMについてデバッグ手法も含め解説する. -そして本研究で得られたCbCを言語処理系に適応した場合の利点と欠点について述べ,今後の展望について記載する. +その為本研究では, CbCを用いた言語処理系の実装の一例としてMoarVMをCbCで構築したCbCMoarVMを実装する． +本研究はCbCをスクリプト言語の実装に適応した場合, どのような利点やプログラミング上の問題点に遭遇するかCbCの応用としての側面でも行う． +本稿ではまずCbC, Perl6の特徴及び現在の実装について述べ,本研究で行ったCbCで書き換えたMoarVMについてデバッグ手法も含め解説する. +そして本研究で得られたCbCを言語処理系に適応した場合の利点と欠点について述べ, 今後の展望について記載する. \section{CbC} \subsection{CbCの概要} CbCは当研究室で開発しているプログラミング言語である． -Cレベルでのプログラミングを行う場合,本来プログラマが行いたい処理の他にmallocなどを利用したメモリのアロケートやエラーハンドリングなどを記述する必要がある． +Cレベルでのプログラミングを行う場合, 本来プログラマが行いたい処理の他にmallocなどを利用したメモリのアロケートやエラーハンドリングなどを記述する必要がある． これらの処理をmeta computationと呼ぶ．これらmeta computationと通常の処理を分離することでバグの原因がmeta computation側にあるか処理側にあるかの分離などが可能となる． -しかしC言語などを用いたプログラミングでmeta computationの分離を行おうとすると,それぞれ事細かに関数やクラスを分割せねばならず容易ではない． +しかしC言語などを用いたプログラミングでmeta computationの分離を行おうとすると, それぞれ事細かに関数やクラスを分割せねばならず容易ではない． CbCでは関数よりmeta computationを細かく記述する為にCodeGearという単位を導入した． またCodeGearの実行に必要なデータをDataGearという単位で受け渡す． -CbCではCodeGear,DataGearを基本単位として記述するプログラミングスタイルを取る． +CbCではCodeGear, DataGearを基本単位として記述するプログラミングスタイルを取る． \subsection{CodeGearとDataGear} CbCではCの関数の代わりにCodeGearを導入する． CodeGearはCの関数宣言の型名の代わりに\_\_codeと書くことで 宣言できる． -\_\_codeはCbCコンパイラの扱いはvoidと同じ型であるが,CbCプログラミングではCodeGearである事を示す識別子としての意味で利用する． +\_\_codeはCbCコンパイラの扱いはvoidと同じ型であるが, CbCプログラミングではCodeGearである事を示す識別子としての意味で利用する． CodeGear間の移動はgoto文によって記述する． -\lstinputlisting[label=cbcexample, caption=cbc\_example.cbc]{./src/cbc_example.cbc} -Code\ref{cbcexample}に示すCbCのコードではmain関数からcs1,cs2に遷移し,最終的にdataの値が2となる． +\lstinputlisting[label=cbcexample, caption=cbc\_example.cbc]{./src/cbc_example.cbc} +Code\ref{cbcexample}に示すCbCのコードではmain関数からcs1, cs2に遷移し,最終的にdataの値が2となる． CodeGear間の入出力の受け渡しは引数を利用する．この引数は小さなDataGearであると言える． \subsection{軽量継続} %TBD -CbCでは次のCodeGearに移行する際,Cのgoto文を利用する． -通常のCの関数呼び出しの場合,スタックポインタを操作しローカル変数などをスタックに保存する． -CbCの場合スタックフレームを操作せず,レジスタの値を変更せずそのまま次のCodeGearに遷移する事が可能である． +CbCでは次のCodeGearに移行する際, Cのgoto文を利用する． +通常のCの関数呼び出しの場合, スタックポインタを操作しローカル変数などをスタックに保存する． +CbCの場合スタックフレームを操作せず, レジスタの値を変更せずそのまま次のCodeGearに遷移する事が可能である． 通常Sechemeのcall/ccなどの継続は現在の位置までの情報を環境として所持した状態で遷移する． -対してCbCは環境を持たず遷移する為,通常の継続と比較して軽量であることから軽量継続であると言える． +対してCbCは環境を持たず遷移する為, 通常の継続と比較して軽量であることから軽量継続であると言える． CbCは軽量継続を利用するためレジスタレベルでのきめ細やかな実装が可能となっている． \subsection{現在の実装} CbCは現在主要なCコンパイラであるgcc及びllvmをバックエンドとしたclang上の2種類の実装が存在する． -gccはバージョン9.0.0に,clangは7.0.0に対応している． +gccはバージョン9.0.0に, clangは7.0.0に対応している． \subsection{CbCコンパイラのバグ} % 局所変数のポインタを握ったままgotoするとtail callにならない CbCコンパイラは現在も開発中であり幾つかのバグが発見されている． まずCodeGear内で宣言した局所変数のポインタを別の変数などで確保した状態でgotoしてしまうとtail call最適化が切られる． -これはただの関数呼び出しになってしまう為,直接的な被害はないもののCbCとしての利点が損なわれてしまう． -また本来は操作しないはずのスタック領域の操作が入ってしまうため,プログラマの意図と反したスタックポインタなのど操作が行われてしまいバグが発生する可能性が存在する． +これはただの関数呼び出しになってしまう為, 直接的な被害はないもののCbCとしての利点が損なわれてしまう． +また本来は操作しないはずのスタック領域の操作が入ってしまうため, プログラマの意図と反したスタックポインタなのど操作が行われてしまいバグが発生する可能性が存在する． \subsection{CbCとCの互換性} CbCコンパイラは内部的に与えられているソースコードがCbCであるかどうかを判断する． この際にCodeGearを利用していない場合は通常のCプログラムとして動作する． -その為今回検証するMoarVMのビルドにおいてもCbCで書き換えたソースコードがあるMoarVMと,手を加えていないオリジナルのMoarVMの2種類を同一のCbCコンパイラでビルドする事が可能である． +その為今回検証するMoarVMのビルドにおいてもCbCで書き換えたソースコードがあるMoarVMと, 手を加えていないオリジナルのMoarVMの2種類を同一のCbCコンパイラでビルドする事が可能である． -またCからCbCへの遷移時に,再びCの関数に戻るように実装したい場合がある． +またCからCbCへの遷移時に, 再びCの関数に戻るように実装したい場合がある． その際は環境付きgotoと呼ばれる手法を取る．これは\_CbC\_return及び\_CbC\_environmentという変数を渡す． -この変数は\_CbC\_returnが元の環境に戻る際に利用するCodeGearを指し,\_CbC\_environmentは復帰時に戻す元の環境である． -復帰する場合,呼び出した位置には帰らず,呼び出した関数の終了する位置に帰る． -\lstinputlisting[label=cbcreturn, caption=環境付き継続の例]{./src/return.cbc} +この変数は\_CbC\_returnが元の環境に戻る際に利用するCodeGearを指し, \_CbC\_environmentは復帰時に戻す元の環境である． +復帰する場合, 呼び出した位置には帰らず,呼び出した関数の終了する位置に帰る． +\lstinputlisting[label=cbcreturn, caption=環境付き継続の例]{./src/return.cbc} Code\ref{cbcreturn}に示す例ではc\_funcから環境付き継続でがcsに継続している． -通常c\_funcの返り値は-1であるが,csから環境付き継続でmainに帰る為にcsから渡される1がtestの値となる． +通常c\_funcの返り値は-1であるが, csから環境付き継続でmainに帰る為にcsから渡される1がtestの値となる． \subsection{言語処理系におけるCbCの応用} -CbCを言語処理系,特にスクリプト言語に応用すると幾つかの箇所に置いて利点があると推測される． +CbCを言語処理系, 特にスクリプト言語に応用すると幾つかの箇所に置いて利点があると推測される． CbCにおけるCodeGearはコンパイラの基本ブロックに相当する． その為従来のスクリプト言語では主にcase文で記述していた命令コードディスパッチの箇所をCodeGearの遷移として記述する事が可能である． -CbCは状態を単位として記述が可能であるため,命令コードなどにおける状態を利用するスクリプト言語の実装は応用例として適していると考えられる． +CbCは状態を単位として記述が可能であるため, 命令コードなどにおける状態を利用するスクリプト言語の実装は応用例として適していると考えられる． \section{Perl6の概要} この章では現在までのPerl6の遍歴及びPerl6の言語的な特徴について記載する． \subsection{Perl6の構想と初期の処理系} Perl6は2002年にLarryWallがPerlを置き換える言語として設計を開始した． Perl5の言語的な問題点であるオブジェクト指向機能の強力なサポートなどを取り入れた言語として設計された． -Perl5は設計と実装が同一であり,Larryらによって書かれたC実装のみだった．Perl6は設計と実装が分離しており様々な処理系が開発されてきた． +Perl5は設計と実装が同一であり, Larryらによって書かれたC実装のみだった．Perl6は設計と実装が分離しており様々な処理系が開発されてきた． まず2005年に唐鳳によってHaskellで実装されたPugs\cite{pugs}が登場した． -Pugsは最初に登場したPerl6実装であり,この実装を基にしてPerl6の仕様も修正された． -現在Pugsは歴史的な実装となっており,更新はされていない． +Pugsは最初に登場したPerl6実装であり, この実装を基にしてPerl6の仕様も修正された． +現在Pugsは歴史的な実装となっており, 更新はされていない． \subsection{Parrot} その後Pythonとの共同動作環境としてParrot\cite{parrot}が実装された． @@ -155,22 +154,22 @@ こちらもPugsと同様に現在のPerl6プロジェクトでは歴史的な実装とされている． 現在主に使用されている実装であるRakudoは2010年にRakudo-Starという一連のツール郡としてリリースされた． -Perl6は言語仕様及び処理実装がPerl5と大幅に異なっており,言語的な互換性が存在しない． +Perl6は言語仕様及び処理実装がPerl5と大幅に異なっており, 言語的な互換性が存在しない． 従って現在ではPerl6とPerl5は別言語としての開発方針になっている． Perl6は現在有力な処理系であるRakudoから名前を取りRakuという別名がつけられている． \subsection{Rakudo} -RakudoとはParrotで構想に上がったNQP,NQPに基づくPerl6を基にしたプロジェクトである． +RakudoとはParrotで構想に上がったNQP, NQPに基づくPerl6を基にしたプロジェクトである． RakudoがPerl6のコンパイラかつインタプリタであると考えても良い． Rakudoは図\ref{fig:perl6construction}に示す構成になっている． Rakudoにおけるコンパイラとは厳密には2種類存在する． -まず第1のものがPerl6,もしくはNQPをMoarVM,JVMのバイトコードに変換するNQPコンパイラである． +まず第1のものがPerl6, もしくはNQPをMoarVM,JVMのバイトコードに変換するNQPコンパイラである． 次にそのNQPが出力したバイトコードをネイティブコードに変換するVMの2種類である． -このVMは現在MoarVM,JavaVM,Javascriptを選択可能である． -Rakudo及びNQP projectではこのNQPコンパイラの部分をフロントエンド,VMの部分をバックエンド\cite{rani1}と呼称している． -NQPで主に書かれ,MoarVMなどNQPが動作する環境で動くPerl6のことをRakudoと呼ぶ． -Perl6はNQP以外にものNQPを拡張したPerl6自身で書かれている箇所が存在し,これはNQPコンパイラ側でMoarVMが解釈可能な形へ変換を行う． +このVMは現在MoarVM, JavaVM,Javascriptを選択可能である． +Rakudo及びNQP projectではこのNQPコンパイラの部分をフロントエンド, VMの部分をバックエンド\cite{rani1}と呼称している． +NQPで主に書かれ, MoarVMなどNQPが動作する環境で動くPerl6のことをRakudoと呼ぶ． +Perl6はNQP以外にものNQPを拡張したPerl6自身で書かれている箇所が存在し, これはNQPコンパイラ側でMoarVMが解釈可能な形へ変換を行う． \begin{figure}[ht] \begin{center} @@ -182,19 +181,19 @@ \subsection{NQP} -RakudoにおけるNQP\cite{nqp}は現在MoarVM,JVM上で動作し,MoarVMを一部利用することでNodeJSからも動作させる事が可能である． +RakudoにおけるNQP\cite{nqp}は現在MoarVM, JVM上で動作し,MoarVMを一部利用することでNodeJSからも動作させる事が可能である． NQPはPerl6のサブセットであるため主な文法などはPerl6に準拠しているが幾つか異なる点が存在する． -NQPは最終的にはNQP自身でブートストラップする言語であるが,ビルドの最初にはすでに書かれたMoarvMByteCodeを必要とする． -このMoarVMByteCodeの状態をStage0と言い,ディレクトリ名として設定されている． -Perl6の一部はNQPを拡張したもので書かれている為,Rakudoを動作させる為にはMoarVMなどのVM,VMに対応させる様にビルドしたNQPがそれぞれ必要となる． -現在のNQPではMoarVM,JVMに対応するStage0はそれぞれMoarVMBytecode,jarファイルが用意されており,Javascriptではバイトコードの代わりにランタイム独自のModuleLoaderなどが設計されている． +NQPは最終的にはNQP自身でブートストラップする言語であるが, ビルドの最初にはすでに書かれたMoarvMByteCodeを必要とする． +このMoarVMByteCodeの状態をStage0と言い, ディレクトリ名として設定されている． +Perl6の一部はNQPを拡張したもので書かれている為, Rakudoを動作させる為にはMoarVMなどのVM,VMに対応させる様にビルドしたNQPがそれぞれ必要となる． +現在のNQPではMoarVM, JVMに対応するStage0はそれぞれMoarVMBytecode,jarファイルが用意されており,Javascriptではバイトコードの代わりにランタイム独自のModuleLoaderなどが設計されている． MoarVMのModuleLoaderはStage0にあるMoarVMBytecodeで書かれた一連のファイルが該当する． Stage0にあるファイルをMoarVMに与えることでnqpのインタプリタが実行される様になっている． これはStage0の一連のファイルはMoarVMBytecodeなどで記述されたNQPコンパイラのモジュールである為である． -NQPは6modelと呼ばれるオブジェクトモデルを採用としているが,これを構築する為に必要なNQPCORE,正規表現系のQRegex,MoarVMのModuleLoaderなどがMoarVMBytecodeで記述されている．これらMoarVMBytecodeの拡張子は.MoarVMである． -MoarVMに対してStage0のディレクトリにライブラリパスを設定し,nqp.MoarVMを実行させることでnqpの対話型環境が起動する． +NQPは6modelと呼ばれるオブジェクトモデルを採用としているが, これを構築する為に必要なNQPCORE,正規表現系のQRegex,MoarVMのModuleLoaderなどがMoarVMBytecodeで記述されている．これらMoarVMBytecodeの拡張子は.MoarVMである． +MoarVMに対してStage0のディレクトリにライブラリパスを設定し, nqp.MoarVMを実行させることでnqpの対話型環境が起動する． \begin{figure}[ht] \begin{center} @@ -206,8 +205,8 @@ NQPのビルドフローを図\ref{fig:nqpbuild}に示す． 実際にperl6を動かすためにはself buildしたNQPコンパイラが必要となる．その為にstage0を利用してStage1をビルドしNQPコンパイラを作成する． -Stage1は中間的な出力であり,生成されたNQPファイルはStage2と同一であるが,MoarVMBytecodeが異なる． -Perl6では完全なセルフコンパイルを実行したNQPが要求される為,Stage1を利用してもう一度ビルドを行いStage2を作成する． +Stage1は中間的な出力であり, 生成されたNQPファイルはStage2と同一であるが,MoarVMBytecodeが異なる． +Perl6では完全なセルフコンパイルを実行したNQPが要求される為, Stage1を利用してもう一度ビルドを行いStage2を作成する． Perl6のテストスイートである「Roast\cite{roast}」やドキュメントなどによって設計が定まっているPerl6とは異なりNQP自身の設計は今後も変更になる可能性が開発者から公表されている． 現在の公表されているNQPのオペコードはNQPのリポジトリ\cite{nqpopcode}に記述されているものである． @@ -216,23 +215,23 @@ \subsection{Rakudo Perl6} Rakudo実装上におけるPerl6はRakudo Perl6と呼ばれているGitリポジトリで管理されているプログラムのことである． 前述した通りRakudo Perl6はPerl6のサブセットであるNQPを用いて記述されている． -従ってyaccやlexと言ったPerl5の文字解析,構文解析に利用していたプログラムは利用せず,NQP側で構文定義などを行っている． -NQPはNQP自身でBootstrappingされている為,Rakudo Perl6のbuild時にはNQPの実行環境として要したVM,それに基づいてbuildしたNQPがそれぞれ必要となる． +従ってyaccやlexと言ったPerl5の文字解析, 構文解析に利用していたプログラムは利用せず,NQP側で構文定義などを行っている． +NQPはNQP自身でBootstrappingされている為, Rakudo Perl6のbuild時にはNQPの実行環境として要したVM,それに基づいてbuildしたNQPがそれぞれ必要となる． -言語的な特徴としては独自にPerl6の文法を拡張可能なGrammer,Perl5と比較した場合のオブジェクト指向言語としての進化も見られる． +言語的な特徴としては独自にPerl6の文法を拡張可能なGrammer, Perl5と比較した場合のオブジェクト指向言語としての進化も見られる． またPerl6は漸進的型付け言語である. 従来のPerlの様に変数に代入する対象の型や文脈に応じて型を変更する動的型言語としての側面を持ちつつ独自に定義した型を始めとする様々な型に静的に変数の型を設定する事が可能である． \subsection{現在のPerl6} Perl6の言語仕様\cite{perl6design}とその時点での実装状況をまとめた公式ドキュメント\cite{perl6doc}は分離している． -従来は言語仕様は自然言語の仕様書であったが,現在はテストスイートである「Roast\cite{roast}」そのものと定義されている． -現在のPerl6の仕様を読む場合Roastを確認し,現在rakudo上に実装されている機能を見る場合は公式ドキュメントを確認する必要がある． +従来は言語仕様は自然言語の仕様書であったが, 現在はテストスイートである「Roast\cite{roast}」そのものと定義されている． +現在のPerl6の仕様を読む場合Roastを確認し, 現在rakudo上に実装されている機能を見る場合は公式ドキュメントを確認する必要がある． \subsection{処理速度} 現在のPerl6が他のプログラミング言語と比較した場合どのような違いがでるのか計測した． mac osの/var/log/system.logファイルから正規表現でログ中のプログラムが書き込んだ回数を個別に数え上げるというものである． -今回はファイルを231Kと3GBの二種類用意し，どの様な違いが出るのか測定した． +今回はファイルを231Kと3GBの二種類用意し, どの様な違いが出るのか測定した． 測定した環境は次の通りである． @@ -254,7 +253,7 @@ \end{tabular} \end{table} -計測結果からファイルサイズが小さい場合はMoarVMよりJVMに乗せたPerl6が低速であるが，ファイルサイズが大きい場合はJavaのJITが働くためMoarVMより高速に動いていると推測できる． +計測結果からファイルサイズが小さい場合はMoarVMよりJVMに乗せたPerl6が低速であるが, ファイルサイズが大きい場合はJavaのJITが働くためMoarVMより高速に動いていると推測できる． %# 計測(3GB) @@ -289,7 +288,7 @@ \section{CbCによるMoarVM} この章では改良を行ったPerl6処理系であるMoarVMについて述べる． -今回改良を行ったMoarVMは2018.04.01,nqpは2018.04-3-g45ab6e3バージョンで行っている． +今回改良を行ったMoarVMは2018.04.01, nqpは2018.04-3-g45ab6e3バージョンで行っている． \subsection{方針} MoarVMそのものをCbCで書き換えることも考えられるがMoarVM自体既に巨大なプロジェクトである為すべてを書き換える事は困難である． その為まず比較的CbCで書き換えることが容易な箇所を修正する． @@ -300,55 +299,55 @@ \subsection{MoarByteCodeのディスパッチ} MoarVMのバイトコードインタプリタはsrc/core/interp.cで定義されている． この中の関数MVM\_interp\_runで命令に応じた処理を実行する． -関数内では命令列が保存されているcur\_op,現在と次の命令を指し示すop,Threadの環境が保存されているThreadcontextなどの変数を利用する． -命令実行は大きく二種類の動作があり,Code\ref{orig_macro}に示すCのgotoが利用できる場合はMVM\_CGOTOフラグが立ちラベル遷移を利用する． +関数内では命令列が保存されているcur\_op, 現在と次の命令を指し示すop,Threadの環境が保存されているThreadcontextなどの変数を利用する． +命令実行は大きく二種類の動作があり, Code\ref{orig_macro}に示すCのgotoが利用できる場合はMVM\_CGOTOフラグが立ちラベル遷移を利用する． それ以外の場合は巨大なcase文として命令を実行する． -ラベル遷移を利用する場合はラベルテーブルにアクセスし,テーブルに登録されているアドレスを取得し,マクロNEXTで遷移する． -Code\ref{cbc_dispatch_c}に示すno\_opは何もせず次の命令に移動する為，NEXTのみ記述されている． +ラベル遷移を利用する場合はラベルテーブルにアクセスし, テーブルに登録されているアドレスを取得し,マクロNEXTで遷移する． +Code\ref{cbc_dispatch_c}に示すno\_opは何もせず次の命令に移動する為, NEXTのみ記述されている． -このラベルテーブルの中身はラベルが変換されたアドレスであるため,実際に呼ばれている命令コードの名前はデバッガレベルでは確認できない． +このラベルテーブルの中身はラベルが変換されたアドレスであるため, 実際に呼ばれている命令コードの名前はデバッガレベルでは確認できない． Cレベルでのデバッグ時にはアドレスと実際に呼ばれる箇所を確認する事に手間がかかる． -巨大なcase文として実行された場合,実行時間が遅いだけでなく,ラベル遷移と共存させて記述を行っている為Cのソースコードにおける可読性も低下する． +巨大なcase文として実行された場合, 実行時間が遅いだけでなく,ラベル遷移と共存させて記述を行っている為Cのソースコードにおける可読性も低下する． -\lstinputlisting[label=orig_macro, caption=interp.cのマクロ部分]{./src/orig_macro.c} +\lstinputlisting[label=orig_macro, caption=interp.cのマクロ部分]{./src/orig_macro.c} -\lstinputlisting[label=dispatch_c, caption=オリジナル版MoarVMのバイトコードディスパッチ]{./src/dispatch.c} +\lstinputlisting[label=dispatch_c, caption=オリジナル版MoarVMのバイトコードディスパッチ]{./src/dispatch.c} -interp.cでは命令コードのディスパッチはマクロを利用したcur\_opの計算及びラベルの遷移，もしくはマクロDISPATCHが展開するswitch文で行われていた． -CbCMoarVMではこの問題を解決するために,それぞれの命令に対応するCodeGearを作成し,CodeGear名前を要素として持つCbCのCodeGearのテーブルを作成した． -このCodeGearのテーブルを参照するCodeGearはcbc\_nextであり，この中のマクロNEXTはinterp.cのマクロNEXTをCbC用に書き直したものである． +interp.cでは命令コードのディスパッチはマクロを利用したcur\_opの計算及びラベルの遷移, もしくはマクロDISPATCHが展開するswitch文で行われていた． +CbCMoarVMではこの問題を解決するために, それぞれの命令に対応するCodeGearを作成し,CodeGear名前を要素として持つCbCのCodeGearのテーブルを作成した． +このCodeGearのテーブルを参照するCodeGearはcbc\_nextであり, この中のマクロNEXTはinterp.cのマクロNEXTをCbC用に書き直したものである． -\lstinputlisting[label=cbc_dispatch_c, caption=CbCMoarVMのバイトコードディスパッチ]{./src/cbc-interp-next.cbc} +\lstinputlisting[label=cbc_dispatch_c, caption=CbCMoarVMのバイトコードディスパッチ]{./src/cbc-interp-next.cbc} \subsection{命令実行箇所のCodeGearへの変換} -ラベルテーブルやcase文のswitch相当の命令実行箇所をCbCに変換し,CodeGearの遷移として利用する． +ラベルテーブルやcase文のswitch相当の命令実行箇所をCbCに変換し, CodeGearの遷移として利用する． interp.cはCode\ref{dispatch_c}に示すスタイルで記述されている． -OP(.*)の.*に該当する箇所はバイトコードの名前である．通常このブロックにはLABELから遷移する為,バイトコードの名前はLABELSの配列の添字に変換されている． -そのため対象となるCodeGearをLABLESの並びと対応させ,CodeGearの配列CODESとして設定すればCodeGearの名前は問わない． +OP(.*)の.*に該当する箇所はバイトコードの名前である．通常このブロックにはLABELから遷移する為, バイトコードの名前はLABELSの配列の添字に変換されている． +そのため対象となるCodeGearをLABLESの並びと対応させ, CodeGearの配列CODESとして設定すればCodeGearの名前は問わない． 今回はCodeGearである事を示す為にsuffixとしてcbc\_をつける． -命令の実行処理でMoarVMのレジスタであるreg\_baseや命令列cur\_opなどの情報を利用しているが,これらはMVM\_interp\_run内のローカル変数として利用している． -ラベルを利用しているオリジナル版では同一関数内であるためアクセス可能であるが,CodeGear間の移動で命令を表現するCbCではアクセスできない． -その為インタプリタの情報を集約した構造体interを定義し,この構造体へのポインタであるINTERP型の変数iをCodeGearの入出力として与える． +命令の実行処理でMoarVMのレジスタであるreg\_baseや命令列cur\_opなどの情報を利用しているが, これらはMVM\_interp\_run内のローカル変数として利用している． +ラベルを利用しているオリジナル版では同一関数内であるためアクセス可能であるが, CodeGear間の移動で命令を表現するCbCではアクセスできない． +その為インタプリタの情報を集約した構造体interを定義し, この構造体へのポインタであるINTERP型の変数iをCodeGearの入出力として与える． CodeGear内ではINTERPを経由することでインタプリタの各種情報にアクセスする． -CodeGear間の遷移ではレジスタの値の調整は行われない為,入力引数を使ってレジスタマッピングを管理できる． +CodeGear間の遷移ではレジスタの値の調整は行われない為, 入力引数を使ってレジスタマッピングを管理できる． その為INTERPのメンバであるMoarVMのレジスタそのものをアーキテクチャのレジスタ上に乗せる事が可能である． 命令実行中のCodeGearの遷移を図\ref{fig:perl6cbcinter}に示す． -この中で実線で書かれている部分はCbCのgoto文で遷移し,波線の箇所は通常のCの関数呼び出しとなっている． +この中で実線で書かれている部分はCbCのgoto文で遷移し, 波線の箇所は通常のCの関数呼び出しとなっている． 現在のCbCMoarVMは次の命令セットのディスパッチをcbc\_nextが行っていた． -その為cbc\_nextから命令コードに対応するCodeGearに継続し，CodeGearからcbc\_nextに継続するサイクルが基本の流れである． -CodeGear内からCの関数は問題なく呼ぶ事が可能であるため，Cの関数を利用する処理は変更せず記述する事ができる． -また変換対象はswitch文であるため，breakせず次のcaseに移行した場合に対応するように別のCodeGearに継続し，その後cbc\_nextに継続するパターンも存在する． +その為cbc\_nextから命令コードに対応するCodeGearに継続し, CodeGearからcbc\_nextに継続するサイクルが基本の流れである． +CodeGear内からCの関数は問題なく呼ぶ事が可能であるため, Cの関数を利用する処理は変更せず記述する事ができる． +また変換対象はswitch文であるため, breakせず次のcaseに移行した場合に対応するように別のCodeGearに継続し，その後cbc\_nextに継続するパターンも存在する． -\lstinputlisting[label=cbc_codesegs_c, caption=CbCMoarVMのバイトコードに対応するCodeGear]{./src/cbc_codesegs.cbc} +\lstinputlisting[label=cbc_codesegs_c, caption=CbCMoarVMのバイトコードに対応するCodeGear]{./src/cbc_codesegs.cbc} \begin{figure}[ht] \begin{center} @@ -358,60 +357,25 @@ \label{fig:perl6cbcinter} \end{figure} -バイトコードの数は膨大である為,すべてを手作業で変換する事は望ましくない． +バイトコードの数は膨大である為, すべてを手作業で変換する事は望ましくない． 本研究ではPerlScriptを用いてinterp.cからCbCのCodeGearを自動生成するスクリプトを作成した． このスクリプトでは以下の修正手続きを実行する． \begin{itemize} - \item OP(.*)の.*部分をCodeGearの名前として,先頭にcbc\_をつけた上で設定する． + \item OP(.*)の.*部分をCodeGearの名前として, 先頭にcbc\_をつけた上で設定する． \item cur\_opなど構造体INTERのメンバ変数はポインタiから参照するように修正する - \item GC対策のためマクロMVMROOTを使い局所変数のポインタをスタックに積む箇所は,局所変数をstatic化する + \item GC対策のためマクロMVMROOTを使い局所変数のポインタをスタックに積む箇所は, 局所変数をstatic化する \item 末尾のgoto NEXTをgoto cbc\_next(i)に修正する - \item case文で下のcase文に落ちている箇所は,case文に対応するCodeGearに遷移する様にgoto文を付け加える + \item case文で下のcase文に落ちている箇所は, case文に対応するCodeGearに遷移する様にgoto文を付け加える \end{itemize} 上記Code\ref{cbc_codesegs_c}ではcbc\_const\_i8などがcase文の下のcase部分に該当するcbc\_const\_i64に遷移する様に変換されている． -またcbc\_pushcompscではMVMROOTに局所変数scを渡している為，これをstaticで宣言し直している． +またcbc\_pushcompscではMVMROOTに局所変数scを渡している為, これをstaticで宣言し直している． 現在CbCで記述されたOSであるGearsOSにはInterfaceが導入されている． -これはJavaのinterface,Haskellの型クラスに該当する概念であり,次のCodeGearにInterface経由で継続する事が可能である． -Interfaceは現在のMoarVMには実装されていない為,今後ThreadeCodeの実装を行うにあたり導入を検討している． - -\subsection{Threaded Code} -現在のMoarVMは次の命令をバイトコードからディスパッチし決定後,ラベルジャンプを利用し実行している． -この処理ではディスパッチの箇所にコストが掛かってしまう． -CbCをMoarVMに導入することで,バイトコード列を直接サブルーチンコールの列に置き換えてしまう事が可能である． -これはCbCが基本ブロックの単位と対応している為である． -CbCでは現在ディスパッチを行うCodeGearであるcbc\_nextを利用しているが,Threaded Codeを実装するにあたり, -cbc\_nextと次のCodeGearに直接遷移するcbc\_fixt\_nextの実装を予定している． - -また段階的に現在8バイト列を1命令コードとして使用しているが,これを16バイトなどに拡張し2命令を同時に扱えるように実装する事なども検討している． - -%CbCはCodeGearで末尾最適化(Tail call optimization)を行う． -%これはCodeGearは必ず関数呼び出しではなくgotoで次の状態に遷移する為にスタック領域の操作が必要とならない為である． -%現在のCbCコンパイラの実装ではCodeGearからCの関数に戻る場合は末尾最適化を切り,CodeSegment間の遷移では末尾最適化が行われる． -%末尾最適化を応用することでContinuation-passingスタイルのThreaded Codeの実装が可能となる．\cite{threadedcode} -%またCodeGear自体を直接次の遷移先として設定することも可能であるため,CbCならThrededCodeを実装するアプローチが複数検討出来る． - -%現在のCbCMoarVMは次の命令セットのディスパッチをcbc\_nextというCodeGearで処理している． -%これは元のMoarVMの命令ディスパッチで行われる現在のオペコードを示すcur\_opと命令列opの操作及び次のラベルに遷移するマクロに該当する． -%CbCMoarVMではラベルに対しての遷移の代わりにMoarVMの命令のCodeGearの集合体である配列CODESにアクセスし,その要素であるCodeSegmentに対して遷移する形を取っている． -%この一連の処理がオーバーヘッドになる為,今後はcbc\_fixt\_nextというCodeGearを導入し直接次の命令に該当するCodeSegmentへgotoする様に実装する予定である． - -\subsubsection{perlcc} -Perl5においてはperlccというモジュールが開発されている． -これはPerl5内部で利用しているPerlバイトコードを,PerlのC APIであるXS言語の様なCのソースファイルに埋め込み,それをCコンパイルでコンパイルするというものである． -perlccを利用することでPerlインタプリタが無い状況でも可動するバイナリファイルを作成する事が可能である． -しかしPerlccはPerlスクリプトが複雑になるほど正確にCに移植を行う事が出来ず,現在ではPerlのコアモジュールから外されている． -PerlccはPerlのバイトコードをCへの変換のみ行う為,Cで実装されているPerl経由で実行した場合と処理速度はほぼ変わらない． -またPerlccで生成されたCのソースコードは難解であり,これをデバッグするのが困難でもある． -MoarVMでthreaded codeを実現出来た場合,その箇所のみCbCプログラムとして切り出す事が可能である為perlccと似たツールを作成することも可能である． -この場合,Perl6を通常動かした際とは異なりバイトコードインタプリタに到達する前の処理が無くなる為多少の高速化が望めると推測できる. - -\subsection{Cのインライン展開} -CbCのCodeGearはgoto文で遷移するため,次のCodeGearが一意に決定している場合Cコンパイラ側でインライン展開する事が可能である． -CodeGearがインライン展開される限界については別途研究する必要があるが,CbCを利用した場合その箇所でもコストを低く設計する事が可能である． +これはJavaのinterface, Haskellの型クラスに該当する概念であり,次のCodeGearにInterface経由で継続する事が可能である． +Interfaceは現在のMoarVMには実装されていない為, 今後ThreadeCodeの実装を行うにあたり導入を検討している． \section{MoarVMのデバッグ} @@ -421,50 +385,50 @@ \subsection{MoarVMのBytecodeのデバッグ} moarに対してMoarVM bytecodeをdumpオプションを付けて読み込ませるとMoarVMのbytecodeがアセンブラの様に出力される． しかしこれはMoarVMが実行したbytecodeのトレースではなくMoarVM bytecodeを変換したものに過ぎない． -また,明らかに異なる挙動を示す両者のmoarを利用しても同じ結果が返ってきてしまう． +また, 明らかに異なる挙動を示す両者のmoarを利用しても同じ結果が返ってきてしまう． そのため今回のMoarVMBytecodeインタプリタの実装のデバッグにはこの方法は適さない． 従って実際に実行した命令を確認するにはgdbなどのCデバッガを利用してMoarVMを直接トレースする必要がある． CbC側はCode\ref{cbc_b}に示す様にcbc\_nextにbreak pointを設定する． -オリジナル側は次のオペコードの設定のマクロにダミーの関数を呼び出すように修正し,そこにbreak pointを設定する． -CbC側ではCodeGearの名前をデバッガ上で直接確認できるが,オリジナル版はLABLEの配列の添え字から自分でどのオペコードに対応しているかをデバッガの外で探す必要がある． +オリジナル側は次のオペコードの設定のマクロにダミーの関数を呼び出すように修正し, そこにbreak pointを設定する． +CbC側ではCodeGearの名前をデバッガ上で直接確認できるが, オリジナル版はLABLEの配列の添え字から自分でどのオペコードに対応しているかをデバッガの外で探す必要がある． -添字を確認するためにはCode\ref{orig_b}に示すようにオリジナルのMoarVMの場合cur\_opの値をMVMuint16のポインタでキャストし,これが指す値を出力する． -break pointを掛けているダミー関数ではcur\_opにアクセスする事が出来ない為,スタックフレームを一つupする必要がある． -\lstinputlisting[label=cbc_b, caption=CbCMoarVMに対してのbreak point設定]{./src/cbc_breakpoint.txt} -\lstinputlisting[label=orig_b, caption=オリジナル版MoarVMに対してのbreak point設定]{./src/origin_b_set.txt} +添字を確認するためにはCode\ref{orig_b}に示すようにオリジナルのMoarVMの場合cur\_opの値をMVMuint16のポインタでキャストし, これが指す値を出力する． +break pointを掛けているダミー関数ではcur\_opにアクセスする事が出来ない為, スタックフレームを一つupする必要がある． +\lstinputlisting[label=cbc_b, caption=CbCMoarVMに対してのbreak point設定]{./src/cbc_breakpoint.txt} +\lstinputlisting[label=orig_b, caption=オリジナル版MoarVMに対してのbreak point設定]{./src/origin_b_set.txt} \subsection{MoarVMの並列デバッグ手法} しかしMoarVMが実行する命令は膨大な数がある． その為gdbでMoarVMをCbCとオリジナル版での並列デバッグを人間が同時に行うことは困難である． -Perlなどのスクリプトを用いて自動的に解析したいため,ログを残す為にscriptコマンドを実行した状態でgdbを起動する． -トレースでは実行した命令名のみ取得できれば良い為，Code\ref{cbc_b},\ref{orig_b}でdebug pointにcommandとして設定している様に，設定されたcur\_opの値を出力し続けるのみの動きを導入する． +Perlなどのスクリプトを用いて自動的に解析したいため, ログを残す為にscriptコマンドを実行した状態でgdbを起動する． +トレースでは実行した命令名のみ取得できれば良い為, Code\ref{cbc_b}, \ref{orig_b}でdebug pointにcommandとして設定している様に，設定されたcur\_opの値を出力し続けるのみの動きを導入する． -実際に実行したログ・ファイルの一部をそれぞれCode\ref{debug_origmoar},\ref{debug_cbcmoar}に示す． -\lstinputlisting[label=debug_origmoar, caption=オリジナル版MoarVMのバイトコードのトレース]{./src/origin_breakpoint.txt} -\lstinputlisting[label=debug_cbcmoar, caption=CbCMoarVMのバイトコードのトレース]{./src/trace_cbc.txt} +実際に実行したログ・ファイルの一部をそれぞれCode\ref{debug_origmoar}, \ref{debug_cbcmoar}に示す． +\lstinputlisting[label=debug_origmoar, caption=オリジナル版MoarVMのバイトコードのトレース]{./src/origin_breakpoint.txt} +\lstinputlisting[label=debug_cbcmoar, caption=CbCMoarVMのバイトコードのトレース]{./src/trace_cbc.txt} -オリジナル版では実際に実行する命令処理はラベルに変換されてしまう為名前をデバッガ上では出力できないが，CbCでは出力する事が可能である． -CbCとオリジナルのCODES,LABELの添字は対応している為,ログの解析を行う際はそれぞれの添字を抽出し違いが発生している箇所を探索する． -これらはscriptコマンドが作成したログを元に異なる箇所を発見するスクリプトを用意し自動化する． -\lstinputlisting[label=logs2, caption=バイトコードの差分検知の一部分]{./src/logs2.txt} +オリジナル版では実際に実行する命令処理はラベルに変換されてしまう為名前をデバッガ上では出力できないが, CbCでは出力する事が可能である． +CbCとオリジナルのCODES, LABELの添字は対応している為,ログの解析を行う際はそれぞれの添字を抽出し違いが発生している箇所を探索する． +これらはscriptコマンドが作成したログを元に異なる箇所を発見するスクリプトを用意し自動化する．(Code \ref{logs2.txt}) +\lstinputlisting[label=logs2.txt, caption=バイトコードの差分検知の一部分]{./src/logs2.txt} -違いが生じている箇所が発見できた場合,その前後のCodeGear及びディスパッチ部分にbreak pointをかけ,それぞれの変数の挙動を比較する． -主にcbc\_return系の命令が実行されている場合は,その直前で命令を切り替えるcbc\_invoke系統の命令が呼ばれているが,この周辺で何かしらの違いが発生している可能性が高い． -また主に次のCodeGearに遷移する際にCbCコンパイラのバグが生じている可能性もある為,アセンブラレベルの命令を確認しながらデバッグを進めることとなる． +違いが生じている箇所が発見できた場合, その前後のCodeGear及びディスパッチ部分にbreak pointをかけ,それぞれの変数の挙動を比較する． +主にcbc\_return系の命令が実行されている場合は, その直前で命令を切り替えるcbc\_invoke系統の命令が呼ばれているが,この周辺で何かしらの違いが発生している可能性が高い． +また主に次のCodeGearに遷移する際にCbCコンパイラのバグが生じている可能性もある為, アセンブラレベルの命令を確認しながらデバッグを進めることとなる． \subsection{MoarVMのテスト方法} MoarVMは単体で実行する事が不可能である． -またNQPのリポジトリに付随するテストはnqpで書かれている為，MoarVMのテストはNQPリポジトリのファイルを直接使う場合は出来ない． -今回は正常に動くMoarVM,NQPを用意しnqpを経由してデバッグ +またNQPのリポジトリに付随するテストはnqpで書かれている為, MoarVMのテストはNQPリポジトリのファイルを直接使う場合は出来ない． +今回は正常に動くMoarVM, NQPを用意しnqpを経由してデバッグ \subsection{CbCコンパイラによるバグ} 現在までのCbCは複数個の入出力をCodeGearに与えるユースケースで利用していた． -CbCコンパイラ自身はそれぞれ用意したテストスイートを通化するものの,MoarVMの様な巨大なプロジェクトのCSをコンパイルを実行する場合,予期せぬバグが発生した． -主にCodeGear間のgotoにおけるtail callフラグの除去や,DataGearとして渡している構造体の変数のアドレスがスタックポインタの値より上位に来てしまい,通常のCの関数をcallした際にローカル変数の領域がDataGearのアドレスの周辺を利用してしまう． -その為DataGearの構造体の値が書き換わり,CからDataGearにreturnした際にDataGearの構造体が破壊されるバグである． +CbCコンパイラ自身はそれぞれ用意したテストスイートを通化するものの, MoarVMの様な巨大なプロジェクトのCSをコンパイルを実行する場合,予期せぬバグが発生した． +主にCodeGear間のgotoにおけるtail callフラグの除去や, DataGearとして渡している構造体の変数のアドレスがスタックポインタの値より上位に来てしまい,通常のCの関数をcallした際にローカル変数の領域がDataGearのアドレスの周辺を利用してしまう． +その為DataGearの構造体の値が書き換わり, CからDataGearにreturnした際にDataGearの構造体が破壊されるバグである． このバグは先程の並列デバッグを行いながらプログラムカウンタや変数の動きをトレースする事などで発見することが出来る． 現状ではCbCコンパイラがプログラマの意図と反する挙動を取るためCbCコンパイラのバグを回避するプログラミングが要求されている． 本来コンパイラ側のバグを回避するプログラミングをプログラマに要求する事は好ましくない． @@ -474,50 +438,49 @@ その為現在はgcc上に実装したcbcコンパイラを利用しgdbを利用しデバッグを行う． -\section{CbCを用いる事についての利点と欠点} +\section{CbCMoarVMの利点と欠点} MoarVMの様な巨大なスクリプト言語処理系にCbCを適応した所現在までに複数の利点と欠点が発見された． -本章ではまず利点を述べ,次に現段階でのCbCを適応した場合の欠点について考察する． +本章ではまず利点を述べ, 次に現段階でのCbCを適応した場合の欠点について考察する． -\subsection{利点} -\subsection{コード分割} -オリジナルのMoarVMでは命令コードに対応する箇所はラベルジャンプ,もしくはswitch文で実装されていた． + +オリジナルのMoarVMでは命令コードに対応する箇所はラベルジャンプ, もしくはswitch文で実装されていた． その為同じCファイルに命令コードの実行の定義が存在しなければならない． 今後MoarVMに新たなバイトコードが導入されていく事を考えるとinterp.cが巨大になる可能性がある． -関数単位での処理の比重が偏る事に加え, -switch文中に書かれている処理は他の関数から呼ぶ事が出来ないため,余計な手間がかかる箇所が発生すると考えられる． +関数単位での処理の比重が偏る事に加え, +switch文中に書かれている処理は他の関数から呼ぶ事が出来ないため, 余計な手間がかかる箇所が発生すると考えられる． -CbCMoarVMの場合,CodeGearとして基本ブロックを記述出来る為オリジナルのMoarVMの様にswtich文のブロック中に書く必要性が無くなる． -その為類似する命令系をコード分割し,モジュール化する事が可能である． + +CbCMoarVMの場合, CodeGearとして基本ブロックを記述出来る為オリジナルのMoarVMの様にswtich文のブロック中に書く必要性が無くなる． +その為類似する命令系をコード分割し, モジュール化する事が可能である． またCbCはgoto文で遷移する以外は通常のCの関数と同じ扱いをする事が可能である． 従ってCodeGear内部の処理を別の箇所から使用する事も可能となる為再利用性も向上する． -\subsection{ThreadeCode} -ThrededCodeを実装する場合,通常命令ディスパッチの箇所と,実際に実行される命令処理を大幅に変更しなければならない． -CbCを用いた実装の場合,命令処理はただのCodeGearの集合である． + +ThrededCodeを実装する場合, 通常命令ディスパッチの箇所と,実際に実行される命令処理を大幅に変更しなければならない． +CbCを用いた実装の場合, 命令処理はただのCodeGearの集合である． その為CodeGearをThrededCodeに対応した並びとして選択する事ができれば命令処理部分の修正をほぼせずにThrededCodeを実現する事が可能である． -またCodeGearはバイトコードレベルと同じ扱いができるため,ThrededCodeそのものを分離して最適化をかける事が可能である． +またCodeGearはバイトコードレベルと同じ扱いができるため, ThrededCodeそのものを分離して最適化をかける事が可能である． これもCodeGearが関数単位として分離できる事からの利点である． -\subsubsection{MoarVMのデバッグ} MoarVMのバイトコードインタプリタの箇所はオリジナルの実装ではラベルジャンプを用いて実装されている． -その為,直接ラベルにbreak pointをかける事が出来ない． -作業者がデバッガが読み込んでいるCソースコードの位置を把握し,行番号を指定してdebug pointを設定する必要があった． +その為, 直接ラベルにbreak pointをかける事が出来ない． +作業者がデバッガが読み込んでいるCソースコードの位置を把握し, 行番号を指定してdebug pointを設定する必要があった． -CbCMoarVMの場合,CodeGear単位でバイトコードの処理単位を記述している為,通常の関数と同じく直接CodeGearにデバッグポイントをかける事が可能である． -これはCプログラミングの関数に対してのデバッグで,状態ごとにbreak pointをかける事が出来ることを意味する． +CbCMoarVMの場合, CodeGear単位でバイトコードの処理単位を記述している為,通常の関数と同じく直接CodeGearにデバッグポイントをかける事が可能である． +これはCプログラミングの関数に対してのデバッグで, 状態ごとにbreak pointをかける事が出来ることを意味する． 通常のC言語で言語処理系を実装した場合と比較して扱いやすくなっていると言える． -さらにラベルテーブルでの管理場合,次のバイトコード箇所は数値でしか確認できず,実際にどこに飛ぶのかはラベルテーブル内と数値を作業者が手作業で確認する必要があった． +さらにラベルテーブルでの管理場合, 次のバイトコード箇所は数値でしか確認できず,実際にどこに飛ぶのかはラベルテーブル内と数値を作業者が手作業で確認する必要があった． スクリプトなどを組めば効率化は出来るがデバッガ上で完結しない為手間がかかる． -CbC実装ではCODESテーブル内は次のCodeGearの名前が入っている為,数値からCodeGearの名前をデバッガ上で確認する事が出来る． +CbC実装ではCODESテーブル内は次のCodeGearの名前が入っている為, 数値からCodeGearの名前をデバッガ上で確認する事が出来る +． -\subsection{JITコンパイルの応用} 現在MoarVMはLuaJit\cite{luajit}を搭載しJITコンパイルを行っている． -LuaJITそのものをCbCに適応させるわけではないが,CbCのABIにJITされたコードを合わせる事が可能であると推測できる． +LuaJITそのものをCbCに適応させるわけではないが, CbCのABIにJITされたコードを合わせる事が可能であると推測できる． % \subsection{単純なループ処理の測定} -% 簡単な例題としてfor文を用いて100000回ループさせ,ある変数をインクリメントするというプログラムを作成する． -% 今回の評価対象としてPerl6は2018年4月にリリースされたMoarVM,NQP,Rakudoの実装を用いる． +% 簡単な例題としてfor文を用いて100000回ループさせ, ある変数をインクリメントするというプログラムを作成する． +% 今回の評価対象としてPerl6は2018年4月にリリースされたMoarVM, NQP,Rakudoの実装を用いる． % Perl5は5.26.2を利用した． % \begin{table}[htb] @@ -528,47 +491,91 @@ % 100000000 & 3.258 & 124.69 \\ \hline % \end{tabular} % \end{table} - -\subsection{欠点} -本来処理系は広く使われる為に著名なOSSなどを利用して開発するのが良いが,CbCプロジェクトの認知度が低いという現状がある． +本来処理系は広く使われる為に著名なOSSなどを利用して開発するのが良いが, CbCプロジェクトの認知度が低いという現状がある． -また,前章までに複数述べた通りCbCコンパイラが現在非常にバグを発生させやすい状態になっている． -CbCコンパイラはgccとllvm/clangに実装している為,これらのアップデートに追従する必要がある． -しかしコンパイラのバージョンに応じてCbCで利用するコンパイラ内のAPIが異なる場合が多く,APIの変更に伴う修正作業などを行う必要がある． +また, 前章までに複数述べた通りCbCコンパイラが現在非常にバグを発生させやすい状態になっている． +CbCコンパイラはgccとllvm/clangに実装している為, これらのアップデートに追従する必要がある． +しかしコンパイラのバージョンに応じてCbCで利用するコンパイラ内のAPIが異なる場合が多く, APIの変更に伴う修正作業などを行う必要がある． -CbCMoarVMではCからCodeGearへ,CodeGearからCへの遷移などが複数回繰り返されているが,この処理中のCodeGearでのtail callの強制が非常に難関である． -tail callの強制には関数定義の箇所や引数,スタック領域のサイズ修正などを行う必要がある． +CbCMoarVMではCからCodeGearへ, CodeGearからCへの遷移などが複数回繰り返されているが,この処理中のCodeGearでのtail callの強制が非常に難関である． +tail callの強制には関数定義の箇所や引数, スタック領域のサイズ修正などを行う必要がある． 現在のバグではCodeGear内部での不要なスタック操作命令を完全に排除しきれていない． -またCodeGearからCに帰る場合,環境付き継続を行う必要がある． -Cの関数の末尾でCodeGearを呼び出している場合など環境付き継続を使用しなくても良いケースは存在するが,頻繁にCとCbCを行き来する場合記述が冗長になる可能性はある． +またCodeGearからCに帰る場合, 環境付き継続を行う必要がある． +Cの関数の末尾でCodeGearを呼び出している場合など環境付き継続を使用しなくても良いケースは存在するが, 頻繁にCとCbCを行き来する場合記述が冗長になる可能性はある． + +\section{Threaded Code} +現在のMoarVMは次の命令をバイトコードからディスパッチし決定後, ラベルジャンプを利用し実行している． +この処理ではディスパッチの箇所にコストが掛かってしまう． +CbCをMoarVMに導入することで, バイトコード列を直接サブルーチンコールの列に置き換えてしまう事が可能である． +これはCbCが基本ブロックの単位と対応している為である． +CbCでは現在ディスパッチを行うCodeGearであるcbc\_nextを利用しているが, Threaded Codeを実装するにあたり, +cbc\_nextと次のCodeGearに直接遷移するcbc\_fixt\_nextの実装を予定している． -\section{今後の課題} -本論文ではCbCによってPerl6の処理系であるMoarVMインタプリタの一部改良とその手法を示した． -CbCのCodeGear部分を用いることできめ細やかな記述が出来,デバッグし辛い箇所もbreakpointの設定などが容易になった． +また段階的に現在8バイト列を1命令コードとして使用しているが, これを16バイトなどに拡張し2命令を同時に扱えるように実装する事なども検討している． + +%CbCはCodeGearで末尾最適化(Tail call optimization)を行う． +%これはCodeGearは必ず関数呼び出しではなくgotoで次の状態に遷移する為にスタック領域の操作が必要とならない為である． +%現在のCbCコンパイラの実装ではCodeGearからCの関数に戻る場合は末尾最適化を切り, CodeSegment間の遷移では末尾最適化が行われる． +%末尾最適化を応用することでContinuation-passingスタイルのThreaded Codeの実装が可能となる．\cite{threadedcode} +%またCodeGear自体を直接次の遷移先として設定することも可能であるため, CbCならThrededCodeを実装するアプローチが複数検討出来る． + +%現在のCbCMoarVMは次の命令セットのディスパッチをcbc\_nextというCodeGearで処理している． +%これは元のMoarVMの命令ディスパッチで行われる現在のオペコードを示すcur\_opと命令列opの操作及び次のラベルに遷移するマクロに該当する． +%CbCMoarVMではラベルに対しての遷移の代わりにMoarVMの命令のCodeGearの集合体である配列CODESにアクセスし, その要素であるCodeSegmentに対して遷移する形を取っている． +%この一連の処理がオーバーヘッドになる為, 今後はcbc\_fixt\_nextというCodeGearを導入し直接次の命令に該当するCodeSegmentへgotoする様に実装する予定である． -今後CbCでの開発をより深く行っていくにあたり,CbCコンパイラそのものの信頼性を向上させる必要がある． -MoarVMの開発を行うにあたり新たに発見された複数のバグを修正し,より安定するコンパイラにする為に改良を行う． +Perl5においてはperlccというモジュールが開発されている． +これはPerl5内部で利用しているPerlバイトコードを, PerlのC APIであるXS言語の様なCのソースファイルに埋め込み,それをCコンパイルでコンパイルするというものである． +perlccを利用することでPerlインタプリタが無い状況でも可動するバイナリファイルを作成する事が可能である． +しかしPerlccはPerlスクリプトが複雑になるほど正確にCに移植を行う事が出来ず, 現在ではPerlのコアモジュールから外されている． +PerlccはPerlのバイトコードをCへの変換のみ行う為, Cで実装されているPerl経由で実行した場合と処理速度はほぼ変わらない． +またPerlccで生成されたCのソースコードは難解であり, これをデバッグするのが困難でもある． +MoarVMでthreaded codeを実現出来た場合, その箇所のみCbCプログラムとして切り出す事が可能である為perlccと似たツールを作成することも可能である． +CレベルでもPerlccの様に内部構造をCの関数化すればThrededCodeの様な物を構築できるが, CbCと比較して処理の単位が明確ではない為高速化は見込めない． +CbCを用いたThrededCodeでPerlccの様なツールを作成した場合, CodeGearの単位が正常に機能すればCbCのCodeGearがThrededCodeをより効率化出来ると推測できる． + + +CbCのCodeGearはgoto文で遷移するため, 次のCodeGearが一意に決定している場合Cコンパイラ側でインライン展開する事が可能である． +CodeGearがインライン展開される限界については別途研究する必要があるが, CbCを利用した場合CodeGear単位でインライン展開が可能である． +その為, ThrededCodeを実装する場合に決定した次のCodeGearをインライン展開する事が可能である． +従ってThreadeCodeを実現するにあたり新たな処理系を開発する必要がなく, 既存の資源を利用してThreadeCodeが実現出来る． +これを繰り返す事でPerlccなどと比較してより高速化したThrededCodeが実現できる． + -現在CbCMoarVMで直接バイトコードを入力した場合のnqpのテストはJVM,Javascriptのテストを除く中で80\%パスする． -また数値の計算と出力などの簡単なNQPの例題を作成し,オリジナルのNQP,MoarVMでバイトコード化したものを入力した際も正常に動作している． +\section{まとめ} +本論文ではCbCによってPerl6の処理系であるMoarVMインタプリタの一部改良とその手法を示した． +CbCMoarVMではオリジナルのMoarVMと比較して以下の様な利点が見られた. + +\begin{itemize} + \item CodeGear単位で命令処理を記述する事が可能となり, モジュール化が可能となった. + \item ThreadeCodeを実装する際に効率的に実装ができる見込みが立った. + \item CodeGearを導入した命令単位での最適化が可能となった. + \item break pointを命令の処理単位でかける事可能となった. +\end{itemize} + +今後CbCでの開発をより深く行っていくにあたり, CbCコンパイラそのものの信頼性を向上させる必要がある． +MoarVMの開発を行うにあたり新たに発見された複数のバグを修正し, より安定するコンパイラにする為に改良を行う． + +現在CbCMoarVMで直接バイトコードを入力した場合のnqpのテストはJVM, Javascriptのテストを除く中で80\%パスする． +また数値の計算と出力などの簡単なNQPの例題を作成し, オリジナルのNQP,MoarVMでバイトコード化したものを入力した際も正常に動作している． しかしNQPのセルフビルドは現在オブジェクトの生成に一部失敗している為成功していない． -今後はさらに複雑な例題やNQPのセルフビルド，Perl6の動作を行っていく． +今後はさらに複雑な例題やNQPのセルフビルド, Perl6の動作を行っていく． -MoarVMではGCからオブジェクトを守る為にMVMROOTというマクロを利用し,局所変数のポインタをスタックに登録する処理を行っている． -GCの制御を効率的に行えば本来は必要ない処理であり,実行するとCodeGearの優位性が損なわれてしまう． +MoarVMではGCからオブジェクトを守る為にMVMROOTというマクロを利用し, 局所変数のポインタをスタックに登録する処理を行っている． +GCの制御を効率的に行えば本来は必要ない処理であり, 実行するとCodeGearの優位性が損なわれてしまう． 従ってMoarVMのGCの最適化を行う． -また高速化という面では,Perlの特徴である正規表現に着目し,正規表現の表現のみ高速で動く最適化の導入なども検討している． -他にrakudoのコンパイラ系統からCbCのコードを直接生成させ,それをllvmでコンパイルすることによってLLVMの最適化フェーズを得て +また高速化という面では, Perlの特徴である正規表現に着目し,正規表現の表現のみ高速で動く最適化の導入なども検討している． +他にrakudoのコンパイラ系統からCbCのコードを直接生成させ, それをllvmでコンパイルすることによってLLVMの最適化フェーズを得て 高速化することも可能であると推測できる． -Perl6の開発は非常に活発に行われている為,CbCMoarVMの最新版の追従も課題となっている． +Perl6の開発は非常に活発に行われている為, CbCMoarVMの最新版の追従も課題となっている． 現在はinterp.cからPerlスクリプトを用いて自動でCbCのCodeGearを生成している． 今後の開発領域の拡大と共により効率的にCbCコードへの自動変換も複数のCコードに対応する様に開発を行っていく． %å\subsection{MoarVMの処理流れ} -%MoarVMはC言語で実装されており,Perl5で記述されたConfigure.plを +%MoarVMはC言語で実装されており, Perl5で記述されたConfigure.plを % BibTeX を使用する場合 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%