R&D ができて 2 年が経ちました

R&D(研究開発部)部長の原島です。普段は部のマネージメントと自然言語処理関連の研究開発に従事しています。

タイトルの通り、クックパッドに R&D ができて 2 年(正確には 2 年 3 ヶ月)が経ちました。2 年の間に様々な取り組みがありました。また、ありがたいことに、それらについて聞かせてほしいと言っていただく機会も増えてきました。

そこで、このエントリでは R&D のこの 2 年間の主な取り組みを紹介したいと思います。

R&D の役割と体制

これまでの取り組みを紹介する前に、クックパッドにおける R&D の役割と体制を簡単に紹介しておきます。クックパッドの R&D の役割は「社内外の最新の研究成果にもとづくサービスの企画と開発」です。「研究成果」は、より具体的には、「食や料理、レシピに関する研究成果」です。これらのシーズとユーザーのニーズを紐付け、他部署と一緒にサービスを開発するのが R&D の役割です。また、シーズからサービスを企画し、他部署に提案するのも役割の一つです。

現在、R&D には 22 人(兼任やアルバイトを除くと 17 人)が所属しています。9 人は機械学習関連の研究開発に、8 人はスマートキッチン関連の研究開発に従事しています。また、それぞれの業務をサポートするメンバーが 5 人いて、マネージメントやアノテーションに従事しています。8 人(兼任やアルバイトを除くと 4 人)だった 2 年前と比べると、大分しっかりした体制になりました。最初の 1 年間は採用活動ばかりしていた気がします。

これまでの取り組み

さて、上記の役割と体制で様々な取り組みに挑戦してきました。これらの取り組みは下記のように大別できます。

  • 機械学習
    • 自然言語処理
    • 画像認識
    • MLOps
    • オープンサイエンス
  • スマートキッチン
    • VUI(Voice User Interface)
    • IoT

以下で、それぞれの取り組みを紹介します。

機械学習

自然言語処理

クックパッドにおいて自然言語処理は必要不可欠です。というのも、レシピが自然言語で記述されているからです。クックパッドには約 300 万品もの日本語のレシピが投稿されており、これらが自然言語処理の対象となります。また、クックパッドは 2014 年からサービスの海外展開を加速させており、この 4 年で 22 言語約 160 万品のレシピが追加されました。自然言語処理はますます重要な技術となっています。

この 2 年間の主な取り組みとしては、Encoder-Decoder による材料の正規化やロジスティック回帰による手順の分類等があります。前者の成果は今年 4 月にリリースした食材購入サービス(Amazon フレッシュ連携)で、後者の成果は 7 月にリリースした Amazon Echo Spot 向けサービス(後述)で利用されています。また、他の取り組みとして、SVM によるユーザーのご意見の分類等もあります。

画像認識

画像認識もクックパッドにおいて必要不可欠です。クックパッドのほとんどのレシピに画像が付与されています。レシピを検索する時も、投稿する時も、画像は大きな影響力を持ちます。また、近年の画像認識の進歩は目覚ましいものがあります。画像認識が実用段階になったことで、クックパッドに限らず、画像認識にもとづく様々なサービスが開発されています。

この 2 年間の主な取り組みとしては、Inception v3 による料理写真の検出や分類、類似写真の検索、SRGAN による料理写真の超解像等があります。特に、料理写真の検出は、2016 年 12 月にリリースした料理きろくというサービスの根幹をなす技術になりました。料理きろくは 26 万人以上に利用されるサービスになり、この 2 年間の最大の成果の一つになりました。

MLOps

機械学習の運用は、この分野における最近のホットトピックの一つです。GPU 環境をどのように用意するか、実験結果をどのように共有するか、モデルをどのようにデプロイするか、バッチをどのように実行するか、データをどのように管理するか。まだベストプラクティスはありません。クックパッドでも、日々、より良い方法を模索しています。

クックパッドの R&D では、GPU 環境を簡便に用意するため、Slack Chat Bot で Amazon EC2 インスタンスを管理できるようにしています。また、実験結果を関係者間で共有するため、Dockercookiecutter で実験環境を構築しています。さらに、クックパッドがこれまでに開発してきたツールや環境もフル活用しています。具体的には、hako でモデルをデプロイし、Kuroko2 でバッチを実行し、DWH でデータを管理しています。

