Google は AI 技術を使用して、コンテンツをご希望の言語に翻訳しています。AI 翻訳には誤りが含まれる場合があります。

メモリ局所性とパフォーマンス

メモリは単一の均一なストレージプールと見なされることが多いですが、その物理的な構成と CPU がメモリにアクセスする方法は、アプリケーションのパフォーマンスに大きな影響を与えます。メモリの局所性を理解することは、CPU のキャッシュ階層を効率的に使用する高性能コードを作成するうえで重要です。

CPU キャッシュの階層

最新のモバイル CPU は、システムのメイン RAM（DRAM）よりもはるかに高速です。このパフォーマンスのギャップを埋めるために、CPU はキャッシュと呼ばれる高速なメモリを複数のレベルで使用します。

L1 キャッシュ（レベル 1）: 最小かつ最速（約 1 ナノ秒）。3 GHz の CPU では、約 3 クロックサイクルです。
L2 キャッシュ（レベル 2）: より大きく、わずかに低速（約 3 ～ 5 ns、または約 10 ～ 15 サイクル）。
L3 キャッシュ（レベル 3）: 最大のキャッシュ（約 10 ～ 20 ナノ秒、または約 30 ～ 60 サイクル）。
メインメモリ（DRAM）: 最も大きく、最も遅い（100 ns 以上、または 300 サイクル以上）。

メモリレイテンシピラミッド

レイテンシのコンテキスト化: 停止のコスト

これらの数値の影響を理解するには、クロックサイクルあたり 4 ～ 8 個の命令をリタイアできる最新のスーパースカラー CPU を考えてみましょう。

CPU がすべてのキャッシュをミスし、DRAM の読み取りを 100 ns（300 サイクル）待つ必要がある場合:

Cycles Lost: 約 300 サイクル。
「無駄」な命令: データがローカルレジスタまたは L1 キャッシュにすでに存在する場合に実行できたはずの 1,200 ～ 2,400 個の命令。

コードのメモリ局所性が低い場合、CPU は複雑な計算でビジー状態になっているとは限りません。メモリサブシステムを待機している間、数千の命令相当のアイドル状態で頻繁に「停止」します。

サイクルあたりの命令数（IPC）

この効率性を測定するための重要な指標は、Instructions Per Cycle（IPC）です。IPC は、各クロックサイクル中に CPU が正常に「リタイア」（完了）した命令の平均数を示します。

高い IPC（3.0 ～ 5.0 など）: CPU が高効率で動作しており、データのほとんどが L1/L2 キャッシュまたはレジスタに存在している可能性があります。
IPC が低い（0.5 未満など）: CPU がボトルネックになっています。システムモニターで CPU の使用率が 100% になっていても、実際にはほとんどがメモリの待機に費やされています。この状態はメモリスタールと呼ばれます。

メモリの局所性は、データ集約型のループが高 IPC で実行されるか、一連のストールに折りたたまれるかを決定する主な要因です。

キャッシュライン

CPU はメモリから単一のバイトを読み込みません。代わりに、通常 64 バイトのキャッシュラインと呼ばれる固定サイズのブロックを読み込みます。単一の変数にアクセスすると、CPU はその変数を含む 64 バイトのチャンク全体をキャッシュにフェッチします。

キャッシュラインの仕組み

TLB（変換ルックアサイドバッファ）

Android は仮想メモリを使用します。メモリアクセスごとに、仮想アドレスを物理アドレスに変換する必要があります。TLB は、最近の変換を保存する専用のキャッシュです。TLB ミスが発生すると、カーネルはメインメモリ内のページテーブルをウォークする必要があります。これは、TLB ヒットと比較して比較的コストの高いオペレーションです。

ハードウェアプロファイル: Google Pixel 10 Pro Fold

以下の演習では、Google Pixel 10 Pro Fold ハードウェアデバイスを使用しました。このデバイスは Google Tensor G5 SoC を搭載しています。

ハードウェアの照会

メモリサブシステムを理解するには、まず CPU 構成とキャッシュパラメータを確認します。

# Check CPU architecture and core parts
adb shell cat /proc/cpuinfo | grep 'CPU part' | sort -u
# Output:
# CPU part  : 0xd8b
# CPU part  : 0xd8c
# CPU part  : 0xd90

# Check cache line size
adb shell getconf -a | grep CACHE_LINESIZE
# Output:
# LEVEL1_ICACHE_LINESIZE             64
# LEVEL1_DCACHE_LINESIZE             64

