配列とEnumerable,どちらが高速?
問題
いくつかのrubyコードに対して実行時間を計測する.
require 'benchmark' # p `ruby -v` foo = (1..5050505) [ 'foo.reduce(:+)', 'foo.to_a.reduce(:+)', 'foo.to_a.reverse.reduce(:+)', 'foo.each.reduce(:+)', 'foo.each.to_a.reduce(:+)', 'foo.reverse_each.reduce(:+)', 'foo.reverse_each.to_a.reduce(:+)' ].each do |e| puts e p Benchmark.realtime { eval(e) } end
どのコードが高速で,どのコードが低速だろうか?
予想
foo.to_a.reduce(:+)
は低速だろう.Range(1..3030303)
を 一度配列化するため,3030303*8byteのメモリを確保する手間が掛かるから.foo.to_a.reverse.reduce(:+)
はさらに低速だろう.配列化した上に,reverse操作をしているから.foo.reduce(:+)
とfoo.each.reduce(:+)
は変わらないのでは.reverse_each
を使ったほうが良いのかreverse
使ったほうが良いのか知りたくて実験した
実際には
環境によって結果がころころ変わる.
wandbox
ruby 2.0.0-p648
一番期待通りだった結果から.
foo.reduce(:+) 0.422865207 foo.to_a.reduce(:+) 1.08674423 foo.to_a.reverse.reduce(:+) 1.603410527 foo.each.reduce(:+) 0.383624219 foo.each.to_a.reduce(:+) 0.956897335 foo.reverse_each.reduce(:+) 1.028164733 foo.reverse_each.to_a.reduce(:+) 1.791400497
やっぱり to_a
はインスタンス化するので遅いですね.
reverse_each
が to_a
並に遅いです.each
を使って定義されているとの事なので,配列に一旦押し込んでいるのでしょうか.
ruby 1.8.7-p358
Time Limit Exceedでした. この頃のRuby はやっぱり遅い!
ruby 2.3.3
foo.reduce(:+) 0.43357594311237335 foo.to_a.reduce(:+) 1.233360068872571 foo.to_a.reverse.reduce(:+) 1.7924626003950834 foo.each.reduce(:+) 0.5590240471065044 foo.each.to_a.reduce(:+) 1.1674661748111248 foo.reverse_each.reduce(:+) 1.1371833588927984 foo.reverse_each.to_a.reduce(:+) 1.949059072881937
2.0.0 と変化なし.ただ若干遅いような.
ruby 2.4.3
foo.reduce(:+) 0.4620166979730129 foo.to_a.reduce(:+) 0.5434980448335409 foo.to_a.reverse.reduce(:+) 0.8991025779396296 foo.each.reduce(:+) 0.36869976855814457 foo.each.to_a.reduce(:+) 0.5822492782026529 foo.reverse_each.reduce(:+) 0.8750727437436581 foo.reverse_each.to_a.reduce(:+) 1.2820214964449406
全ての to_a
が早くなりました.foo.to_a.reduce(:+)
と foo.reduce(:+)
で0.1ms
しか違わない.
ruby 2.5.1
foo.reduce(:+) 0.31516589038074017 foo.to_a.reduce(:+) 0.6082005519419909 foo.to_a.reverse.reduce(:+) 1.1273395996540785 foo.each.reduce(:+) 0.32723737694323063 foo.each.to_a.reduce(:+) 0.604427982121706 foo.reverse_each.reduce(:+) 0.9205244313925505 foo.reverse_each.to_a.reduce(:+) 0.6740624848753214
reverse_each.to_a
が早くなってる.to_a
すると早くなるんですね…
ideone
ruby 2.3.3
foo.reduce(:+) 0.2855961509048939 foo.to_a.reduce(:+) 0.39363980293273926 foo.to_a.reverse.reduce(:+) 0.4211822748184204 foo.each.reduce(:+) 0.2322438396513462 foo.each.to_a.reduce(:+) 0.39031748846173286 foo.reverse_each.reduce(:+) 0.38831575214862823 foo.reverse_each.to_a.reduce(:+) 0.5566895194351673
Windows[msys2]
ruby 2.4.3p205
"ruby 2.4.3p205 (2017-12-14 revision 61247) [x64-mingw32]\n"
foo.reduce(:+) 0.6485602000029758 foo.to_a.reduce(:+) 0.3039164000074379 foo.to_a.reverse.reduce(:+) 0.3378013000037754 foo.each.reduce(:+) 0.6483177999907639 foo.each.to_a.reduce(:+) 0.31006479999632575 foo.reverse_each.reduce(:+) 0.9291686000069603 foo.reverse_each.to_a.reduce(:+) 0.5548352999903727
each
より to_a
したほうが早い.何で?
jit
Ruby はどんどん高速化され続けていて,Ruby 2.6ではJIT (Just-in-time) コンパイラが導入されています.(Ruby 2.6.0-preview2 Released) どうなるやら.