Cより速いRubyコンパイラって実際のところどうなの？

はじめに

　名古屋Ruby会議4に出られた人たちの中には、今作っているRubyコンパイラのmmcはCより速いのが最低条件です　とかいうとち狂った発言を聞いた方もいらっしゃるかもしれません。大部分は、華麗にスルーしたことでしょうが、これってどういう意味なんだろう？って思った方もいるのかもしれません。ここでは、私が作っているRubyコンパイラmmcのさわりを説明します。

概要

　mmcは

• 型プロファイリング
• エスケープ解析

の2つをフルに使うことで効率的なコードを生成することを目指します。現在の所Cに変換しますが、こんなコード絶対手では書きたくないというコードが出てきますので、 Cより速いと名乗っても良いのではないかと思います(もちろんそのコードが速ければですが)。

例えば、フィボナッチ級数はこんな感じのコードになります。

#include <mruby.h>
#include <mruby/value.h>
#include <mruby/array.h>
#include <mruby/throw.h>
#include <mruby/proc.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#undef mrb_int
typedef mrb_float mrb_float2;

#define mrb_float_value2(n) ({\
  mrb_value rc;               \
  rc.f = n;                   \
  rc;                         \
})

typedef void *gproc;
struct gctab {
  int size;
  int csize;
  int osize;
  struct gctab *prev;
  mrb_value **complex;
  mrb_value **object;
  mrb_value *single[0];
};

void mrb_mark_local(mrb_state *mrb)
{
  struct gctab *curtab = (struct gctab *)mrb->ud;
  while (curtab) {
    for (int i = curtab->size; i--;) {
      mrb_gc_mark(mrb, mrb_basic_ptr(*curtab->single[i]));
    }

    for (int i = curtab->osize; i--;) {
      mrb_gc_mark(mrb, mrb_basic_ptr(*curtab->object[i]));
    }

    for (int i = curtab->csize; i--;) {
      mrb_value *cptr = curtab->complex[i];
      for (int j = 0; cptr[j].value.ttt != MRB_TT_FREE; j++) {
        mrb_gc_mark(mrb, mrb_basic_ptr(cptr[j]));
      }
    }
    curtab = curtab->prev;
  }
}
struct env2 {
struct env1 *prev;
};
struct cls0_3 {
};
static mrb_int main_Object_0(mrb_state *, mrb_value self,struct gctab *);
static mrb_int fib__Object__1(mrb_state *, mrb_value self, mrb_float2 v109, mrb_value v110,struct gctab *);
static mrb_int fib__Object__2(mrb_state *, mrb_value self, mrb_float2 v109, mrb_value v110,struct gctab *);
int main(int argc, char **argv)
{
  mrb_state *mrb = mrb_open();
  struct mrb_jmpbuf c_jmp;

  MRB_TRY(&c_jmp) {
    mrb->jmp = &c_jmp;
    main_Object_0(mrb, mrb_top_self(mrb), NULL);
  }
  MRB_CATCH(&c_jmp) {
    mrb_p(mrb, mrb_obj_value(mrb->exc));
    return 1;
  }
  MRB_END_EXC(&c_jmp);

  return 0;
}
/*
Class Object
 Instance variables

 methodes 
  fib: (Object val=#<Object:0x2009b0f0> e=false, Float val=42 e=false, NilClass e=false) -> Fixnum e=false 
  fib: (Object val=#<Object:0x2009b0f0> e=false, Float e=false, NilClass e=false) -> Fixnum e=false 

*/
static mrb_int main_Object_0(mrb_state *mrb, mrb_value self, struct gctab *prevgctab) {
mrb_int v15;
struct gctab *gctab = prevgctab;
L0:; 
v15 = fib__Object__1(mrb, self, 42, mrb_nil_value(), gctab);
return v15;
}
static mrb_int fib__Object__1(mrb_state *mrb, mrb_value self, mrb_float2 v109, mrb_value v110, struct gctab *prevgctab) {
struct env2 env;
struct REnv *venv = NULL;
mrb_int v166;
mrb_int v152;
mrb_int v159;
struct gctab *gctab = prevgctab;
L7:; 
if ((42 < 2)) goto L8; else goto L9;
L8:; 
v166 = 1;
L10:; 
return v166;
L9:; 
v152 = fib__Object__2(mrb, self, (42 - 1), mrb_nil_value(), gctab);
v159 = fib__Object__2(mrb, self, (42 - 2), mrb_nil_value(), gctab);
v166 = (v152 + v159);
goto L10;
}
static mrb_int fib__Object__2(mrb_state *mrb, mrb_value self, mrb_float2 v109, mrb_value v110, struct gctab *prevgctab) {
struct env2 env;
struct REnv *venv = NULL;
mrb_int v166;
mrb_int v152;
mrb_int v159;
struct gctab *gctab = prevgctab;
L7:; 
if ((v109 < ((mrb_float)2))) goto L8; else goto L9;
L8:; 
v166 = 1;
L10:; 
return v166;
L9:; 
v152 = fib__Object__2(mrb, self, (v109 - 1), mrb_nil_value(), gctab);
v159 = fib__Object__2(mrb, self, (v109 - 2), mrb_nil_value(), gctab);
v166 = (v152 + v159);
goto L10;
}

