YARV Maniacs 【第 2 回】 VM ってなんだろう

書いた人: ささだ

はじめに

YARV Maniacs の第 2 回です。前回 (YARV Maniacs 【第 1 回】 『Ruby ソースコード完全解説』不完全解説) は RHG の紹介という 手抜き 工夫をしたおかげで結構簡単に書けたのですが、早速 2 回目からネタに詰まりました。連載開始前はソースコードの細かいところを逐一解説して、「だから高速化されてるんですよ」ということを示そうと思っていたのですが、それだとあまりにマニアックだし、あまりに興味を持つ人は少ないだろうし、あまりにそもそも理解してくれる人が少なそうなので、どうしようかなぁ、と。

というわけで、もうちょっと簡単なところから解説していこうかと思っています。という建前で、本当のところは簡単なことじゃないと説明できそうにないからなんですが。

というわけで、本稿では YARV: Yet Another RubyVM の名前にある VM とはいったい何なのか、いったいナニモノで、あると何がうれしいのか、そもそもプログラミング言語 Ruby とどういう関係があるのか、具体的にどんなことをするものなのか、どんなふうに作るのか、そこから説明してみます。

自分でも、ここまで簡単なところまで引き返すことないじゃないか、とも思うんですけどね。まぁ、先は長いし。

Virtual Machine

日本語でいうと仮想機械ですが、いったいこれはなんでしょう。わからないことがあったらすぐに Google。聞いてみましょう。

真・コンピュータ用語辞典:仮想マシン より引用:

謳い文句として「アーキテクチャ非依存」「既存のプラットフォームからの独立」など大層ご立派な事が並ぶが、仮想的なマシンの上で魅力的な環境を構築し、次の世代のコンピュータ界を牛耳ろうと企んだ連中に都合良く作られたアーキテクチャのこと。

はい。そういうことらしいです。

えーと、これじゃよくわからないですね、ほかの解説は無いかな。うーん、「仮想マシン」の解説はこれくらいしか見つからないな。Virtual Machine だと KVM (IT用語辞典 e-Words : KVMとは 【K Virtual Machine】 ─ 意味・解説) とか、JVM (IT用語辞典 e-Words : JVMとは 【Java仮想マシン】 (Java Virtual Machine) ─ 意味・解説) くらいしか見つけることができませんね。まぁ、知名度から言うとこんな感じなのかも。

もうちょっと基本的なところから見てみましょう。「真〜」のほうの解釈は、まぁそういうこともあるのかもなぁ、と思うけど、別に私はそういうことをたくらんでいるわけじゃないから、ここに反例が居るってことになりますねぇ。って、真に受けてる人は居ませんか。

仮想化って何?

調子に乗って、IT用語辞典 e-Words : 仮想化とは 【virtualization】 ─ 意味・解説 より引用します。

プロセッサやメモリ、ディスク、通信回線など、コンピュータシステムを構成する資源 (および、それらの組み合わせ) を、物理的構成に拠らず柔軟に分割したり統合したりすること。

1台のサーバコンピュータをあたかも複数台のコンピュータであるかのように論理的に分割し、それぞれに別のOSやアプリケーションソフトを動作させる「サーバ仮想化」や、複数のディスクをあたかも1台のディスクであるかのように扱い、大容量のデータを一括して保存したり耐障害性を高めたりする「ストレージ仮想化」などの技術がある。

とのことです。IT用語辞典、ということで、かなり偏った用語解説になってますね。一行目も物理デバイスについての仮想化の例にはなっていますが、仮想化ということ自体の説明ではありません。

仮想化を簡単に言うと、「何かそうでないもの (かもしれないもの) をある (仮想化された) ものとして見せる」ことかと思います。ここでは、計算機に限った仮想化について、もう少し深くみてみます。

というわけで、女の子を仮想化してどうこうということは関係ありません。多分。

計算機資源を仮想化するということ

そもそもなんで仮想化するんでしょうね。

私は実は OS (Operating System) 系研究室の学生で、OS の話はちょっと齧ったりするんですけど (ちゃんと勉強しろよ)、要するに OS というのはいかに効率よく、便利に計算機資源を仮想化するか、というモノなのだそうです。これは OS だけでなく、システムソフトウェア、つまりソフトウェアを動かすために必要なソフトウェア全般に言える事なのですが。

