23

アプリケーションにとってパフォーマンスが重要な場合、スタックとヒープのどちらで配列を宣言するかを考慮する必要がありますか? この質問が頭に浮かんだ理由を概説させてください。

C/C++ の配列はオブジェクトではなく、ポインターに分解されるため、コンパイラーは指定されたインデックスを使用してポインター演算を実行し、要素にアクセスします。私の理解では、この手順は、最初の次元を通過するときに、静的に宣言された配列と動的に宣言された配列とは異なります。

次のようにスタックで配列を宣言するとします。

  int array[2][3] = { 0, 1, 2, 3, 4, 5 }
  //In memory        { row1 } { row2 }

この配列はメモリの連続したブロックに格納されるため、メモリに行メジャー形式で格納されます。つまり、配列内の要素にアクセスしようとすると、コンパイラは正しい位置を確認するために加算と乗算を実行する必要があります。

したがって、次のことを行う場合

  int x = array[1][2]; // x = 5

コンパイラは、次の式を使用します。

i = 行インデックス j = 列インデックス n = 1 行のサイズ (ここでは n = 2)
配列 = 最初の要素へのポインタ

  *(array + (i*n) + j)
  *(array + (1*2) + 2)

つまり、この配列をループして各要素にアクセスすると、インデックスによるアクセスごとに追加の乗算ステップが実行されます。

現在、ヒープで宣言されている配列では、パラダイムが異なり、多段階のソリューションが必要です。注: ここで C++ の new 演算子を使用することもできますが、データの表現方法に違いはないと思います。

  int ** array;
  int rowSize = 2;
  // Create a 2 by 3 2d array on the heap
  array = malloc(2 * sizeof(int*));
  for (int i = 0; i < 2; i++) {
      array[i] = malloc(3 * sizeof(int));
  }

  // Populating the array
  int number = 0;
  for (int i = 0; i < 2; i++) {
      for (int j = 0l j < 3; j++) {
          array[i][j] = number++;
      }
  }

配列は動的であるため、その表現は 1 次元配列の 1 次元配列です。アスキー絵を描いてみます...

              int *        int int int
int ** array-> [0]          0   1   2
               [1]          3   4   5

これは、乗算がもはや含まれていないことを意味しますよね? 私が次のことをした場合

int x = array[1][1];

これにより、array[1] に対して間接/ポインター演算が実行されて 2 番目の行へのポインターにアクセスされ、これをもう一度実行して 2 番目の要素にアクセスされます。私はこれを言うのが正しいですか？

いくつかのコンテキストがあるので、質問に戻ります。フレームのレンダリングに約 0.016 秒かかるゲームなど、鮮明なパフォーマンスを必要とするアプリケーションのコードを書いている場合、スタックとヒープで配列を使用することについてよく考えるべきでしょうか? これで、malloc または new 演算子を使用すると 1 回限りのコストがかかることがわかりましたが、(Big O 分析と同様に) データ セットが大きくなる特定の時点で、行優先を回避するために動的配列を反復処理する方がよいでしょう。索引付け？

4

5 に答える 5

31

これらは「プレーンな」C (C++ ではない) に適用されます。

まず、いくつかの用語を明確にしましょう

「静的」は C のキーワードであり、関数内で宣言された変数に適用されると、変数の割り当て/アクセス方法が大幅に変更されます。

(C に関して) 変数 (配列を含む) が置かれる場所は 3 つあります。

  • スタック: これらは関数のローカル変数であり、static.
  • データ セクション: プログラムの開始時にこれらの領域が割り当てられます。これらは、任意のグローバル変数 (staticキーワードが可視性に関連するかどうかに関係なく) と、宣言された任意の関数ローカル変数ですstatic。
  • ヒープ:ポインタによって参照される動的に割り当てられたメモリ ( malloc()& )。free()このデータには、ポインターを介してのみアクセスします。

それでは、一次元配列にアクセスする方法を見てみましょう

