Ruby: Enumerableのパフォーマンスを測定する（2）（翻訳）
Enumerableのパフォーマンスの話は今回でおしまいにしておきます。しかし過去記事で申し上げた【URL更新】ように、この問題にはオタク心をくすぐる要素が盛りだくさんです。
過去記事に書いた私の「ベスト」ソリューションについて、その後Brandon、Michael、Piotr、Kasperの4名から、Enumerable#partitionを使えば4つのループのうち2つを書かずに済むという指摘をいただきました。
また、Daveからは、単純なループは言語レベルでの最適化がものすごく進んでいるから、過去記事で最初に書いた普通のループ方式についてもベンチマークを取るとよいと教わりました。
そこで、以下のようにすべてのベンチマークを盛り込みました。
require 'benchmark/ips'
n = 100
a = Array.new(n) { |i| rand(1_000_000) }
b = Array.new(n) { |i| rand(1_000_000) }
Benchmark.ips do |x|
# 偶数/奇数で事前フィルタしてから積を計算
x.report('odd & even') do
(a.select(&:odd?).product(b.select(&:even?)) +
b.select(&:odd?).product(a.select(&:even?)))
.uniq
end
# 別解: すべての積を計算してから和でフィルタ
x.report('full product, +') do
a.product(b).select { (_1 + _2).odd? }.uniq
end
x.report('full product, sum') do
a.product(b).select { _1.sum.odd? }.uniq
end
x.report('loops') do
results = []
a.each do |x|
b.each do |y|
if ((x + y) % 2) == 1
results << [x, y]
end
end
end
results.uniq
end
x.report('partition') do
odd_as, even_as = a.partition(&:odd?)
odd_bs, even_bs = b.partition(&:odd?)
(odd_as.product(even_bs) + odd_bs.product(even_as)).uniq
end
x.compare!
end
結果は以下のとおりです。
Calculating -------------------------------------
odd & even 1.347k (± 2.2%) i/s (742.59 μs/i) - 6.850k in 5.089081s
full product, + 785.253 (± 1.5%) i/s (1.27 ms/i) - 3.952k in 5.034013s
full product, sum 719.042 (± 2.1%) i/s (1.39 ms/i) - 3.650k in 5.078324s
loops 893.864 (± 1.3%) i/s (1.12 ms/i) - 4.488k in 5.021755s
partition 1.370k (± 1.8%) i/s (729.79 μs/i) - 6.900k in 5.037264s
Comparison:
partition: 1370.3 i/s
odd & even: 1346.6 i/s - same-ish: difference falls within error
loops: 893.9 i/s - 1.53x slower
full product, +: 785.3 i/s - 1.74x slower
full product, sum: 719.0 i/s - 1.91x slower
というわけで、Enumerable#partitionを使うという、さらなる改善方法が示されました。
これに加えて、配列結合メソッド（例: |やunion）などのより適切な方法を使えば、最終結果の配列にuniqループを追加せずに済むようになり、さらなるパフォーマンス改善が見込めそうです。
require 'benchmark/ips'
n = 100
a = Array.new(n) { |i| rand(1_000_000) }
b = Array.new(n) { |i| rand(1_000_000) }
Benchmark.ips do |x|
x.report('odd & even') do
(a.select(&:odd?).product(b.select(&:even?)) +
b.select(&:odd?).product(a.select(&:even?)))
.uniq
end
x.report('odd & even union') do
a.select(&:odd?).product(b.select(&:even?)).union(
b.select(&:odd?).product(a.select(&:even?)))
end
x.report('odd & even |') do
a.select(&:odd?).product(b.select(&:even?)) |
b.select(&:odd?).product(a.select(&:even?))
end
x.report('loops') do
results = []
a.each do |x|
b.each do |y|
if ((x + y) % 2) == 1
results << [x, y]
end
end
end
results.uniq
end
x.report('loops |') do
results = []
a.each do |x|
b.each do |y|
if ((x + y) % 2) == 1
results | [x, y]
end
end
end
results
end
x.report('partition') do
odd_as, even_as = a.partition(&:odd?)
odd_bs, even_bs = b.partition(&:odd?)
(odd_as.product(even_bs) + odd_bs.product(even_as)).uniq
end
x.report('partition union') do
odd_as, even_as = a.partition(&:odd?)
odd_bs, even_bs = b.partition(&:odd?)
odd_as.product(even_bs).union(odd_bs.product(even_as))
end
x.report('partition |') do
odd_as, even_as = a.partition(&:odd?)
odd_bs, even_bs = b.partition(&:odd?)
odd_as.product(even_bs) | odd_bs.product(even_as)
end
x.compare!
end
結果は、partition方式とシンプルな偶数&奇数（odd & even）方式のどちらも、ほぼ同じです。
Calculating -------------------------------------
odd & even 1.375k (± 0.4%) i/s (727.08 μs/i) - 6.987k in 5.080142s
odd & even union 1.334k (± 0.4%) i/s (749.77 μs/i) - 6.700k in 5.023541s
odd & even | 1.339k (± 0.4%) i/s (746.81 μs/i) - 6.700k in 5.003743s
loops 896.130 (± 0.9%) i/s (1.12 ms/i) - 4.500k in 5.022004s
loops | 1.416k (± 1.1%) i/s (706.43 μs/i) - 7.100k in 5.016274s
partition 1.378k (± 0.8%) i/s (725.47 μs/i) - 6.900k in 5.006093s
partition union 1.349k (± 0.6%) i/s (741.43 μs/i) - 6.834k in 5.067094s
partition | 1.346k (± 0.4%) i/s (742.74 μs/i) - 6.834k in 5.075995s
Comparison:
loops |: 1415.6 i/s
partition: 1378.4 i/s - 1.03x slower
odd & even: 1375.4 i/s - 1.03x slower
partition union: 1348.7 i/s - 1.05x slower
partition |: 1346.4 i/s - 1.05x slower
odd & even |: 1339.0 i/s - 1.06x slower
odd & even union: 1333.7 i/s - 1.06x slower
loops: 896.1 i/s - 1.58x slower
しかし、「単純な」ループ方式（"loops"）は相変わらず最低のパフォーマンスですが、ループの内側で|演算子を使うと（"loops |"）、むしろ他のどの実装よりも速度がわずかに上回っていることがわかります。
最後に、Rubyにある遅延評価機能（Enumerator::Lazy）を使えば、巨大なデータセットで中間配列を作成するオーバーヘッドを回避できます。ただし遅延評価はEnumerableの一部のメソッドでしか使えません。
書き換えられたメソッドの1つはuniqですが、このuniqループをlazy enumeratorに変えるとパフォーマンスは向上するでしょうか？このループの例でもeachにlazyを追加できます。
この追加によってベンチマークはどう変わるでしょうか？
require 'benchmark/ips'
n = 100
a = Array.new(n) { |i| rand(1_000_000) }
b = Array.new(n) { |i| rand(1_000_000) }
Benchmark.ips do |x|
x.report('odd & even') do
(a.select(&:odd?).product(b.select(&:even?)) +
b.select(&:odd?).product(a.select(&:even?)))
.uniq
end
x.report('odd & even lazy') do
(a.select(&:odd?).product(b.select(&:even?)) +
b.select(&:odd?).product(a.select(&:even?)))
.lazy.uniq
end
x.report('loops') do
results = []
a.each do |x|
b.each do |y|
if ((x + y) % 2) == 1
results << [x, y]
end
end
end
results.uniq
end
x.report('loops |') do
results = []
a.each do |x|
b.each do |y|
if ((x + y) % 2) == 1
results | [x, y]
end
end
end
results
end
x.report('loops | lazy') do
results = []
a.lazy.each do |x|
b.lazy.each do |y|
if ((x + y) % 2) == 1
results | [x, y]
end
end
end
results
end
x.report('partition') do
odd_as, even_as = a.partition(&:odd?)
odd_bs, even_bs = b.partition(&:odd?)
(odd_as.product(even_bs) + odd_bs.product(even_as)).uniq
end
x.report('partition lazy') do
odd_as, even_as = a.partition(&:odd?)
odd_bs, even_bs = b.partition(&:odd?)
(odd_as.product(even_bs) + odd_bs.product(even_as)).lazy.uniq
end
x.report('partition |') do
odd_as, even_as = a.partition(&:odd?)
odd_bs, even_bs = b.partition(&:odd?)
odd_as.product(even_bs) | odd_bs.product(even_as)
end
x.compare!
end
どうやらuniqにlazyを併用すると（"odd & even lazy"と"partition lazy"）、lazyなしの場合や、ループを|演算子で改善した場合よりも著しく高速になる「ようです」。
Calculating -------------------------------------
odd & even 1.351k (± 2.5%) i/s (740.37 μs/i) - 6.834k in 5.063314s
odd & even lazy 6.145k (± 1.1%) i/s (162.74 μs/i) - 31.263k in 5.088472s
loops 917.432 (± 0.7%) i/s (1.09 ms/i) - 4.641k in 5.058882s
loops | 1.481k (± 2.7%) i/s (675.29 μs/i) - 7.446k in 5.032326s
loops | lazy 1.466k (± 0.3%) i/s (682.27 μs/i) - 7.436k in 5.073396s
partition 1.373k (± 0.5%) i/s (728.15 μs/i) - 6.936k in 5.050569s
partition lazy 5.224k (± 1.0%) i/s (191.41 μs/i) - 26.180k in 5.011751s
partition | 1.339k (± 0.7%) i/s (746.74 μs/i) - 6.732k in 5.027289s
Comparison:
odd & even lazy: 6144.7 i/s
partition lazy: 5224.3 i/s - 1.18x slower
loops |: 1480.9 i/s - 4.15x slower
loops | lazy: 1465.7 i/s - 4.19x slower
partition: 1373.3 i/s - 4.47x slower
odd & even: 1350.7 i/s - 4.55x slower
partition |: 1339.2 i/s - 4.59x slower
loops: 917.4 i/s - 6.70x slower
uniqにlazyを併用するとlazyなしの場合より高速になるのは、その裏で何らかのマジックが働いているのでしょうか？残念ながら、違います。
ループではlazyを使っても使わなくてもパフォーマンスが変わらないことが手がかりになるはずです。
uniqは配列全体を即座に処理して、重複を取り除いた新しい配列を返します。この処理では、配列のあらゆる要素をもれなく調べなければなりません。
一方、lazy.uniqはEnumerator::Lazyを返しますが、これは要素にアクセスするときまで「何もしません」。
公平に比較するなら、以下のような感じのコードが必要でしょう。
# 例
x.report('partition lazy') do
odd_as, even_as = a.partition(&:odd?)
odd_bs, even_bs = b.partition(&:odd?)
(odd_as.product(even_bs) + odd_bs.product(even_as)).lazy.uniq.to_a
end
結果からも裏付けられます。
Calculating -------------------------------------
loops | 1.436k (± 2.6%) i/s (696.42 μs/i) - 7.191k in 5.011518s
loops | lazy 1.424k (± 1.4%) i/s (702.40 μs/i) - 7.228k in 5.078029s
partition 1.359k (± 1.7%) i/s (735.93 μs/i) - 6.885k in 5.068374s
partition lazy 814.193 (± 2.9%) i/s (1.23 ms/i) - 4.116k in 5.060084s
Comparison:
loops |: 1435.9 i/s
loops | lazy: 1423.7 i/s - same-ish: difference falls within error
partition: 1358.8 i/s - 1.06x slower
partition lazy: 814.2 i/s - 1.76x slower
オタク心の向くままに追いかけてみたこの結果から、どんな学びを得られたでしょうか？
- 読みやすくするための最適化は「あり」
- 最適化を試すときはベンチマークを「正確に」行うことが重要
- Rubyは楽しい
- こういう問題に出会うと、つい夢中になってしまう
概要
元サイトの許諾を得て翻訳・公開いたします。
日本語タイトルは内容に即したものにしました。