Hatena::ブログ(Diary)

miura1729の日記 このページをアンテナに追加 RSSフィード

2014-04-16

あなとみー おぶ mrubyのJIT (その13)

18:42 |  あなとみー おぶ mrubyのJIT (その13)を含むブックマーク  あなとみー おぶ mrubyのJIT (その13)のブックマークコメント

お久しぶりです。ずいぶんと更新をさぼっていたのですが、ときどきバグるけどmrubyのJITは元気です。さて、この半年、mrubyのJITもいろいろいじっていたのですが、多くの変更が 力技 | 黒魔術 って感じでエレガントな記事を望む皆様にはふさわしくないような気もしました。そこで、コミットログをあさってみたら、型推論もどきでガードを消しちゃうよというネタがちょっとアカデミックで良いのではないかと思って書いてみます。

型を格納する構造体

mrubyのJITでは各RITE VMの命令ごとにいろんなコンパイルネイティブコードの実行に使う情報を格納するmrbjit_code_infoという構造体を用意しています。*1この構造体はこんな感じの定義です。

typedef struct mrbjit_code_info {
  mrbjit_code_area code_base;
  mrb_code *prev_pc;
  struct mrbjit_code_info *prev_coi;
  mrb_code *caller_pc;
  void *(*entry)();
  mrbjit_reginfo *reginfo;	/* For Local assignment */
  int used;
} mrbjit_code_info;

この中のreginfo構造体がRITE VMレジスタの型情報を格納します。RITE VMレジスタはどんな型のデータも自由に格納できるので、あくまでこの情報はその命令を実行した時点の情報です。レジスタは複数あるのでポインタ型になっていて配列として用意します。

reginfo構造体の中身はこんな感じです。

typedef struct mrbjit_reginfo {
  enum mrb_vtype type;     /* 型 */
  struct RClass *klass;    /* クラス */
  int constp;              /* 定数か? */
} mrbjit_reginfo;

constpだけはなんだこりゃ?と思うかもしれないですね。文字通り値が決定している場合にnon-0になります。その値は?と思われるかもしれませんが、RITE VMレジスタから取ってくればいいです。なにせ定数ですから。定数のたたみこみとか出来そうで夢が広がりそうですね。まだ定数のたたみこみサポートしてないですが。

こんな感じでレジスタの型情報を入れる入れ物を用意します。では、次に型情報を書き込み所を見てみましょう。

レジスタの型情報の書き込み

まず簡単なところで、シンボルを書き込みLOADSYM命令をコンパイルするコードを見てみましょう。

  const void *
    emit_loadsym(mrb_state *mrb, mrbjit_vmstatus *status, mrbjit_code_info *coi) 
  {
    const void *code = getCurr();
    mrb_code **ppc = status->pc;
    mrb_irep *irep = *status->irep;
    const Xbyak::uint32 dstoff = GETARG_A(**ppc) * sizeof(mrb_value);
    int srcoff = GETARG_Bx(**ppc);
    const Xbyak::uint32 src = (Xbyak::uint32)irep->syms[srcoff];
    mrbjit_reginfo *dinfo = &coi->reginfo[GETARG_A(**ppc)];  /* 書き込みレジスタの型情報 */
    dinfo->type = MRB_TT_SYMBOL;               /* もちろんシンボル型 */
    dinfo->klass = mrb->symbol_class;                        /* Symbol class */
    dinfo->constp = 1;                                       /* シンボル番号命令にあるので定数 */

    mov(dword [ecx + dstoff], src);
    mov(dword [ecx + dstoff + 4], 0xfff00000 | MRB_TT_SYMBOL);

    return code;
  }

ここで、dinfoが書き込みレジスタの型情報です。シンボルを格納する命令だからシンボル型になる。単純な話です。

こんな感じで、書き込んだ型情報は次の命令を実行するときに基本的には引き継がれます。引き継ぐコードはこんな感じ。vm.cのmrbjit_dispatchにあります。

    if (ci->prev_coi && ci->prev_coi->reginfo) {
   /* 前回実行した命令にレジスタ情報がある場合 */
      mrbjit_reginfo *prev_rinfo;
      prev_rinfo = ci->prev_coi->reginfo;
      for (i = 0; i < irep->nregs; i++) {
	ci->reginfo[i] = prev_rinfo[i];
      }
    }
    else {
      /* ない場合 */
      for (i = 0; i < irep->nregs; i++) {
	ci->reginfo[i].type = MRB_TT_FREE;
	ci->reginfo[i].klass = NULL;
	ci->reginfo[i].constp = 0;
      }
    }

こんな感じで作った型情報をどう使うのか? ちょっと疲れたので中断

