静的配列と動的配列のC/C++パフォーマンス

Question

パフォーマンスがアプリケーションにとって重要な場合は、スタックとヒープのどちらを宣言するか考慮する必要がありますか？なぜこの質問が心に浮かんだのかを概説することができます。

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 =単一の行のサイズ（ここでは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]; 

以下の[1]第二列へのポインタをアクセスした後、第2の要素にアクセスするために再度これを実行します。私はこれを言って正しいですか？

ここでいくつかの文脈があります。質問に戻る。フレームをレンダリングするのに約0.016秒かかるゲームのように、鮮明なパフォーマンスが必要なアプリケーション用のコードを記述している場合は、スタックとヒープの配列の使用について2回考える必要がありますか？今では、mallocや新しい演算子を使うのに一度のコストがかかることを認識していますが、データセットが大きくなる特定の点（Big O解析のような点）では、行のメジャーを避けるためにダイナミック配列を反復する方が良いでしょう索引付け？

Answer 1

これらは "プレーン" C（ないC++）に適用されます。

まずはいくつかの専門用語に

をクリアしてみましょう「静的」は大幅にそれが関数内で宣言した変数に適用された場合、あなたの変数にアクセス/割り当てられている方法が変更されますCのキーワードです。

• スタック：

  は、（アレイを含む）変数が座ることができる（Cに関する）3つの場所があり、これらはstaticなし関数のローカル変数です。

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

さて、あなたは一定の屈折率（#define Dではなく、プレーンなCでconstでもよい）の配列にアクセスする場合は、このインデックスはで算出することができる1次元配列が

にアクセスしている方法を見てみましょうコンパイラ。 データセクションに真の配列がある場合は、間接的にアクセスされることはありません。あなたはポインタ（ヒープ）またはスタック上のアレイを持っている場合は、間接は常に必要です。したがって、このタイプのアクセスを持つデータセクションの配列は、ほんの少し速いかもしれません。しかし、これは世界を変える非常に有用なものではありません。

もしインデックス変数とアレイをアクセスする場合、インデックスが（ためのループの例増分のために）変更することができるので、それは本質的に常にポインタに減衰します。生成されたコードは、ここではすべてのタイプで非常によく似ています。

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

もたらします。

あなたはインデックスでアクセスした場合、メモリが線形であることに注意してください。真の配列の後の次元が2の倍数でない場合、コンパイラは乗算を生成する必要があります。例えば、配列int arr[4][12];に二次元はあなたが今iとjがインデックス変数ですarr[i][j]としてそれにアクセスする場合は、リニアメモリが12 * i + jとしてインデックスを作成する必要がある12。したがって、コンパイラはここで定数を乗算するコードを生成する必要があります。複雑さは、定数が2の累乗からどの程度離れているかによって決まります。ここで得られるコードは、(i<<3) + (i<<2) + jと計算され、配列内の要素にアクセスするように見えます。

あなたはポインタから2次元の「アレイ」を構築する場合は、あなたの構造の参照ポインタがあるので、寸法の大きさは重要ではありません。ここであなたは一例int* arr[4]用として、それを宣言した意味という、arr[i][j]を書き、その後、malloc()ことができれば、それに12 int sは、それぞれのメモリの4つのチャンクを編。 4つのポインタ（コンパイラが現在ベースとして使用できる）は、実際の配列の場合は使用されなかったメモリも消費することに注意してください。また、ここで生成されたコードは二重間接を含むことに注意してください。iからコードをロードした後、jによってそのポインタからintをロードします。

長さは、次に、ポインタを使用して高速なアクセスコードを生成することができる（非常に複雑コード「定数と乗算」要素にアクセスするために生成しなければならない）、「遠い」2のべき乗からのものである場合。彼の答えで述べたようにJames Kanze

、いくつかの状況では、コンパイラは、真の多次元アレイのアクセスを最適化することができるかもしれません。このような最適化は、ポインタから構成された配列では不可能です。なぜなら、「配列」は実際には線形のメモリチャンクではないからです。

地域では、通常のデスクトップ/モバイル・アーキテクチャー（インテル/ ARM 64分の32ビットプロセッサ）用に開発されている場合は局所性も重要

を重要。それがキャッシュに座っている可能性が高いです。何らかの理由で変数がすでにキャッシュに入っていると、それらの変数はより早くアクセスされます。 スタックはそう頻繁にそれは常にキャッシュに座ってすることは非常に可能性があることを使用しているため、地域スタックの用語で

は常に勝者です。だから、小さな配列がそこに置かれるのが最善です。

真の配列は常にメモリの線形チャンクなので、ポインタからポインタを作成するのではなく、真の多次元配列を使用すると、このような場合に役立ちます。分散するために必要なブロック数は少なくなります。別のキャッシュブロックを必要とする可能性があり、チャンクが物理的にヒープ上でどのように終わったかによって、キャッシュラインの競合が増加する可能性があります。

Answer 2

どちらの選択肢でパフォーマンスが向上するかは、お使いの環境によって大きく異なります。一方の方法が良いかどうかを知るための唯一の方法、またはそれらがおおよそ同等であるかどうかの唯一の方法は、アプリケーションのパフォーマンスを測定することです。

要因の1つは、実行頻度、アレイ/データの実際のサイズ、システムのメモリ容量、システムがメモリをどれくらいうまく管理しているかなどです。

あなたが2つの選択肢の中から選択できるという贅沢を持っているなら、それは既にサイズが決まっていることを意味するはずです。次に、説明した複数の割り当てスキームは必要ありません。 2D配列の単一の動的割り当てを実行することができます。 Cでは：

C++で

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

：

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

限りCOLUMNSが釘付けされ、あなたの2次元配列を得るために、単一の割り当てを行うことができますよう。どちらも落とされない場合は、とにかく静的配列を使用する選択肢はありません。

Answer 3

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

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

特に、reallocを使用すると、配列のサイズが大きくなるので、アイテムの連続した位置を維持するためにページの置換（上下） 。

スタックに格納できるもののサイズの下限があることも考慮する必要があります。ヒープの上限は高くなりますが、パフォーマンスのコストについて言えばそうです。

std::vector<int>

Answer 4

を使用して、クラスでラップすることであろう C++で2次元アレイを実装する通常の方法、及び インデックスを計算するクラスアクセサを有します。ただし、

最適化に関する質問は、 測定でのみ応答することができ、測定したマシンで使用しているコンパイラ に対してのみ有効です。

あなたが書く場合：

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

、その後のようなもの：

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

：

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

をそれが実際の線に沿って 何かを生成しないコンパイラを想像するのは難しいです

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

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

は、あなたは通常、メモリ用std::vector<int>を使用して、乗算を使用して明示的に インデックスを計算するMatrixクラス、 を記述します。 （ の乗算にもかかわらず、改良された地域 はおそらくより良いパフォーマンスをもたらします）。これは コンパイラが上記の最適化を行うことをより困難にする可能性がありますが、これが になる場合は、この1つの特定のケースを処理するイテレーター あなたは、パフォーマンスのほとんど、あるいは全くの損失で、（例えば、寸法が一定になるように を持っていない） 、より読みやすく、より柔軟なコードで終わります。

Answer 5

ストークメモリ割り当てでは、ヒープよりも高速にデータにアクセスできます。 CPUは、キャッシュ内のアドレスを見つけなかった場合はキャッシュ内のアドレスを探し、キャッシュ内のアドレスが見つからない場合はメインメモリ内でルックアップします。 Stalkは、キャッシュの後の優先的な場所です。あなたが使用することができ