2020年1月12日に発行したチケットと、その実装である Pull-Request が2020年2月10日に ruby/ruby のtrunkにマージされました。

以下、そのPRの内容などについて述べます。

背景

クックパッド株式会社の夏インターンシップに参加した際、InstructionSequence (ISeq) のバイナリ表現を改善しました。 上記チケットはその出力機能の速度改善に関するものです。

問題点

ISeqのバイナリシリアライザは、内部で命令列やオブジェクトなどをバイナリ列に変換するのですが、 その際に同一のオブジェクトが複数回 (無駄に) 出力されないよう、内部でオブジェクトの重複排除が行われています。

既存の実装では、その重複排除はオブジェクトの格納された配列を線形探索することで実現されていました (該当部分)。 この実装では、.rbファイルに含まれるオブジェクトの数が多いほど (≒ .rbファイルが大きいほど) バイナリの出力にかかる時間が増加します。

実際に、Railsなどでも用いられている mail gem は Ragel を用いて各種パーザを自動生成しているため、その内部にとても巨大な構文解析テーブルを複数持っています。 もっとも巨大なものである address_lists_parser.rb は数十万要素からなるテーブルによって構成されているため、それをバイナリに出力する際にはとてつもなく非効率的な操作が行われていたことになります。

実装

配列の線形探索ではなくハッシュテーブルを用いることで効率的に重複排除を行う変更を提案しました。

また、@XrXr さんの指摘に基づいて、配列とハッシュテーブルの両方を用いていた実装を改め、 ハッシュテーブルのみを利用するように変更しました。

パフォーマンスの変化などは上記チケットを参照してください。