Hash Benchmark for mruby

Introduction

mruby における Hash オブジェクトのメモリー使用量を削減することを目的として、Hash オブジェクトのデータ構造を次のように変更しました。

挿入順を保持するエントリーリストをセグメントリストからフラット配列に変更した。
ハッシュバケットのスロットの値をエントリーへのポインターからエントリーリストのインデックスに変更し、ハッシュバケットの容量に応じた可変長ビットで表現するようにした。
エントリーリストやハッシュテーブルの管理情報を可能な限り struct RHash に収めた。

本ベンチマークはこのデータ構造の変更によるメモリー使用量の削減結果と性能への影響を計測したものです。

データ構造の変更による性能への影響をより適切に計測するために、基本的にはそれ以外の変更は行っていません。例えば、以下のような点は変更していません。

Hash サイズが16以下の場合はハッシュテーブルを持たず (エントリーリストを線形探索する) サイズが17からハッシュテーブルを追加する (以降これらの構造の違いをそれぞれ「ハッシュテーブルなし」「ハッシュテーブルあり」と表現することがあります)
エントリーリストの初期容量
ハッシュテーブルの基本性質 (衝突発生時の解決方法やハッシュ関数など)
ハッシュバケットの初期容量/拡大契機/拡大率 (エントリーリストの拡大率は実装上の理由によりやや小さくなっている)

ただし、今回何らかの変更があった箇所については以下の対応を行っている場合もあります。