で、なんで仮想化するかということですが、まぁ、ぶっちゃけ便利になるからですね。OS の例でいうと、たとえば Linux カーネルはたくさんの CPU のマシン上で動作しています。たとえば、Intel の CPU 、IBM の CPU という感じです。Linux 上で動作するプログラムは Linux が保証する方法で作ってさえいれば、たいていの場合は Intel の CPU 用、IBM の CPU 上などの Linux で動かすことが出来ます。大抵は。

Ruby もそうですね。プログラミング言語 Ruby で書いたプログラムは、なんとか Linux とか、なんとか BSD とか、Windows なんとか等で大抵同じように動きます。この大抵、というのがいろいろとアレですが、まぁ、多分動きます。動くこともあります。動かないこともないです。動いたらいいなぁ。

ここではいくつかの層が出来ていることも注意が必要です。つまり、CPU などの物理的なレイヤーの上に、OS というレイヤーがあり (ここで一段目の仮想化が行なわれている)、その上に Ruby というレイヤーがあるという感じです。つまり、2段の仮想化が行なわれているんですね (細かく見ていくと、本当はもう少し色々挟まってるんですが、面倒なのでそういうことにしておきます)。

こんなわけで、具体的な何かに依存するよりは、中間層を設けることによって別々のものを扱いやすくしましょう、というのが仮想化です。中間層により、上層で利用することのできるインターフェースを共通化することで利用しやすくしましょうね、ということです (移植性の向上)。

仮想化によるメリットは移植性の向上よりも、たとえば、下位レイヤーになかった機能を付加することが可能なところのほうが大きいかもしれません。たとえば、セキュリティのための何らかのチェック機構を中間層に加えるというのが最近の流行ですね。

この辺で難しいところは、「じゃぁどこを中間層として何を仮想化するか」、つまり、何を目的として、どこで上と下を分けるか、ということなんですね。数学と違って計算機の分野 (科学・工学) では処理速度、処理効率が大変重要な研究課題ですが、一般的に、中間層を上のほうに持ち上げると、扱いやすくはなるのだけれど遅くなり、下げると高速に動作するけど使いづらい (たとえば、プログラミングがしづらくなる)、というトレードオフがあります。で、そのバランスが難しいから OS の研究者はいまだに研究が続けられるんですね (いや、もちろんそればっかりじゃないですけど)。

最近、計算機分野で仮想化の技術が頻繁に叫ばれているのは、計算機資源が以前とくらべて (とても低予算な環境でも) 潤沢になり、仮想化のオーバヘッドがあっても便利さを取ったほうがいいや、と考える人が増えてきたからなのですね。

低予算じゃない、たくさんのお金で作るような計算機では仮想化の技術はよく利用されており、研究もずいぶん進んでいるそうです。だから、最近の VMWare などに代表される複数 OS の同一計算機上での同時利用のような技術は昔からある、などという人も居ます。環境が違うので、話はそんなに単純じゃないんですけどね。

言語処理系と Virtual Machine

言語処理系で VM というと、Java が有名ですね。例の "Write Once, Run Anywhere" というやつです。最近だと、Microsoft が推している .NET フレームワークというのもアレですね。

言語処理系で VM を作ってその上で実行させる、というのは、トータルで見たとき言語処理系が作りやすくなるからです。以下、その理由を説明してみます。

とりあえず、解釈実行系、つまりインタプリタを念頭に話を進めます。

プログラミング言語 P があったとき、P を動作させるには環境 E (CPU であったり OS であったり) で P を解釈実行するための機構が必要ですが、E が E1 〜 En まであったとき、n 個の処理系が必要になります。そこで、P を実行することを目的とするのではなく、もっと簡単な中間言語 I を実行する処理系を E1 〜 En に用意することで、P を I に変換するコンパイラ (変換器) を作ることができれば E1 〜 En のどの環境でも P を動作させることが可能になります。

E1 〜 En で I 処理系を作るのは簡単だが、P 処理系を作るのが面倒くさい、と思っていただければいいんじゃないかと思います。

図にするとこんな感じです。

