N倍速くした技術部のフルタイムRubyコミッタの遠藤(@mametter)です。開催報告に続き、2日連続で記事を投稿します。今回は、ある条件下でのRubyの実行速度を高速化した話を紹介します。2.6に含まれる予定です。N)からO(1)に改善した。高速化される」ということです。背景:Rubyのバイトコードの構造この最適化を理解するにはまず、Rubyのバイトコードのある特徴を知る必要があります。:bazというRubyプログラムは、概念的には次のようなバイトコードになります。zPCはプログラムカウンタ、putobjectはオブジェクトをスタックにpushする命令、setlocalはスタックのトップを指定変数に代入する命令です。ソースコードの行番号を保持しているのがポイントです。行番号の情報は、例外発生時のバックトレースや、コードカバレッジの測定などで必要になります。ここで注目してほしいのは、行番号の情報は一部の命令だけが持っているということです(他に、TracePointのイベントタイプも、一部の命令だけが保持します)。そのため、このバイトコードをそのままメモリに保持すると、無駄が生じることになります*2。そこで、RubyのVMはこのテーブルを「命令列」と「命令情報テーブル」という2つのテーブルに分解して保持しています。3命令情報テーブルは、行番号のある命令の分しか情報を保持しないので、余計なメモリを消費しません。性能の問題メモリ消費量を減らすことはできましたが、実際に行番号を調べる必要が生じたとき、命令情報テーブルを表引きする必要があります。この表引きが定数時間でないために、行番号やTracePointイベントフラグを頻繁に参照するような状況下(たとえばTracePoint有効下)で、ちょっとびっくりする性能特性が生まれます。次の図は、ローカル変数への代入をN回やるだけのN行のメソッドを、TracePoint有効下で実行するのにかかる時間を測定した結果です。N行のメソッドの実行にかかる時間が非線形になっていることがわかります。10000行もあるようなメソッドを書くことは(自動生成を除けば)稀なので、あまり問題になっていませんでしたが、直観的な挙動とは言えません。2)の時間がかかるためです。N)で、線形にはなっていません。今回は、さらなる最適化として、命令情報テーブルに「簡潔ビットベクトル」を索引としてもたせることで、表引きを定数時間に改善しました。これにより、N行のメソッドの実行にかかる時間がO(N)という、当たり前の期待を達成することができます。簡潔ビットベクトルとは簡潔ビットベクトルは、ビットの列を表すデータ構造です。...図:ビットベクトルの例インデックスが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)にする方法を説明します。命令情報テーブルを再掲します。3図:命令情報テーブルPCのインデックスだけ1になった簡潔ビットベクトルを作ります。この例だと、PCは0000、0004、0008なので、"10001000100.."というビット列を簡潔ビットベクトルで表現します。これが索引になります。...図:簡潔ビットベクトルによる命令情報テーブルの索引あるPCに対応する行番号を得たいときは、rank(PC)を計算します。この値は、命令情報テーブルの上から2番目の行(行番号は2)であることを表しています。3なので、上から3番目の行(行番号は3)になります。簡潔ビットベクトルのrank操作はO(1)なので、命令情報テーブルの表引きが定数時間でできることになります。簡潔ビットベクトルの分だけメモリ使用が増えることが心配になるかもしれません。この最適化によって命令情報テーブルからPCの列を消すことができる(二分探索ではPCの情報が必要だった)ので、結果的にはだいたい相殺されます。実験N行のメソッドをTracePoint有効下で実行するのにかかる時間を測定した結果が次の図です。大きな改善ではありませんが、行数が大きくなったときに二分探索を凌駕していることがわかります。メモリ使用量に変化がないことも確かめるため、cookpadのWebアプリのソースコードをすべてバイトコードにコンパイルしたときのインタプリタのメモリ使用量を測定しました。実行のたびにブレが発生するので、それぞれ1000回実行したときの頻度を取ってみました。RubyVM::InstructionSequence.compile_fileで測定。メモリ使用量の傾向が変わっていないことがわかると思います。まとめ簡潔ビットベクトルを使って、Rubyの命令情報テーブルの表引き速度を改善しました。これにより、頻繁に命令情報テーブルの表引きを行う条件下での実行(具体的にはTracePoint有効時やコードカバレッジ測定下での実行)が高速化されます。簡潔データ構造は理論的にも実用的にも非常に興味深い技術で、全文検索やゲノム解析など一部の分野では有名ですが、言語処理系の実装にも活用の可能性があるというのは意外でした*4。みなさんも応用を考えてみるとおもしろいのではないでしょうか。追記:この話は、クックパッドのフルタイムRubyコミッタである笹田が現状の問題を整理し、遠藤が簡潔ビットベクトルを用いるアイデアを思いつき、笹田が初期の実装を行い、遠藤がそれを改良して実現したものです。フルタイムRubyコミッタが机を並べることでRubyが改良された良い例です。*1:実は1月にコミットした古いもので、会津大学でのLTイベントで紹介済みだったりもするのですが、記録の意味もこめて記事にしてます。*2:「ケチな話」と思うかもしれませんが、Rubyではバイトコードのサイズはわりと無視できない関心事のひとつになっています。単なるメモリの無駄遣いというだけでなく、キャッシュを無駄遣いすることになるのでキャッシュミスにつながり、速度低下の原因にもなります。*3:簡潔ビットベクトルは、n番目の1のインデックスを求めるselect(n)という操作も高速に扱えます。今回の最適化にselect操作は登場しないので、説明を省略します。*4:関連研究をご存知の方はぜひ教えてください。開発チームの遠藤です。f...技術部の笹田です。インタプリタの開発をしている笹田です。インタプリタを開発している笹田です。探す技術部開発基盤グループのシム(@shia)です。使ったセキュリティログ検索基盤の構築サービス特性にあった検索システムの設計戦略クックパッド採用説明会「クックパッドはサービスの作り手を採用したいんです。/*}*/スターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。