if文がgotoで飛んでるとか不自然なところはありますが、不必要なBOXING/UNBOXINGの変換がなく素直にintによる計算がおこなわれていることが分かると思います(mrb_intはintのalias)。

GCやProcオブジェクト

Rubyが遅いのは伊達ではなく、それなりに理由があります。いろいろあるのですが比較的単純なプログラムでも遭遇する原因としてGCとProcオブジェクトがあります。これらをどう高速化しているかを見てみます。

GC

CRubyでは保守的GCなのでレジスタなりスタックにオブジェクトを突っ込んでおけばとりあえずGCからオブジェクトを保護できます。でも、そのたまにCRunyが払うコストはちょっとしたものになります。mrubyは正確なGCを採用しててスタックやレジスタもスキャンするような気のきいたことはしてくれません。
mmcではレジスタ(VMの)がこの先アクセスされるのか(生存しているのか)やレジスタの型や今のメソッドの外にエスケープするかなどの情報が静的に得ることができます(SSAのおかげです)。この機能を使ってGCのルートをプログラムのコードで生成することができます。

GCに関係するオブジェクトを扱うCの関数でには次のようなコードが生成されます。先ほどのフィボナッチの例では扱うのは整数と浮動小数点数のみなのでこのようなコードは生成されません。

struct gctab *gctab = (struct gctab *)alloca(sizeof(struct gctab) + 1 * sizeof(mrb_value *));
gctab->prev = prevgctab;
gctab->complex = NULL;
gctab->object = NULL;
gctab->size = 0;
gctab->csize = 0;
gctab->osize = 0;

これがGCの対象になるオブジェクトがスタックやレジスタにある場合、GCが発生する可能性のあるメソッドを実行する場合に退避しておくための領域です。これをスタック上に取ります。

struct gctab {
  int size;
  int csize;
  int osize;
  struct gctab *prev;
  mrb_value **complex;
  mrb_value **object;
  mrb_value *single[0];
};

この領域はこんな感じの構造になています。prevはcallerのgctabでprevにはいる値は引数で渡ってきます。
singleは単一のオブジェクトでどれだけはいってるかはsizeで表します
complexは配列に対するエントリーです。ここでいう配列はmrubyのArrayオブジェクトではなくArrayオブジェクトのunbox表現の単なるCの配列です。singleに要素毎に格納することもできますが遅いので配列の先頭のポインタで一気に格納できます。配列の要素はTT_FREE型のオブジェクトが来ます。csizeが格納されているオブジェクトの数です。
objectはスタックアロケートしたオブジェクトが持つインスタンス変数の内容を格納するためのものです。osizeがその要素の数です。

オブジェクトをアロケートしたりオブジェクトを返すメソッドを読んだときはこのgctabを更新します。gctabの内容はコンパイル時に把握しているので1から構築することはなく、変更のあった所だけが更新されます。更新の例です。