CPU パーツのデコード

/proc/cpuinfo の CPU part 値は、ARM CPU コアの 16 進数 ID です。Google Pixel 10 Pro Fold に搭載されている Laguna SoC の場合、これらは次のようにマッピングされます。

0xd8b: ARM Cortex-A520（高効率コア）
0xd90: ARM Cortex-A720（パフォーマンスコア）
0xd8c: ARM Cortex-X4（プライムコア）

この 4+3+1 構成は、最新のモバイル SoC で一般的です。ここでは、クラスタごとにキャッシュサイズとレイテンシが異なる場合があります。

地域区分

効率的なソフトウェア設計は、主に次の 2 種類の局所性に依存しています。

空間局所性: メモリ位置にアクセスすると、近くのメモリ位置にもすぐにアクセスされる可能性が高くなります。順次配列トラバーサルが典型的な例です。CPU はキャッシュライン全体を読み込むため、配列内の次の要素がキャッシュラインにすでに存在する場合、その要素へのアクセスはほぼ「無料」です。
時間的局所性: メモリロケーションにアクセスすると、同じロケーションにすぐに再びアクセスされる可能性が高くなります。優れたアルゴリズムは、キャッシュでデータが「ホット」な状態の間にデータを再利用します。

ハンズオン演習: simpleperf で局所性を測定する

この演習では、256 MB の行列の 2 つの異なるトラバーサルを実行しながら、simpleperf を使用してハードウェアパフォーマンスカウンタをモニタリングします。

行優先トラバーサル: 行優先順でメモリに格納されている順に、行列要素にアクセスします。これはキャッシュフレンドリーで、空間的局所性を利用します。
列優先トラバーサル: メモリをジャンプして、列ごとに要素にアクセスします。これにより、キャッシュと TLB が頻繁にミスし、CPU が停止します。

1. Simpleperf で実行する

バイナリをプッシュし、実行可能であることを確認して、simpleperf stat を使用してキャッシュと TLB イベントを測定します。:u 接尾辞は、ユーザー空間でイベントを測定するために使用します。これらのコマンドでは、ほとんどのデバイスで adb root がハードウェア PMU カウンタにアクセスする必要があります。

adb root
adb shell "chmod +x /data/local/tmp/LocalityLab"

プロファイル行優先:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab row"

プロファイル列優先:

adb shell "simpleperf stat -e cpu-cycles:u,instructions:u,cache-misses:u,L1-dcache-load-misses:u,dTLB-load-misses:u /data/local/tmp/LocalityLab col"

2. 測定例（Google Pixel 10 Pro Fold）

以下の結果は、Google Pixel 10 Pro Fold のハードウェアデバイスで測定されたものです。

指標	行優先（Friendly）	列優先（非推奨）	差
実行時間	0.83 秒	68.3 秒	約 82 倍遅い
手順	52.7 億	102 億	約 1.9 倍
CPU サイクル	12 億	621 億 8,000 万	約 52 倍
Instructions Per Cycle（IPC）	4.40	0.16	効率が 27 倍低い
L1 データキャッシュミス	2 億 1,000 万	3,369 百万	ミスが 16 倍に増加
dTLB ロードミス	13 万	2,888 百万人	22,000 倍のミス

3. 結果の分析

IPC クラッシュ: 行優先テストでは、CPU は 4.40 の IPC を達成しており、サイクルごとに複数の命令を効率的に実行していることを示しています。列優先テストでは、IPC は 0.16 に低下します。つまり、CPU は 96% の時間で停止し、DRAM からデータが到着するのを待機しています。
TLB ボトルネック: 最も大きな違いは dTLB-load-misses です。順次アクセス（行優先）は同じメモリページ内にとどまるため、TLB ミスはほとんど発生しません。列をまたいでジャンプすると（列優先）、CPU が常に新しいページを参照することになり、TLB がオーバーフローして、高コストのページテーブルウォークが強制されます。
キャッシュ効率: 列優先のトラバーサルでは、L1 キャッシュミスが 16 倍多く発生するため、CPU ははるかに遅い L3 または DRAM からデータを常に取得する必要があります。

観察: 両方のトラバーサルは同じデータに対して同じ論理演算を実行しましたが、列優先トラバーサルは 80 倍以上遅くなりました。この大きな違いは、アクセスパターンが CPU のメモリサブシステムの物理的な現実とどのように相互作用するかに完全に起因しています。

Java と Kotlin のデータ構造でのポインタ追跡