オープンサイエンス

機械学習に関する取り組みとして、最後に、オープンサイエンスに関するものを紹介します。ここ数年、機械学習の研究が注目されているのは周知の通りです。そして、R&D の取り組みの多くはそれらの成果にもとづいています。機械学習の研究に少しでも貢献するため、R&D はオープンサイエンスにも注力しています。

この 2 年間の主な取り組みとしては去年の第 1 回 AI チャレンジコンテストがあります。これは人工知能技術戦略会議や内閣府、文部科学省と共催したものです。今年はデータ解析コンペティションを人工知能学会と共催しました。また、R&D ができる前からの取り組みとして、クックパッドは国立情報学研究所からレシピデータを研究者に公開しています。このデータは今や国内約 150 の研究室に利用されるものになりました。さらに、我々自身が論文を投稿することもあります。この 2 年間で 9 本の査読付き論文(ほとんどはワークショップの論文ですが)がアクセプトされました。

スマートキッチン

VUI

クックパッドでは VUI の可能性に注目しています。調理中にスマートフォンでレシピを閲覧するのは珍しいことではありません。しかし、汚れた手でスマートフォンに触れるのは抵抗があります。このような状況で VUI はその真価を発揮します。スマートスピーカーの半分はキッチンに設置されているという調査もあり、クックパッドとしては無視できない存在です。

R&D は昨年 11 月に Amazon Echo 向けサービスを、今年 3 月に Google Home 向けサービスをリリースしました。これらは VUI でレシピを検索できるものです。また、7 月には Amazon Echo Spot 向けサービスをリリースしました。さらに、12 月には Amazon Echo Show 向けサービスをリリースします。これらは VUI で料理動画を再生できたり、レシピの内容を確認できるものです。ありがたいことに、クックパッドの Alexa スキルは Amazon ランキング大賞 2018 上半期 Alexa スキルで 7 位にランキングされました。

IoT

IoT も無視できない存在です。上述のスマートスピーカーはもちろん、近年では多くの調理器具がインターネットと繋がっています。海外では、この 1 〜 2 年、調理器具メーカーとレシピサービスのアライアンスが加速しています。クックパッドがこの流れを看過するわけにはいきません。

そこで、R&D ではスマートキッチンサービス OiCy を開発しています。OiCy は、インターネット上のレシピと現実世界の調理器具を繋ぐサービスです。機械可読なレシピを定義し、これを調理器具メーカーに提供する予定です。今年 5 月には OiCy のコンセプトを体現した調味料サーバー OiCy Taste を、8 月にはあるべきスマートキッチンの姿を表現した Smart Kitchen Level を発表しました。既に国内メーカー数社と連携しており、今後は海外メーカーとも連携していく予定です。

おわりに

このエントリではクックパッドの R&D のこの 2 年間の主な取り組みを紹介しました。R&D ができた当初は、「どんな取り組みがありえるだろうか」「ちゃんとユーザーや会社の役に立てるだろうか」という一抹の不安がありました。今はそのような不安はありません。逆に、以下の点でクックパッドと研究開発は相性が良いと感じています。

  • 自社サービスがあり、研究開発の成果を活かすチャンスが沢山ある
  • データが沢山あるだけでなく、それらを簡単に利用できる環境(DWH)がある
  • 部内外に優秀なエンジニアが多く、開発やデプロイで困ることが少ない
  • 研究開発の対象(食や料理、レシピ)が普遍的で、また、幅広い

クックパッドの R&D は今後も様々な取り組みに挑戦していきます。メンバーもまだまだ募集しているので、ご興味がある方は採用ページを是非ご覧ください。ご応募をお待ちしています。

cookpad storeTV の広告配信を支えるリアルタイムログ集計基盤

こんにちは。メディアプロダクト開発部の我妻謙樹(id:kenju)です。 サーバーサイドエンジニアとして、広告配信システムの開発・運用を担当しています。

今回は、cookpad storeTV (以下略:storeTV )の広告商品における、リアルタイムログ集計基盤の紹介をします。

storeTV における広告開発

storeTV とは?

