mrubyのContextThreading化 その4

Ruby

例外を処理するには現在のContextThreadingの仕掛けでは致命的な問題がある。ブロックの呼び出しにCPUスタックを使ってネストしたcall命令で処理しているところだ。
もともと、mrubyのVMではブロックの呼び出しにcallinfoとgotoを使っていてCPUのスタックを消費しない作りになっている。ContextThreading化するときに、生成コードをct_funcの呼び出しという形で関数コールしてやることで、ブロックから上位に戻るのをret命令で処理できるようにした。これは戻りのジャンプで間接分岐を使わなくなる代わりにCPUスタックを消費する。

mrubyの例外はsetjmp-longjmpを使っている。setjmp-longjmpはCの標準関数で、setjmpで保存した場所に、スタック階層を飛び越えてlongjmpで飛び込むことができる。mrb_runの頭のほうにあるコード、

  if (setjmp(c_jmp) == 0) {
    mrb->jmp = &c_jmp;
  }
  else {
    goto L_RAISE;
  }

がその部分で、setjmpは場所を保存したら0が返ってきて、longjmpしたら、setjmpで0以外が返ってきたようにここから実行を開始する。深い階層の関数内からでも呼び出しスタックを全部捨ててここまで戻れる。mrubyの例外はこの仕掛けを使ってmrb_runの最初まで戻って、L_RAISEにジャンプする形で実現されているのだ。
ContextThreading化mrubyでは、ブロックの呼び出しがct_funcの関数呼び出しになっているから、スタックを捨てられるとブロック内からブロックの外まで飛び出してしまう。つまり、例外をこの仕組みで実現するためには、ブロックの呼び出しにスタックを使ってはいけないのだ。

ではどうするか、というのが今回のお題。


スタックを使ってブロックを呼び出すのは、call-retでブロックの呼び出しを処理することで間接分岐予測ミスを減らそうという理由である。でもそれが問題なのなら、call-retをやめて間接分岐にするしかない。そもそもct_funcの呼び出しは間接分岐なのだからここに問題は無いが、retは予測可能だったものが間接分岐になってしまう。しかも恐らく確実にミスする。速度低下は免れない。とはいえ、きちんと動かないけど速い、では意味が無い。
方針としては、ct_funcをgotoで呼び出すことにして、そこから先の個別命令はcallで呼び出す。あとはそのcall-retのスタック確保解放にさえ気をつければ、longjmpで飛び込んできたときにもスタックがネストしていないわけだから、きちんと処理できるはずだ。

まず、ct_funcの呼び出しをcallからjmpに変更する。例としてOP_SENDの最後の部分。

        MAKE_CT_FUNC
        i = *pc;
//        irep->ct_func();
        asm("movl %0, %%eax;" : : "r" (irep->ct_func) : "%eax");
        asm("addl $40, %esp;");
        asm("ret $0");
        JUMP;
      }
    }

OP_SEND内から直接ジャンプしてしまうと40byteのゴミとOP_SENDに飛ぶcallの戻りアドレスがスタックに残ってしまうので、これを消すためにいったん生成コード内に戻る。ジャンプ先のアドレスはeaxに入れておく。OP_SEND以外も同様に修正する。で、生成コード側にこれを追加する。

      case OP_SEND:\
      case OP_SUPER:\
      case OP_CALL:\
      case OP_TAILCALL:\
      case OP_EXEC:\
      case OP_RETURN:\
        *data = 0xff; /* jmp *eax */ \
        *(data + 1) = 0xe0;\
        data += 2;\
        break;\
      }\

戻ってきたときのeaxに間接ジャンプする。これでirep間のジャンプは実現できる。この方法だとCのメソッドを呼び出して戻ってきたときにも次の命令に間接ジャンプを実行しなければならないので、Cメソッド呼出し後にも似たようなコードを入れる。次の命令の位置は現状では実行時にはわからないから、とりあえずadr_bufは解放せずに保持しておかなければならない。

typedef struct mrb_irep {
  int idx;

  int flags;
  int nlocals;
  int nregs;

  mrb_code *iseq;
  mrb_value *pool;
  mrb_sym *syms;
  mrb_value (*ct_func)(void);
  unsigned char **adr_buf;  // ←追加

  int ilen, plen, slen;
} mrb_irep;

