mrubyの可変引数最適化

はじめに

Rubyでは、可変引数を配列としてアクセスする仕様があります。たとえばこんな感じ

def foo(*arg)
  p arg
end

foo(1)       # -> [1]
foo(1, 2, 3) # -> [1, 2, 3]

このような可変引数の配列は、mrubyの実装ではRITE VMの命令OP_ENTER中で作られます。つまり、可変引数を使うとメソッドコールの度に配列のアロケーションが行われるわけです。メソッドコールの数が多ければGCも頻発することでしょう。
可変引数の使用頻度が少なければ問題ないのですが、ループを構成してメソッドコールが頻発するmrblib/enum.rbで定義されているEnumerableモジュールのメソッドは軒並み使われています。たとえば、all?の定義です。

  def all?(&block)
    if block
      self.each{|*val|
        unless block.call(*val)
          return false
        end
      }
    else
      self.each{|*val|
        unless val.__svalue
          return false
        end
      }
    end
    true
  end

つまり、Rubyらしく記述したコードはそうではない場合に比べて速度が激減する可能性があります。
しかし、解決策があります。Enumerableで使われている可変引数は、多くの場合1つだけの引数を渡します。引数が1つの場合は配列を作らずにその値をレジスタに入れることで配列の生成を避けることができます。もちろん、バイトコード列は配列を処理することを前提に生成されていますので、バイトコードを書きかえる必要があります。また、常に引数が１つで呼び出されるとは限らないのでバイトコード列は書き換えたものとオリジナルのもの両方を保存する必要があります。
今回このようなバイトコード列を書きかえる方針で速度向上を実現し、make testが通りましたので詳細を記述したいと思います。
なお、実際のコードはこんな感じです。　https://github.com/miura1729/mruby/commit/c584ec101116b537e10a085f97efc59fb0f2d849

OP_ENTERの書き換え

Rite VMのOP_ENTER命令はメソッドのバイトコード列の先頭にあり(ない場合もある)、Rubyの複雑な引数の規則に合わせて渡された引数をRite VMのレジスタに格納していく命令です。その中で、メソッドの呼び出し元からRite VMレジスタ経由で渡ってきた引数を配列にまとめる処理はこんな感じのコードです。

        if (r) {
          rnum = argc-m1-o-m2;
          regs[m1+o+1] = mrb_ary_new_from_values(mrb, rnum, argv+m1+o);
        }

このコードを良く見ると、rnumが実際にわたってきた引数の数を表すことがわかると思います。つまり、実際に1つだけの引数を渡しているのかチェックするにはrnumをチェックすればいいわけです。そして、rnumが1の時、要素1の配列が返ってくるわけでその要素を直接レジスタに入れることも簡単です。
しかし、この先のコードはregs[m1+o+1]に配列が入っていることが前提になりますので配列ではなくその要素が直接入っていることを前提にバイトコード列を書き変えるわけです。この書き換えはそれほど重い処理ではないのですが、毎回やるのは馬鹿らしいのでどこかにキャッシュする必要があります。ここからはとても面倒で面白くない話が続くので、次の章　バイトコードの書き換えまで　飛ばすのがいいでしょう。

絶対に引数が1つしか来ないことが保障できればirep->iseqを書き変えてもいいのですが、一般的にそんな仮定はできません。そこで書き換えた版のirepをどこかに保存する場所を作る必要があります。irepにメンバーを追加するのが簡単でいいのですが、今後同じようにバイトコードを書き変えて最適化するようなことを行う場合、同じようにメンバーを追加するのも面白くない話です。そこで、今回はirep->poolにirepを格納するようにしました。OP_ENTERは必ず先頭に来るのでirep->pool[0]に常に格納されます。
また、現在のメソッド・ブロックのProcオブジェクトを格納する変数procの扱いも面倒です。引数が1つしか渡ってこないことが前提のirepを指し示すように書き換えてしまうと、入れ子になったメソッドコールの途中で再帰的に呼び出された場合に困ります。また、Procオブジェクトをキャッシュすることも考えたのですがやはりGCで不具合が出ます。そこで、バイトコードを書き変えた場合は新たにProcオブジェクトを生成するようにしています。幸い、これによるオーバヘッドはあるのですが少ないようです。

バイトコード書き換え

バイトコードは次のような方針で書き換えます。
バイトコード中の可変引数が入っているレジスタ(本来は配列が入っているけど、さぼって要素を入れているもの)の番号をdrnoとします。

• 子irep(irep->repsで示されたもの)でOP_GETUPVER, OP_SETUPVERを使ってdrnoレジスタをアクセスしているものが無いかチェックします。もしあれば、残念ながらこの最適化の対象外です。おとなしく配列を作るようにします。
• OP_MOVE命令でdrnoレジスタの内容をコピーしていたらtdrnoとして覚えておきます。逆に、drnoレジスタに書き込もうとしていたら、残念ながら最適化の対象外です。
• OP_RETURN命令でdrnoレジスタをメソッドの値として返そうとしていたら最適化対象外です
• OP_SEND命令、これが少々複雑です
  • 引数の数(ARG_C)が127でその引数がtdrnoだったら、OP_SEND命令でARG_Cを1に書き換えます。
  • メソッド名が_svalueか[]だったらNOPに書き換えます。これで要素を取りだしたふりをします。レジスタにはもともと要素が入っているわけです。
  • メソッド名がsizeでselfがtdrnoだったらLOADI tdrno, 1とします。これでサイズ1の配列のふりをします。
  • そのほかのOP_SEND, OP_ARRAY, OP_HASHで引数にtdrnoが含まれていたら最適化対象外です
• 次のようなシーケンスはOP_ARRAY, OP_ARYCATをNOPにして、OP_SEND命令のARG_Cを1に書き換えます

OP_ARRAY (サイズは0, そうでなければ最適化対象外)
OP_MOVE  (srcがdrno)
OP_ARYCAT
OP_SEND  (ARG_Cが127)

未来の話

配列やオブジェクトを作るべきところであえて作らずにレジスタに要素を展開する最適化はいろいろなコンパイラで行われています。今後、データフロー解析などでオブジェクトの寿命が把握できるところはそういったコードの変換も可能ではないかなと考えます。