Rubyではシフト演算 `1 << k` より配列参照 `lookup[k]` のほうが速い

AtCoderの問題をRubyで復習していて、どうしても時間制限超過（TLE）してしまうものがあった。

他の方の解答を見たりして試しているうちに、どうもシフト演算の実行回数が多いとTLEしやすいということがわかった¹。計算したいのは 1 << k という単純なもの（を最大3000万回ほど）なので、これを事前に計算しておき配列参照 lookup[k] に置き換えたところ無事に通過した。

そんなに速度差があるのか気になったので、ベンチマークしてみた。

ベンチマーク

AtCoderのコードテストを利用。その結果、配列参照のほうが約1.3倍速く、3000万回計算すると0.3秒ほど短くなった。

shift-vs-lookup.rb

puts RUBY_DESCRIPTION
puts

require 'benchmark'

n = 30
lookup = Array.new(n) { |i| 1 << i }

m = 30_000_000
ary = Array.new(m) { rand(n) }

Benchmark.bmbm do |x|
	x.report("shift")  { ary.each { |k| 1 << k } }
	x.report("lookup") { ary.each { |k| lookup[k] } }
end

標準出力

ruby 2.7.1p83 (2020-03-31 revision a0c7c23c9c) [x86_64-linux]

Rehearsal ------------------------------------------
shift    1.528244   0.000037   1.528281 (  1.528378)
lookup   1.152500   0.000020   1.152520 (  1.152588)
--------------------------------- total: 2.680801sec

             user     system      total        real
shift    1.260826   0.000017   1.260843 (  1.260900)
lookup   0.958101   0.000000   0.958101 (  0.958157)

1. 他の演算なども遅い可能性はあるが、削減しやすいのはシフト演算だけだった。 ↩