+-----------+  +-----------+  +-----------+
| 言語 P1   |  | 言語 P2   |  | 言語 P3   |
|           |  |           |  |           |
+-----------+  +-----------+  +-----------+
| 環境 E1   |  | 環境 E2   |  | 環境 E3   |
+-----------+  +-----------+  +-----------+

                     ↓

+-----------------------------------------+
|             プログラム言語 P            |
+-----------+--+-----------+--+-----------+
| 中間層 I1 |  | 中間層 I2 |  | 中間層 I3 |
+-----------+  +-----------+  +-----------+
| 環境 E1   |  | 環境 E2   |  | 環境 E3   |
+-----------+  +-----------+  +-----------+

なんとこの図は青木峰郎さん謹製です。ありがたや。*1

たとえば、C 言語で中間言語 I を処理するプログラムを書けば、大抵ほかの環境で動きます (これは、OS その他による仮想化のおかげですね)。

そこで、具体例を挙げてみると、各種 OS 上にある C で書いたプログラムを動かす各種環境 (C 環境) 上で、configure なんかで作った Ruby 処理系を作っておけば、Ruby プログラムは (大抵) 何も環境を考えずに動作させることができます。

+-----------------------------------------+
|              Ruby プログラム            |
+-----------+--+-----------+--+-----------+
|Ruby 処理系|  |Ruby 処理系|  |Ruby 処理系|
+-----------+  +-----------+  +-----------+
|    C 層   |  |    C 層   |  |    C 層   |
+-----------+  +-----------+  +-----------+
|   Linux   |  |  Solaris  |  |  Windows  |
+-----------+  +-----------+  +-----------+

プログラム言語 P を I に変換するプログラムを書けば大抵の環境で動かすことができます。中間層の I を使いまわせばプログラム言語 Q を I に変換するプログラムを書くことで Q を簡単に動かせるかもしれません。

+--------+--------+
| 言語 P | 言語 Q |
+--------+--------+
|     中間層 I1   |
+-----------------+
|     環境 E1     |
+-----------------+

こんな感じですね。この辺の話は .NET 環境 (仮想マシン) 上でいくつものプログラミング言語が動作していることをみればわかってもらえると思います。

また、P を直接実行するよりも I を実行させるほうが高速化のための最適化も行いやすく、また利用メモリなどの必要な計算資源も (それを考慮した I とその処理系であるならば) 十分小さくなるそうです。たとえば、計算機資源が一般的に少ない組み込みシステムや、BIOS のような環境ではインタプリタで何か処理を書くこともあるそうです。残念ながら YARV ではそういう省資源設計にしてませんが。

一般にインタプリタと呼ばれる言語処理系はほぼすべてこういう構造を取っていて、現在の Ruby の処理系も Virtual Machine ということができます (構文木という煩雑な中間構造を処理する仮想機械)。

理論的には、VM はいくら重複してもいいんですよね。VM1 上で VM2 を動かして、...、VMn 上で VMn+1 を動かす、ということも可能です。どんな意味があるかはわかりませんが。

ところで、コンパイラを考えてみると、P から E1 〜 En 用の機械語コードを生成する必要がありますので、色々と面倒だなぁと思ってもらえればいいと思います。C 言語は GCC が頑張っていろんな環境で動作させているので、C 言語を中間言語 I として、その他のプログラミング言語 R を C 言語に変換して、ということもやります。YARV でも、Ruby -> C 変換を行なう機能を有しています。

バイトコードマシン

バイトコードとはなんでしょうか。

T用語辞典 e-Words : バイトコードとは 【byte code】 ─ 意味・解説より引用します。

特定のOSやハードウェアに依存しないように定義された命令の集合によって記述された実行形式のプログラム。人間の書いた設計図であるソースコードと、実際にコンピュータで実行可能なネイティブコードの中間に当たる形式である。

命令をすべて1バイトで表現し、プログラムのサイズを小さく抑えているためバイトコードと呼ばれる。Java言語のバイトコード(Javaバイトコード) のことを単に「バイトコード」と呼ぶことが多い。

バイトコード形式のプログラムを動作させるには、バイトコードを解釈してそのコンピュータのネイティブコードに変換する仮想マシンと呼ばれるソフトウェアが必要である。アプリケーションソフトをバイトコードで配布することにより、仮想マシンが実装されているOSが動作すれば、機種を問わずにそのアプリケーションソフトを実行することができるという利点がある。

