コンパイルを 18% 高速化、妥協はゼロ

Android ランタイム（ART）チームは、コンパイル済みコードやピークメモリの回帰を損なうことなく、コンパイル時間を 18% 短縮しました。この改善は、メモリ使用量やコンパイル済みコードの品質を犠牲にすることなくコンパイル時間を短縮するという、2025 年の取り組みの一環です。

コンパイル時の速度の最適化は、ART にとって重要です。たとえば、ジャストインタイム（JIT）コンパイルは、アプリケーションの効率とデバイス全体のパフォーマンスに直接影響します。コンパイルが高速化されると、最適化が開始されるまでの時間が短縮され、ユーザー エクスペリエンスがよりスムーズで応答性の高いものになります。さらに、JIT と AOT（Ahead-Of-Time）の両方で、コンパイル時間の短縮はコンパイル プロセス中のリソース消費量の削減につながり、特にローエンド デバイスでバッテリー駆動時間とデバイスの温度にメリットをもたらします。

これらのコンパイル時間の短縮に関する改善の一部は、2025 年 6 月の Android リリースでリリースされました。残りは、年末の Android リリースで利用可能になる予定です。さらに、Android 12 以降のすべての Android ユーザーは、メインライン アップデートを通じてこれらの改善を利用できます。

最適化コンパイラの最適化

コンパイラの最適化は、常にトレードオフを伴います。速度を無料で手に入れることはできません。何かを犠牲にする必要があります。私たちは、コンパイラを高速化するという、非常に明確で挑戦的な目標を設定しました。ただし、メモリの回帰を発生させず、生成されるコードの品質を低下させないことが重要です。コンパイラが高速になっても、アプリの実行速度が低下したのでは意味がありません。

私たちが費やすことをいとわなかったリソースは、これらの厳しい基準を満たす巧妙なソリューションを深く掘り下げ、調査し、見つけるための、私たち自身の開発時間でした。改善すべき領域を見つけ、さまざまな問題に対する適切な解決策を見つけるために、Google がどのように取り組んでいるかを詳しく見ていきましょう。

価値のある最適化の可能性を見つける

指標を最適化するには、まずその指標を測定できる必要があります。そうしないと、改善されたかどうかを判断できません。幸いなことに、コンパイル時間は、変更の前後で同じデバイスを使用する、デバイスのサーマル スロットリングが発生しないようにするなど、いくつかの予防措置を講じる限り、かなり一貫しています。さらに、コンパイラ統計情報などの決定論的な測定値も、内部で何が起こっているかを把握するのに役立ちます。

これらの改善のために犠牲にしていたリソースは開発時間だったため、できるだけ早くイテレーションできるようにしたいと考えていました。そのため、いくつかの代表的なアプリ（ファーストパーティ製アプリ、サードパーティ製アプリ、Android オペレーティング システム自体の組み合わせ）を対象に、ソリューションのプロトタイプを作成しました。その後、手動テストと自動テストを広範囲に実施して、最終的な実装に価値があることを確認しました。

厳選した APK のセットを使用して、ローカルで手動コンパイルをトリガーし、コンパイルのプロファイルを取得して、pprof を使用してどこに時間がかかっているかを可視化します。

pprof のプロファイルのフレームグラフの例

pprof ツールは非常に強力で、データをスライス、フィルタ、並べ替えして、たとえば、どのコンパイラ フェーズやメソッドに最も時間がかかっているかを確認できます。pprof 自体については詳しく説明しませんが、バーが大きいほどコンパイルに時間がかかったことを意味します。

これらのビューの 1 つが「ボトムアップ」ビューです。このビューでは、どのメソッドに最も時間がかかっているかを確認できます。下の画像では、Kill というメソッドがコンパイル時間の 1% 以上を占めていることがわかります。その他の上位のメソッドについても、このブログ投稿の後半で説明します。

プロファイルのボトムアップ ビュー

最適化コンパイラには、グローバル値番号付け（GVN）と呼ばれるフェーズがあります。全体として何を行うかを気にする必要はありませんが、関連する部分として、フィルタに従って一部のノードを削除する「Kill」というメソッドがあることを知っておく必要があります。この方法では、すべてのノードを反復処理して 1 つずつ確認する必要があるため、時間がかかります。その時点で稼働しているノードに関係なく、チェックが false になることが事前にわかっているケースがあることに気づきました。このような場合、反復処理を完全にスキップすることで、1.023% から約 0.3% に削減し、GVN のランタイムを約 15% 改善できます。

