簡潔ビットベクトルでRubyをlog N倍速くした

技術部のフルタイムRubyコミッタの遠藤（@mametter）です。昨日の Hackarade #04 の開催報告に続き、2日連続で記事を投稿します。

今回は、ある条件下でのRubyの実行速度を高速化した話を紹介します。この改善はすでにMRIの先端にコミットされていて*1、年末リリース予定のRuby 2.6に含まれる予定です。

ひとことで言うと、「簡潔ビットベクトルを索引に使うことで、プログラムカウンタから行番号を計算するアルゴリズムをO(log N)からO(1)に改善した。これにより、TracePoint有効時やコードカバレッジ測定下で、長さ N のメソッドの実行が O(N log N) から O(N) に高速化される」ということです。順に説明します。

背景：Rubyのバイトコードの構造

この最適化を理解するにはまず、Rubyのバイトコードのある特徴を知る必要があります。

たとえば

x = :foo
y = :bar
z = :baz

というRubyプログラムは、概念的には次のようなバイトコードになります。

PC	命令	行番号
0000	putobject :foo	1
0002	setlocal x
0004	putobject :bar	2
0006	setlocal y
0008	putobject :baz	3
0010	setlocal z

PCはプログラムカウンタ、putobjectはオブジェクトをスタックにpushする命令、setlocalはスタックのトップを指定変数に代入する命令です。ソースコードの行番号を保持しているのがポイントです。行番号の情報は、例外発生時のバックトレースや、コードカバレッジの測定などで必要になります。

ここで注目してほしいのは、行番号の情報は一部の命令だけが持っているということです（他に、TracePointのイベントタイプも、一部の命令だけが保持します）。そのため、このバイトコードをそのままメモリに保持すると、無駄が生じることになります*2。そこで、RubyのVMはこのテーブルを「命令列」と「命令情報テーブル」という2つのテーブルに分解して保持しています。

PC	命令
0000	putobject :foo
0002	setlocal x
0004	putobject :bar
0006	setlocal y
0008	putobject :baz
0010	setlocal z

図↑：命令列

図↓：命令情報テーブル

PC	行番号
0000	1
0004	2
0008	3

命令情報テーブルは、行番号のある命令の分しか情報を保持しないので、余計なメモリを消費しません。

性能の問題

メモリ消費量を減らすことはできましたが、実際に行番号を調べる必要が生じたとき、命令情報テーブルを表引きする必要があります。この表引きは、Ruby 2.4は線形探索でO(N)、Ruby 2.5は二分探索に改善してO(log N)でした。

この表引きが定数時間でないために、行番号やTracePointイベントフラグを頻繁に参照するような状況下（たとえばTracePoint有効下）で、ちょっとびっくりする性能特性が生まれます。次の図は、ローカル変数への代入をN回やるだけのN行のメソッドを、TracePoint有効下で実行するのにかかる時間を測定した結果です。

N行のメソッドの実行にかかる時間が非線形になっていることがわかります。10000行もあるようなメソッドを書くことは（自動生成を除けば）稀なので、あまり問題になっていませんでしたが、直観的な挙動とは言えません。このようになるのは、N行のメソッドはO(N)個の命令からなり、線形探索（Ruby 2.4）だと命令ごとにO(N)の表引きが行われるので、メソッドの実行全体ではO(N ^ 2)の時間がかかるためです。二分探索（Ruby 2.5）は圧倒的に改善していますが、まだO(N log N)で、線形にはなっていません。

今回は、さらなる最適化として、命令情報テーブルに「簡潔ビットベクトル」を索引としてもたせることで、表引きを定数時間に改善しました。これにより、N行のメソッドの実行にかかる時間がO(N)という、当たり前の期待を達成することができます。

簡潔ビットベクトルとは

簡潔ビットベクトルは、ビットの列を表すデータ構造です。

インデックス	0	1	2	3	4	5	6	7	8	9	...
ビット列　　	1	0	1	0	0	1	0	0	1	0	...

図：ビットベクトルの例

インデックスが0..nの間にある1の数を数える操作をrank(n)と言います。上のビット列で考えると、たとえばrank(2)=2、rank(5)=3、rank(9)=4です。

ただのビット列では、rank(n)を計算するためにO(n)の時間がかかります。しかし簡潔ビットベクトルはとてもかしこいので、rank(n)の問い合わせに定数時間で応えてしまいます。そのために、少し補助データを持つ必要がありますが、そのサイズはビット列自体の20%から25%程度です（ただのビット列に比べると、1.25倍のメモリ消費）。*3