ご飯食べてた、続き、

ガード

Tracing JITでは型チェックや分岐命令などでガードが大活躍します。ガードとは、想定した型や値になっているかチェックする仕組みでmrubyのJITでは想定と違った場合はVMに戻ります。ここで、もし型がコンパイル時に分かった場合はガードを省くことができるわけです。まず、レジスタが想定した型になっているかチェックするコードを生成する、gen_type_guardを見ています。

  void 
    gen_type_guard(mrb_state *mrb, int regpos, mrbjit_vmstatus *status, mrb_code *pc, mrbjit_code_info *coi)
  {
    enum mrb_vtype tt = (enum mrb_vtype) mrb_type((*status->regs)[regpos]);
    mrbjit_reginfo *rinfo = &coi->reginfo[regpos];

    if (rinfo->type == tt) {
      return;
    }

    mov(eax, dword [ecx + regpos * sizeof(mrb_value) + 4]); /* Get type tag */
    rinfo->type = tt;
    rinfo->klass = mrb_class(mrb, (*status->regs)[regpos]);
    /* Input eax for type tag */
    if (tt == MRB_TT_FLOAT) {
      cmp(eax, 0xfff00000);
      jb("@f");
    } 
    else {
      cmp(eax, 0xfff00000 | tt);
      jz("@f");
    }

    /* Guard fail exit code */
    gen_exit(pc, 1, 0, status);

    L("@@");
  }

ここで、

    mrbjit_reginfo *rinfo = &coi->reginfo[regpos];

    if (rinfo->type == tt) {
      return;
    }

が静的に分かっている型と想定している型が同じかどうかのチェックです。同じだった場合はガードを生成する必要が無いので戻ります。

また、ガードが通った場合はこの先想定した型であることが保障されるので、レジスタの型情報も行進しておきます。こうすることで、同じ値を何度もガードでチェックすることが避けられます。

    rinfo->type = tt;
    rinfo->klass = mrb_class(mrb, (*status->regs)[regpos]);

同様にレジスタが想定したクラスかどうかチェックするgen_class_guardも静的なレジスタの型情報でガードが減らせます。

  void 
    gen_class_guard(mrb_state *mrb, int regpos, mrbjit_vmstatus *status, mrb_code *pc, mrbjit_code_info *coi, struct RClass *c)
  {
    enum mrb_vtype tt;
    mrb_value v = (*status->regs)[regpos];
    mrbjit_reginfo *rinfo = &coi->reginfo[regpos];

    tt = (enum mrb_vtype)mrb_type(v);

    if (rinfo->type != tt) {

      rinfo->type = tt;

      mov(eax, ptr [ecx + regpos * sizeof(mrb_value) + 4]);

      if (tt == MRB_TT_FLOAT) {
	cmp(eax, 0xfff00000);
	jb("@f");
      }
      else {
	cmp(eax, 0xfff00000 | tt);
	jz("@f");
      }

      /* Guard fail exit code */
      gen_exit(pc, 1, 0, status);

      L("@@");
    }

    /* Import from class.h */
    switch (tt) {
    case MRB_TT_FALSE:
    case MRB_TT_TRUE:
    case MRB_TT_SYMBOL:
    case MRB_TT_FIXNUM:
    case MRB_TT_FLOAT:
      /* DO NOTHING */ /* クラスオブジェクトは分かり切っているので比較はしない */
      break;

    default:  /* クラスオブジェクトのチェック */
      {
	if (c == NULL) {
	  c = mrb_object(v)->c;
	}
	if (rinfo->klass == c) {
	  return;
	}
	rinfo->klass = c;
	mov(eax, dword [ecx + regpos * sizeof(mrb_value)]);
	mov(eax, dword [eax + OffsetOf(struct RBasic, c)]);
	cmp(eax, (int)c);
	jz("@f");
	/* Guard fail exit code */
	gen_exit(pc, 1, 0, status);

	L("@@");
      }
      break;
    }
  }

また、定数かどうかを示すconstpを使うことで、条件分岐命令使うレジスタが想定しているbool値になっているかチェックするgen_bool_guardで条件判定の削除が実現できます。

  void
    gen_bool_guard(mrb_state *mrb, int b, mrb_code *pc, 
		   mrbjit_vmstatus *status, mrbjit_reginfo *rinfo)
  {
    if (rinfo->constp) {  /* 定数だった場合 */
      if (b && rinfo->type != MRB_TT_FALSE) {  /* 真と予想して、そうだった場合 */
	return;
      }
      if (!b && rinfo->type == MRB_TT_FALSE) {  /* 偽と予想して、そうだった場合 */
	return;
      }
    }

    cmp(eax, 0xfff00001);
    if (b) {
      jnz("@f");
    } 
    else {
      jz("@f");
    }

    /* Guard fail exit code */
    gen_exit(pc, 1, 0, status);

    L("@@");
  }