MAKE_CT_FUNCはローカル変数adr_bufではなくirep->adr_bufを使うように変えておく。その上で、OP_SENDのCメソッドを呼ぶ部分を変更する。

      if (MRB_PROC_CFUNC_P(m)) {
        if (n == CALL_MAXARGS) {
          ci->nregs = 3;
        }
        else {
          ci->nregs = n + 2;
        }
        mrb->stack[0] = m->body.func(mrb, recv);
        mrb->arena_idx = ai;
        if (mrb->exc) goto L_RAISE;
        /* pop stackpos */
        regs = mrb->stack = mrb->stbase + ci->stackidx;
        cipop(mrb);
// ここから
        i = *++pc;
        asm("movl %0, %%eax;" : : "r" (irep->adr_buf[pc - irep->iseq]) : "%eax");
        asm("addl $40, %esp;");
        asm("ret $0");
// ここまで追加
        NEXT;
      }

pcとirep->iseqがあればどのVM命令のアドレスでも求まる。

次にOP_RETURNを細工する。上のMAKE_CT_FUNC内でOP_SENDと一緒にOP_RETURNも間接分岐するようにしてあったが、このための布石だ。

        regs[acc] = v;
// ここから
        i = *pc;
        asm("movl %0, %%eax;" : : "r" (irep->adr_buf[pc - irep->iseq]) : "%eax");
        asm("addl $40, %esp;");
        asm("ret $0");
// ここまで追加
      }
      JUMP;
    }

戻り先のpcはこの上でci->pcから入れているので、それを使って計算してadr_bufから取り出して、生成コード側でジャンプする。あと、Cのコードから呼ばれた場合のOP_RETURNも細工する。

        if (acc < 0) {
          mrb->jmp = prev_jmp;
// ここから
          asm("movl %0, %%eax;" : : "r" (&&L_CT_RETURN) : "%eax");
          asm("addl $40, %esp;");
          asm("ret $0");
// ここまで追加
    L_CT_RETURN:
          return v;
        }

call-retの構造を壊さないように、いったん生成コードに戻ってから、returnに飛び込む。これをしないとcall-retの関連が狂ってペナルティが痛いことになるが、このコードがあっても分岐予測が増えるからそのぶんのペナルティは発生する。
これでcall-retをネストしないContextThreadingができた。処理も増えて間接分岐も増えるから、かなり遅くなる。
元のmruby：10分8秒(608秒)
ContextThreading：10分45秒(645秒)
例外を正しく処理しようとしたら元のmrubyよりも遅くなってしまった。処理のオーバーヘッドと間接分岐が増えるのはやはり相当辛いということだ。無駄なコードが多い気はするから細かいチューニングでそのへんを改善しなければ、ContextThreadingに存在価値がなくなる。これはつまり、いまのCPUでは分岐予測ミスのペナルティは(Pentium4などと比較して)少なくなっているから、とりあえず間接分岐を減らしさえすれば速くなるというほど楽観的な状態ではない、ということだ。例外対応前は速くはなっていたし、確かに効果はあるのだが、オーバーヘッドを丁寧に削らないと逆に遅くなってしまうぐらいの微妙な差である。少なくとも20%とか向上するようには思えない。

最後に例外に対応しておく。OP_RETURN内のL_RAISE側の最後。

        irep = ci->proc->body.irep;
        pool = irep->pool;
        syms = irep->syms;
        regs = mrb->stack = mrb->stbase + ci[1].stackidx;
        pc = mrb->rescue[--ci->ridx];
        goto *irep->adr_buf[pc - irep->iseq]; // ←追加
      }
      else {

callネストがなくなったから例外処理から生成コードにgotoしても大丈夫。これでブロックをネストした例外も処理することができる。

今後の展開は、なんとかチューニングして速くするか、make testが途中でコケるからそれをどうにかするか。どっちもContextThreadingの存在価値としては重要だ。
ContextThreadingの論文はPentium4を使っていたから、今のCPUでも速くなるのか、というのはみんな疑問に思っていることで、mrubyを使ってそれを検証するのはある程度は意味があることなのかもしれない。作るの結構大変だし。とりあえず作ってみて試せるようなものでもない。
どれぐらい頑張ったらどれぐらい速くなるのか、コストに応じたメリットはあるのか。どの程度の技術力をもってして作りこまなければならないのか。
まあ、そんなところが明らかになればいいな、みたいな。