バイトコード形式をサポートしている言語にはJavaやSmalltalkなどがある。

らしいです。Ruby もこの中に書かれる日は来るんだろうか。

実際、この定義をご存知の方も多いと思うのですが、そうじゃない解釈も結構あって、たとえばバイトコードは 1 byte じゃないといけない、とは言わない場合があります。実際 YARV はこの定義ではバイトコードではなくワードコードということができます。まぁ、面倒なんでもういいません (高速な命令実行について解説するとき、もう一度だけこれについて触れます)。

バイトコードという言葉は、たとえば現在の Ruby 処理系が実際に実行するときに参照している構文木 (ツリー構造のデータ) と対比して、命令の並びが一本道になっているものを指すことが多いようです。YARV はこの定義ではバイトコード処理系になります。

バイトコードを中間言語とする処理系には多くの最適化が知られており、実行の高速化が容易です。なので、YARV はバイトコードを解釈実行する処理系になっています。というか、そのために YARV を作りました。

バイトコード処理系は、C 言語で書くと本当に簡単でこんな感じで動作します。

while(まだ次の命令があるか){
  命令 = 命令列[プログラムカウンタ];
  なんかする(命令);
}

なんかする(命令){
  switch(命令){
    case なんか1:
      なんか1 の処理;
      break;
    ...
    case なんか2:
      なんか2 の処理;
      break;
  }
  プログラムカウンタを次の命令に移す;
}

えらい簡単ですが、多かれ少なかれみんなこんな感じです。CPU も、中の人はこんな感じで動いています。

計算モデル

ここでいう VM は要するに計算機を仮想化したものなので、計算をしなければなりません。計算するには計算するためのモデルが必要なんですが、その辺を紹介してみます。なお、実際に計算機などで使われているものを紹介しますので、論理的に計算可能である、とか、そういうものは載せていません (あんまり知らないだけなんですが)。

スタックマシン

計算の途中経過を主にスタックに保存して計算していきます。逆ポーランド記法で書いた計算式は、まさにこのモデルで計算することを想定しています。たとえば、"1 2 +" は、1 と 2 をスタックに積んで、記号 "+" によりスタックトップの2つの値 (1 と 2) を取り出し (pop)、足し合わせてスタックトップに追加する、などです。

この方式はコンパイラが非常に簡単に作れますが、最適化が少しやりづらいです。命令レベルの並列化も (多分) 苦手です。

YARV は考えることがあまりなさそうな、このスタックマシンモデルを採用しています。

レジスタマシン

計算の途中経過を限られた数のレジスタに保存して実行していきます。ふつーの CPU はこの計算モデルを採用していますね。ハードウェア的には作りやすいモデルです。というか、ほかはほとんどありません。また、ソフトウェアによる最適化もやりがいが大変あるのが特徴です。

また、命令レベル並列化もやりやすく、命令列が短くなることが知られています。ただ、レジスタをどうやって利用するかという点は非常に難しい問題なので、開発も難しいし、コンパイル時間も増加してしまう恐れがあります。

その他

すみません、よく知りません。論理型、関数型とかに面白そうな計算モデルがありそうなのですが。現在の Ruby 処理系のツリーを辿る計算モデルは、スタックマシンなんだろうか。

スタックマシンを作ってみる

まぁ、文章ばっかりではつまらないのでスタックマシンを作ってみましょう。簡単なプログラミング言語を でっち上げて とりあえず設計してみました。

とりあえず、スタックが一個あって、そのスタックに push する命令と pop する命令、それからスタック上のデータを2つとってきて演算 (加減乗除) する命令と、無条件、条件ジャンプする命令を付ければ、とりあえず計算は出来そうなので、それでやりましょう。

名づけて RubiMaVM です。

ソースコード

RubiMaVM は、もちろん Ruby で書きます。Ruby ではコンパイラ、VM をあわせて簡単に書けます。これからは VM は Ruby で書くのがトレンドですよ。YARV は C で書いてるけどね。

#
# RubiMaVM
#

