続編 (Go) へ 続編 (Streem) へ

LINQ ライク・メソッドの高速化と Ruby 1.9

2012-10-02 (鈴)

1. はじめに

"Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド" では,Ruby 2.0.0 開発版の Enumerator::Lazy と同等の機能が一部の例外を除き mruby と共通する Ruby 言語の骨格だけで実現できることを示し,それを C# 3.0 以降にある同類のメソッドにちなみ LINQ ライクなメソッドと名付けた。 "解説: Ruby/mruby LINQ ライク・メソッド" ではその内部動作を解説し, "Ruby のための LINQ ライク・メソッドの使用例" ではいくつかの例を与えた。

しかし,そのメソッドを使ったとき,従来と比べ計算量のオーダーが同じであることは示したが,具体的な速度については今まで議論してこなかった。 本稿ではその速度を測り,さらに Ruby 1.9 を念頭において実装を高速化し改良する。

2. ベンチマーク・テスト

Ruby 2.0.0 開発版の Enumerator::Lazy に対するベンチマーク bench.rb"Bug #6183: Enumerator::Lazy performance issue" [ruby-lang.org] で与えられている。 同ページによれば C 言語による Enumerator::Lazy の初期実装は従来の方法に比べて 1.46/0.42 ≒ 3.5 倍遅かったが 4月3日の時点で 0.77/0.37 ≒ 2.1 倍だけ遅いまでに改善されたという。 さしあたりこれを目標性能としよう。

まずベンチマークのメソッド連鎖から .lazy を取り除き,map_map に置き換えたプログラムを用意する。

require 'benchmark'
require './_enum'

def make_test len
  arr = [1] * len
  n = 1000
  Benchmark.bm(15) do |r|
    l = r.report('Lazy enumerator') do
      n.times { arr._map { |x| x * 9 }._map { |x| x * 55 }.each { |x| x * 100 } }
    end
    s = r.report('Simple array') do
      n.times { arr.map { |x| x * 9 }.map { |x| x * 55 }.each { |x| x * 100 } }
    end
    [s / l]
  end
end

make_test(1000)

これを "Ruby 1.8.7 からの LINQ ライクな Enumerable メソッド"_enum.rb 1.1 に対して実行すると,

の結果が得られた (Core i7-3820QM 2.7GHz, 8GB RAM, OS X 10.7.5)。 別のマシンでは

の結果が得られた (Pentium III Coppermine 667MHz, 128MB RAM, Linux 2.6.27)。

予期しないこの好結果にはむしろ当惑させられる。 驚くべきことに,C 言語によらない純粋な Ruby 言語コードだけで ruby 1.9.3 に対しすでに目標性能が概ね達成されているからだ。

ちなみに 10月2日現在の Ruby 2.0.0 開発版を上記の Pentium III Linux マシンで試すと と,ruby 1.9.3 の場合と概ね同じ結果が得られました。

しかし,それでもなお高みを目指して高速化を試みることにしよう。

3. 高速化

_enum.rb では,Ruby 1.9 の Enumerator のブロック付きコンストラクタの仕様にあわせて

  # {|y| ... y << v ...} を内部イテレータに仕立てる
  class Iterator
    include Enumerable
    def initialize(block); @block = block; end
    def each(&body); @block[Yielder.new(body)]; end

    # {|y| ... y << v ...} での y となる
    class Yielder
      def initialize(body); @body = body; end
      def << (val); @body[val]; end
    end
  end

  def iterator(&block); Iterator.new(block); end
  module_function :iterator
  # これは Ruby 1.9.* では単に Enumerator.new(&block) と定義できる

のように Iterator クラスを定義していた。 そして,例えば _collect メソッドを次のように定義していた。

  def _collect
    return enum_for(:_collect) unless block_given?
    iterator {|y| each {|e|
        y << (yield e)
      }}
  end

その意図は Ruby 1.8 から Ruby 1.9 に完全移行したとき,iterator 関数の本体を C 言語で実装された Enumerator.new(&block) にすげかえることにあった。 しかし,実際にすげかえたところ,性能はむしろ悪化した。

すげかえた場合の Pentium III, Linux マシンでのベンチマークの結果は でした。約 1.3 倍遅くなっています。 Enumerator インスタンスは第一義的には外部イテレータであり,そのためにいろいろと手間があるのでしょう。 しかし,LINQ ライク・メソッドはこれを Ruby 伝統の内部イテレータとしてしか使いませんから,せっかくかけた手間が空しく無駄になっているはずです。

