Proc#call vs. yield

ご存知の通り Ruby では仮引数の最後に '&' を前置した「ブロック引数」を宣言することで、メソッドに渡されるブロックをProcオブジェクトとして受け取ることができます。つまりメソッドに渡されたブロックを呼ぶ方法には2通りあります。

def m1
  yield :m1
end

def m2(&block)
  block.call(:m2)
end

m1{|a| p a }   # => :m1
m2{|a| p a }   # => :m2

この2通りのブロック呼び出しの違いについて触れた記事もいくらかあります。*1 *2 主にブロックが渡されていない時のエラーメッセージが違うなどの挙動の違いについて触れられていますが、この文章では両者のYARVでの実装上の差異とパフォーマンスの違いについて書きます。

最初に結論を

"可能なら Proc#call ではなく yield を使おう"
「可能なら」というのは、Proc#call でできて yield でできないことがあるからです。Proc#call を使うとブロックの起動時にブロックを渡すことができますが、yield 文にはブロックもブロック引数も渡せません。
「何故か」についてはまずCRubyのスタックの使い方について解説することから始めます。

スタック消費量

大雑把に言って CRuby は 2種類のスタックを持ちます。YARV (YARV はスタックマシンという種類のVMです)が利用する"VM stack"と、"machine stack"(C言語の関数呼び出しや自動変数に使われる)です。概念的にはYARVには他にもリンクリストとしてスタックのような実行環境の構造を持っていますが、メモリ領域的にはこの2つです。
"VM stack" はさらにスタックのアドレスの小さいほうからスタックマシンとして使う部分と、アドレスの大きいほうからメソッド呼び出しの度に control frame という構造を積んでいく部分があります。両者が衝突するとスタックオーバーフローが起きることになります。

CRuby 1.9 (YARV) は Ruby で書かれたメソッドの実行中は、たとえメソッド呼び出しがネストしてもC言語の実装としては vm_exec() という関数の中で処理されるため、"machine stack"は消費しません(もちろん C 言語で実装されたメソッドの処理のためにその都度利用されますが、その関数から return すれば元に戻ります)。
"VM stack" はメソッドの呼び出し、ブロックの起動をする度に引数やローカル変数、ブロック変数の数に応じた領域が確保されます。また control frame が積まれるので現在の trunk の実装だと 11*sizeof(VALUE) が消費されます。

スタックの消費量を取得する拡張ライブラリを書きました。ソースコードは Gist に。https://gist.github.com/1341532
ただし CRuby のソースツリーのヘッダに依存しているので、ソースからRubyをビルドして、そのソースディレクトリとビルドディレクトリ(同じでもいい)を指定してextconf.rb を実行する必要があります。

$ ruby extconf.rb --ruby-src-dir=<ruby のソースディレクトリ> --ruby-build-dir=<ruby のビルドディレクトリ>
$ make

これを使うと Thread クラスに以下の3つのクラスメソッドが追加されます。

Thread.stack_length # => VM stack の通常の領域の消費量 [byte]
Thread.frame_stack_length # => control frame の領域の消費量 [byte]
Thread.machine_stack_length # => machine stack の消費量 [byte]

これでメソッド呼び出しした時のスタック消費量を調べることができます。たとえばこんな感じに。

require_relative "stacksize"


p [Thread.stack_length, Thread.frame_stack_length, Thread.machine_stack_length]

def pure_ruby_method0
  p [Thread.stack_length, Thread.frame_stack_length, Thread.machine_stack_length]
end

def pure_ruby_method1
  a = nil
  p [Thread.stack_length, Thread.frame_stack_length, Thread.machine_stack_length]
end

def pure_ruby_method2(a)
  p [Thread.stack_length, Thread.frame_stack_length, Thread.machine_stack_length]
end

pure_ruby_method0
pure_ruby_method1
pure_ruby_method2(nil)
[0].each do
  p [Thread.stack_length, Thread.frame_stack_length, Thread.machine_stack_length]
end

手元(x86_64 Mac OS X)での実行結果はこちら。

[80, 352, 1736]
[104, 440, 1736]
[112, 440, 1736]
[112, 440, 1736]
[136, 616, 3240]

pure_ruby_method0,1,2 の呼び出しでは machine stack が消費されていないこと、control frame の消費量が一定なことと VM stack の消費量が引数、ローカル変数の数に依存すること、それから Array#each のブロックの中では machine stack が消費されていることがわかります。
Array#each のブロックについて、Array#each は C 言語で実装されているメソッドですのでまず Array#each の処理中はその関数呼び出しのため machine stack が消費されます。そしてそこからブロックの呼び出し、つまり Ruby のコードの実行が呼ばれる時にはvm_exec() をネストして呼ばれます。
このように Ruby(YARV) -> C -> Ruby(YARV) と C の関数の中からブロック呼び出しするとどんどん C の関数呼び出しがネストしていき machine stack が消費されていきます。

yield と Proc#call のスタック消費

ここで本題に戻って yield と Proc#call の違いをみます。

require_relative "stacksize"

def blk_proc_call(&blk)
  blk.call
end

def blk_yield
  dummy=nil  # VM stack 消費量をそろえるため
  yield
end

p [:base, Thread.stack_length, Thread.frame_stack_length, Thread.machine_stack_length]

blk_proc_call do
  p [:call, Thread.stack_length, Thread.frame_stack_length, Thread.machine_stack_length]
end

blk_yield do
  p [:yield, Thread.stack_length, Thread.frame_stack_length, Thread.machine_stack_length]