こんな感じです。それではまた、ごきげんよう。

*1:正確には直前に実行した命令が異なれば別の構造体を割り当てています。これが、型推論を簡単にする秘訣になっています

2013-09-29

あなとみー おぶ mrubyのJIT (その12)

09:26 |  あなとみー おぶ mrubyのJIT (その12)を含むブックマーク  あなとみー おぶ mrubyのJIT (その12)のブックマークコメント

今回はオブジェクト作成のメソッドnewのインライン化のお話です。newのインライン化はそれほど規模が大きくないのですが、mrubyのJITの大きな転換点になっています。

前回取り組んだytljitがRuby型推論(ブロックや要素ごとに違う型が格納できる配列などを含む)やオブジェクトのスタック割り付けなどを行って複雑すぎて手に負えなくなっちゃったことがありました。その反省を踏まえて、できるだけオーソドックスに分かりやすく気を使っていました(結果どうなったかは知らない)。

ところが、aoベンチでオブジェクトの生成がボトルネックっぽいと分かったことでnewをインライン化を初めて、検討の結果またも悪魔に魂を売り渡してしまいました。その、技法とは「バイトコードの書き換え」です。

newの難しいところはオブジェクトを生成した後、initilaizeメソッドを呼ばないといけないところです。簡単じゃないかと思われるかもしれませんが、mrubyではnewでのinitilizeメソッドはmrb_run直接ではなく、vm.cで定義されているmrb_funcall_with_block経由で呼ばれます(結局mrb_runで実行されるのですが)。そうすると、詳しい理由は避けますがJITコンパイルはうまくいきません。そういうことで、newをコンパイルしてその機械語を実行するときinitizlzeメソッド機械語コードが生成されていないのです。mrb_funcall_with_blockを呼び出してインタープリタでinitilizeメソッドを実行してもいいのですが、それでは面白くないです。

いろいろ考えて、newをmrb_instance_allocで得た初期化していないオブジェクトレシーバーにしてinitializeメソッドを呼び出す動作にコンパイルしたらどうだろうと考えました。このようにすることで、initalizeはmrb_funcall_with_block経由ではなく、mrb_run直接実行になります。前述のとおり、initializeメソッド機械語が生成されていないので、メソッド呼び出しのためのcallinfoを構築したら、即座にVMに戻るコードを生成するようにしました。

これで、基本的にうまくいったのですが1つ問題があります。newメソッドは生成したオブジェクトを返すのですが、initializeメソッドは生成したオブジェクト(initializeメソッドのself)を返すとは限らないことです。initializeメソッドから戻ったところで改めて生成したオブジェクトを返すようにすればいいのですが、そうするとinitializeメソッドを呼びっぱなしにできないのでcallinfo構築にコストがかかります。要は必ずinitializeメソッドで必ずselfを返してくれればいいのです。

戻り値を返すVMの命令はOP_RETURNなわけですが、

  OP_RETURN    R0

とすると現在のmrubyでは必ずselfを返します。つまり、OP_RETURNのAオペランドを0クリアすればよいのです。initializeメソッド戻り値は使われることがないので副作用もありません。簡単に実装できて効果のあり、被害も少なそう、な命令書き換えをやらない手があるだろうか? ということで命令書き換えで実装しました。

コードを見てみましょう