一方,ここで Enumerator との互換性を無視して見直せば,Iteratoreach メソッド本体で Yielder インスタンスを構築してブロック引数をラップする必要がないことに気付く。 Yielder インスタンスの唯一の役割は各メソッド実装で y << 式 と書けるようにすることである。 もしも y[] と書くようにすれば,この構築を省くことができる。

  class Iter
    include Enumerable
    def initialize(&block); @block = block; end
    def each(&y); @block[y]; end
  end

このとき _collect メソッドは次のように定義できる。

  def _collect
    return enum_for(:_collect) unless block_given?
    Iter.new {|y| each {|e|
        y[yield e]
      }}
  end

ブロック引数の省略に対する処理が若干うるさいのが残念だが,ある意味,数学的な美しさがある簡潔な定義となった。

せっかくの調和を乱しているブロック引数の省略ですが,これは次のように使えます。
>> x = (0..10)._collect
=> #<Enumerator: 0..10:_collect>
>> x.each {|e| print e; e + 100}.take(5)
01234=> [100, 101, 102, 103, 104]
>>  
次に示す従来の collect メソッドの動作と比べてください。
>> y = (0..10).collect
=> #<Enumerator: 0..10:collect>
>> y.each {|e| print e; e + 100}.take(5)
012345678910=> [100, 101, 102, 103, 104]
>>  

この定義で書き直した _enum2.rb で同じようにベンチマーク bench.rb を実行すると,

の結果が得られた (Core i7-3820QM 2.7GHz, 8GB RAM, OS X 10.7.5)。 別のマシンでは

の結果が得られた (Pentium III Coppermine 667MHz, 128MB RAM, Linux 2.6.27)。

つまり,§2_enum.rb の結果と比べて約 1.3 倍から約 1.5 倍の高速化の効果が見られた。

4. 使用例

"Ruby のための LINQ ライク・メソッドの使用例 - 5. _iterate と単一代入で Happy number を挙げる" で与えた例を,この新しい _enum2.rb を使って書き直してみよう。

Haskell にちなむ _iterate メソッドを定義する iterate.rb_enum2.rbIter クラスを使って書き直すこともできるが,Ruby 1.9 以降ならば,標準の Enumerator クラスを使うことが (たとえ性能では若干不利になるとしても) Ruby プログラミングとしては正攻法であろう。 Iter クラスはあくまで内部実装での利用を意図したものである。 下記に iterate2.rb を示す。

# Haskell 風の iterate を Object に追加する。 

class Object
  # "a"._iterate {|s| s + s}.take(3) => ["a", "aa", "aaaa"]
  def _iterate
    Enumerator.new {|y|
      a = self
      loop {
        y << a
        a = (yield a)
      }
    }
  end

  # "a".iterate {|s| break if s.length > 5; p s; s + s} => nil
  #                        (ただし "a" "aa" "aaaa" を印字する)
  def iterate
    a = self
    loop {
      a = (yield a)
    }
  end
end

happy_numbers22.rb は元の happy_numbers2.rb とは require だけが異なる。

#!/usr/bin/env ruby

require 'iterate2'
require '_enum2'

# digits_of(31416).to_a => [6, 1, 4, 1, 3]
def digits_of(k)
  Enumerator.new {|y|
    k.iterate {|n|
      break unless n > 0
      y << n % 10
      n / 10
    }
  }
end

def is_happy(k)
  seq = k._iterate {|n|
    digits_of(n)._map {|i| i * i}.inject {|x, y| x + y}
  }
  seq.each {|n|
    return true if n == 1
    return false if n == 4
  }
end

n = ARGV[0].to_i
(1..n)._select {|i| is_happy(i)}.each {|i| print i, " "}
puts

実行例を示す。

01:~/tmp$ ruby1.9 -I. happy_numbers22.rb 1000
1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 94 97 100 103 109 129 130 133 1
39 167 176 188 190 192 193 203 208 219 226 230 236 239 262 263 280 291 293 301 3
02 310 313 319 320 326 329 331 338 356 362 365 367 368 376 379 383 386 391 392 3
97 404 409 440 446 464 469 478 487 490 496 536 556 563 565 566 608 617 622 623 6
32 635 637 638 644 649 653 655 656 665 671 673 680 683 694 700 709 716 736 739 7
48 761 763 784 790 793 802 806 818 820 833 836 847 860 863 874 881 888 899 901 9
04 907 910 912 913 921 923 931 932 937 940 946 964 970 973 989 998 1000 
01:~/tmp$  