module RubiMaVM
  class Instruction
    def initialize code, opts
      @code = code
      @opts = opts
    end
    attr_reader :code, :opts

    def inspect
      "#{code} <#{opts.join ', '}>"
    end
  end

  class Label
    @@id = 0
    def initialize label
      @label = label
      @pos = -1
      @id  = @@id+=1
    end
    attr_accessor :pos

    def inspect
      "#{@label} <#{@id}@#{@pos}>"
    end
    alias to_s inspect
  end

  class Evaluator
    def initialize
      @stack = []
      @pc    = 0
    end

    def evaluate sequence
      while insn = sequence[@pc]
        dispatch insn
      end
      @stack[0]
    end

    def dispatch insn
      case insn.code
      when :nop

      when :push
        push insn.opts[0]

      when :pop
        pop

      when :dup
        popped = pop
        push popped
        push popped

      when :add
        push pop + pop

      when :sub
        push pop - pop

      when :mul
        push pop * pop

      when :div
        push pop / pop

      when :not
        push !pop

      when :smaller
        push pop < pop

      when :bigger
        push pop > pop

      when :goto
        @pc = insn.opts[0].pos
        return

      when :if
        if pop
          @pc = insn.opts[0].pos
          return
        end

      else
        raise "Unknown Opcode: #{insn}"

      end

      @pc += 1
    end

    def push obj
      @stack.push obj
    end

    def pop
      @stack.pop
    end
  end

  class Parser
    def self.parse program
      pc     = 0
      labels = {}
      program.map{|line|
        p line
        line = line.strip
        insn = []

        if /\A:\w+\z/ =~ line
          label = $~[0].intern
          unless lobj = labels[label]
            lobj  = ::RubiMaVM::Label.new label
            labels[label] = lobj
          end
          next lobj
        end

        while line.size > 0
          case line
          when /\A:[a-z]+/
            # label
            label = $~[0].intern
            unless lobj = labels[label]
              lobj = ::RubiMaVM::Label.new label
              labels[label] = lobj
            end
            insn << lobj

          when /\A\s+/, /\A\#.*/
            # ignore

          when /\A[a-z]+/
            insn << $~[0].intern

          when /\A\d+/
            insn << $~[0].to_i

          else
            raise "Parse Error: #{line}"

          end
          line = $~.post_match
        end

        insn.size > 0 ? insn : nil
      }.compact.map{|insn|
        if insn.kind_of? ::RubiMaVM::Label
          insn.pos = pc
          nil
        else
          pc += 1
          ::RubiMaVM::Instruction.new insn[0], insn[1..-1]
        end
      }.compact
    end
  end
end


if $0 == __FILE__
  program = <<-EOP
    #
    push 1
  :label
    push 1
    add
    dup
    push 100000
    bigger
    if :label
  EOP

  parsed_program = RubiMaVM::Parser.parse program
  parsed_program.each_with_index{|insn, idx|
    puts "#{'%04d' % idx}\t#{insn.inspect}"
  }

  result = RubiMaVM::Evaluator.new.evaluate parsed_program
  puts result
end

解説

今回、RubiMaVM で実行しようとしているプログラムは program という変数に格納されています。この時点ではまだ文字列ですね。

何をするプログラムか見てみると、100000 になるまで数を足していっているだけですね。見ればなんとなくやっていることがわかると思います。簡単すぎますが、面倒だったのでこれで。

RubiMaVM の処理内容を見てみましょう。まず、パーサがプログラムを表現している文字列を命令列 (Symbol の列) にしています。各命令はオペランド (命令に渡す引数) を持っており、各命令は結局、命令とオペランドからなる配列として表現されています。

次に、VM 部分がこの命令列を尽きるまで実行します。ときどきプログラムカウンタを前に戻すことで繰り返しを実現しています。

さて、この RubiMaVM プログラムで一番大事なことですが、丸括弧の無い Ruby プログラムになっています。

宿題

RubiMaVM にはいくつか機能が足りません。そこで、ご自分で拡張してみてください。

メソッド呼び出し

今回のとても簡単な例ではメソッド呼び出し (まずは関数呼び出しか) に相当するものがありませんね。コレについての解説はしていませんでした。どうやるか、考えてみてください。ほかの VM、とくに一番資料が見つけやすい JavaVM でどうやっているか、どんな命令なのかを調べると参考になると思います。

実は、VM 自体は簡単なんですが、パーサ部分が面倒くさい気がします。

Ruby のメソッド呼び出し

