teyuに届いたPullRequestで使われているRubyの高速化手法

Ruby プログラミング

この記事は ZOZOテクノロジーズ #1 Advent Calendar 2019 21日目の記事です。
昨日の記事は @awsmgsさんによる「Classic ASPによるRESTful APIのルーティング実装例」でした。

この記事では、会社の開発合宿でつくったgem teyu に届いたPullRequestで使われていた高速化手法の紹介と、なぜ速くなるのか？の考察をします。

techblog.zozo.com

届いたPullRequest

sonots さんから2件の高速化PullRequestが届きました。

前者では each ではなく while でループをさせる手法が
後者ではメソッド定義に define_method ではなく class_eval を使う手法が使われており、なぜその変更を加えることで速くなるのか気になったため調べてみました。

まずはそれぞれの手法を比較するため、ベンチマークスクリプトを書いてみました。
実行環境は以下の通りです。

高速化その1 each → while

こちらは while の方が 1.9倍 速い結果となりました。

require 'benchmark_driver'

Benchmark.driver do |x|
  x.prelude <<~RUBY
    def loop_with_each
      i = 0
      100.times.each { i += 1 }
    end

    def loop_with_while
      i = 0
      while i < 100 do
        i += 1
      end
    end
  RUBY

  x.report 'each', %{ loop_with_each }
  x.report 'while', %{ loop_with_while }
end

# 結果

Warming up --------------------------------------
                each   240.338k i/s -    259.188k times in 1.078431s (4.16μs/i)
               while   695.778k i/s -    720.603k times in 1.035680s (1.44μs/i)
Calculating -------------------------------------
                each   242.415k i/s -    721.014k times in 2.974293s (4.13μs/i)
               while   702.913k i/s -      2.087M times in 2.969545s (1.42μs/i)

Comparison:
               while:    702913.1 i/s
                each:    242415.3 i/s - 2.90x  slower

なぜ while の方が高速なのでしょうか？
Rubyのしくみ　Ruby Under a Microscope の
『実験8-1: while ループと each にブロックを渡すのとどちらが速いか』という章で、この疑問について触れていました。

each を使用すると遅くなる理由は、 Range#each メソッドはループの繰り返しごとにそのつどブロックを呼び出すか yield する必要があるからだ。 ブロックの呼び出しにはかなりの量の仕事が含まれる。ブロックをyield するために、Ruby はまずそのブロック用に新しい rb_block_t 構造体を作成する必要がある。 続いて、新しい rb_block_t構造体の EP に参照元の環境を設定し、ブロックを each 呼び出しへと引き渡す。それから、ループを繰り返すごとに Ruby は YARV の内部スタックに新しいスタックフレームを作成し、ブロックのコードを呼び出す。 そして、最後にブロックの EP を新しいスタックフレームにコピーする必要がある。それに比べて、単純な while ループの実行は、ループの繰り返しごとに PC（プログラムカウンタ）をリセットするだけでよいため、速い。 while ループの実行はメソッドも呼び出さないし、新しいスタックフレームも新しい rb_block_t 構造体も作成しない。 ＰａｔＳｈａｕｇｈｎｅｓｓｙ. Rubyのしくみ　Ruby Under a Microscope (p.225). Kindle 版.

Rubyのしくみ -Ruby Under a Microscope-

Rubyのしくみ -Ruby Under a Microscope-

  • 作者:Pat Shaughnessy
  • 発売日: 2014/11/29
  • メディア: 単行本（ソフトカバー）

eachを使ったループはブロックの実行を伴う。
ブロックの実行には rb_block_t 構造体の作成と、ブロックの呼び出し元の情報にアクセスするためのスタックフレームの位置情報(EP)をコピーする作業が必要なため、whileループと比較して高コストであるという説明が書かれています。

実際に CRuby のソースコードを見てみると、eachメソッドの内部で rb_yieldメソッドが呼ばれ、Cでブロックが実行されていることがわかります。

高速化その2 define_method → class_eval

こちらも class_eval の方が速い結果となりました。

require 'benchmark_driver'

Benchmark.driver do |x|
  x.prelude <<~RUBY
    class NormalInitialize
      def initialize; end
    end

    class DefineMethod
      define_method(:initialize) { }
    end

    class ClassEval
      class_eval "def initialize; end"
    end
  RUBY

  x.report 'Normal', %{ NormalInitialize.new }
  x.report 'define_method', %{ DefineMethod.new }
  x.report 'ClassEval', %{ ClassEval.new }
end

# 結果

Warming up --------------------------------------
              Normal     9.398M i/s -      9.592M times in 1.020589s (106.40ns/i)
       define_method     8.562M i/s -      8.690M times in 1.014931s (116.79ns/i)
           ClassEval     9.376M i/s -      9.529M times in 1.016375s (106.66ns/i)
Calculating -------------------------------------
              Normal    11.058M i/s -     28.194M times in 2.549770s (90.44ns/i)
       define_method     9.689M i/s -     25.686M times in 2.651137s (103.21ns/i)
           ClassEval    10.825M i/s -     28.128M times in 2.598282s (92.37ns/i)

Comparison:
              Normal:  11057643.6 i/s
           ClassEval:  10825450.8 i/s - 1.02x  slower
       define_method:   9688723.0 i/s - 1.14x  slower

るりまを見てみると両者の挙動の差がわかります。

class_evalは以下のようにドキュメントが書かれており、上記のベンチマークコードで考えると
ClassEvalクラスのコンテキストで文字列 def initialize; end が評価されてメソッド定義がされます。

モジュールのコンテキストで文字列 expr またはモジュール自身をブロックパラメータとするブロックを評価してその結果を返します。 モジュールのコンテキストで評価するとは、実行中そのモジュールが self になるということです。つまり、そのモジュールの定義式の中にあるかのように実行されます。

対して define_method のドキュメントを読むと、定義された DefineMethod#initialize メソッドは new するたびに DefineMethod クラスのインスタンス上で instance_eval されることがわかります。

ブロックを与えた場合、定義したメソッドの実行時にブロックがレシーバクラスのインスタンスの上で BasicObject#instance_eval されます。

メソッド実行のたびに instance_eval される時点で class_eval 経由で定義されたメソッドと比較して遅くなりそうなものですが
加えて instance_eval は、そのオブジェクトのコンテキストで「ブロックを評価」するため
each と while の項目で書いたように、ブロック実行に伴うスタックフレーム作成などの処理が発生しこのようなベンチマーク結果の差に繋がるようです。

最後に

普段Webアプリケーションを書く上ではなかなか使う機会がなさそうな高速化手法をgem開発を通じて知ることができました。
このPullRequestを取り込んだバージョンは v0.2.0 としてリリース済みで、似たような機能を持つ attr_extras gemより高速に動作するベンチマーク結果が出ています。
※こちらのPullRequestをご参照ください Fastest version #3

初期化時に引数を大量に受け取るクラスを書いている方はぜひteyuの導入をご検討ください。

明日の記事は @inductor さんによる「GKE完全に理解した」です。