ネストされたベクトルと連続した配列のパフォーマンスへの影響

Question

ネストされたベクトルとC++の組み込み配列へのアクセスと書き込みのパフォーマンスの違いを明確に示す信頼できるテストがありましたか？私は、ネストされた（多次元の）ベクタを使用すると、通常、単一の配列（すべての要素が連続したメモリに格納されている）にアクセスする場合と比較して、パフォーマンス上のオーバーヘッドがあると聞いています。私は実際にこれらの違いを実際に示すテストはまだ見ていません。彼らは重要ですか？私はそれがシナリオに依存していると確信していますが、経験の浅いプログラマーとして、これらの違いがどんなレベルで重要になっているかはよくわかりません。

Answer 1

私はそれが一般的な方法で最も速い方法で答えることはできないと思うほど、シナリオによるのは間違いありません。最も速いアプローチは、アクセスパターンがアクセスパターンに最も優れたデータローカリティを持つものになることです。これは、アクセスパターンに大きく依存します。また、ネストされたベクトルの場合、アロケータに依存するメモリ内で構造がどのようにレイアウトされるかおそらくコンパイラ間で多少の違いがあります。

私は最適化の一般的なルールに従います。これはまず、最も簡単な方法で物事を書いてから、ボトルネックがあることを証明できたら最適化を試みます。

Answer 2

2つのことは、ネストされたと平坦化アレイ間のランタイムの違いに貢献：
キャッシュの動作および間接

• CPUが直接、あまりにも頻繁にRAMへのアクセスを避けるためにキャッシュの階層を使用しています。これは、大部分のメモリアクセスが連続的であるか、ある特定の一時的局所性を有すること、すなわち最近アクセスされたものがすぐに再びアクセスされるという事実を利用する。
  これは、ネストした配列の最も内側の配列がかなり大きい場合、隣接するファンクションの値を反復処理するとフラットな配列との違いが小さいことに気付くでしょう。これは、フラット配列の場合、値の範囲を反復するとき、最も内側のループが連続した要素を反復処理する必要があることを意味し、ネストされた配列の場合、最も内側のループが最も内側の配列を反復処理する必要があります。
• アクセスパターンがランダムである場合、タイミングの最も重要な違いは、回帰です。
  フラットアレイの場合は、A[(Z * M + Y) * N + X]のようなものを使用しているため、4回の算術演算とメモリアクセスを行います。
  ネストされた配列の場合はA[Z][Y][X]を使用します。したがって、実際には3つの相互依存メモリアクセスがあります。A[Z][Y]にアクセスする前にA[Z]を知る必要があります。現代のCPUのスーパースカラ・アーキテクチャーのため、並行して実行できる操作は特に効率的で相互依存的な操作ではありません。 したがって、ある側では算術演算とメモリの負荷があり、もう一方の側では3つの相互依存する負荷がありますが、これはかなり遅くなります。ネストされた配列の場合、Aの内容とA[Z]の値の一部がZである可能性がありますが、ネストされた配列が十分に大きい場合、キャッシュに完全に収まることはありません。アレイへの単一のランダムアクセスのための単一のキャッシュミスおよびロード（フラット）ではなく、複数のキャッシュミスおよびメモリロード（ネスト）

はまた、ネストされたとフラットアレイ間の顕著な相違が存在しない例を提供し、キャッシング（私の答え）と間接（ピーターの答え）、のより詳細な議論については、下記の特に短い答え（、his question見ますあなたがランダムアクセスを行う場合、あなたは間違いなく意志

• ：））

  あなたがそれらの間に有意な実行時の違いがあるかどうかを知りたいのであれば、私の答えは次のようになり、当然のインデックスのバグを修正した後複数の間接的に気づくネストされた配列の実行時間が長くなります。

• あなたは連続したアクセスとは多次元配列のあなたの最も内側の寸法が十分な大きさのループの正しい順序（最内ループ=最も内側の配列/最も内側の平らな配列のインデックス）とを使用する場合は、コンパイラはすべての迂回を最も内側のループから移動させることができるため、その差は無視できるものになります。