storeTV は、スーパーで料理動画を流すサービスで、店頭に独自の Android 端末を設置し、その売り場に適したレシピ動画を再生するサービスです。

より詳しいサービス概要にについては、弊社メンバーの Cookpad TechConf 2018 における以下の発表スライドを御覧ください。

storeTV における広告商品の概要

storeTV では、imp 保証型の広告商品を提供予定です。imp 保証型の広告商品とは、例えば「週に N 回広告を表示することを保証する」商品です。storeTV では、レシピ動画を複数回表示させるたびに広告動画を再生する仕様を想定しています。

f:id:itiskj:20181017154217j:plain

基本的には、実際の再生稼働数から在庫(広告動画の再生できる総回数)をおおまかに予測し、その在庫を元に比率を計算、配信比率を含む配信計画を全国に設置されている端末に配布する流れになります。

具体的な計算ロジックについて説明します。

配信比率は1時間を単位として算出しています。ある 1 時間の「配信比率」は、「 1 時間あたりの割当量 / 1 時間あたりの在庫量」と定義しています。

f:id:itiskj:20181017154304j:plain

  • Ratio ... 「配信比率」
  • HourlyAllocated ... 「1 時間あたりの割当量」
  • HourlyInventory ... 「1 時間あたりの在庫量」

ここで、「1 時間あたりの割当量」とは、1 時間あたりに再生したい回数です。広告商品によって達成したい目標 imp が異なりますので、「目標 imp」と「実績 imp」の差を、「残り単位時間」で割ることで算出できます。

また、「1 時間あたりの在庫量」とは、1時間あたりに再生され得る最大の広告再生回数と定義しています。storeTV の imp 保証型の広告商品の場合、先述したとおり「90 秒に 1 回配信される」という特性から、「1 時間あたりの最大広告再生回数」は 40 回と置くことができます。

したがって、「1 時間あたりの在庫量」は、「現在稼働中の端末数 / 1時間あたりの最大広告再生回数」で算出できます。

f:id:itiskj:20181017154316j:plain

  • Goal ... 「目標 imp」
  • TotalImpression ... 「実績 imp」
  • RemainingHours ... 「残り単位時間」
  • = MaxCommercialMoviePlayCount ... 「1 時間あたりの最大広告再生回数」

最後に、「現在稼働中の端末数」ですが、正確な値をリアルタイムで取ることはほぼ不可能であるため、実際に発生した imp ログから大体の稼働数を予測する必要があります。

具体的には、まだ imp ログの発生が見られていない時(例:広告配信開始直後で、まだどの端末からもログが到達していない状態)は、「配布済みの全端末数 / カテゴリ数1」で算出したものをデフォルト値として利用します。

imp ログが到達し始めたら、「直近 2 時間あたりの imp / 1 時間あたりの最大広告再生回数 / 直近 2 時間あたりの配信比率」で大体の値を算出しています。

f:id:itiskj:20181017154328j:plain

  • TotalDeviceCount ... 「配布済みの全端末数」
  • CategoryCount ... 「カテゴリ数」
  • EstimatedRunningDeviceCount ... 「現在稼働中の端末数」
  • HourlyImpression(currenthour - 2hours) ... 「直近 2 時間あたりの imp」
  • MaxCommercialMovierPlaycount ... 「1 時間あたりの最大広告再生回数」
  • Ratio(currenthour - 2hours) ... 「直近 2 時間あたりの配信比率」

storeTV ならではの課題

これだけでみると、一見簡単そうな要件に見えますが、cookpad 本体で配信している純広告とは異なる課題が多々存在します。

例えば、実際のハードウェアの配布数と実際の稼働数が大きく乖離するという点です。具体的には、「システム起因」(ネットワーク遅延、アップデート不具合)や「オペレーション起因」(バッテリー切れ、動画を流す手順操作をしない)などの様々な理由によって、広告動画が再生できない状態にある可能性があります。そういった広告が再生できない端末数を加味して配信比率を計算しないと、商品としての保証再生数を達成できないリスクが生じてしまいます。