mrb->ud = (void *)gctab;
v5967 = mrb_ary_new_capa(mrb, 3);
for (int i = 0;i < 3; i++) ARY_PTR(mrb_ary_ptr(v5967))[i] = mrb_nil_value();
ARY_SET_LEN(mrb_ary_ptr(v5967), 3);
initialize__Vec__15(mrb, v5967, 0, 0, 0, mrb_nil_value(), gctab);
mrb_gc_arena_restore(mrb, ai);
gctab->single[1] = &v5967;
gctab->size = 2;

mrubyのGCに次のようなマーク処理を加えます。なお、gctabはmrb_obj_alloc等GCを起動する関数を呼ぶ直前にmrb->udに入れておきます。

void mrb_mark_local(mrb_state *mrb)
{
  struct gctab *curtab = (struct gctab *)mrb->ud;
  while (curtab) {
    for (int i = curtab->size; i--;) {
      mrb_gc_mark(mrb, mrb_basic_ptr(*curtab->single[i]));
    }

    for (int i = curtab->osize; i--;) {
      mrb_gc_mark(mrb, mrb_basic_ptr(*curtab->object[i]));
    }

    for (int i = curtab->csize; i--;) {
      mrb_value *cptr = curtab->complex[i];
      for (int j = 0; cptr[j].value.ttt != MRB_TT_FREE; j++) {
        mrb_gc_mark(mrb, mrb_basic_ptr(cptr[j]));
      }
    }
    curtab = curtab->prev;
  }
}

Procオブジェクト

Procオブジェクトの構造

rubyではeachメソッドをはじめとするイテレータなどProcオブジェクトをこれでもかと大量に使います。Procオブジェクトも生成には動的にオブジェクトをアロケートする必要があり、ナイーブな実装では速くなるわけがないわけです。CRubyなど良く使うイテレータなどのパターンでProcオブジェクトを生成しないように特別扱いする処理がなされており、これがCRubyとmrubyの速度の差の主原因であるとわたしは考えています。
とうぜん、mmcでもProcオブジェクトを何とかする必要がありますが、CRubyとは違うアプローチ　すなわちエスケープしないProcオブジェクトはスタックアロケーションする方針で高速化します。この方法とCコンパイラのinline　function最適化でほぼオーバーヘッド無しでイテレータを使うことができます。

Procオブジェクトの構造の一例です。

struct proc22 {
int id;
void *code[2];
struct env18 *env;
struct cls1_74 * self;
};

idはprocオブジェクトの番号です。ある変数に複数の種類のProcオブジェクトを入れてcallするとか良くあるのでどのProcなのかを知るためにあります。

codeはprocのプログラムコードのアドレスです。配列なのはTUPによって違うコードになるからです。TUPとは引数の型の組に番号を付けた物です。詳しくは(あまり詳しくないけど)　名古屋Ruby会議の発表スライド とか型推定部の資料を見てください。ただ、後述するようにこのメンバーのアドレスはほとんど使いません。ある変数に1種類のProcオブジェクトが入ることが確定していれば直接その関数を呼び出すコードを生成します。その関数はstatic宣言されているので多くの場合インライン化されることが期待できます。

Procオブジェクトの持つ環境はProcオブジェクトによって違います。動的型付けなら型タグやメンバーの数を保持することにより同一の型として扱うことができますが、C言語の型にきっちり合わせるためにはProcオブジェクトは全て別の型として取り扱う必要があります。
struct env18の型を示します。

struct env18 {
mrb_int v5788;
struct env17 *prev;
};

env18にはmrb_int型のv5788という変数とproc22が作られた外側の環境へのポインタprev(struct env17型)、の2つのメンバをもちます。

このようにクロージャはCレベルでコンパイル時に型が決まる構造なので構造体のアクセスと同じコストでクロージャ内の変数をアクセスする事が出来ます。

実際のコードを示してみます。

Procオブジェクトの呼び出し

これまで説明したとおり、mmcのProcオブジェクトは実質、スタック上の単なる構造体です。そして、実際のProcオブジェクトは現在実行中の変数を参照したり変更したりできます。このギャップはProcオブジェクトを呼び出すときのコード生成で埋めています。