mrb_value
MRBJitCode::mrbjit_prim_instance_new_impl(mrb_state *mrb, mrb_value proc,
					  mrbjit_vmstatus *status, mrbjit_code_info *coi)
{
  mrb_value *regs = *status->regs;
  mrb_irep *irep = *status->irep;
  mrb_code *pc = *status->pc;
  int i = *pc;
  int a = GETARG_A(i);
  int nargs = GETARG_C(i);

  struct RProc *m;
  mrb_value klass = regs[a];
  struct RClass *c = mrb_class_ptr(klass);

  m = mrb_method_search_vm(mrb, &c, mrb_intern(mrb, "initialize"));

  // TODO add guard of class
  
  // obj = mrbjit_instance_alloc(mrb, klass);
  push(ecx);
  push(ebx);
  mov(eax, *((Xbyak::uint32 *)(&klass) + 1));
  push(eax);
  mov(eax, *((Xbyak::uint32 *)(&klass)));
  push(eax);
  push(esi);
  call((void *)mrbjit_instance_alloc);
  add(esp, 3 * sizeof(void *));
  pop(ebx);
  pop(ecx);

  // regs[a] = obj;
  mov(ptr [ecx + a * sizeof(mrb_value)], eax);
  mov(ptr [ecx + a * sizeof(mrb_value) + 4], edx);

  if (MRB_PROC_CFUNC_P(m)) {
    CALL_CFUNC_BEGIN;
    mov(eax, (Xbyak::uint32)c);
    push(eax);
    mov(eax, (Xbyak::uint32)m);
    push(eax);
    CALL_CFUNC_STATUS(mrbjit_exec_send_c, 2);
  }
  else {
    /* patch initialize method */
    mrb_irep *pirep = m->body.irep;
    mrb_code *piseq = pirep->iseq;
    for (int i = 0; i < pirep->ilen; i++) {
      if (GET_OPCODE(piseq[i]) == OP_RETURN) {
	/* clear A argument (return self always) */
	piseq[i] &= ((1 << 23) - 1);
      }
    }
    
    /* call info setup */
    CALL_CFUNC_BEGIN;
    mov(eax, (Xbyak::uint32)c);
    push(eax);
    mov(eax, (Xbyak::uint32)m);
    push(eax);
    CALL_CFUNC_STATUS(mrbjit_exec_send_mruby, 2);

    mov(eax, dword [ebx + OffsetOf(mrbjit_vmstatus, regs)]);
    mov(ecx, dword [eax]);

    gen_set_jit_entry(mrb, pc, coi, irep);

    gen_exit(m->body.irep->iseq, 1, 0);
  }

  return mrb_true_value();
}

細かく見てみます。

  // obj = mrbjit_instance_alloc(mrb, klass);
  push(ecx);
  push(ebx);
  mov(eax, *((Xbyak::uint32 *)(&klass) + 1));
  push(eax);
  mov(eax, *((Xbyak::uint32 *)(&klass)));
  push(eax);
  push(esi);
  call((void *)mrbjit_instance_alloc);
  add(esp, 3 * sizeof(void *));
  pop(ebx);
  pop(ecx);

  // regs[a] = obj;
  mov(ptr [ecx + a * sizeof(mrb_value)], eax);
  mov(ptr [ecx + a * sizeof(mrb_value) + 4], edx);

