ar_table の話（もっと良い提案を募集します）
Hash なのに Hash 値を使わない O(n) な Hash table
いきなり色々すっ飛ばして、hash.c に定義してある ar_table の話をする。
話の前提は Ruby 2.6 の改善を自慢したい - クックパッド開発者ブログ にまとめた transient heap。この話は今後、ここでもちゃんとまとめたい。theap の話は、本記事には直接関係しない。
簡単に言うと、ar_table は、Hash を実装するためのデータ構造であり、8 要素に限定した連想配列。8要素以上であれば、st_table を使う（これも、今後紹介する）ようにするので、とりあえず 8 要素以下の Hash オブジェクトのための特殊なデータ構造、と考えて欲しい。線形探索を行うので、探索コストは O(n)。
Hash の要素は key, value の2要素、に加えて key のハッシュ値の3要素。
それを格納するのが ar_table_entry (https://github.com/ruby/ruby/blob/ruby_2_6/internal.h#L816)。
typedef struct ar_table_entry {
VALUE hash;
VALUE key;
VALUE record;
} ar_table_entry;
VALUE はまだ紹介していないけど、オブジェクトへのポインタ。ちなみに、ハッシュ値を格納する hash が VALUE なのはバグで（実害はない）、本当は単なる数値であるべき。trunk では直っている。value が record なのは、単なる趣味だと思う（元にした実装があるんです、多分）。
ar_table は、見てわかるように ar_table_entry の配列 (https://github.com/ruby/ruby/blob/ruby_2_6/internal.h#L822)。
typedef struct ar_table_struct {
ar_table_entry entries[RHASH_AR_TABLE_MAX_SIZE];
} ar_table;
凄い古典的な連想リストとして実装。探索 (lookup) を疑似 ruby コードで実装すると、こんな感じ：
def lookup(table, key) hash_value = key.hash table.size.times do |i| if table.entries[i].hash == hash_value && table.entries[i].key == key return table.entries[i].record end end raise not_found end
要するに、最初から辿っていく、というもの。挿入 (insert) は、空いてるエントリに key, value, ハッシュ値をセットするだけの、そのまんまなので省略。
削除 (delete) はちょっとだけ考えなければならなくて、
- compaction する（後ろにあるエントリを詰める。削除時、ちょっと時間がかかるかもしれないが、8要素フルに使える）
- skip エントリを入れておく（消されたのでスキップとする。ちょっとエントリが無駄になる）
の2つの選択肢がある。MRI 2.6 では、後者 skip エントリを入れるという実装になっている。今考えてみると、前者でも良かったかもしれない（delete よりも lookup のほうが圧倒的に多そうだし。実装が圧倒的に簡単になるし...。今から変えようかな。
なお、skip エントリかどうかは、ar_table_entry::hash に RESERVED_HASH_VAL が入っているかどうかでチェックしている(https://github.com/ruby/ruby/blob/ruby_2_6/hash.c#L349)。
insert は翻って、8要素全部使っているが skip が含まれているなら compaction してから insert を行う (https://github.com/ruby/ruby/blob/ruby_2_6/hash.c#L677)。
これでアルゴリズムの詳細の説明が終わった。Hash テーブルといいながら、8要素以下であれば、単なる線形探索を行う O(n)。ただし、n <= 8 なので、探索時間なんてたいしてかからないだろう、というのが、実装当初の意図。ただ、本当に O(n) でいいの？
Hash なんだから、Hash 値を使って O(1) にしよう
たかだか8要素、されど8要素、ということで、8要素のハッシュ表をオープンアドレッシングで教科書通り作ってみる。
用語があやふやなので ハッシュテーブル - Wikipedia の用語を利用してみる。
ルート配列を用意しなければならない。そこで、8 エントリを 7 エントリにすることで、その空いた領域をルート配列にしよう。64bit CPU の場合は 8 x 3 = 24B だった。さて、ルート配列をどれくらい用意しよう。
7 要素なので、index は 3 bit あれば足りる。キリが良く 4 bit にしておこう。どれくらいのルート配列の長さがあれば良いか。とりあえずエントリ数の2倍 14、ちょっとキリが悪いので、16 エントリにしてみよう。すると、4bit * 16 = 64bit = 8B。まぁ、こんなもんだろう。8B にルート配列を突っ込めば良さそう。
と思って作ったのがこちら https://github.com/ko1/ruby/compare/hash_ar
さて、どれくらい速くなったかな、わくわく、ということで、ベンチマークを用意してみた。
require_relative 'benchmark/lib/load'
Benchmark.driver(repeat_count: 5){|x|
x.executable name: 'clean', command: %w'../clean-trunk/miniruby'
x.executable name: 'modify', command: %w'./miniruby'
10.times{|i|
x.prelude %Q{h#{i} = { #{i.times.map{|j| "#{j+1} => #{j+1}, "}.join } }}
}
[100, :symbol, 's', 'short_str', 'long ' * 100 + 'str'].each{|key|
10.times{|i|
x.report "x = h#{i}[#{key.inspect.to_s[0..10]}]", %Q{x = h#{i}[#{key.inspect}];}
}
}
[100, :symbol, 's', 'short_str', 'long ' * 100 + 'str'].each{|key|
10.times{|i|
x.report "h#{i}[#{key.inspect.to_s[0..10]}] = true", %Q{h#{i}[#{key.inspect}] = true;}
}
}
}
何をやっているかというと、要素数が 0～9 のハッシュ h0～h9 までを用意し、それぞれに対して、いろいろなキーで (1) 表引き（x = h0[100] のように。ただし、エントリは存在しない）、(2) セット（h0[100] = true のように。2度目以降は存在するキーに対してセット）を行う。
clean がパッチ適用前の MRI trunk で、modify が適用後。
実行結果（全データ、5回計測し、最良値）：
# 表から取得（存在しないキーについて）
clean modify
x = h0[100] 71.382M 68.264M i/s - 111.733M times in 1.565281s 1.636780s
x = h1[100] 64.569M 65.207M i/s - 103.362M times in 1.600807s 1.585127s
x = h2[100] 58.040M 70.716M i/s - 100.978M times in 1.739816s 1.427940s
x = h3[100] 57.785M 64.796M i/s - 99.286M times in 1.718206s 1.532288s
x = h4[100] 53.154M 65.509M i/s - 95.571M times in 1.798011s 1.458906s
x = h5[100] 52.951M 64.176M i/s - 94.424M times in 1.783222s 1.471311s
x = h6[100] 50.729M 63.956M i/s - 94.091M times in 1.854785s 1.471170s
x = h7[100] 52.343M 64.688M i/s - 94.679M times in 1.808842s 1.463625s
x = h8[100] 48.283M 59.181M i/s - 80.856M times in 1.674611s 1.366249s
x = h9[100] 59.493M 65.898M i/s - 103.146M times in 1.733747s 1.565252s
x = h0[:symbol] 71.649M 76.317M i/s - 111.117M times in 1.550855s 1.455993s
x = h1[:symbol] 66.340M 72.472M i/s - 106.463M times in 1.604811s 1.469017s
x = h2[:symbol] 61.781M 67.467M i/s - 104.569M times in 1.692584s 1.549918s
x = h3[:symbol] 59.895M 67.812M i/s - 101.895M times in 1.701233s 1.502618s
x = h4[:symbol] 58.011M 68.718M i/s - 79.001M times in 1.361837s 1.149642s
x = h5[:symbol] 54.835M 67.058M i/s - 83.361M times in 1.520197s 1.243109s
x = h6[:symbol] 51.676M 69.619M i/s - 95.163M times in 1.841535s 1.366927s
x = h7[:symbol] 51.936M 66.584M i/s - 91.941M times in 1.770270s 1.380817s
x = h8[:symbol] 52.347M 63.100M i/s - 94.175M times in 1.799060s 1.492460s
x = h9[:symbol] 61.492M 61.434M i/s - 97.341M times in 1.582983s 1.584480s
x = h0["s"] 52.246M 47.940M i/s - 90.479M times in 1.731800s 1.887331s
x = h1["s"] 45.926M 47.301M i/s - 66.259M times in 1.442724s 1.400785s
x = h2["s"] 44.499M 47.372M i/s - 85.578M times in 1.923133s 1.806515s
x = h3["s"] 45.103M 47.777M i/s - 85.701M times in 1.900123s 1.793763s
x = h4["s"] 43.234M 47.875M i/s - 74.151M times in 1.715084s 1.548830s
x = h5["s"] 42.249M 47.268M i/s - 79.976M times in 1.892973s 1.691973s
x = h6["s"] 41.281M 47.383M i/s - 81.115M times in 1.964935s 1.711905s
x = h7["s"] 40.827M 43.986M i/s - 58.734M times in 1.438612s 1.335291s
x = h8["s"] 39.907M 43.387M i/s - 79.366M times in 1.988796s 1.829248s
x = h9["s"] 41.744M 42.676M i/s - 83.145M times in 1.991773s 1.948295s
x = h0["short_str"] 46.725M 45.238M i/s - 88.081M times in 1.885112s 1.947063s
x = h1["short_str"] 44.019M 43.855M i/s - 84.102M times in 1.910584s 1.917716s
x = h2["short_str"] 42.807M 44.158M i/s - 80.763M times in 1.886661s 1.828943s
x = h3["short_str"] 42.550M 44.119M i/s - 82.935M times in 1.949125s 1.879820s
x = h4["short_str"] 40.764M 44.179M i/s - 78.123M times in 1.916487s 1.768325s
x = h5["short_str"] 40.123M 44.326M i/s - 78.880M times in 1.965977s 1.779536s
x = h6["short_str"] 39.368M 44.127M i/s - 77.492M times in 1.968403s 1.756120s
x = h7["short_str"] 39.351M 43.959M i/s - 78.870M times in 2.004282s 1.794183s
x = h8["short_str"] 37.973M 40.953M i/s - 76.933M times in 2.025977s 1.878552s
x = h9["short_str"] 40.919M 40.928M i/s - 80.092M times in 1.957326s 1.956906s
x = h0["long long ] 7.609M 7.583M i/s - 20.516M times in 2.696223s 2.705468s
x = h1["long long ] 7.549M 7.532M i/s - 20.622M times in 2.731816s 2.737974s
x = h2["long long ] 7.522M 7.531M i/s - 20.596M times in 2.737924s 2.734750s
x = h3["long long ] 7.492M 7.531M i/s - 20.516M times in 2.738329s 2.724281s
x = h4["long long ] 7.487M 7.534M i/s - 20.238M times in 2.703273s 2.686341s
x = h5["long long ] 7.444M 7.500M i/s - 19.177M times in 2.576132s 2.557040s
x = h6["long long ] 7.425M 7.533M i/s - 20.351M times in 2.740651s 2.701387s
x = h7["long long ] 7.397M 7.530M i/s - 20.290M times in 2.743029s 2.694600s
x = h8["long long ] 7.387M 7.440M i/s - 20.270M times in 2.743931s 2.724420s
x = h9["long long ] 7.503M 7.444M i/s - 20.052M times in 2.672382s 2.693812s
# セット
h0[100] = true 46.083M 42.413M i/s - 83.860M times in 1.819765s 1.977203s
h1[100] = true 43.511M 42.373M i/s - 84.211M times in 1.935364s 1.987362s
h2[100] = true 41.062M 42.208M i/s - 81.507M times in 1.984945s 1.931053s
h3[100] = true 39.654M 42.213M i/s - 77.406M times in 1.952063s 1.833701s
h4[100] = true 39.428M 42.478M i/s - 74.194M times in 1.881773s 1.746667s
h5[100] = true 42.973M 42.265M i/s - 80.608M times in 1.875779s 1.907174s
h6[100] = true 40.662M 42.281M i/s - 76.306M times in 1.876611s 1.804727s
h7[100] = true 38.067M 40.084M i/s - 70.484M times in 1.851591s 1.758405s
h8[100] = true 48.033M 47.918M i/s - 89.954M times in 1.872740s 1.877238s
h9[100] = true 48.293M 47.340M i/s - 89.425M times in 1.851723s 1.888990s
h0[:symbol] = true 43.157M 42.848M i/s - 78.601M times in 1.821269s 1.834401s
h1[:symbol] = true 43.926M 45.265M i/s - 88.841M times in 2.022519s 1.962692s
h2[:symbol] = true 41.430M 42.967M i/s - 82.082M times in 1.981232s 1.910365s
h3[:symbol] = true 40.009M 42.854M i/s - 80.231M times in 2.005313s 1.872203s
h4[:symbol] = true 39.538M 43.023M i/s - 77.901M times in 1.970253s 1.810694s
h5[:symbol] = true 41.638M 42.950M i/s - 75.416M times in 1.811218s 1.755912s
h6[:symbol] = true 38.124M 42.889M i/s - 67.325M times in 1.765961s 1.569744s
h7[:symbol] = true 37.903M 42.646M i/s - 76.329M times in 2.013815s 1.789841s
h8[:symbol] = true 48.710M 44.633M i/s - 80.689M times in 1.656528s 1.807852s
h9[:symbol] = true 51.595M 45.664M i/s - 90.569M times in 1.755380s 1.983365s
h0["s"] = true 35.082M 35.235M i/s - 68.348M times in 1.948236s 1.939793s
h1["s"] = true 34.785M 34.682M i/s - 69.035M times in 1.984618s 1.990507s
h2["s"] = true 34.107M 34.471M i/s - 65.289M times in 1.914228s 1.894018s
h3["s"] = true 33.682M 34.424M i/s - 68.677M times in 2.039002s 1.995034s
h4["s"] = true 32.591M 34.496M i/s - 69.715M times in 2.139110s 2.020991s
h5["s"] = true 32.173M 33.911M i/s - 63.276M times in 1.966719s 1.865913s
h6["s"] = true 32.307M 34.608M i/s - 66.085M times in 2.045527s 1.909525s
h7["s"] = true 31.360M 31.992M i/s - 67.392M times in 2.149006s 2.106543s
h8["s"] = true 33.849M 33.663M i/s - 71.534M times in 2.113358s 2.124989s
h9["s"] = true 33.690M 33.655M i/s - 68.199M times in 2.024321s 2.026436s
h0["short_str"] = true 33.163M 32.519M i/s - 70.550M times in 2.127370s 2.169500s
h1["short_str"] = true 32.358M 32.684M i/s - 67.495M times in 2.085887s 2.065060s
h2["short_str"] = true 32.791M 32.503M i/s - 68.566M times in 2.091024s 2.109524s
h3["short_str"] = true 31.632M 32.729M i/s - 66.508M times in 2.102565s 2.032062s
h4["short_str"] = true 30.384M 32.541M i/s - 66.774M times in 2.197653s 2.052010s
h5["short_str"] = true 30.526M 32.531M i/s - 66.923M times in 2.192355s 2.057222s
h6["short_str"] = true 31.069M 32.508M i/s - 64.041M times in 2.061248s 1.969987s
h7["short_str"] = true 29.933M 30.252M i/s - 64.463M times in 2.153544s 2.130880s
h8["short_str"] = true 31.347M 31.222M i/s - 67.977M times in 2.168574s 2.177243s
h9["short_str"] = true 31.765M 31.263M i/s - 61.937M times in 1.949834s 1.981173s
h0["long long ] = true 7.173M 7.168M i/s - 19.712M times in 2.747900s 2.749936s
h1["long long ] = true 7.155M 7.166M i/s - 19.670M times in 2.749118s 2.744699s
h2["long long ] = true 7.123M 7.159M i/s - 18.257M times in 2.563142s 2.550164s
h3["long long ] = true 7.115M 7.161M i/s - 19.520M times in 2.743328s 2.725762s
h4["long long ] = true 7.081M 7.162M i/s - 19.297M times in 2.725344s 2.694446s
h5["long long ] = true 7.059M 7.151M i/s - 19.410M times in 2.749527s 2.714388s
h6["long long ] = true 7.048M 7.163M i/s - 19.428M times in 2.756493s 2.712289s
h7["long long ] = true 7.040M 7.043M i/s - 19.244M times in 2.733740s 2.732542s
h8["long long ] = true 7.190M 7.181M i/s - 19.782M times in 2.751245s 2.754663s
h9["long long ] = true 7.186M 7.179M i/s - 18.897M times in 2.629533s 2.632356s
なんというか、正直ぱっとしない。
x = h0[100] 71.382M 68.264M i/s - 111.733M times in 1.565281s 1.636780s
x = h1[100] 64.569M 65.207M i/s - 103.362M times in 1.600807s 1.585127s
x = h2[100] 58.040M 70.716M i/s - 100.978M times in 1.739816s 1.427940s
x = h3[100] 57.785M 64.796M i/s - 99.286M times in 1.718206s 1.532288s
x = h4[100] 53.154M 65.509M i/s - 95.571M times in 1.798011s 1.458906s
x = h5[100] 52.951M 64.176M i/s - 94.424M times in 1.783222s 1.471311s
x = h6[100] 50.729M 63.956M i/s - 94.091M times in 1.854785s 1.471170s
x = h7[100] 52.343M 64.688M i/s - 94.679M times in 1.808842s 1.463625s
x = h8[100] 48.283M 59.181M i/s - 80.856M times in 1.674611s 1.366249s
x = h9[100] 59.493M 65.898M i/s - 103.146M times in 1.733747s 1.565252s
これを見ると、clean では、エントリ数に比例してちょっと遅く案っている（O(n)）んだけど... modify のほう、O(1) といわれればそんな気もするんだけど、もうちょっと速いままにならないかな...。ルート配列を一度アクセスする分、どーしょーもないかなー。
ご意見募集
というわけで、スゲー単純なデータ構造の話なんだけど、もうちょっと「ぱっとした」値になりそうな気がするので、もしよかったら教えてください。アセンブラで AVX とかの命令使ってもいいけど、ほとんどのバイナリで使えなくなる可能性があるので、ちょっと...。
8要素とか、そういう単位なので、何かカッコいい方法が知られてるんじゃないかと期待しています。
ちなみに、8要素だと 8B * 3 * 8 = 192B かかるんだけど、これをもっと圧縮する何か素敵なアイディアがあれば...。これはさすがに無いかなー。hash値を 32bit しか格納しない（eql? されるかもしれない回数が増える）、とかくらいか。それでも 4B * 8 = 32B しか浮かない。いや、しかってだけでもないか。
なんというか、とてもショーモナイ話だし、実際ここが2倍に高速化しても、あまり実アプリでは意味ないんだけど...。弄りやすくはあります。
既存研究
- hash 値だけを先頭に集めれば線形探索速いよね？
- trunk に比べて速くなる場合があることは確認しているが、O(1) に比べてどうか？
- ブルームフィルタはどう？
- 結果ほとんど見えなかった