そこで、稼働状態を把握するために、動画再生のログをリアルタイムで集計する必要がありました。リアルタイムで imp ログを参照できることで、より実際の稼働状況に即した配信比率が計算できます。より正確な配信比率に沿って広告を再生できることで、imp がショートしてしまったり、逆に出すぎてしまったりするようなリスクを可能な限り避けることができます。

なお、本件については、以下の資料もご参考ください。

storeTV 広告におけるリアルタイムログ集計基盤

そこで、リアルタイムログ集計基盤を用意する必要がありました。次節より、具体的なアーキテクチャや、実装上の課題、それに対する工夫についてお話しておきます。adtech研究会#1 にて発表した以下のスライドがベースとなっています。

当プロジェクトをまさに実装中に発表した資料で、ストリーミング処理における理論や資料についてまとめてあります。そのため、今回紹介する最終形とは異なり、一部古い記述(具体的には、Analysis レイヤーのアーキテクチャ)があります。

Architecture

まずは、全体のアーキテクチャを紹介します。

f:id:itiskj:20181017154341j:plain

主に、以下の 3 レイヤーから構成されています。

  • Aggregation ... imp ログを集計するレイヤー
  • Monitoring ... ストリームの詰まりやログの遅延を検出するためのモニタリングレイヤー
  • Analysis ... リアルタイムログを、分析用に Redshift に入れるための分析レイヤー

先ほど説明したように、元々は配信比率の計算のためのリアルタイムでの imp ログの集約が最優先タスクでした。それに伴い、Aggregation/Monitoring レイヤーを作成しました。

その後、せっかく Kinesis Streams ですべての広告動画再生ログを受け取っているので、ニアリアルタイム(大体 10 ~ 15 分程度)で分析するための Analysis レイヤーを作成しました。弊社では、DWH チームが提供するデータ活用基盤 に分析するデータを寄せることで、全社的に品質の高い分析フローを低コストで用意することができます。今回も、S3 Bucket に Kinesis Firehose 経由で投げたら、後は DWH の仕組みに乗って Redshift にデータが入ってきます。

Aggregation

f:id:itiskj:20181017154354j:plain

Core Design

Aggregation レイヤーでは、Android 端末から、以下のような JSON ログが送信されてきます。

{
  "delivery_id": 123,
  "delivery_plan_commercial_movie_hourly_goal_id": 100,
  "identifier": "foobar1234",
  "sending_time": "2018-07-12T10:22:58+09:00"
}

端末が送信してきたタイムスタンプに従って、1 分間ごとのログに集約させ、DynamoDB に格納します。

name type schema example
delivery_id String Hash Key 123
period_id Int Sort Key 201807121022
impressions Int - 1

この時、DynamodDB - Update Expressions の ADD 演算 を利用し、impressions の項目は、インクリメントさせます。これによって、JSON ログが流れてくるたびに、imp が徐々に増えていくようになります。

次に、このレコードを集約させた DynamoDB の Streams を有効にし、別の Lambda で吸い取ります。その Lambda は、minute 単位で格納されたレコードを、今度は hourly で集約し、別の DynamoDB に格納します。さらにその DynamoDB Streams から、daily 別に格納します。

このように徐々に集約させていくことで、ストリームデータを適切な粒度でカウントさせます。配信比率を計算するクライアントは、適宜必要なテーブルの imp レコードを参照します。

Late Logs & Watermarks

1 つめの Lambda が書き込んでいる DynamoDB が、2 つあることに気づいた方もいらっしゃるかもしれません。

f:id:itiskj:20181017154412j:plain

ここでは、ある一定時間以上遅延したログは、それ以降の集約ロジックに含めず、別の遅延専用テーブルに書き込んでいます。

一般に、ストリーミング処理において「遅延したログをどう扱うか」というのは、古くからある命題の一つです。ログは、様々な理由で遅延します。クライアントがオフライン状態にあったり、message broker が障害で落ちていたり、message broker からデータを吸い取り処理する consumer 側にバグが有ってデータが処理されなかったり、バグはないが想定以上のデータが来ることで consumer が一定時間以内に処理しきれず、かつスケールアウトも間に合わなかったり。

ストリーミング処理における理論や一般的プラクティスについては、『Designing Data-Intensive Applications』の十一章と、Oreilly における二部長編エッセイに詳しいので、興味がある方はそちらをおすすめします。