2D 行列ベンチマークは連続したネイティブ配列の空間的局所性を示していますが、ほとんどの Android アプリケーションとフレームワークのコードは Java と Kotlin で記述されています。マネージド言語では、オブジェクト変数とコレクション要素はオブジェクトをインラインで保存しません。ART ヒープ全体に分散されたヒープ割り当てオブジェクトへの参照（ポインタ）を保存します。

ネストされた参照グラフのコスト

Android アプリとシステムサービスでよく見られるパターンとして、状態オブジェクトの ArrayList などのネストされたコレクションをトラバースするパターンがあります。各状態オブジェクトには、リスナーまたは接続の ArrayMap または ArraySet が含まれており、それぞれが別の状態レコードを指しています。

ArrayList、ArrayMap、ArraySet は内部の Object[] 配列を連続して保存しますが、その Object[] の各要素はヒープ参照です。process.services.valueAt(i).connections.valueAt(j).client などのチェーンの逆参照には、5 つの連続した依存メモリ読み込みが必要です。

Object[] バッキング services を読み込みます。
ServiceRecord オブジェクトのヘッダーとフィールドを読み込みます。
Object[] バッキング connections を読み込みます。
ConnectionRecord オブジェクトを読み込みます。
ターゲットの ProcessRecord フィールドを読み込みます。

各読み込みのメモリアドレスは前の読み込みで返された値に依存するため、CPU のアウトオブオーダー実行エンジンとハードウェアプリフェッチャはそれらをオーバーラップできません。これらのオブジェクトが異なるタイミングで割り当てられた場合や、ガベージコレクション中に異なるリージョンに移動された場合、各ホップで L1 または L2 キャッシュミスが発生する可能性があります。

ボックス化されたプリミティブ（ArrayList<Integer>、HashMap<Long, Boolean>）と汎用ラムダは、このオーバーヘッドを複合化します。すべての要素ルックアップで、値のボックス化解除のための追加のポインタ逆参照が必要になり、汎用 Consumer<T> コールバックは、命令キャッシュ（L1-icache）のプレッシャーを追加するランタイム型チェック（CheckCast）スタブを挿入します。

`simpleperf` を使用してポインタチェイシングを診断する

実際の Java と Kotlin のワークロード（system_server の OomAdjuster 走査プロセス、サービス、プロバイダ参照グラフなど）では、ワーキングセットの一部が L2 または L3 キャッシュに収まるため、ポインタチェイスで合成 256 MB 列優先スキャンのように IPC が 0.16 まで低下することはほとんどありません。代わりに、simpleperf でこの特徴的なシグネチャを探します。

IPC の低下（0.6 ～ 0.9 程度）: CPU のスーパースカラーリタイア幅を大幅に下回っています。
バックエンドメモリのストールが多い（raw-stall-backend-mem）: CPU サイクルの 35 ～ 45% がデータキャッシュの充填待ちに費やされることがよくあります。
L1-dcache-load-misses と L1-icache-load-misses の上昇: ホットトラバーサルループが仮想メソッドと汎用ラムダスタブをジャンプするときに、高いデータキャッシュミス率と命令キャッシュミスが組み合わされます。

simpleperf stat を使用して、実行中のプロセスでこれらのカウンタを測定できます。

adb shell simpleperf stat \
  -e cpu-cycles:u,instructions:u,raw-stall-backend-mem:u,L1-dcache-load-misses:u,L1-icache-load-misses:u \
  -p $(pidof system_server) --duration 10

マネージドコードの局所性を改善する

ボックス化されたコレクションをプリミティブ配列または AndroidX コレクションに置き換える: IntArray、LongArray、SparseIntArray、または androidx.collection プリミティブ（IntList、LongLongMap、ScatterMap）を使用して、ラッパーオブジェクトを排除し、単一の配列割り当て内で値を連続させます。
ホットトラバーサルパスをフラット化する: ホットループがオブジェクトグラフを 3 ～ 4 ホップ繰り返し歩いて単一のブール値または整数フラグを読み取る場合、その状態を密な ID でインデックス付けされたフラットな配列またはビットマスクにホイストまたはキャッシュに保存します。
タイトな内部ループでキャプチャまたは汎用ラムダを使用しない: forEach またはイテレータチェーンの代わりに、RandomAccess リストで標準のインデックス付き for ループを使用し、イテレータの割り当て、メガモルフィックディスパッチ、実行時の型チェックのオーバーヘッドを回避します。

← スレッド | ↑ 上へ | サービスバインディング →