From Pinning To IORap (3): Redex

2020-09-16

Facebook は Redex と呼ばれる dex ファイル最適化ツールを公開している。この Redex にも Profile-Guided なディスクアクセスの最適化機能がある。

具体的には実行時プロファイルに基づき dex ファイル内のクラスを登場順に並べ替えることで局所性を高めてランダムアクセスを減らす。 Profiled-Guided Dex Relocation といったところだろうか。(彼ら自身は “Feedback-directed class layout” と称している。)

ランダムアクセスが減るだけでなく、アクセスするページの総量も減る。クラス定義はふつうページより小さく、アクセス順に並べると断片化が減るため。ツールが出力するメトリクスを見ると、APK 内に複数ある dex のうち最初の primary dex にいかに起動時に使うクラスを押し込めるかを苦心している。

この機能 “Interdex” は実行時情報としてヒープダンプ(hprof ファイル)を使う。ヒープダンプをクラスローディングのプロファイルに使うアイデアは自明でないが、実装を覗くと工夫が見られた。

  • Android の hprof ファイルに含まれるクラスの ID はクラスのロード順を示すという実装の詳細を利用し、ヒープ内オブジェクトのクラスをソートしている(dump_classes_from_hprof.py)。おそらくこれが「ランダムアクセスを減らす」という主張を裏付けている。
  • ヒープダンプだけでなく dex 内のコード (method body) もトラバースし、ヒープダンプにあったオブジェクトのメソッドから参照されているクラスもリストに追加する(InterDex.cpp:find_unrefenced_coldstart_classes)。これで static method の参照や GC されてしまった短命オブジェクトのクラスもカバーできるだろう。

AOSP を改造すればクラスのロード順をダンプするのは簡単だろうが、かわりに hprof ファイルを使い敷居を下げているのが面白い。

Redex は 2015 年に公に紹介され、翌年 2016 年にオープンソースとなった。一方で 2020 年現在の Facebook アプリをトレースすると起動時間の大半はネイティコードの初期化に費やされている。またここ数年で普及した ART は AOT の一環で dex ファイルの後処理なども行う。Dex 単位で Java コードの初期化を高速化する Redex の効き目が今でも有意なのかはよくわからない。

BOLT

プロファイリングに基づく code relocation は Redex 以前から行われている。 Facebook 自身もサーバサイドでのネイティブバイナリ最適化ツール BOLT を開発している。

BOLT の主眼はプログラムの起動速度ではなく、分岐予測の支援やキャッシュ局所性の改善にある。上でリンクした論文によれば最大 20% の性能改善が見られたという。

BOLT を追試した Google も 2%-6% の性能改善を確認し、自社のツールチェイン向けに BOLT 相当の機能を再実装する Propeller プロジェクト を進めている。

関連リンク

Ack

一連の草稿に目を通して感想をくれた皆様ありがとう: Yuichi Tateno, Jun Mukai, Kensuke Nagae, Kazuyoshi Kato, Kenichi Ishibashi, Hiroshi Kurokawa, karino2