初期化していないオブジェクトの生成です。コメントのCのコードのほぼ直訳です。

  if (MRB_PROC_CFUNC_P(m)) {
    CALL_CFUNC_BEGIN;
    mov(eax, (Xbyak::uint32)c);
    push(eax);
    mov(eax, (Xbyak::uint32)m);
    push(eax);
    CALL_CFUNC_STATUS(mrbjit_exec_send_c, 2);
  }
  else {

mにはinitializeのProcオブジェクトが入っています。mがC関数だった場合の処理です。ここを通ることは意外と少ないです。配列とかもmrubyでinitializeが定義されていますし。

    /* patch initialize method */
    mrb_irep *pirep = m->body.irep;
    mrb_code *piseq = pirep->iseq;
    for (int i = 0; i < pirep->ilen; i++) {
      if (GET_OPCODE(piseq[i]) == OP_RETURN) {
	/* clear A argument (return self always) */
	piseq[i] &= ((1 << 23) - 1);
      }
    }
    

initializeがmrubyで定義されている場合の処理です。ここで、命令書き換えをやっています。

    /* call info setup */
    CALL_CFUNC_BEGIN;
    mov(eax, (Xbyak::uint32)c);
    push(eax);
    mov(eax, (Xbyak::uint32)m);
    push(eax);
    CALL_CFUNC_STATUS(mrbjit_exec_send_mruby, 2);

    mov(eax, dword [ebx + OffsetOf(mrbjit_vmstatus, regs)]);
    mov(ecx, dword [eax]);

    gen_set_jit_entry(mrb, pc, coi, irep);

次にmrubyのメソッドを呼び出すcallinfoの構築です。説明はとても面倒なので省略します。

    gen_exit(m->body.irep->iseq, 1, 0);

最後にVMに戻ります。

泥臭い話が続きますが、次回も多分泥臭いです。コンパイラは開発が進むと泥臭くなるもののようです。

2013-08-17

あなとみー おぶ mrubyのJIT (その11)

15:07 |  あなとみー おぶ mrubyのJIT (その11)を含むブックマーク  あなとみー おぶ mrubyのJIT (その11)のブックマークコメント

とってもお久しぶりです。ずいぶん間が空いてしまいましたが、新たな機能のプリミティブのインライン化が実装できたので再開したいと思います。あなとみー おぶ mrubyのJIT の開始当時オリジナルmrubyの数割速いとか遅くなるとか言っていましたが、現在大体のベンチマークでmrubyの2〜4倍の速度が出ます。その秘密が今回紹介するプリミティブのインライン化です。

Rubyはかなり基本的な機能もすべてメソッド呼び出しで実装されています。これは、必要に応じて動作をカスタマイズしたりして柔軟性をもたらしますが、速度的には大きなハンディになります。とくに、mrubyはメソッド呼び出しのオーバーヘッドが大きいので問題になります。

そこで、mrubyのJITでは良く使うメソッドについてはインライン化して速度を稼ぐようにしました。

 インライン化を支えるコード

具体的なコードを見てみましょう。

これは、array.cの[]メソッドの定義ですが、こんな感じでプリミティブとしてインライン化したいメソッドを登録します。

  mrb_define_method(mrb, a, "[]",              mrb_ary_aget,         MRB_ARGS_ANY());  /* 15.2.12.5.4  */
  mrbjit_define_primitive(mrb, a, "[]", mrbjit_prim_ary_aget);

こうすると、JITコンパイル時に、mrbjit_prim_ary_agetを呼び出してインライン化するようになります。

mrbjit_define_primitiveの定義です。class.cにあります。

void
mrbjit_define_primitive_id(mrb_state *mrb, struct RClass *c, mrb_sym mid, mrb_func_t func)
{
  struct RProc *p;
  int ai = mrb_gc_arena_save(mrb);

  p = mrb_proc_new_cfunc(mrb, func);
  p->target_class = c;
  mrb_obj_iv_set(mrb, (struct RObject*)c, mid, mrb_obj_value(p));
  mrb_gc_arena_restore(mrb, ai);
}

void
mrbjit_define_primitive(mrb_state *mrb, struct RClass *c, const char *name, mrb_func_t func)
{
  mrbjit_define_primitive_id(mrb, c, mrb_intern(mrb, name), func);
}  

コードを見てわかるとおり、インスタンス変数領域にインライン化の関数をProcオブジェクトとして格納します。インスタンス変数は@, @@で普通始まるので通常のインスタンス変数とは衝突しません。まれに特殊目的で@,@@で始まらない変数を登録する場合もありますので注意が必要です。

実際にインライン化する場所を見てみましょう。jitcode.hのemit_sendです。

    if (MRB_PROC_CFUNC_P(m)) {
      prim = mrb_obj_iv_get(mrb, (struct RObject *)c, mid);
      mrb->vmstatus = status;
      if (mrb_type(prim) == MRB_TT_PROC) {
	mrb_value res = mrb_proc_ptr(prim)->body.func(mrb, prim);
	if (!mrb_nil_p(res)) {
	  return code;
	}
      }

      //puts(mrb_sym2name(mrb, mid)); // for tuning
      CALL_CFUNC_BEGIN;
      mov(eax, (Xbyak::uint32)c);
      push(eax);
      mov(eax, (Xbyak::uint32)m);
      push(eax);
      CALL_CFUNC_STATUS(mrbjit_exec_send_c, 2);
    }
    else {

呼び出そうとするメソッドがCで定義された場合の処理ですが、インライン化すると登録された場合は登録された関数を呼び出してインライン化するコードを生成します。生成に成功したら、nil以外を返すことになっているのでチェックして、その後のmrbjit_exec_send_cの呼び出しはキャンセルします。コード生成が失敗したら、nilを返して何事もなかったようにmrbjit_exec_send_cを生成して通常のメソッド呼び出し

シーケンスを実行します。


インライン化コードの例

では、実際にインライン化を行うコードを見てみましょう。primitive.ccでいろいろ定義していますが、その中で簡単なFixnum#succのインライン化を解説します。

mrb_value
MRBJitCode::mrbjit_prim_fix_succ_impl(mrb_state *mrb, mrb_value proc)
{
  mrbjit_vmstatus *status = mrb->vmstatus;
  mrb_code *pc = *status->pc;
  int i = *pc;
  int regno = GETARG_A(i);
  const Xbyak::uint32 off0 = regno * sizeof(mrb_value);

  add(dword [ecx + off0], 1);

  return mrb_true_value();
}

extern "C" mrb_value
mrbjit_prim_fix_succ(mrb_state *mrb, mrb_value proc)
{
  MRBJitCode *code = (MRBJitCode *)mrb->compile_info.code_base;

  return code->mrbjit_prim_fix_succ_impl(mrb, proc);
}

インライン化するコードはC++で書かれた実際にインライン化を行うMRBJitCodeのメソッド(MRBJitCode::mrbjit_prim_fix_succ_impl)と、そのメソッドを単に呼び出すCで書かれた関数(mrbjit_fix_succ)の組になります。C++で定義されたメソッドはProcオブジェクトとして扱えないからです。

インライン化するメソッドを見てみましょう。

mrb_value
MRBJitCode::mrbjit_prim_fix_succ_impl(mrb_state *mrb, mrb_value proc)
{
  mrbjit_vmstatus *status = mrb->vmstatus;
  mrb_code *pc = *status->pc;
  int i = *pc;
  int regno = GETARG_A(i);
  const Xbyak::uint32 off0 = regno * sizeof(mrb_value);

  add(dword [ecx + off0], 1);

  return mrb_true_value();
}

単にadd命令を生成するだけです。足すだけといってもどこを足すのか指定しなければならないので少し複雑です。オーバフロー時の処理を忘れていました。TODOということで・・・。

mrb->vmstatusにvmの内部状態が入っています。この中から現在実行中の命令(当然OP_SENDですね)を取り出します。これはpcメンバーにあります。

OP_SEND命令のA引数にはselfのレジスタ番号が入っているのでこれを取り出してmrb_valueのサイズを掛けてバイト単位のオフセットを求めています。

そして、add命令を生成してTrueを戻り値として返します。Non-Nilなのでこのインライン化は有効です。

今回は常にインライン化は有効になりますが、引数の条件によってインライン化は行わないようにすることも可能です。この場合はreturn mrb_nil_value();とします。

primitive.ccを見るともっと複雑な例をありますので、興味のある人は見てください。

そんなこんなで今回は終わり。そろそろねたも尽きかけたのでまた新しい機能ができたらお会いしましょう。ではでは

2013-05-03

luajitの実力

20:37 |  luajitの実力を含むブックマーク  luajitの実力のブックマークコメント

追記

LuaJITの作者Mike Pall氏より、twitterで次のようなアドバイスをいただきました。

1. No compiler is allowed to make this optimization. Floating-point arithmetic ist NOT associative.

2. Please use 'local' functions when publishing Lua benchmarks.

3. Please use the current version of LuaJIT.

訳(かなり怪しい)

1.このような最適化出来るコンパイラは無いよ。浮動小数点数の算術命令は結合的じゃないから

2. Luaベンチマークを取るなら局所関数を使ってください

3. 最新バージョンのLuaJITを使ってください

そういうわけで、ベンチマークを取り直します。

ベンチマークをやり直しました。functionの前にlocalを入れて、LuaJITを最新にしています。Mike Pall氏には、ベンチマークのやり直しにあたりアドバイスをいただきました。ありがとうございます。

$ luajit -v

LuaJIT 2.0.1 -- Copyright (C) 2005-2013 Mike Pall. http://luajit.org/

最適化

$ time luajit spline0.lua

real    0m1.275s
user    0m1.170s
sys     0m0.031s

最適化

$ time luajit spline1.lua

real    0m0.806s
user    0m0.732s
sys     0m0.015s

最適化前が3%ほど速くなって最適化後との差が少し縮みました。JIT無しのLuaでの結果です。

$ time ./lua ../../luajit.org/spline0.lua

real    0m1.273s
user    0m1.185s
sys     0m0.045s

$ time ./lua ../../luajit.org/spline1.lua

real    0m0.327s
user    0m0.249s
sys     0m0.046s

追記終わり

それはあまりにもコンパイラ最適化に期待し過ぎです。実際に吐き出したコードを読んでみましょう。あなたがコンパイラの作者だったら、あなたがJITの作者だったら、入って来たコードから同じような最適化ができるでしょうか。まず無理です。どんな高度な最適化コンパイラも、所詮は人間の作ったコードです。コンパイラは神ではないのです。あくまでも人間の創りだした不完全な道具のひとつに過ぎません。

よくわかる最適化 (http://d.hatena.ne.jp/shi3z/20130502/1367490202) より

うう、luajitなら、luajitならやってくれる。と信じて確かめてみました。

結果、

最適化

$ time luajit-2.0.0-beta10 spline0.lua

real    0m1.268s
user    0m1.200s
sys     0m0.016s

最適化

$ time luajit-2.0.0-beta10 spline1.lua

real    0m0.795s
user    0m0.733s
sys     0m0.046s

理論値3倍のはずなのでかなり盛り返しています。

ちなみに、JIT無しのluaだとこんな感じ。

時間がかかってしょうがないのでループを1/100にしています。

最適化

$ time ./lua ../../luajit.org/spline0.lua

real    0m1.309s
user    0m1.216s
sys     0m0.046s

最適化

$ time ./lua ../../luajit.org/spline1.lua

real    0m0.331s
user    0m0.249s
sys     0m0.061s

ちゃんと、最適化は出来ているようです。

まとめ

 luajitはとても頑張っているが完璧ではない。

移植したソースコードです

最適化

function catmullRom(p0, p1, p2, p3, t)
  local v0 = (p2 - p0) / 2.0
  local v1 = (p3 - p1) / 2.0
  return ((2.0 * p1 - 2.0 * p2) + v0 + v1) * t * t * t + 
          ((-3.0 * p1 + 3.0 * p2) - 2.0 * v0 - v1) * t * t + v0 * t + p1
end

function main(xp0, xp1, xp2, xp3, yp0, yp1, yp2, yp3, pp0, pp1, pp2, pp3)
  local d = math.sqrt((xp1 - xp2) * (xp1 - xp2) + (yp1 - yp2) * (yp1 - yp2))
  local num = math.ceil((d / 5.0) + 0.5)
  local x,y,p
  local invertNum = 1.0/num
  local deltaT = 0
  for i = 0, num do
    deltaT = deltaT + invertNum
    x = catmullRom(xp0,xp1,xp2,xp3, deltaT)
    y = catmullRom(yp0,yp1,yp2,yp3, deltaT)
    p = catmullRom(pp0,pp1,pp2,pp3, deltaT)
  end
end

for j = 0, 10000 do
  main(1.0, 100.0, 200.0, 200.0, 300.0, 100.0, 0.0, 200.0, 0.0, 100.0, 200.0, 300.0)
end

最適化

function main(xp0, xp1, xp2, xp3, yp0, yp1, yp2, yp3, pp0, pp1, pp2, pp3)
local dx = xp1-xp2
local dy = yp1-yp2
local d = math.sqrt(dx*dx+dy*dy) 
local num = math.ceil((d*0.2) + 0.5)
local x,y,p
local invertNum = 1.0/num
local deltaT = 0
local xv0 = (xp2-xp0)*0.5
local xv1 = (xp3-xp1)*0.5
local xfact1=((xp1 - xp2)*2.0 + xv0 + xv1)
local xfact2=((xp2 - xp1)*3.0 - 2.0 * xv0 - xv1) 
local yv0 = (yp2-yp0)*0.5
local yv1 = (yp3-yp1)*0.5
local yfact1=((yp1 - yp2)*2.0 + yv0 + yv1)
local yfact2=((yp2 - yp1)*3.0 - 2.0 * yv0 - yv1) 
local pv0 = (pp2-pp0)*0.5
local pv1 = (pp3-pp1)*0.5
local pfact1=((pp1 - pp2)*2.0 + pv0 + pv1)
local pfact2=((pp2 - pp1)*3.0 - 2.0 * pv0 - pv1)
local xfact1n =0
local yfact1n =0
local pfact1n =0
local xFact1step = xfact1 * invertNum
local yFact1step = yfact1 * invertNum
local pFact1step = pfact1 * invertNum
  for i = 0, num do
     deltaT = deltaT + invertNum
     x =((xfact1n + xfact2) * deltaT + xv0) * deltaT + xp1
     y =((yfact1n + yfact2) * deltaT + yv0) * deltaT + yp1
     p =((pfact1n + pfact2) * deltaT + pv0) * deltaT + pp1
     xfact1n = xfact1n + xFact1step
     yfact1n = yfact1n + xFact1step
     pfact1n = pfact1n + xFact1step
  end
end

for j = 0, 1000000 do
  main(1.0, 100.0, 200.0, 200.0, 300.0, 100.0, 0.0, 200.0, 0.0, 100.0, 200.0, 300.0)
end

2013-04-28

あなとみー おぶ mrubyのJIT (その10)

07:41 |  あなとみー おぶ mrubyのJIT (その10)を含むブックマーク  あなとみー おぶ mrubyのJIT (その10)のブックマークコメント

お久しぶりです。ここんとこしばらくProcオブジェクトのサポートを作りこんでました。これが無いとイテレータとかみんなVMに戻ってしまって性能が上がらないのです。実はProcオブジェクトをサポートしてもあまり性能が上がらなかったのですが…。

で、この作業ですごくとりにくいバグがいっぱい出て数カ月デバッグ三昧という感じでした。おかげてうまく動くようになると却って落ち着かないという状態なのですが、それはそれとしてそのデバッグで作ったツールを紹介したいと思います。全国に31名くらいいると思われるmrubyでJITコンパイラを作っている人たちに参考になれば幸いです。

デバッグしていて困るのはどの命令を実行していた時にバグったのかが分からないことです。vm.cで実行していた場合は命令毎に処理が分かれているのでまだいいのですが、ネイティブコードでバグった場合(例えばセグフォしたばあいとか)、mrubyのどの命令がコンパイルされたものでバグったのか分からないわけです。

幸い、mrubyのJITではVMに処理を渡すためにmrubyのVMプログラムカウンタ(pc)と実行中のメソッドのirepをこまめに更新しています。これらを頼りに実行位置が付きとめられます。ところが、pcとirepがつじつまが合っていないという場合があって、この場合ほぼ確実にセグフォするのですがpcに対応するirepが分からないからいろいろ不便です。また、バイナリを見てmruby VMのどの命令か判断するのは結構出来るようになったのですが、とてもむなしい作業です。

そんなこんなで次のような関数を作ってデバッグ効率を上げました。

  • search_irep(mrb, pc)       pcに対応するirepを探す
  • disasm_irep(mrb, irep)      irepを逆アセンブルする
  • disasm_once(mrb, irep, 命令)   1命令を逆アセンブルする

実装は、https://github.com/miura1729/mruby/blob/95dc9d1c5596c96aae6a6814e98e09954f0c96f4/src/jit.cの398行目以降です。

こんな感じで使います

For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/miura/work/mruby/bin/mruby...done.

aoベンチを実行

(gdb) r benchmark/ao-render.rb
Starting program: /home/miura/work/mruby/bin/mruby benchmark/ao-render.rb
[New Thread 7272.0x2f00]
[New Thread 7272.0x3118]
P6
64 64
255

ちなみに今のバージョンはちゃんと動きます。説明用にバグを仕込ませています。

Program received signal SIGSEGV, Segmentation fault.
0x3d24418b in ?? ()

取り合えず、irep, pcがアクセスできそうな関数を探す。mrbjit_dispatchではpcはppcという変数名でpcへのポインタという形で持っている。

(gdb) where
#0  0x3d24418b in ?? ()
#1  0x00429041 in mrbjit_dispatch (status=0x22a8c0, mrb=0x20039920)
    at C:\cygwin\home\miura\work\mruby\src\vm.c:682
#2  mrb_run (mrb=0x20039920, proc=0x2003b798, self=...)
    at C:\cygwin\home\miura\work\mruby\src\vm.c:2325
#3  0x00419ecf in load_exec (mrb=0x20039920, p=0x200c01a0, c=<optimized out>) at src/parse.y:5206
#4  0x00427474 in mrb_load_file_cxt (mrb=0x20039920, f=0x200bff34, c=0x200c0148) at src/parse.y:5215
#5  0x004017ac in main (argc=2, argv=0x22ac40)
    at C:\cygwin\home\miura\work\mruby\tools\mruby\mruby.c:281

mrbjit_dispatchに対象フレームを移す

(gdb) up
#1  0x00429041 in mrbjit_dispatch (status=0x22a8c0, mrb=0x20039920)
    at C:\cygwin\home\miura\work\mruby\src\vm.c:682
682           asm volatile("call *%0\n\t"

pcに対応するirepを探す。

(gdb) p search_irep (mrb, *ppc)
$1 = (mrb_irep *) 0x200f3ec8

irepの命令列を逆アセンブルする

(gdb) p disasm_irep (mrb, $1)
   0 OP_ENTER   1:0:0:0:0:0:0
   1 OP_GETIV   R4      @x
   2 OP_MOVE    R5      R1
   3 OP_SEND    R5      :x      0
   4 OP_NOP
   5 OP_MUL     R4      :*      1
   6 OP_NOP
   7 OP_GETIV   R5      @y
   8 OP_MOVE    R6      R1
   9 OP_SEND    R6      :y      0
   a OP_NOP
   b OP_MUL     R5      :*      1
   c OP_NOP
   d OP_ADD     R4      :+      1
   e OP_NOP
   f OP_GETIV   R5      @z
  10 OP_MOVE    R6      R1
  11 OP_SEND    R6      :z      0
  12 OP_NOP
  13 OP_MUL     R5      :*      1
  14 OP_NOP
  15 OP_ADD     R4      :+      1
  16 OP_NOP
  17 OP_MOVE    R3      R4
  18 OP_RETURN  R3
$2 = void

どこを実行していたかはこんな感じで調べられる

(gdb) p *ppc - $1->iseq
$3 = 4

そんな感じです。またお会いしましょう。

monamour555monamour555 2013/04/29 14:52 JITに限らず有用性が高いので,monami-ya.mrb では bundled gems に含めました.素晴らしい hack に感謝いたします.
https://bitbucket.org/mruby/monami-ya.mrb/commits/54e2edc2a040bdfbbbdce42850f3789194e9b04c

miura1729miura1729 2013/04/29 15:35 おお!ありがとうございます。この記事を書いた甲斐がありました。