Hash オブジェクトの内部データ構造が更新されていました

CRuby の開発リポジトリの trunk へ、 1 月間前の2016年11月7日にハッシュ法の新しい実装がマージされました。

CRuby trunk st.c ⇒ Introduce table improvement by Vladimir Makarov <vmakarov@redhat.com>. · ruby/ruby@7577515 · GitHub

開発ブランチ ⇒ GitHub - vnmakarov/ruby at hash_tables_with_open_addressing

オリジナルの st.c のハッシュ表はチェイン法で、 チェインの各エントリを小さなオブジェクトとして記憶割り当てするやりかたになっていました。 このエントリはハッシュ法のチェインとは独立にエントリの登録順に連なる双方向リストにもなっていました。 CRuby の Hash オブジェクトを inspect したり each でなぞると登録順に並ぶのはそのためです。

11月にマージされた新しい実装のソース・ファイル名は st.c のままで、 オリジナルのクレジットも残されていますが、 中身はアルゴリズムもデータ構造も一新されて別物になりました。 エントリは大きな配列ベクタに格納順に並べられて Array オブジェクトの内部配列に似た方式へ変わってます。 これは添字アクセスなしの push、 shift、 delete、 each が可能な Array の機能限定版のような感じですが、 途中のエントリを delete すると削除マークをエントリに書き込み、 each でスキップします。 エントリへの索引は、 オープン・アドレス法へアルゴリズムが変更になっています。

オープン・アドレス法は、 mruby の Hash オブジェクトの内部実装にも採用されていました。 ですが、 mruby ではオープン・アドレスのハッシュ表へ直接エントリを書き込んでおり、 エントリには登録順のリスト情報がなかったため、 each をおこなうと登録順ではなく、 ハッシュ表内での出現順でエントリをリストアップしていました。 mruby はフットプリントを抑えるために、 新しい st.c のハッシュ検索表と配列ベクタを組み合わせる方式へ今後変えるのかどうかわかりませんが、 可能性はありそうです。