今回、遅延してきたログの対処法として、具体的には、Watermarks2 で処理することにしました。Watermarks とは、「どこまでログを処理したか」という情報を「透かし」としてストリームデータに仕込み、各 consumer がデータを処理する時、遅延したかどうかを判別できるようにするものです。

特に、今回は Apache Spark における Watermarks[^2] 実装 を参考に、オンメモリで計算できる設計にしました。外部データソースに、consumer ごとに「最後に処理したタイムスタンプ」を保存しておく実装も考えられましたが、別にテーブルを用意するコストや、毎回問い合わせが発生することによるコストを考慮し、避けました。

具体的には、冒頭で紹介したスライド p31 に擬似コードを載せています。「consumer が処理する一連のログのタイムスタンプの内、中央値に対してプラスマイナス 5 分以上乖離しているかどうか」で判別しています。

Apache Spark の例では最大値を利用していますが、storeTV ではクライアント側のシステム時間を操作できてしまうという特性上、かなり未来の時間が誤って送られてくることも考えられます。最大値を用いる手法だと、そのような外れ値に引っ張られて、本来集約ロジックに含めたい大量の正しいログを捨ててしまうことになります。ですので、中央値を利用しています。

Monitoring

Streaming Delay

次は、モニタリングです。ストリーミング処理においては、先程も説明したとおり、以下のような様々な理由によって詰まる可能性があります。

  • クライアントがオフライン状態
  • message broker が障害で落ちている
  • message broker からデータを吸い取り処理する consumer 側にバグが有ってデータが処理されない
  • バグはないが想定以上のデータが来ることで consumer が一定時間以内に処理しきれず、かつスケールアウトも間に合わない

f:id:itiskj:20181017154430j:plain

そこで、2 通りの方法を使ってモニタリングしています。

  1. Kinesis Streams の GetRecords.IteratorAgeMilliseconds 3
  2. DynamoDB に実際に書き込まれた imp ログのタイムスタンプが一定の閾値以内かどうか

まず、Kinesis Streams の IteratorAgeMilliseconds は、最後に処理されたレコードの時間を示します。もし、IteratorAge と現在時刻が乖離すればするほど、この値は大きくなっていきます。この値をモニタリングすることによって、Lambda 側でバグや障害が発生するなどしてレコードが処理されない事象を検知します。

また、DynamoDB に実際に書き込まれた imp ログが、現在時刻から一定の閾値以内かどうかを検知するための Lambda も存在しています。これは、例えば Kinesis に障害が発生するなどして、一定時間ストリーム自体が流れて来ず、復旧後に溜まっていた一連のストリームが流れてくるような場合を検知します。

CloudWatch Alarms の通知先として、SNS Topics を指定します。この Topics を、Slack に通知する責務をもたせた Lambda の event source として指定しておきます。こうすることで、通知ロジックの責務自体は分散させずに一連のモニタリングフローを整備できました。

CloudWatch Dashboard

また、Kinesis Streams や Lambda, DynamoDB など各種コンポーネントの稼働率も別途モニタリングする必要があります。今回は、全て AWS のサービス群で構成しているので、モニタリングツールには CloudWatch Dashboard を利用しました。既存の Metrics から必要な指標を手軽に作ることができるのでおすすめです。

Analysis

最後に、Analysis レイヤーです。Kinesis Streams の consumer として、Kinesis Firehose を指定し、S3 に吐くだけです。指定のフォーマットで S3 に出力した後は、DWH の仕組みに乗って Redshift に書き込まれていきます。

f:id:itiskj:20181017154511j:plain

ポイントは、Kinesis Firehose の Transformer として Lambda を指定している箇所です。Firehose では、Streams から来たログをそのまま S3 に流すのではなく、Lambda で前処理を加えることができます。これは、一般的な ETL4 処理における、Transform 機構をシンプルに実現できるということです。

Firehose はバッファリングとしての機構を持つので、例えば「5分間 or ログの総量が 1 MB を越えたら S3 に出力する」といった設定をすることができます。No Configuration が Firehose のウリでもあるので、例えばこのバッファリングの頻度を変更したいときは、コードを変更することなく、AWS Console から設定一つで変更することができます。

