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

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

スポンサーサイト

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

週アレ(15) レジスタマシンと関数呼び出し

週に一回アレしてアレするらしき記事:十五回目

下書きしたはいいけど公開してなかったPart1
前回「週アレ(14) スタックマシンとレジスタマシン」ではVMにおける計算モデルの話でした
今回はレジスタマシンの方についてもう少しだけ突っ込んで見ていこうかと思います
主に速度的な観点が1つと,もう一つはレジスタマシンでの関数呼び出し周りの話

どちらかというと私が書きたいだけの内容なので,あまり有意義ではないかもしれないです


スタックマシンとレジスタマシン比較

前回に入れるべき内容だったような気がしますが,書き忘れたので今回に含めました

スタックマシン

pros

・実装がシンプルになりやすく,簡単である
・一つの命令長は短い
cons

・スタックのPush,Popが全ての計算で必要であるため,値のコピーが高価である場合速度がでない
・バイトコードはアライメントしづらい(一つの命令長は極めて短くて済む)
・命令数は多い
・一つの値を複数回使う場合もPushしてコピーする必要があるため非効率的

レジスタマシン

pros

・バイトコードはアライメントしやすい
・命令数は少ない
・局所変数はレジスタに割付けコピーなしで使いまわせるため効率的
cons

・どの命令もいくつかのレジスタを用いるため,命令長が長くなる
・実装が複雑になりやすく,難しい(特にレジスタ割付問題など)

特にパフォーマンス上で違いがでてくるのは
・バイトコードがアライメントしやすい
・一つの値を複数回使う場合のコピー
でしょうか

VM上でバイトコードを読み取る箇所は非常に頻繁に実行されるところであり,ボトルネックになりやすいところです
命令長が短いというのは長所に思えますが,アライメントがしづらい=決まったサイズで読み込みがしづらいため,ワード単位で読み込む現在のCPUでは大したメリットになりません(むしろデメリットにもなり得ます)
レジスタマシンではバイトコードを解析するステップが入りますが,一回レジスタに読み込んだ後はそこまで大きなパフォーマンス上のデメリットにはなりません

値のコピーは高価です
スタックマシンでは関数の引数を使いまわす際も毎回Pushする必要があり,これが毎演算必要になるのでスタックマシンでの速度低下の要因はこの辺もあります
レジスタマシンはこれらをレジスタに割付て演算させます
個人的には,スタックマシンでは値をPushやPopさせ実行する時に演算する値を定めますが,レジスタマシンではそれらの指定をバイトコード吐き出す時に計算するようにしたものだと思っています



レジスタマシンにおける関数呼び出し

なぜ今回これを取り上げたかというと,スタックマシンとレジスタマシンとで実装が異なってくる部分の一つだからです
スタックマシンの場合は関数呼び出しは引数をスタックに積んで関数側のコードへ移り,戻り値はスタックに積んだ状態で変えれば済みます,割りと単純です
一方,レジスタマシンでは関数呼び出しから戻ってきても正常に処理を続行できるように「レジスタの退避・復元」処理や,戻り値をどこに格納するかといった問題があります
また,関数の引数もどこに格納するのでしょうか
レジスタ以上の数の引数があった場合,関数呼び出しができないことになります

こういったレジスタの退避・復元や引数の保持にはスタックが用いられます
スタックマシンのときもそうでしたが,ここで言うスタックは抽象データ型を指しており,スタックマシンのそれとは含んでいる内容(保持している値)が異なります
レジスタマシンにおけるスタックは関数コール時に退避するレジスタの中身を保存しておき,戻ってきたらスタックからPopしてレジスタの中身を復元します

…というのは理論上の話で,機械語レベルならともかく,言語処理系のVMレベルでは実際にそんなことをやっていたら効率が悪くてレジスタマシンである利点が薄くなってきます
そこでパフォーマンスを上げるため,引数保持のスタックとレジスタは一緒にするような実装がよく見られます

前回Luaのバイトコードでは,レジスタマシンであることを確認する時に関数の内容を吐かせました
その時,関数の引数はレジスタの最初の部分に既に入った状態で関数が呼ばれるようなバイトコードでしたね
Luaの実装では,レジスタとなる領域を大量に用意しておきます
そこでいくつかのレジスタをひとまとまりにし,一つの関数内ではこのひとまとまりのレジスタを用いて計算を行います
関数などの呼び出し時などにはこのひとまとまりでシフトさせることで,擬似的に関数内のレジスタの復元・退避を行います
reg_lua_slide.png