価値のある最適化を実装する

時間の測定方法と、時間がどこで費やされているかを検出する方法について説明しましたが、これはほんの始まりにすぎません。次のステップは、コンパイルに費やされる時間を最適化する方法です。

通常、上記の「Kill」のようなケースでは、ノードを反復処理する方法を検討し、たとえば、並列処理やアルゴリズム自体の改善によって処理を高速化します。実際、私たちも最初はそうしようとしました。しかし、何もすることが見つからなかったときに、「ちょっと待てよ…」と思い、解決策は（場合によっては）まったく反復しないことだと気づきました。このような最適化を行う場合、木を見て森を見ずという状況に陥りがちです。

その他のケースでは、次のようなさまざまな手法を使用しました。

• ヒューリスティクスを使用して、最適化で価値のある結果が得られないかどうかを判断し、スキップできるようにする
• 追加のデータ構造を使用して、計算されたデータをキャッシュする
• 現在のデータ構造を変更してスピード ブーストを得る
• 場合によってはサイクルを回避するために結果を遅延計算する
• 適切な抽象化を使用する - 不要な機能はコードの速度を低下させる可能性がある
• 頻繁に使用されるポインタを多くのロードで追跡しない

最適化を追求する価値があるかどうかを判断するにはどうすればよいでしょうか。

実は、その必要はありません。コンパイル時間が長い領域を特定し、開発時間を費やして改善を試みても、解決策が見つからないことがあります。何もする必要がない、実装に時間がかかりすぎる、別の指標が大幅に低下する、コードベースが複雑になるなど、さまざまな理由が考えられます。このブログ投稿で紹介している成功した最適化の裏には、実を結ばなかった無数の最適化があることを知っておいてください。

同様の状況にある場合は、できるだけ少ない作業で指標をどれだけ改善できるかを見積もってみてください。これは、次の順序を意味します。

1. すでに収集した指標や直感で見積もる
2. 簡易プロトタイプによる見積もり
3. ソリューションを実装する。

ソリューションのデメリットを見積もることも忘れないでください。たとえば、追加のデータ構造に依存する場合、どの程度のメモリを使用する予定ですか？

詳細を学ぶ

それでは、実施した変更の一部をご紹介します。

FindReferenceInfoOf というメソッドを最適化する変更を実装しました。このメソッドは、ベクトルの線形検索を行ってエントリを見つけていました。このデータ構造を、命令の ID でインデックス化されるように更新しました。これにより、FindReferenceInfoOf は O(n) ではなく O(1) になります。また、サイズ変更を避けるために、ベクトルを事前に割り当てました。ベクトルに挿入したエントリ数をカウントするフィールドを追加する必要があったため、メモリはわずかに増加しましたが、ピークメモリは増加しなかったため、小さな犠牲でした。これにより、LoadStoreAnalysis フェーズが 34 ～ 66% 高速化され、コンパイル時間が約 0.5 ～ 1.8% 改善されました。

HashSet のカスタム実装があり、複数の場所で使用しています。このデータ構造の作成にかなりの時間がかかっていたのですが、その理由がわかりました。何年も前、このデータ構造は、非常に大きな HashSet を使用するいくつかの場所でのみ使用され、そのために最適化されるように調整されていました。しかし、現在では、エントリ数が少なく、有効期間が短い逆方向で使用されています。つまり、この巨大な HashSet を作成することでサイクルを浪費していましたが、使用したのは数個のエントリだけで、その後は破棄していました。この変更により、コンパイル時間が約 1.3 ～ 2% 改善されました。さらに、以前ほど大きなデータ構造を使用しなくなったため、メモリ使用量が約 0.5 ～ 1% 減少しました。

データ構造を参照渡ししてラムダに渡すことで、データ構造のコピーを回避し、コンパイル時間を約 0.5 ～ 1% 改善しました。これは、最初のレビューで見落とされ、何年もの間コードベースに存在していたものです。pprof でプロファイルを確認したことで、これらのメソッドが多くのデータ構造を作成して破棄していることに気づき、調査と最適化を行うことができました。