Misc

その他、一連の Lambada の実装には Golang を用いました。デプロイツールとしては Serverless Framework を使いました。ここらへんの技術選定の背景は、冒頭でも紹介したスライドの後半 に記載してありますので、興味がある方はそちらを御覧ください。

Conclusion

普段は cookpad 本体の広告配信サーバーの開発を担当していますが、動画広告領域も、技術的にチャレンジングな課題が数多く、非常に面白い領域です。ぜひ、興味を持っていただけたら、Twitter からご連絡ください。

また、メディアプロダクト開発部では、一緒に働いてくれるメンバーを募集しています。少しでも興味を持っていただけたら、以下をご覧ください。



  1. 「カテゴリ数」とは、農産・畜産・水産の部門ごとの数で、カテゴリごとに配信する広告動画が違うことからカテゴリ数で割ります

  2. https://cdn.oreillystatic.com/en/assets/1/event/155/Watermarks_%20Time%20and%20progress%20in%20streaming%20dataflow%20and%20beyond%20Presentation.pdf

  3. https://docs.aws.amazon.com/streams/latest/dev/monitoring-with-cloudwatch.html

  4. https://en.wikipedia.org/wiki/Extract,transform,load

簡潔ビットベクトルで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:関連研究をご存知の方はぜひ教えてください。

/* */ @import "/css/theme/report/report.css"; /* */ /* */ body{ background-image: url('https://cdn-ak.f.st-hatena.com/images/fotolife/c/cookpadtech/20140527/20140527163350.png'); background-repeat: repeat-x; background-color:transparent; background-attachment: scroll; background-position: left top;} /* */ body{ border-top: 3px solid orange; color: #3c3c3c; font-family: 'Helvetica Neue', Helvetica, 'ヒラギノ角ゴ Pro W3', 'Hiragino Kaku Gothic Pro', Meiryo, Osaka, 'MS Pゴシック', sans-serif; line-height: 1.8; font-size: 16px; } a { text-decoration: underline; color: #693e1c; } a:hover { color: #80400e; text-decoration: underline; } .entry-title a{ color: rgb(176, 108, 28); cursor: auto; display: inline; font-family: 'Helvetica Neue', Helvetica, 'ヒラギノ角ゴ Pro W3', 'Hiragino Kaku Gothic Pro', Meiryo, Osaka, 'MS Pゴシック', sans-serif; font-size: 30px; font-weight: bold; height: auto; line-height: 40.5px; text-decoration: underline solid rgb(176, 108, 28); width: auto; line-height: 1.35; } .date a { color: #9b8b6c; font-size: 14px; text-decoration: none; font-weight: normal; } .urllist-title-link { font-size: 14px; } /* Recent Entries */ .recent-entries a{ color: #693e1c; } .recent-entries a:visited { color: #4d2200; text-decoration: none; } .hatena-module-recent-entries li { padding-bottom: 8px; border-bottom-width: 0px; } /*Widget*/ .hatena-module-body li { list-style-type: circle; } .hatena-module-body a{ text-decoration: none; } .hatena-module-body a:hover{ text-decoration: underline; } /* Widget name */ .hatena-module-title, .hatena-module-title a{ color: #b06c1c; margin-top: 20px; margin-bottom: 7px; } /* work frame*/ #container { width: 970px; text-align: center; margin: 0 auto; background: transparent; padding: 0 30px; } #wrapper { float: left; overflow: hidden; width: 660px; } #box2 { width: 240px; float: right; font-size: 14px; word-wrap: break-word; } /*#blog-title-inner{*/ /*margin-top: 3px;*/ /*height: 125px;*/ /*background-position: left 0px;*/ /*}*/ /*.header-image-only #blog-title-inner {*/ /*background-repeat: no-repeat;*/ /*position: relative;*/ /*height: 200px;*/ /*display: none;*/ /*}*/ /*#blog-title {*/ /*margin-top: 3px;*/ /*height: 125px;*/ /*background-image: url('https://cdn-ak.f.st-hatena.com/images/fotolife/c/cookpadtech/20140527/20140527172848.png');*/ /*background-repeat: no-repeat;*/ /*background-position: left 0px;*/ /*}*/