class Array
  def each0(&block)
    i = self.length
    while i > 0
      block.call self[i]
      i = i - 1
    end
  end
end

def foo
  i = 0
  [1,2,3].each0 do |j|
    i = i + j
  end
  nil
end

MTypeInf::inference_main {
  foo
}

こんなコードのfooのメソッドをCに変換した例を示します。

static mrb_value foo__Object__1(mrb_state *mrb, mrb_value self, mrb_value v83, struct gctab *prevgctab) {
struct env2 env;
struct REnv *venv = NULL;
mrb_int v93;
mrb_value v117;
struct gctab *gctab = prevgctab;
L5:; 
v93 = 0;
env.v93 = v93;
mrb_int v97[4] = {
1, 2, 3};
struct proc3 v98;
v98.id = 3;
v98.self = self;
v98.env = &env;
v117 = each0__Array__2(mrb, v97, ((gproc)&v98), gctab);
v93 = env.v93;
return mrb_nil_value();
}

ちょっと長くて分かりづらいのですが、

env.v93 = v93;

と

v93 = env.v93;

の部分を見てもらうと言いたいことが理解できるのではないかと思います。つまり、いちいちenvのメンバーから実際のローカル変数に代入文を生成しているのです。あるprocオブジェクトは実際にはどのローカル変数を参照しているのか、また変更しているのかは静的に解析出来ますので、こういったコードが生成できるのです。

オブジェクトのスタック割り付け

これまでの話でまあそこそこ速いものができますが、GCやselfを受け渡すオーバヘッドもありますし、配列や文字列の機能がリッチなので生成コストが高いと言った問題があります。つまりこのままではCより速いとは名乗れないです。GCやselfの受け渡しはRubyがRubyであるためには何ともならないですが、リッチなデータ構造は必要に応じてプアにできる可能性があります。その為の道具として重要になるのがエスケープ解析(とこれまでも説明した型解析)です。

エスケープ解析

エスケープ解析とは有るオブジェクトが現在実行中のメソッド(正確にはブロック)の終了後にもアクセスされる可能性があるかを判定する処理です。もし、アクセスされなければ、そのオブジェクトはスタックに割りつけたり型を表すタグをつけなくてもよかったりと何かと効率の良いコードを作ることができます。ただ、Rubyでは色々な場所にオブジェクトを格納できるのでエスケープ解析もそれなりに大変です。

mmcでは型そのものに対してそれを表現するオブジェクトを用意しています。これを型オブジェクトと呼びます。型オブジェクトはRubyレベルのクラスや要素の型(配列やハッシュテーブルの場合)などがあります。この型オブジェクトにどこに格納されたことがあるかを示す@placeというインスタンス変数をもっています。@placeはハッシュテーブルでkeyが格納場所を表すオブジェクト、valueが格納した命令情報(デバッグ用)です。valueは使っていないのですが効率よく更新するためにハッシュテーブルを使っています。
keyは次のような意味をもちます

key	説明
true	グローバル変数や定数など絶対にエスケープするもの
ContainerType	配列やハッシュテーブル
ProcType	Procオブジェクトの環境
UserDefinedType	インスタンス変数
:return(シンボル)	メソッドの戻り値

これらの情報を抽象実行により集めてコード生成時にエスケープするか解析します。

実際にエスケープするか判定するコードはこんな感じです

    def is_escape?
      if !is_gcobject? then
        return false
      end

      if @escape_cache then
        return true
      end
      plist = @place
      if plist.size == 0 then
        return false
      end

      plist.any? {|e, val|
        case e
        when :return
          @escape_cache = is_gcobject?

        when ProcType,
          UserDefinedType,
          ContainerType
          @escape_cache = e.is_escape?

        else
          # true ... etc
          @escape_cache = true
        end
      }
    end

こんな面倒くさいことをするのは、例えばオブジェクトのインスタンス変数に格納されたとしても、そのオブジェクトがメソッドからエスケープしなければエスケープしないわけで全体のデータの流れを見ないとエスケープするかどうかの判断ができないためです。
ご想像のとおり、エスケープするかどうかの判断はかなり重い処理です。キャッシュを用いるなど工夫はしていますが限界があります。

