なんだか雲行きの怪しい雑記帖

ぐだぐだ日記とメモと,あと不定期更新

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

週アレ(14) スタックマシンとレジスタマシン

週に一回アレしてアレすると思われた記事:十四回目

時間が空きました
分かってたつもりですが,本当に一回やらなくなるとその先もずっと手を付けられなくなりますね
主に私が新しいものに手をつける理由が最近ないからなのですが,それが何に起因するのか(あるいは起因しないからなのか)については言及しようとしてもしょうがないことですね
…意味不明だな…

それはさておき,今回は仮想機械(VirtualMachine:VM)の設計寄りの話でスタックマシンとレジスタマシンについてです
この辺はオレオレ言語の為に自分でVM作ろうとかそういうことを思わない限り個人で関わることはない話だと思います
”仮想機械”という単語だけだと,VirtualBoxやVMWarePlayerなどOSなどの大規模なシステムごと仮想化するシステム仮想機械(SystemVirtualMachines)も含まれてしまうのですが,今回はそちらではなく言語の実装などに使われるプロセス仮想機械(ProcessVirtualMachines)に焦点を絞ります

最初は仮想機械全体についての話も少し入れてありますが,それよりもスタックマシンとレジスタマシンの話を聞きたいんよという方は最初の方は飛ばして頂ければと思います
仮想機械

仮想機械ということで,文字通りに解釈すると「仮想化された機械」です
とだけ書くとあまりに意地悪なのですが,要点は「仮想化」と「機械」です
 (うぅむ,何も話が進んでないような気がしますね…)

今回は仮想機械の中でもプロセス仮想機械に話を絞るのですが,プロセス仮想機械は何らかのプログラムを動作させるためのものです
何らかのプログラム,というのはPythonやRuby,Luaなどの言語処理系で書いたプログラム,といえば具体的でしょうか
それらのプログラムは例えば「ネットワークに接続してある文字列をツイートする」とか,「キーボードの入力を受け付けて画面に標示する」とか何でもいいのですが,とどのつまり「何らかの計算をする」ような処理がかかれたものです
プログラム自体にはその「処理の内容が書かれている」だけなので,これを動作させるためにはその内容を理解して実行する環境が必要となります
”仮想機械”の「機械」にはそういう意味が含まれています

さて,では”仮想機械”ですが,一体何が「仮想化」されているのでしょうか
答えは(ある程度暴力的な表現となりますが)”計算機資源”です
”計算機資源”には含まれているものとしては,計算に必要な値を格納するメモリであったり,計算自体に必要なCPUなどの実行コアであったり,外部に存在するためのデータを入出力するインタフェースであったり,…様々なものがあります
仮想化すると何が嬉しいのかという点について書くと長くなるので割愛しますが(see:リファ-1),

今回の話は仮想機械のどの部分なのか

大きく仮想機械の話から始めてしまったのに,この記事が対象としている部分はそれら仮想機械の中での中核部分で,仮想機械の中での計算モデルにあたります
具体的には,計算を行う際どこに計算すべき値が入っていて,どこに計算した値を格納するのかのモデルと言えます
まさに”機械”の部分の中核ですね

スタックマシン

スタックマシンは非常にシンプルな計算モデルで,古くからよく用いられてきたモデルです
スタックマシンとしては,Java仮想マシン(JavaVirtualMachine:JVM),Rubyのインタプリタ実装の1つであるYARV,CPythonとかが挙げられます
ただ,最近は後述するレジスタマシンの方がパフォーマンスがでやすいということで,比較的大きめのプロジェクトではスタックマシンからレジスタマシンへの移行がよく見られます
LuaやXtal,Perlもそうです

スタックを用いた計算

さて,スタックマシンは名前の通りスタックを使って計算を行うのですが,スタックという単語自体は抽象データ型を指します
stack_push_pop.png
値を”積んで”いって,取り出す時は積まれた山の一番上から取っていくため,FILO(First In Last Out)またはLIFO(Last In First Out)なデータ構造です
「積む」操作はPush,「山の一番上から取る」操作はPopと呼ばれます

このスタックを用いて計算を行う場合は次のような処理フローになります
 ・計算に必要な値をスタックからPopする
 ・値同士の演算を行う
 ・演算によって得た値をスタックにPushする
stack_pushpop_calc.png

この操作はちょうど計算式を逆ポーランド記法で示した時の順番と一緒になるため,スタックマシンの話をするときによく一緒になりますよね

実際の言語の実装を見てみる

折角なので実際の言語が吐き出すバイトコードを眺めてみようかと思います

Ruby

RubyのVMとしてver 1.9.0から本家にYARVがマージされたらしく,最近のRubyはインストールするとデフォルトでYARVらしい
というわけで,ついさっきインストールしてきたRuby 2.1.0を使ってバイトコードを見ていきましょう
Ruby自体のダウンロードはこちら:Ruby -A PROGRAMMER'S BEST FRIEND-