定数インデックス ( #defined の場合もありますがconst、プレーンな C ではありません) を使用して配列にアクセスする場合、このインデックスはコンパイラによって計算されます。Data セクションに真の配列がある場合、間接的にアクセスされることはありません。Stackにポインタ ( Heap ) または配列がある場合、常に間接化が必要です。したがって、このタイプのアクセスを使用するデータ セクションの配列は、非常に高速になる可能性があります。しかし、これは世界を変えるほど有用なものではありません。

インデックス変数を使用して配列にアクセスすると、インデックスが変更される可能性があるため (たとえば、for ループでのインクリメントなど)、基本的に常にポインターに減衰します。生成されたコードは、ここにあるすべてのタイプで非常に似ているか、まったく同じである可能性があります。

より多くの次元を取り入れる

2 次元以上の配列を宣言し、定数によって部分的または完全にアクセスする場合、インテリジェントなコンパイラはこれらの定数を上記のように最適化することができます。

インデックスでアクセスする場合、メモリは線形であることに注意してください。真の配列の後の次元が 2 の倍数でない場合、コンパイラは乗算を生成する必要があります。たとえば、配列int arr[4][12];の 2 番目の次元は 12 ですarr[i][j]。ここでiおよびjがインデックス変数としてアクセスする場合、線形メモリは としてインデックスを付ける必要があります12 * i + j。したがって、コンパイラはここで定数を乗算するコードを生成する必要があります。(i<<3) + (i<<2) + j複雑さは、定数が 2 のべき乗からどれだけ離れているかによって異なります。ここで、結果のコードは、配列内の要素にアクセスするための計算のように見える可能性があります。

ポインターから 2 次元の「配列」を構築する場合、構造内に参照ポインターがあるため、次元のサイズは問題になりません。ここで を書くことができればarr[i][j]、それはあなたがそれを example として宣言したことを意味し、次にそれぞれ 12 秒のメモリの 4 つのチャンクをint* arr[4]それにmalloc()edintしました。4 つのポインター (コンパイラーがベースとして使用できるようになった) も、それが真の配列である場合には使用されなかったメモリーを消費することに注意してください。また、ここで生成されたコードには二重の間接性が含まれることにも注意してください。最初にコードは from によってポインターをロードし、次に によってiそのarrポインターintからロードしますj。

長さが 2 の累乗から「遠い」場合 (要素にアクセスするには、複雑な「定数を掛ける」コードを生成する必要があります)、ポインターを使用すると、より高速なアクセス コードが生成される可能性があります。

James Kanzeが回答で述べたように、状況によっては、コンパイラが真の多次元配列へのアクセスを最適化できる場合があります。この種の最適化は、ポインターから構成される配列では不可能です。その場合、「配列」は実際にはメモリの線形チャンクではないためです。

地域性の問題

通常のデスクトップ/モバイル アーキテクチャ (Intel / ARM 32 / 64 ビット プロセッサ) 向けに開発している場合は、地域性も重要です。それがキャッシュに残っている可能性が高いものです。何らかの理由で変数が既にキャッシュにある場合は、より高速にアクセスできます。

スタックは非常に頻繁に使用されるため、常にキャッシュに存在する可能性が非常に高いため、ローカリティの観点からはスタックが常に勝者となります。そのため、小さな配列をそこに配置するのが最適です。

真の配列は常にメモリの線形チャンクであるため、ポインターから配列を構成する代わりに真の多次元配列を使用することも、この点で役立つ場合があります。したがって、通常、ロードするキャッシュのブロックが少なくて済みます。別々malloc()に ed チャンクを使用する場合) 逆に、より多くのキャッシュ ブロックが必要になる可能性があり、チャンクがヒープ上で物理的にどのようになったかによっては、キャッシュ ラインの競合が発生する可能性があります。

于 2013-07-21T19:15:17.113 に答える
4

どちらを選択するとパフォーマンスが向上するかは、特定の状況によって大きく異なります。一方の方法が優れているか、またはほぼ同じかどうかを知る唯一の方法は、アプリケーションのパフォーマンスを測定することです。

要因となるいくつかのことは、それを行う頻度、配列/データの実際のサイズ、システムのメモリ量、およびシステムがメモリをどの程度管理しているかです。

2つの選択肢から選択できるという贅沢がある場合、サイズはすでに釘付けになっていることを意味するに違いありません. 次に、説明した複数の割り当てスキームは必要ありません。2D 配列の単一の動的割り当てを実行できます。C:

int (*array)[COLUMNS];
array = malloc(ROWS * sizeof(*array));

C++ の場合:

std::vector<std::array<int, COLUMNS>> array(ROWS);

が確定している限りCOLUMNS、単一の割り当てを実行して 2D 配列を取得できます。どちらも確定していない場合は、とにかく静的配列を使用するという選択肢はありません。

于 2013-07-21T17:57:11.913 に答える
4

C++ で 2 次元配列を実装する通常の方法は、 を使用してクラスでラップしstd::vector<int>、インデックスを計算するクラス アクセサーを使用することです。でも：

最適化に関する質問は、測定によってのみ回答できます。また、測定を行うマシンで使用しているコンパイラに対してのみ有効です。

あなたが書く場合：

int array[2][3] = { ... };

そして次のようなもの：

for ( int i = 0; i != 2; ++ i ) {
    for ( int j = 0; j != 3; ++ j ) {
        //  do something with array[i][j]...
    }
}

次の行に沿って実際に何かを生成しないコンパイラを想像するのは困難です。

for ( int* p = array, p != array + whatever; ++ p ) {
    //  do something with *p
}

これは最も基本的な最適化の 1 つであり、少なくとも 30 年間使用されています。

提案どおりに動的に割り当てると、コンパイラは この最適化を適用できなくなります。また、単一のアクセスの場合でも、マトリックスの局所性が低く、より多くのメモリアクセスが必要になるため、パフォーマンスが低下する可能性があります。

C++ を使用している場合は、通常、メモリMatrixを使用してクラスを記述しstd::vector<int>、乗算を使用して明示的にインデックスを計算します。(乗算にもかかわらず、改善された局所性により、おそらくパフォーマンスが向上します。) これにより、コンパイラが上記の最適化を実行することがより困難になる可能性がありますが、これが問題であることが判明した場合は、これを処理するための特殊な反復子をいつでも提供できます。 1つの特定のケース。より読みやすく、より柔軟なコード (たとえば、次元が一定である必要はありません) が得られ、パフォーマンスはほとんどまたはまったく低下しません。

于 2013-07-21T18:02:56.290 に答える
1

多くの場合、メモリ消費と速度の間にはトレードオフがあります。経験的に、スタックに配列を作成する方がヒープに割り当てるよりも高速であることがわかりました。配列のサイズが大きくなるにつれて、これはより明確になります。

いつでもメモリ消費を減らすことができます。たとえば、int などの代わりに short または char を使用できます。

配列のサイズが大きくなると、特に realloc を使用すると、アイテムの連続した位置を維持するために、より多くのページ置換 (上下) が発生する可能性があります。

また、スタックに格納できるサイズには下限があることも考慮する必要があります。ヒープの場合、この上限は高くなりますが、パフォーマンスのコストで述べたように.

于 2013-07-21T17:57:33.637 に答える