5. Ruby 1.9 の each_with_index 対策

Ruby 1.9 の each_with_index メソッドに LINQ ライク・メソッドを連鎖させたとき,ブロックの第2引数として index 値が渡らない問題を "Ruby のための LINQ ライク・メソッドの使用例 - 3.1 Ruby 1.9 に対する注意" で議論した。 LINQ ライク・メソッド実装内部のブロックに引数を渡すとき,それを配列として受け取らせることが解決方法である。

しかし,すべての LINQ ライク・メソッド実装にその処理を負わせるかわりに配列への変換を陽に行うメソッドを一つだけ用意し,そのメソッドを each_with_index の後に連鎖させることが効率的に望ましい。 この目的のため,_enum2.rb にメソッド __ を設けた。

  # Ruby 1.9.* で each_with_index の戻り値に連鎖させるときは複数引数を
  # 引き渡すために seq.each_with_index.__._map{|e, i| f(e, i)} とする。
  # Ruby 1.8.7 でもこれは無駄になるだけで正常に動作する。
  def __
    Iter.new {|y| each {|*e|
        y[(e.length == 1) ? e[0] : e]
      }}
  end
ここでは無色透明な名前として __ を選びました。 複数個の実引数を一つにまとめて引き渡す働きから,Haskell の uncurry 関数にそれとなくちなんで uncurry と名付けてもよかったかもしれません。

下記の fizz_numbers2.rb"Ruby のための LINQ ライク・メソッドの使用例 - 3. FizzBuzz で Fizz になる数を n 個挙げる"fizz_numbers.rb を,このメソッドを使って書き換えた例である。

#!/usr/bin/env ruby

require '_enum2'

n = ARGV[0].to_i

fizzbuzz = (1 .. 1.0/0)._map {|i| 
  if i % 3 == 0 then
    if i % 5 == 0 then
      :FizzBuzz
    else
      :Fizz
    end
  elsif i % 5 == 0 then
    :Buzz
  else
    i
  end
}

fizzbuzz.each_with_index.__._map {|value, index|
  [value, index + 1]
}._select {|value, i|
  value == :Fizz
}._take(n).each {|value, i|
  print i, " "
}

puts

実行例を示す。

01:~/tmp$ ruby1.9 -I. fizz_numbers2.rb 100
3 6 9 12 18 21 24 27 33 36 39 42 48 51 54 57 63 66 69 72 78 81 84 87 93 96 99 10
2 108 111 114 117 123 126 129 132 138 141 144 147 153 156 159 162 168 171 174 17
7 183 186 189 192 198 201 204 207 213 216 219 222 228 231 234 237 243 246 249 25
2 258 261 264 267 273 276 279 282 288 291 294 297 303 306 309 312 318 321 324 32
7 333 336 339 342 348 351 354 357 363 366 369 372
01:~/tmp$  

6. おわりに

§3 の高速化の結果として LINQ ライク・メソッドは従来の非 LINQ ライクなメソッドと比べて ruby 1.9.3 で 約 1.6 倍だけ遅いまでに性能が向上した。 Ruby の応用分野の多くでこれは許容できる値であろう。 きたるべき明日の Ruby 2.0.0 の Enumerator::Lazy を待つのではなく,今ここにある LINQ ライク・メソッドを今日から使うことは十分に合理的な判断である,と言ってよい。

参考までに 10月2日現在の Ruby 2.0.0 開発版を件の Pentium III Linux マシンで試すと,_enum2.rb について と ruby 1.9.3 の場合と概ね同じ結果が得られました。一方,Enumerator::Lazy については と,_enum2.rb との比較で三倍近く低速な値が得られました ((9.31/2.08) / (3.28/2.09) = 2.85...)。 "Bug #6183: Enumerator::Lazy performance issue" [ruby-lang.org] で議論されていた Enumerator::Lazy のパッチは現在の開発版には反映されていないように見えます。 しかし,ソースコードを読むとパッチとは異なるものの確かに enumerator.c の C 言語コードで Enumerator::Lazy が実装されているようです。 なぜ単なる Ruby コードが C より約三倍高速になっているのか,もしかしたら何か基本的な見落としをしているのではないかと気になります。

Copyright (c) 2012 OKI Software Co., Ltd.