配列のスタック割り付け

Rubyではeachとかmapとか多用する傾向があるので比較的ローカルな配列を作る傾向がありそうです(要出典)。配列はエスケープしなければ、スタック上にアロケート出来ます。
例えば、こんな感じのプログラムを考えてみましょう。

def foo
  t = 0
  [1, 2, 3].each do |i|
   t += i
  end
  t
end

MTypeInf::inference_main {
foo
}

これの、fooメソッドはこんな感じでCに変換されます。

static mrb_int foo__Object__1(mrb_state *mrb, mrb_value self, mrb_value v78, struct gctab *prevgctab) {
struct env2 env;
struct REnv *venv = NULL;
mrb_int v88;
mrb_int *v112;
struct gctab *gctab = prevgctab;
L5:; 
v88 = 0;
env.v88 = v88;
mrb_int v92[4] = {
1, 2, 3};
struct proc3 v93;
v93.id = 3;
v93.self = self;
v93.env = &env;
v112 = each__Array__2(mrb, v92, ((gproc)&v93), gctab);
v88 = env.v88;
return v88;
}

一方、こんな感じで配列をエスケープさせてみましょう。Array#eachはselfを返すので、eachで終わると配列はメソッドの外にエスケープします。

def foo
  t = 0
  [1, 2, 3].each do |i|
   t += i
  end
end

MTypeInf::inference_main {
foo
}

これをCに変換するとこんな感じになります。

static mrb_value foo__Object__1(mrb_state *mrb, mrb_value self, mrb_value v78, struct gctab *prevgctab) {
struct env2 env;
struct REnv *venv = NULL;
mrb_int v88;
mrb_value v92;
mrb_value v112;
int ai = mrb_gc_arena_save(mrb);
struct gctab *gctab = prevgctab;
L5:; 
v88 = 0;
env.v88 = v88;
{
mrb_value tmpele[] = {
(mrb_fixnum_value(1)), (mrb_fixnum_value(2)), (mrb_fixnum_value(3))
};
mrb->ud = (void *)gctab;
v92 = mrb_ary_new_from_values(mrb, 3, tmpele);
ARY_SET_LEN(mrb_ary_ptr(v92), 3);
mrb_gc_arena_restore(mrb, ai);
}
struct proc3 v93;
v93.id = 3;
v93.self = self;
v93.env = &env;
v112 = each__Array__2(mrb, v92, ((gproc)&v93), gctab);
v88 = env.v88;
return v112;
}

このように、エスケープする配列はヒープにアロケートされていることがわかります。
配列については、レンジチェックしていないとか負のindexを渡す場合がサポートしていない(しようとすると速度が落ちる)などの問題点があります。これは、次世代のType Profilerで解決したいと思っています。

オブジェクトのスタック割り付け

さて、ここまではうまくいった話なんですが、これからはうまくいっていない話です。配列と同じような考え方でオブジェクトもスタックに割りつけたいと当然考えます。mmcではインスタンス変数のオブジェクト上の位置が静的に決定できるので、mrubyのRObjectのような大掛かりな構造は必要なく単なる配列でよいのです。ですので一見簡単だと思いました。
しかし、要素の型がほぼ均一の配列と違い、インスタンス変数は変数ごとに型も使い方も大きく異なる場合があります。そして、同じクラスのオブジェクトでも使う場所によってエスケープするかしないかは異なる場合は普通にあります。それは、インスタンス変数に入っているオブジェクトも同じです。
このようなことから、同じクラスのオブジェクトであっても、インスタンス変数の型の組み合わせが膨大になってしまいます。実際aobenchで試したところ組み合わせでたくさんの構造体が定義されてしまいました。インスタンス変数に入るオブジェクトはヒープに取るとすれば
いいのですが、そうするとほとんどオブジェクトはスタックに割り当てられません。
この辺は今良いアイデアがあるか思案中です。

結論

おちこんだりするけどわたしは元気です