この大量のレジスタ領域をシフトさせるのはちょうどスタックであり,「レジスタマシンのVMとか言いつつスタック使ってるし結局スタックマシンじゃん!」という突っ込みが入りそうなのですが,というか私も最初そう思ったのですが
前回お話した通り計算モデルとしてのスタックマシンとレジスタマシンは,各演算がスタックを使うかレジスタを使うかで分類するので,そのレジスタが例えスタックに入っていたとしても計算モデルはレジスタマシンとなります


こうすることで全てのレジスタが一操作で退避・復元することができるため,パフォーマンス上かなりのメリットを持つことができます
かなりリソースとしては富豪的なやり方ですが,これでも各レジスタが持つ値が大きくないので組み込みでも何とかなるんですかね…ちょっと不思議


終わりに

若干誰得な微妙な感じでしたが,主にLuaのレジスタマシンの実装よりの話でした

本当に誰得ですね
実際に自分で作ったVMをスタックマシンからレジスタマシンに書き換えたら,パフォーマンス測って比較してみたいと思います


りふぁ

Luaのコード生成
LuaVM: 12分くらいでしるLuaVM
ひとり勉強会 レジスタマシンとスタックマシン
関連記事
スポンサーサイト

コメント

はじめまして
非常に勉強になる記事です
疑問なのですが、Luaにおいて末尾再帰でない再帰などでレジスタを使い切ってしまった時は、スタックオーバーフローと同じ扱いでプログラムが異常終了するのでしょうか?
というより、たった256個のレジスタでは、再帰でなくとも普通のプログラムで使い切ってしまいそうな気もしますが、十分だったりするんですかね

  • 2015/10/14(水) 01:34:21 |
  • URL |
  • あごみつ #-
  • [ 編集 ]

Re: タイトルなし

> あごみつさん
はじめましてー、筆者です、返信が遅くなってしまい申し訳ないです。

> 疑問なのですが、Luaにおいて末尾再帰でない再帰などでレジスタを使い切ってしまった時は、スタックオーバーフローと同じ扱いでプログラムが異常終了するのでしょうか?
> というより、たった256個のレジスタでは、再帰でなくとも普通のプログラムで使い切ってしまいそうな気もしますが、十分だったりするんですかね

この記事を書いたのは結構前で、最早記事内容からLuaの内部実装まで忘れていたのでちょっと復習してきました。

確かにLuaのVMが一度に扱えるレジスタの大きさは256個ですが、それは関数スコープ内だけの話です。
Luaが持っている全レジスタの領域自体は256個よりもっと多くなり得ますし、再帰したら実際大きくなります。
レジスタ用の領域はある程度乱暴に言ってしまえばC++などのvectorなどと同じ可変長配列で、Luaでは関数コールなどの際に今持っているレジスタ領域の大きさが足りなかったら、自動で伸長する処理が入っています。
VMが関数の処理に入る際、Luaが持つ全レジスタ用の領域からその関数内で使うレジスタの基準となる箇所だけ覚えておいて、実際のVMの実行ではその基準の箇所から最大で256個のレジスタしか使わない、という感じです。(このイメージについては記事内の画像を参照)

なぜ最大で256個しか扱えないのかについては、むしろバイトコードの仕様からくるものだと思われます。
Luaでは一つの命令は(デフォルトだと)4バイトで表されていますが、ここにはオペコードを指す値と、最大でレジスタを表す値が3つ入ります。
つまり大体一個のレジスタを表現するのに1バイトぐらいしか使えなかったので、一度に扱えるレジスタは256個となっています。(この辺、どうやらソースコードを弄ると何か増やせるっぽい気配がしましたが、試してないので定かではないです)
ただ、「一つの関数内」という視点で見ると、256個も使うことは早々なさそうですし、デフォルトで採用されていることもあるため、経験的に十分な量なのでしょう。

以上、少々長くなってしまったり画像がなくて分かりづらかったかもしれませんが、こんな感じです。

  • 2015/10/17(土) 18:46:25 |
  • URL |
  • えくー #-
  • [ 編集 ]

> この記事を書いたのは結構前で、最早記事内容からLuaの内部実装まで忘れていたのでちょっと復習してきました。

おー、わざわざありがとうございます

関数毎にベースレジスタ(って言うんですかね)をシフトしつつ、足りなくなったら伸ばすんですね
それだと伸長時はコピーが必要になるんでちょっと遅くなるのかな

ちなみに Dalvik では関数毎に必要なレジスタ数を確保する形なので、コピーは不要だけど引数なんかはスタックに積んでますね

  • 2015/10/20(火) 05:45:35 |
  • URL |
  • あごみつ #-
  • [ 編集 ]

コメントの投稿


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

トラックバック

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

FC2Ad

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