計算された値をキャッシュに保存することで、コンパイルされた出力を書き込むフェーズを高速化しました。これにより、コンパイル時間全体が約 1.3 ～ 2.8% 短縮されました。残念ながら、追加の簿記は多すぎ、自動テストでメモリ回帰が警告されました。その後、同じコードを再度確認し、メモリの回帰に対処するだけでなく、コンパイル時間をさらに約 0.5 ～ 1.8% 改善する新しいバージョンを実装しました。この 2 つ目の変更では、2 つのデータ構造のうちの 1 つを削除するために、このフェーズの仕組みをリファクタリングして再考する必要がありました。

最適化コンパイラには、パフォーマンスを向上させるために関数呼び出しをインライン化するフェーズがあります。インライン化するメソッドを選択するために、計算を行う前にヒューリスティックを使用し、作業を行った後、インライン化を完了する直前に最終チェックを行います。これらのいずれかでインライン化する価値がないと判断された場合（たとえば、追加される新しい命令が多すぎる場合）、メソッド呼び出しはインライン化されません。

2 つのチェックを「最終チェック」カテゴリから「ヒューリスティック」カテゴリに移動し、時間のかかる計算を行う前にインライン化が成功するかどうかを推定するようにしました。これは推定値であるため、完璧ではありませんが、新しいヒューリスティクスは、パフォーマンスに影響を与えることなく、以前にインライン化されたものの 99.9% をカバーしていることが確認されています。これらの新しいヒューリスティックの 1 つは、必要な DEX レジスタに関するもので（約 0.2 ～ 1.3% の改善）、もう 1 つは命令数に関するものでした（約 2% の改善）。

いくつかの場所で使用している BitVector のカスタム実装があります。サイズ変更可能な BitVector クラスを、特定の固定サイズ ビットベクトル用のよりシンプルな BitVectorView に置き換えました。これにより、一部の間接参照とランタイム範囲チェックが不要になり、ビットベクトル オブジェクトの構築が高速化されます。

さらに、BitVectorView クラスは、基盤となるストレージ タイプでテンプレート化されました（古い BitVector のように常に uint32_t を使用するのではなく）。これにより、Union() などの一部のオペレーションでは、64 ビット プラットフォームで 2 倍のビット数をまとめて処理できます。Android OS のコンパイル時に、影響を受ける関数のサンプルが合計で 1% 以上減少しました。これは、いくつかの変更 [1、2、3、4、5、6] で行われました。

すべての最適化について詳しく説明すると、1 日中かかってしまいます。最適化についてさらに詳しく知りたい場合は、Google が実施したその他の変更をご覧ください。

• 簿記を追加して、コンパイル時間を約 0.6 ～ 1.6% 短縮しました。
• 可能であれば、データを遅延計算してサイクルを回避します。
• コードをリファクタリングして、使用されない場合は事前計算作業をスキップする。
• アロケータを他の場所から簡単に取得できる場合は、依存する読み込みチェーンを避けます。
• 不要な作業を回避するためにチェックを追加するもう 1 つのケース。
• レジスタ アロケータでレジスタタイプ（コア/FP）の頻繁な分岐を避ける。
• コンパイル時に一部の配列が初期化されていることを確認します。clang に依存しないでください。
• ループをクリーンアップする。ループの副作用によりコンテナの内部ポインタを再読み込みする必要がないため、clang でより適切に最適化できる範囲ループを使用します。各入力に対してインライン化された `InputAt(.)` を介して、ループ内で仮想関数 `HInstruction::GetInputRecords()` を呼び出さないようにします。
• コンパイラの最適化を利用して、ビジター パターンの Accept() 関数を回避します。

まとめ

ART のコンパイル時間の短縮に注力した結果、大幅な改善が実現しました。これにより、Android の動作がよりスムーズかつ効率的になり、バッテリー駆動時間とデバイスの温度管理の向上にも貢献しています。最適化を特定して実装することで、メモリ使用量やコード品質を損なうことなく、コンパイル時間を大幅に短縮できることが実証されました。

この取り組みでは、pprof などのツールを使用したプロファイリング、反復処理への意欲、そして時には成果の少ない方法を放棄することも必要でした。ART チームの共同作業により、コンパイル時間が大幅に短縮されただけでなく、今後の進歩の基盤も築かれました。

これらの改善はすべて、2025 年末の Android アップデートで利用可能になり、Android 12 以降では Mainline アップデートを通じて利用可能になります。最適化プロセスの特集が、コンパイラ エンジニアリングの複雑さとメリットに関する有益な知見を得る一助になれば幸いです。