Rubyのソースコードを食ってバイトコードを吐かせるためには次のような感じ
code = "何らかのRubyのソースコード"
puts RubyVM::InstructionSequence.compile( code ).disasm


ちなみにファイルからコンパイルする場合はこう(see:RubyVM::InstructionSequence
filepath = "Rubyのソースコードのファイルパス"
puts RubyVM::InstructionSequence.compile_file( filepath ).disasm



さて,では実際に数値同士のちょっとした演算を行うものを食わせてみます
code = "11*2+3"
puts RubyVM::InstructionSequence.compile( code ).disasm

Output:
== disasm: <RubyVM::InstructionSequence:<compiled>@<compiled>>==========
0000 trace 1
( 1)
0002 putobject 11
0004 putobject 2
0006 opt_mult <callinfo!mid:*, argc:1, ARGS_SKIP>
0008 putobject 3
0010 opt_plus <callinfo!mid:+, argc:1, ARGS_SKIP>
0012 leave

先ほど説明したように,最初の計算(掛け算)に必要な値である「11」と「2」をPushしたあと,掛け算を実行する命令を行っています
演算された値は既にスタックに乗っているため,今度は新しく「3」だけをPushしたのち,足し算を行っています
余談ですが,数値をPushする命令が「putnumber」とかではなく「putobject」となっています
実はRubyでは全ての値がobject型として扱われているため,このような命令だったりします
と思いきや,実は文字列の時は「putstring」だったりしますし,一体どういうことなのかは,なかなか難しいですね…
まぁ多分数値系は固定長のだけど文字列は可変長だからバッファが別とかそういうのだと思われますが


CPython

CによるPython実装CPythonもスタックマシンのようです,今回はちょっと古めのPython 2.7.5を使いました
Pythonoダウンロードはこちらから
Pythonでのバイトコードの表示は「dis」モジュールの「dis」メソッドです,ややこしいですね

ソースコードからバイトコード表示する場合は次のような感じ
import dis
print( dis.dis( compile( "なんらかのコード", "", "eval" ) ) )

関数レベルでバイトコード表示する場合は次のような感じ
import dis
def f():
return

print( dis.dis( f ) )

では早速やってみましょう
import dis
print( dis.dis( compile( "a*b+c", "", "eval" ) ) )

Output:
1 0 LOAD_NAME 0 (a)
3 LOAD_NAME 1 (b)
6 BINARY_MULTIPLY
7 LOAD_NAME 2 (c)
10 BINARY_ADD
11 RETURN_VALUE
None

PushではなくLOADであったりしますが,同様の結果が得られたと言っていいでしょう
実はPythonのコンパイルは定数畳み込みの最適化が入るので,先ほどのRubyの例のように数値リテラルを用いたソースコードを放り込むと演算結果をロードする命令に変換されてしまいます
なので,今回は最適化されないよう変数の「a」,「b」,「c」にしました



レジスタマシン

レジスタマシンは有限個の”レジスタ”という値を格納する場所を考え,計算する値の入出力は全てこのレジスタを介して行うような計算モデルです
チューリングマシンとかそういった学問的な背景についてはこの記事では触れません(し,私もよく知りません)

実際のCPUのアーキテクチャとしてはかなり一般的な計算モデルです
レジスタマシンは最適化の手法もかなり研究されている等の事情もあって,スタックマシンより高速化しやすいという話もあるような
 (あるいは,近年だとレジスタマシンベースのLLVMの登場により,レジスタマシンで作った方が直接(あるいは若干の変換を噛ませつつ)LLVMに食わせられて便利だ,というのもあるでしょうね)

レジスタマシンにおける計算の処理フローは次
 ・計算に必要な値をレジスタにロードする
 ・レジスタを指定して演算を行う
 ・演算結果を指定したレジスタに格納する
reg_loadstore_calc.png

スタックマシンとの主な違いは「入出力先として任意のレジスタを使って良い」という点で,一時的に扱える値がスタックマシンに比べて多いことが分かります

実際の言語の実装を見てみる

折角なので

Lua

Luaはスタックマシンからレジスタマシンになった言語の1つです
Luaのダウンロードはこちらから

Luaのバイトコードの表示は付属している「luac」を使います
コマンドライン(かターミナル)で次のように使うのが通常
luac -l <source filepath>

とりあえず次のような内容に対してバイトコードを表示してみます
function f( a, b, c, d )
return a*b + c*d
end

Output:
main <dis.lua:0,0> (3 instructions at 00331E48)
0+ params, 2 slots, 1 upvalue, 0 locals, 1 constant, 1 function
1 [3] CLOSURE 0 0 ; 0045E5E0
2 [1] SETTABUP 0 -1 0 ; _ENV "f"
3 [3] RETURN 0 1

function <dis.lua:1,3> (5 instructions at 0045E5E0)
4 params, 6 slots, 0 upvalues, 4 locals, 0 constants, 0 functions
1 [2] MUL 4 0 1
2 [2] MUL 5 2 3
3 [2] ADD 4 4 5
4 [2] RETURN 4 2
5 [3] RETURN 0 1

バイトコードもう少し易しい表示かと思ったらそうでもないんですね…
実はバイトコードの形式について正式な資料はLua5.2にはなく,Lua5.1のものであればA No-Frills Introduction to Lua.5.1 VM Instructions:PDFがありますが,いずれにせよすぐに見て分かるものないため補足します

まず大事なのは関数の中身の部分なので,最初の
main <dis.lua:0,0> (3 instructions at 00331E48)
0+ params, 2 slots, 1 upvalue, 0 locals, 1 constant, 1 function
1 [3] CLOSURE 0 0 ; 0045E5E0
2 [1] SETTABUP 0 -1 0 ; _ENV "f"
3 [3] RETURN 0 1

ら辺は飛ばします
Luaでは関数定義「function f~~」は,Global空間に「f」という名前の関数型の変数を作ること「f = function(){~~}」の糖衣構文なのでこういうバイトコードになります
いずれにせよ,今回の対象である関数の内容とは全く関係ないため飛ばします


すると残るのは
function <dis.lua:1,3> (5 instructions at 0045E5E0)
4 params, 6 slots, 0 upvalues, 4 locals, 0 constants, 0 functions
1 [2] MUL 4 0 1; reg[4] = reg[0]*reg[1]
2 [2] MUL 5 2 3; reg[5] = reg[2]*reg[3]
3 [2] ADD 4 4 5; reg[4] = reg[4]+reg[5]
4 [2] RETURN 4 2; return reg[4] = return reg[4] to reg[4+2-2]
5 [3] RETURN 0 1;

となります,分かりづらかったので右側のその意味を書いておきました
reg[i]はi番目のレジスタを表します
RETURNだけちょっと変則的な書き方になっていますが,これはLuaでは関数は複数個の値を返すことができるからで,LuaのVMを本気で読み解こうと思わない限りスルーしていいです

MULやADDなどは,入力として2つの値を受け取り,出力として1つの値を書き込みます
そのため,入力に2つのレジスタ,出力の1つのレジスタを指定します
luacで出力される表示形式では,一番左の数字が出力先のレジスタを,残る真ん中と右の数字が入力となるレジスタ(または定数)のを表します

さて,私が書いたのは4つの引数を受け取って,それらの積や和を返すような関数ですが,引数はどこに格納されているのでしょうか
バイトコードを見て気付いた方もおられるかも知れませんが,Luaでは関数の引数はレジスタに格納されたままで関数本体のバイトコードにジャンプします
今回の例えはreg[0]~reg[3]に関数の引数が入っています(reg[0]からそれぞれa,b,c,dです)
そのため,関数内部では直接それらのレジスタを使った演算のコードが入っています

参考:
どうせなので,スタックマシンで同じような関数を定義した場合はどのようなバイトコードと比較してみましょう
CPythonで次のようなコードに対してバイトコードを表示してみます
import dis
def f(a,b,c,d):
return a*b + c*d

print( dis.dis( f ) )

Output:
3 0 LOAD_FAST 0 (a)
3 LOAD_FAST 1 (b)
6 BINARY_MULTIPLY
7 LOAD_FAST 2 (c)
10 LOAD_FAST 3 (d)
13 BINARY_MULTIPLY
14 BINARY_ADD
15 RETURN_VALUE
None

レジスタマシンより命令数は多いですね
一般的に,スタックマシンはレジスタマシンより命令数が多くなります



終わりに

今回は(プロセス)仮想機械の計算モデルについての話でした
なぜこの話をしたのかというと,ちょうと自分で作っていたVMをスタックマシンからレジスタマシンに変えようかなと思って調べていたからだったりしますが…
でもスタックマシンとレジスタマシンの基本的な話に終始してしまい(というよりここまで書いて私の体力が尽きた),当初オレが書きたかったことがまるで書けてないことに今更気付いてどうしようか悩んでいる
むー,まぁちょっと突っ込んだ細かい話は次回あたりに回そうかと思います(

ところで,一応書いておきますがこれらスタックマシンやレジスタマシンはただの実装の問題ですので,言語そのものとは別です
だから「Pythonはスタックマシンだからダメだ!」とかそういう論法は全く的外れであり,意味がないので注意しましょう
 (実際RubyなどはJRubyはMacRuby,Rubiniusなど様々な実装派生が存在しますが,実装によってスタックマシンかレジスタマシンかは異なります)

…それにしても,最近軽めの記事しか書いてないなぁ


リファ

毎回思う,先人様方の記事の解りやすさと偉大さね
以下参考にさせて頂いたサイトでした

[1] Ruby Magazine: YARV Maniacs 【第 2 回】 VM ってなんだろう
関連記事
スポンサーサイト

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://fe0km.blog.fc2.com/tb.php/106-59ba6f64
この記事にトラックバックする(FC2ブログユーザー)

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。