設計パターン・最適化図鑑 · 基礎から応用へ

データ指向のメモリ配置

オブジェクトの見た目よりアクセスする列と順序を基準に、AoS・SoAを選ぶ。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 必要なフィールドを連続させる
  2. 64バイトのキャッシュラインで考える
  3. ベクトル化と変換費用
  4. 全フィールドをランダムに使う場合
  5. この記事をロゲイアに質問する理解を確かめる

必要なフィールドを連続させる

位置x、y、zと寿命を持つ粒子を大量に処理するとします。粒子ごとに全フィールドを並べるAoSでは、一つの粒子を扱う処理は近い場所から読めます。xだけを全粒子について加算する処理なら、xを連続させたSoAが不要なフィールドの読み込みを減らせます。どちらが常に速いと決めるのではなく、同じ処理がどのバイト列を順に触るかを図にして選びます。

64バイトのキャッシュラインで考える

説明用に、粒子を16バイト、キャッシュラインを64バイトと仮定します。AoSでxだけを使うと、1ラインに4個のxと他のフィールドが入ります。SoAのx配列では、4バイトのxを16個並べられます。これは転送されたバイトの利用率の違いで、実測の4倍高速を意味しません。キャッシュヒット、CPUの演算、メモリ帯域、先読みなどが全体時間を決めます。パディングや実際の型のサイズも確認します。

ベクトル化と変換費用

連続した同じ型の値はSIMDのロードと相性がよい場合があります。反対に離れたフィールドを集めるgatherや、型の変換が必要になると費用が増えます。しかし、ループの直前にAoSからSoAへ全データをコピーし、直後に戻すなら、変換が利益を消すことがあります。保存形式、描画、更新など他の利用箇所も含めて変更します。少数ずつまとめるAoSoAは局所性とベクトル化を両立する選択肢です。

全フィールドをランダムに使う場合

各要求が無作為に選んだ粒子の全フィールドを使うなら、SoAでは複数の配列へ離れたアクセスが発生します。AoSの方が少ない場所から必要情報を読める場合があります。また、複数スレッドが別粒子を更新していても同じキャッシュラインを共有すると偽共有が起きます。配置を変えた後は、正しさを同じ入力と出力で照合し、対象のアクセスパターンごとに測定します。一つのベンチマークの結果を全処理へ一般化しないことが大切です。

配置を変えると、データを参照するIDと配列添字の対応も管理対象になります。粒子を削除して詰めるときにxだけを移動すると、yや寿命が別の粒子へ対応します。性能の比較前に、各フィールドの対応が保たれる操作をテストする必要があります。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 8

AI基盤へ進む · STEP 5

学習コースから次を選ぶ