ハッシュは頻繁に参照する値を最後に入れると高速
明日から RubyKaigi なので、ちょっとした小ネタを一つ。
例えば、0 から 9999 までをハッシュに順に入れます。
h = {}
10000.times do |n|
h[n] = true
end
このとき、h[9998] や h[9999] は、h[0] や h[1] より高速です。
どのくらい高速かというと、
1_000_000_000.times { h } # 40.8 sec (ループ自体の速度)
1_000_000_000.times { h[9999] } # 57.2 sec
1_000_000_000.times { h[0] } # 89.1 sech[0] は 89.1 - 40.8 = 48.3 nsec 、h[9999] は 57.2 - 40.8 = 16.4 nsec ということになります。なんと 3 倍も速い。*1
なぜこんなことが起きるのか
ハッシュの実装に起因します。Ruby のハッシュは closed hashing とか separate chaining とかいうやつで、同じビンに入れることになった要素をリンクリストでつないで格納します。（Wikipedia の図解）
後から入れた要素は、リストの最後に連結するのではなく、先頭に割り込ませます。つまり、最近入れた要素はリストの最初の方に来ることになります。参照の際はリストを前からたどるので、最近入れた要素ほど早く発見される。
このリンクリストは放っておくとドンドン長くなるので、ある程度長くなったら rehash します。Ruby の場合、要素の数がビンの大きさに対して 5 倍を超えたときに rehash をします。例えばビンの大きさが 2048 のとき、要素数が 10240 を超えると rehash します。
冒頭の例は要素数 10000 で、ぎりぎり rehash していない状態です *2 。そういうハッシュにおいては、リンクリストの長さの平均は 5 なので、最初に入れた 0 を発見するには、期待値としてリンクリストを 2.5 回程度たどることになります（最近挿入された要素が先頭にある可能性が高いので、実際にはもう少し多くなる）。一方、最後に入れた 9999 はほぼ確実にリンクリストの先頭にあるので、リンクリストをたどる回数は 1 です。この差が現れていると思われます。
「5 倍という閾値が高すぎる」という話はたまに聞きます。かといって安易に閾値を下げると、頻繁に rehash が起きることのオーバーヘッドやメモリの無駄遣いが起きます。ユースケースごとに最適な閾値は変わるでしょう。評価が難しい。
応用：case 文の高速化
追記：この節に書いてあることはさっそく古くなりました。この記事を受けて、内部的なハッシュを rehash するようになったようです。
Ruby の case 文は when 節を上から順にマッチするか調べていきますが、when 節が全部リテラルの場合、内部的にハッシュを作ってジャンプテーブルみたいに実行するよう最適化されます。ここにもハッシュがあるので、同じ問題が起きます。*3
例えば、以下のようなコードを考えます。
100000000.times do case 0 when 0 do_something when 1, 2, 3, ..., 10000 raise end end
省略してますが、実際には全部の数字を書き下しています。*4
残念ながらこのコードは遅いです。以下のように書き換えましょう。
100000000.times do case 0 when 1, 2, 3, ..., 10000 raise when 0 do_something end end
when 節の順番を入れ替えただけです。こうすることで、0 が最後にハッシュに格納されます。参照するのは 0 ばかりなので、高速です。測ってみると、case の処理だけ見れば 2 倍程度早かったです。まあ、Integer#times の方が遅いですが。
何かのバイトコードインタプリタみたいなのを作るとき、こういう巨大な case 文を書きたくなり、しかも実行速度が大切です *5 。そういう状況において、頻繁に実行される when 節を後ろの方に持っていく、という工夫が考えられます。
case 文の最適化を考えなければ、頻繁に実行される when 節は上の方に置いた方が効率的なので、そう思って上に置いてる人は逆に損してることになりますね。皮肉なものです。
本当に言いたかったこと
Ruby でこういう小手先の高速化とか考えるのは不毛だからやめた方がいいと思います。よかれと思ってやったことが、いつの間にか逆効果になってたり、ひどいと動かなくなったりします。（関連)
ここに書いたことも、いつ傾向が逆になってもおかしくないです。Ruby ではアルゴリズムレベルの高速化だけに集中すべき。それでどうしてもしょうがない場合には、普通に他の速い言語に移行すべきだと思います。でも、アルゴリズムレベルの最適化の余地って思ったより残ってるものですよ。
なお、不毛を不毛とわかった上で楽しんでやるのはアリかもしれない。