VM から Ruby のメソッドを呼べるようにしてください。どんな命令になりますかね。

RubiMaVM で他のプログラムを作ってみる

今回は簡単な繰り返しプログラムしか書いてませんが、もうちょっと他のプログラムを書いてみるのも面白いかもしれません。その際、色々と機能不足に感じるところもあるかもしれませんが、そのときは VM を拡張してみてください。

おまけ:ベンチマーク

上記 RubiMaVM でプログラム (100000 回繰り返しプログラム) を動かしてみると、現在の Ruby と YARV で実行に要した時間はそれぞれ次のようになりました。

ruby  8.953000   0.020000   8.973000 (  9.100000)
yarv  3.164000   0.000000   3.164000 (  3.244000)

YARV は3倍くらい速いのがわかるかと思います。

おわりに

今回は VM についていろいろ書いてみました。VM という言葉は、言語処理系のためのソフトウェアという意味で使われる以上に、VMWare などのもっとローレベルな計算機の仮想化をさすことがあります。むしろ、一言 VM と言った場合、後者を指すことが多いように思います。VM に限ったことではないのですが、言葉の定義というのは背景などによって違うため、注意が必要です。本稿で解説した用語などもほかの解釈がありえるのでご注意ください (ただの間違いだったりして)。

VM を作っていると「凄いですねー」とか言われることも (ごくたまに) あるんですが、ここで説明したように、いたって基本は簡単です。もちろん、命令セットを考えるときには色々と考えることがあるのですが、たとえば Java の VM であれば仕様がすでにきちんと決まっているので、作るのは簡単です (それが使い物になるかどうかは別問題ですが)。

まぁ、VM というのはこんなに簡単なんだなぁ、と思っていただけるといいんじゃないかと思います。

次回は、うーん。何書こう。リクエストがあれば一番楽なんですが。いよいよ YARV のソースコードに踏み込むかなぁ。それとも、命令セットの紹介かなぁ。それとも RubiMaVM でもう少しひっぱるかなぁ。

どれだけの読者が居るかわかりませんが、お楽しみに。

参考文献

VM の歴史を紐解くにはいろんな文献がありますが、最近出た『IT Text コンパイラとバーチャルマシン』という本がわかりやすかったです。最初のほうは、ちょっと教科書っぽい (いや、教科書なんですが) ので読みづらいところもありましたが、うまくまとまってました。

ほかの VM は、Java についてはとりあえず『Java 仮想マシン仕様』という本が日本語として出ているのでわかりやすいです。英語でよいならウェブ上でも見れます (The JavaTM Virtual Machine Specification (Second Edition))。第 3 版のステータスはどうだったかな。何か出ていたような気がします。Java VM の解説としては「Java技術情報」が日本語でウェブサイトで読めるものとして詳細な解説があり、大変有用です。ほかには、私が以前書いた最高のジョークソフトウェア Rava / JavaVM on Ruby (2) (Ruby で書いた JavaVM) のソースと、これをネタに JavaPress 誌に書かせてもらった「Rava で見る仮想マシンのしくみ」 (Rava / JavaVM on Ruby : JAVA PRESS 誌の掲載原稿+サポートページ) があります (私が唯一書いたことがある一般雑誌記事ですね)。しかし今読むとなんというかとてもアレな記事だなぁ。というか、かなり駄目なことを書いている気がする orz。

Java 以外だと、.NET フレームワークの VM の仕様は ECMA の仕様としてみることができます (ECMA and ISO/IEC C# and Common Language Infrastructure Standards)。歴史的に重要な Smalltalk の VM の仕様 (バイトコードに BitBlt があるのかよ! などと突っ込みながら読める大変楽しい仕様) が読めます (Smalltalk-80: The Language and Its Implementation )。忘れちゃいけない Lisp の VM については、コレという読み物を知りません。あったら教えてください。論文をあさるとたくさん出てきます。

著者について

ささだ こういち。学生。スークリという職業ではない。

本稿はモスバーガーで書こうと思って店員さんに電源使ってもいいか聞いてからコンセントをさしてみたら、電源通ってなくてショボーン。タバコは煙いし、バッテリーはぜんぜんもたないし。まぁいいか。

*1 ありがたいのでテキストベースの図にしている。決して手抜きではない、はず