Performance
性能については、基本的には次のような傾向あります。
- エントリーリストの実装が、Baseline 実装はセグメントリストで New 実装はフラット配列であるため、反復はオーバーヘッドが小さいぶん New 実装のほうがやや速い。
- ハッシュテーブルなしの場合における挿入/参照の性能は反復性能に依存するが、挿入/参照そのものの処理があるぶん性能差がほぼなくなることもある。
- ハッシュバケットの実装が、New 実装はビットセットであるため、挿入/参照はオーバーヘッドが大きいぶん New 実装のほうが遅い。
- Ruby メソッドの呼び出しは同機能の C API の呼び出しよりもオーバーヘッドが大きいきいため遅い。これは、Rubyメソッドのほうが C API よりも性能差が小さくなるということでもある。
機能や計測条件によっては別な傾向を示す場合があります。それらは以降で考察します。
なお、今回は改造による性能差をより適切に計測できるよう、改造部分以外のオーバーヘッドを小さくするために Hash のキーはすべて整数を使用しています。しかし、現実には整数キーを使用することは少なく、シンボルキーか文字列キーを使うことが多いと思います。シンボルキーの場合はおそらく同程度の性能差になると思いますが、文字列キーの場合はハッシュ値計算等のオーバーヘッドが大きくなるため、性能差はより小さくなります。
Basic Operations
改造による性能差をより適切に計測するために、挿入/参照/反復の基本操作は C API を直接呼び出して性能を計測します。
mrb_hash_set
空の Hash に N 個のエントリーを mrb_hash_set で挿入した際の、1回あたりの時間 (上図) と総時間 (下図) の計測結果です。
64-bit CPU
1回あたりの時間は、エントリーリストの拡大時を除くと、(ややばらつきがあるものの) ハッシュテーブルなしの場合は両実装とも概ね同等の性能です。ハッシュテーブルありの場合は Hash サイズが50前後までは New 実装のほうが遅く基本傾向の通りですが、Hash サイズが大きくなると New 実装のほうが速くなっています。挿入の場合はハッシュバケットの探索範囲が広い (同一ハッシュ値のスロットを必ずすべて探索する) ため、ハッシュバケットが小さい New 実装はキャッシュに載りやすくヒット率が高いためだと考えています。
エントリーリストの拡大時は、一貫して New 実装がかなり遅いです。エントリーリストの拡大は Baseline 実装は新しいセグメントを malloc で追加し、New 実装は全体を realloc で拡大するという違いがあり、malloc より realloc が高コストなのだと考えています。
総時間は、エントリーリストの拡大時の遅さが原因で Hash サイズが小さいうちは New 実装が遅いですが、1回あたりの時間が速くなりだすと差が詰まり Hash サイズが100前後で逆転しています。
32-bit CPU
32-bit CPU の場合は、1回あたりの時間が New 実装のほうが明確に速くなるということはないようで、Hash サイズ100あたりからばらつきながら両実装が同等の性能になっているようです。これは、32-bit CPU の場合はポインターサイズが4バイトであるため、Baseline 実装でもハッシュバケットのスロットサイズが大きくなくキャッシュに載りやすいためではないかと考えています (これは 64-bit CPU より i/s が大きいこととも整合性があります)。
そのため、総時間は逆転には至らず、0.85倍程度で収束しています。
mrb_hash_get
サイズが N の Hash に対してすべてのキーと1個の存在しないキーを mrb_hash_get で参照した際の、1回あたりの平均時間の計測結果です。
ハッシュテーブルなしの場合は両実装ともほぼ同等の性能で、ハッシュテーブルありの場合は0.7倍から0.8倍程度になっており、基本傾向の通りです。
mrb_hash_foreach
サイズが N の Hash に対して全エントリーを mrb_hash_foreach で反復した時間の計測結果です。
64-bit CPU では New 実装が1.3倍程度には速くなっています。32-bit CPU でも概ねやや速くなっています。ただし、No-boxing では特に Hash サイズが40から100あたりで明確に遅くなっている部分も見られ、この原因は不明です。別な環境での追試ではこのように明確に遅くなる傾向は見られなかったため、計測環境に依存する傾向だと考えていますが、直接的な原因は分かっていません。
Other Operations
基本操作以外は Ruby メソッドの呼び出しにより性能を計測します (基本操作に対応する Ruby メソッドも含みます)。
Hash#[]=
空の Hash に N 個のエントリーを Hash#[]= で挿入した時間の計測結果です。
ハッシュテーブルなしの場合は概ね両実装とも同等の性能です。ハッシュテーブルありの場合は New 実装のほうが遅く Hash サイズが大きくなるにつれ差が広がっています。対応する C API の mrb_hash_set では Hash サイズが大きくなると性能差が収束し、64-bit CPU では逆転していましたがそのような傾向はみられません。これは、Ruby メソッドの呼び出し時は様々なメモリーアドレスにアクセスするため、ハッシュバケットがキャッシュに載りに続け難くなり、New 実装になって計算量が増えたことがそのまま性能低下に反映されていると考えています。
Hash#[]
サイズが N の Hash に対してすべてのキーと1個の存在しないキーを Hash#[] で参照した際の、1回あたりの平均時間の計測結果です。
ハッシュテーブルなしの場合は概ね両実装とも同等の性能で、ハッシュテーブルありの場合は0.85倍前後で対応する C API の mrb_hash_get の性能差より小さくなっており、基本傾向の通りです。
Hash#each
サイズが N の Hash に対して全エントリーを Hash#each で反復した時間の計測結果です。
64-bit No-boxing, 32-bit Word-boxing, 32-bit No-boxing では、両実装ともほぼ同等の性能です。同等の C API である mrb_hash_foreach における性能差が表れていませんが、これは Hash#each は以下の利用によりオーバーヘッドが極めて大きいため、C API の性能差は誤差の範囲になっているためだと考えています。
- Ruby で実装されている。
Hash#keysとHash#valuesの結果に対して反復している。- ブロック呼び出しのコストがとても大きい。
しかし、64-bit Word-boxing と 64-bit NaN-boxing では0.9倍前後になっており理由は不明です。mrb_hash_foreach と同様に別な環境での追試ではこのような傾向は見られなかったため、計測環境に依存する傾向だと考えていますが、直接的な原因は分かっていません。
Hash#delete
サイズが N の Hash に対してすべてのキーと1個の存在しないキーを引数として Hash#delete を呼び出した際の、1回あたりの平均時間の計測結果です。
Baseline 実装ではハッシュテーブルなしの場合もエントリーリストを線形探索していたため計算量は O(N) でしたが、New 実装ではハッシュテーブル探索を行うようにしたため O(1) となり、処理時間は概ね一定になっています。
Hash#shift
サイズが N の Hash に対して N + 1 回 Hash#shift を呼び出した際の、1回あたりの平均時間の計測結果です。
Hash#shift で取り除かれる先頭エントリーの探索はエントリーリストの線形探索であるため、ここでの計測方法の場合は Hash サイズが増えると (先頭の削除済み要素が増えると) 遅くなります。そのため、性能は基本的に反復性能に依存するはずで、全体的に New 実装のほうが速めなので概ねその通りになっているように見えます。ただし、次の点は注意が必要です。
Hashサイズが増えるほど性能差が大きくなっていますがmrb_hash_foreachではそのような傾向は見られません。これは、Hash#shiftを N + 1 回行うと探索を繰り返し行うため性能差が累積されるためだと考えています。Hashサイズが40の場合は New 実装のほうがやや遅い場合もありますが、これは New 実装のほうが計算量が多いためだと考えています。エントリーが削除済みかどうかを、Baseline 実装ではエントリーリストにのみ保持していましたが、New 実装ではハッシュバケットにも保持するようにしたため (ハッシュテーブル探索の際にエントリーが削除済みかどうかをエントリーリストを参照せずに判断できるため探索の効率が良い)、エントリーを取り除く際にハッシュバケットの更新も必要になっています。
Hash#dup
サイズが N の Hash を Hash#dup で複製した時間の計測結果です。
Hash#dup は Baseline 実装では C 実装も用意されていましたが Ruby 実装が使われていたため、New 実装では C 実装を利用するようにしました (単純な memcpy を利用できるようになったためさらに効率的になっています)。そのため、大幅に高速化されています。