このように、補助データをほとんど使わずに（漸近的にo(n)の補助データで）高速に問い合わせに応えることができるデータ構造を、簡潔データ構造といいます。簡潔ビットベクトルは、簡潔データ構造の最も基本的なものです。簡潔データ構造をうまく使うと、高速全文検索や、圧縮データを展開せずに検索するアルゴリズムなどの応用があります。具体的な実装方法や応用を詳しく知りたい方は、今年発売された『簡潔データ構造』（定兼邦彦 著）などをご参照ください。

簡潔ビットベクトルによる命令情報テーブルの表引き

簡潔ビットベクトルを用いることで、命令情報テーブルの表引きをO(1)にする方法を説明します。命令情報テーブルを再掲します。

PC	行番号
0000	1
0004	2
0008	3

図：命令情報テーブル

PCのインデックスだけ1になった簡潔ビットベクトルを作ります。この例だと、PCは0000、0004、0008なので、"10001000100.."というビット列を簡潔ビットベクトルで表現します。これが索引になります。

インデックス	0	1	2	3	4	5	6	7	8	9	10	...
ビット列　　	1	0	0	0	1	0	0	0	1	0	0	...

図：簡潔ビットベクトルによる命令情報テーブルの索引

あるPCに対応する行番号を得たいときは、rank(PC)を計算します。たとえば0004だったら、rank(4) = 2になります。この値は、命令情報テーブルの上から2番目の行（行番号は2）であることを表しています。PC=0008だったらrank(8) = 3なので、上から3番目の行（行番号は3）になります。簡潔ビットベクトルのrank操作はO(1)なので、命令情報テーブルの表引きが定数時間でできることになります。

簡潔ビットベクトルの分だけメモリ使用が増えることが心配になるかもしれません。しかし、この最適化によって命令情報テーブルからPCの列を消すことができる（二分探索ではPCの情報が必要だった）ので、結果的にはだいたい相殺されます。

実験

N行のメソッドをTracePoint有効下で実行するのにかかる時間を測定した結果が次の図です。

図：線形探索→二分探索→簡潔ビットベクトル

線形探索→二分探索ほどの大きな改善ではありませんが、行数が大きくなったときに二分探索を凌駕していることがわかります。

メモリ使用量に変化がないことも確かめるため、cookpadのWebアプリのソースコードをすべてバイトコードにコンパイルしたときのインタプリタのメモリ使用量を測定しました。実行のたびにブレが発生するので、それぞれ1000回実行したときの頻度を取ってみました。

• RubyVM::InstructionSequence.compile_fileで測定。
• /usr/bin/time -f %M kbで測定。

とくにメモリ使用量の傾向が変わっていないことがわかると思います。

まとめ

簡潔ビットベクトルを使って、Rubyの命令情報テーブルの表引き速度を改善しました。これにより、頻繁に命令情報テーブルの表引きを行う条件下での実行（具体的にはTracePoint有効時やコードカバレッジ測定下での実行）が高速化されます。

簡潔データ構造は理論的にも実用的にも非常に興味深い技術で、全文検索やゲノム解析など一部の分野では有名ですが、言語処理系の実装にも活用の可能性があるというのは意外でした*4。みなさんも応用を考えてみるとおもしろいのではないでしょうか。

追記：この話は、クックパッドのフルタイムRubyコミッタである笹田が現状の問題を整理し、遠藤が簡潔ビットベクトルを用いるアイデアを思いつき、笹田が初期の実装を行い、遠藤がそれを改良して実現したものです。フルタイムRubyコミッタが机を並べることでRubyが改良された良い例です。

*1:実は1月にコミットした古いもので、会津大学でのLTイベントで紹介済みだったりもするのですが、記録の意味もこめて記事にしてます。

*2:「ケチな話」と思うかもしれませんが、Rubyではバイトコードのサイズはわりと無視できない関心事のひとつになっています。単なるメモリの無駄遣いというだけでなく、キャッシュを無駄遣いすることになるのでキャッシュミスにつながり、速度低下の原因にもなります。

*3:簡潔ビットベクトルは、n番目の1のインデックスを求めるselect(n)という操作も高速に扱えます。しかし、今回の最適化にselect操作は登場しないので、説明を省略します。

*4:関連研究をご存知の方はぜひ教えてください。