end

実行結果は以下のようになりました。

[:base, 80, 352, 1736]
[:call, 168, 704, 3448]
[:yield, 128, 528, 1736]

yield のほうが消費量が抑えられています。特に machine stack は消費されていません。

次に2通りのブロック起動方法が YARV の命令にどのようにコンパイルされるのかをみてみます。まずは Proc#call による起動。

== disasm: <RubyVM::InstructionSequence:blk_proc_call@stk.rb>===========
local table (size: 2, argc: 0 [opts: 0, rest: -1, post: 0, block: 0] s0)
[ 2] blk<Block> 
0000 trace            8                                               (   3)
0002 trace            1                                               (   4)
0004 getlocal         blk
0006 send             :call, 0, nil, 0, <ic:0>
0012 trace            16                                              (   5)
0014 leave                                                            (   4)

本質的なのは "0004 getlocal blk" と "0006 send :call, ..." という命令です。ローカル変数(引数) blk をスタックに積み、それをレシーバとして call メソッドを呼ぶという通常のメソッド呼び出しの方法です。Proc#call はただのメソッドなので当然といえば当然ですね。それから Proc#call が C 言語で実装されているメソッドであることにも注目しましょう。Array#each のブロック呼び出しと同じように、これも Ruby -> C -> Ruby のネストが起きているため、 machine stack を消費してしまうのです。
次に yield によるブロック起動の時の YARV 命令。

== disasm: <RubyVM::InstructionSequence:blk_yield@stk.rb>===============
local table (size: 2, argc: 0 [opts: 0, rest: -1, post: 0, block: -1] s1)
[ 2] dummy
0000 trace            8                                               (   7)
0002 trace            1                                               (   8)
0004 putnil
0005 setlocal         dummy
0007 trace            1                                               (   9)
0009 invokeblock      0, 0
0012 trace            16                                              (  10)
0014 leave                                                            (   9)

今度のブロック起動は "0009 invokeblock" という1つの命令で実行されています。これはメソッド呼び出しではなく YARV の命令であることに注目してください。つまり yieldによるブロックの起動は YARV の実行の中で完結しているため、Ruby で書かれたメソッドの呼び出しの時と同様に machine stack を消費しません。さらに yield の場合ブロックを直接起動するので control frame なども1つぶんしか消費しないのに対して、Proc#call を用いるとまず Proc#call 自体の呼び出しと、そこからブロックの起動とネストするので VM stack の消費量も増えます。

ベンチマーク

最後に Proc#call と yield のベンチマークを載せます。利用したコードは先程のGist 上の stacksize 拡張ライブラリに同梱しています。https://gist.github.com/1341532#file_block_benchmark.rb
ブロックを起動する回数を増やした場合のものと、ブロックの起動を深くネストしたものでそれぞれベンチマークを取っています。さらにブロック呼び出しをネストしたほうは、ネストの最深部で GC.start を呼んで GC を走らせたものも取っています。結果はこちら。

------------------------------------------------------
                 invoke block
Proc#call:         2.120000   0.010000   2.130000 (  2.149005)
yield    :         0.810000   0.000000   0.810000 (  0.817537)
                   2.930000   0.010000   2.940000 (  2.966542)
                   1.465000   0.005000   1.470000 (  1.483271)

------------------------------------------------------
                 Deeply nested blocks
Proc#call :        0.010000   0.010000   0.020000 (  0.009859)
yield     :        0.000000   0.000000   0.000000 (  0.005181)
                   0.010000   0.010000   0.020000 (  0.015040)
                   0.005000   0.005000   0.010000 (  0.007520)

------------------------------------------------------
                 Deeply nested blocks with GC
Proc#call :        0.010000   0.020000   0.030000 (  0.032005)
yield     :        0.010000   0.000000   0.010000 (  0.006444)
                   0.020000   0.020000   0.040000 (  0.038449)
                   0.010000   0.010000   0.020000 (  0.019225)

yield 全勝です。特にネスト版は通常は約2倍程度の差なのですが、GCが走ると差が広がります。これはおそらく mahine stack の消費量の差が大きく影響しています。CRuby の GC は machine stack も mark の root として用いますが、machine stack 上の値は正確に VALUE かどうか(つまり Ruby のオブジェクトを指しているか)わからないため、Ruby のオブジェクトを指している可能性があるかどうかのチェックが行なわれます。これはそれなりに重い処理なので、machine stack の消費量が多くなるとそのぶんGC の mark 処理の負荷が高くなってしまうからだと思います。
現実的なアプリケーションで深いネストをするのは、大きな tree 構造の traverse をするような場合が考えられるので、その最中に GC が走るというのはありがちなシチュエーションだと思います。したがって machine stack の利用を抑制するのはパフォーマンスに大きな影響があるものと思われます。

machine stack を消費しない Proc#call

Proc#call が machine stack を消費しないように処理できれば……と思っていたらささださんの日記(http://atdot.net/~ko1/diary/201110.html#d31)で"Proc#call の高速化(殆どできてるんだけどバグがあるので放置している)"
という項目があって、どうやら既にそういう最適化は実験されていたようです。例外処理にバグがあるらしいのですがそこをつぶしたら 2.0 に入れられるかもしれません。
もっとも Array や Hash などのメソッドはほとんどが C 実装なので、そこをかえないとあまり効果がないのかもしれませんね。Rubinius みたいに組み込みクラスの実装を Rubyに置きかえていくという話題が最近 ruby-core でありましたが、こういう効用もある、かも、しれません。