63

ポインタを介したメモリアクセスは、配列を介したメモリアクセスよりも効率的であると言われています。私はCを学んでおり、上記はK＆Rに記載されています。具体的に彼らは言う

配列の添え字によって実行できる操作はすべて、ポインターを使用して実行することもできます。ポインタバージョンは一般的に高速になります

Visual C ++を使用して次のコードを分解しました（私のものは686プロセッサです。すべての最適化を無効にしました）。

int a[10], *p = a, temp;

void foo()
{
    temp = a[0];
    temp = *p;
}

驚いたことに、ポインタを介したメモリアクセスは、配列を介したメモリアクセスによって取得された2つの命令に対して3つの命令を取得します。以下は対応するコードです。

; 5    : temp = a[0];

    mov eax, DWORD PTR _a
    mov DWORD PTR _temp, eax

; 6    : temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx

私が理解するのを手伝ってください。私はここで何が欠けていますか？

多くの回答やコメントで指摘されているように、私はコンパイル時定数を配列インデックスとして使用していたため、配列を介したアクセスがほぼ間違いなく簡単になりました。以下は、変数をインデックスとするアセンブリコードです。これで、ポインタと配列を介してアクセスするための同じ数の命令ができました。私のより広い質問はまだ有効です。ポインタを介したメモリアクセスは、より効率的であるとは言えません。

; 7    :        temp = a[i];

    mov eax, DWORD PTR _i
    mov ecx, DWORD PTR _a[eax*4]
    mov DWORD PTR _temp, ecx

; 8    : 
; 9    :    
; 10   :        temp = *p;

    mov eax, DWORD PTR _p
    mov ecx, DWORD PTR [eax]
    mov DWORD PTR _temp, ecx
4

14 に答える 14

77

ポインタを介したメモリアクセスは、配列を介したメモリアクセスよりも効率的であると言われています。

コンパイラが比較的愚かな獣だった過去には、それは真実だったかもしれません。高最適化モードで出力されたコードの一部を見るだけでgcc、それがもはや真実ではないことがわかります。そのコードのいくつかは理解するのが非常に難しいですが、一度理解すると、その輝きは明白です。

まともなコンパイラは、ポインタアクセスと配列アクセスに対して同じコードを生成するので、おそらくそのレベルのパフォーマンスについて心配する必要はありません。コンパイラーを作成する人々は、私たちが単なる人間よりも、ターゲットアーキテクチャーについてはるかによく知っています。コード（アルゴリズムの選択など）を最適化するときは、マクロレベルにさらに集中し、ツールメーカーに仕事を任せてください。

実際、コンパイラが全体を最適化していないことに驚いています

temp = a[0];

temp次の行で別の値で上書きされ、aマークが付けられていないため、行が存在しなくなりvolatileます。

競合他社を数桁上回った最新のVAXFortranコンパイラー（ここに私の年齢を示しています）のベンチマークについての昔からの都市伝説を覚えています。

コンパイラは、ベンチマーク計算の結果がどこにも使用されていないことを理解したため、計算ループ全体を忘却に最適化しました。したがって、実行速度が大幅に向上します。

更新：特定のケースで最適化されたコードがより効率的である理由は、場所を見つける方法のためです。aリンク/ロード時に決定された固定位置にあり、同時にそれへの参照が固定されます。したがってa[0]、または実際a[any constant]に固定された場所になります。

またp、同じ理由でそれ自体も固定された場所にあります。ただし、 *p（の内容pは可変であるため、正しいメモリ位置を見つけるために追加のルックアップが必要になります。

xさらに別の変数を0（ではなくconst）に設定して使用a[x]すると、余分な計算が発生することに気付くでしょう。

あなたのコメントの1つで、あなたは次のように述べています。

あなたが提案したように行うと、配列を介したメモリアクセスのための3つの命令も得られました（インデックスのフェッチ、配列要素の値のフェッチ、一時的な保存）。しかし、私はまだ効率を見ることができません。:-(

それに対する私の反応は、ポインタを使用する際の効率が見られない可能性が非常に高いということです。最新のコンパイラーは、配列操作とポインター操作を同じ基になるマシンコードに変換できることを理解するだけではありません。

実際、最適化をオンにしないと、ポインターコードの効率が低下する可能性があります。次の翻訳を検討してください。

int *pa, i, a[10];

for (i = 0; i < 10; i++)
    a[i] = 100;
/*
    movl    $0, -16(%ebp)              ; this is i, init to 0
L2:
    cmpl    $9, -16(%ebp)              ; from 0 to 9
    jg      L3
    movl    -16(%ebp), %eax            ; load i into register
    movl    $100, -72(%ebp,%eax,4)     ; store 100 based on array/i
    leal    -16(%ebp), %eax            ; get address of i
    incl    (%eax)                     ; increment
    jmp     L2                         ; and loop
L3:
*/

for (pa = a; pa < a + 10; pa++)
    *pa = 100;
/*
    leal    -72(%ebp), %eax
    movl    %eax, -12(%ebp)            ; this is pa, init to &a[0]
L5:
    leal    -72(%ebp), %eax
    addl    $40, %eax
    cmpl    -12(%ebp), %eax            ; is pa at &(a[10])
    jbe     L6                         ; yes, stop
    movl    -12(%ebp), %eax            ; get pa
    movl    $100, (%eax)               ; store 100
    leal    -12(%ebp), %eax            ; get pa
    addl    $4, (%eax)                 ; add 4 (sizeof int)
    jmp     L5                         ; loop around
L6:
*/

その例から、ポインタの例が長く、不必要にそうなっていることが実際にわかります。変更せずに複数回ロードpaされ、実際にとを交互に繰り返します。ここでのデフォルトの最適化は基本的にまったくありません。%eax%eaxpa&(a[10])

最適化レベル2に切り替えると、取得するコードは次のようになります。

    xorl    %eax, %eax
L5:
    movl    $100, %edx
    movl    %edx, -56(%ebp,%eax,4)
    incl    %eax
    cmpl    $9, %eax
    jle     L5

アレイバージョンの場合、および：

    leal    -56(%ebp), %eax
    leal    -16(%ebp), %edx
    jmp     L14
L16:
    movl    $100, (%eax)
    addl    $4, %eax
L14:
    cmpl    %eax, %edx
    ja      L16

ポインタバージョンの場合。

ここではクロックサイクルの分析は行いませんが（作業が多すぎて基本的に怠惰なので）、1つ指摘しておきます。アセンブラ命令に関しては、両方のバージョンのコードに大きな違いはありません。また、最新のCPUが実際に実行される速度を考えると、これらの操作を何十億回も実行しない限り、違いに気付くことはありません。私はいつも読みやすさのためにコードを書くことを好み、それが問題になった場合にのみパフォーマンスを心配する傾向があります。

余談ですが、あなたが参照するそのステートメントは次のとおりです。

5.3ポインターと配列：ポインターのバージョンは一般的に高速ですが、少なくとも初心者にとっては、すぐに把握するのがやや困難です。

K＆Rの最も初期のバージョンにまでさかのぼります。これには、関数がまだ記述されている私の古代の1978年のものが含まれます。

getint(pn)
int *pn;
{
    ...
}

コンパイラはそれ以来、非常に長い道のりを歩んできました。

于 2010-02-21T12:01:38.363 に答える
11

組み込みプラットフォームをプログラミングしている場合、ポインタメソッドはインデックスを使用するよりもはるかに高速であることがすぐにわかります。

struct bar a[10], *p;

void foo()
{
    int i;

    // slow loop
    for (i = 0; i < 10; ++i)
        printf( a[i].value);

    // faster loop
    for (p = a; p < &a[10]; ++p)
        printf( p->value);
}

スローループは毎回+（i * sizeof（struct bar））を計算する必要がありますが、2番目のループは毎回pにsizeof（struct bar）を追加する必要があります。乗算操作は、多くのプロセッサの加算よりも多くのクロックサイクルを使用します。

ループ内でa[i]を複数回参照すると、実際に改善が見られ始めます。一部のコンパイラはそのアドレスをキャッシュしないため、ループ内で複数回再計算される場合があります。

構造体を使用して複数の要素を参照するようにサンプルを更新してみてください。

于 2010-02-21T15:49:24.373 に答える
8

最初のケースでは、コンパイラは配列のアドレス（これは最初の要素のアドレスでもあります）を直接知っており、それにアクセスします。2番目のケースでは、彼はポインターのアドレスを知っており、そのメモリー位置を指すポインターの値を読み取ります。これは実際には1つの追加の間接参照であるため、ここではおそらく低速です。

于 2010-02-21T12:00:28.350 に答える
8

速度は、何よりもループで得られます。配列を使用する場合は、インクリメントするカウンターを使用します。位置を計算するために、システムはこのカウンターに配列要素のサイズを掛けてから、最初の要素のアドレスを追加してアドレスを取得します。ポインタを使用すると、次の要素に移動するために必要なのは、すべての要素がメモリ内で互いに隣接していると仮定して、現在のポインタを要素のサイズで増やして次のポインタを取得することです。

したがって、ポインタ演算は、ループを実行するときに計算が少し少なくなります。また、配列内でインデックスを使用するよりも、適切な要素へのポインタを使用する方が高速です。

ただし、最近の開発では、多くのポインタ操作が徐々に削除されています。プロセッサはどんどん速くなり、配列はポインタよりも管理しやすくなっています。また、配列はコードのバグの量を減らす傾向があります。配列はインデックスチェックを許可し、配列外のデータにアクセスしていないことを確認します。

于 2010-02-21T12:19:51.833 に答える
8

ポインターは自然に単純な帰納法変数を表現しますが、添え字は本質的に、より高度なコンパイラーの最適化を必要とします

多くの場合、添え字付きの式を使用するだけで、問題に追加のレイヤーを追加する必要があります。下付き文字iをインクリメントするループは、ステートマシンと見なすことができ、式a [i]は、使用されるたびに、各要素のサイズにiを掛けて、ベースアドレスに追加することを技術的に要求します。

そのアクセスパターンをポインタを使用するように変換するには、コンパイラはループ全体を分析し、たとえば、各要素がアクセスされていることを確認する必要があります。次に、コンパイラは、添え字に要素サイズを乗算する複数のインスタンスを、前のループ値の単純な増分で置き換えることができます。このプロセスは、共通部分式除去と誘導変数強度低減と呼ばれる最適化を組み合わせたものです。

ポインターを使用して書き込む場合、プログラマーは通常、配列をステップスルーするだけなので、最適化プロセス全体は必要ありません。

コンパイラが最適化を実行できる場合とできない場合があります。近年、洗練されたコンパイラが手元にあることが一般的であるため、ポインタベースのコードが常に高速であるとは限りません。

通常、延滞は連続している必要があるため、ポインタのもう1つの利点は、増分的に割り当てられた複合構造を作成することです。

于 2010-02-22T00:09:03.770 に答える
7

paxdiabloが言ったように、どんな新しいコンパイラでもそれらは非常に似たものになります。

さらに、配列がポインターよりも高速である状況を見ました。これは、ベクトル演算を使用するDSPプロセッサ上にありました。

この場合、配列の使用は制限ポインターの使用と同様でした。2つの配列を使用することにより、コンパイラは、それらが同じ場所を指していないことを暗黙的に認識しているためです。ただし、2ポインターを処理する場合、コンパイラーはそれらが同じ場所を指していると見なし、パイプの裏打ちをスキップする可能性があります。

例えば：

int a[10],b[10],c[10];
int *pa=a, *pb=b, *pc=c;
int i;

// fill a and b.
fill_arrays(a,b);

// set c[i] = a[i]+b[i];
for (i = 0; i<10; i++)
{
   c[i] = a[i] + b[i];
}

// set *pc++ = *pa++ + *pb++;
for (i = 0; i<10; i++)
{
   *pc++ = *pa++ + *pb++;
}

ケース1の場合、コンパイラはaとbを追加し、cに値を格納するパイプライニングを簡単に実行します。

ケース2の場合、コンパイラはCに保存しているときにaまたはbを上書きしている可能性があるため、パイプラインを作成しません。

于 2010-02-21T12:21:08.823 に答える
3

これは非常に古い質問であり、回答済みです。そのため、回答する必要はありません。しかし、私は簡単な答えに気づかなかったので、それを提供しています。

答え：間接アクセス（ポインタ/配列）は（ベース）アドレスをロードするために1つの追加命令を追加する可能性がありますが、その後のすべてのアクセス（配列の場合は要素/構造体へのポインタの場合はメンバー）は1つの命令である必要がありますこれは、すでにロードされている（ベース）アドレスへのオフセットの単なる追加であるためです。したがって、ある意味では、直接アクセスと同じくらい優れています。そのため、ほとんどの場合、配列/ポインターを介したアクセスは同等であり、要素アクセスも変数への直接アクセスと同じくらい優れています。

元。10個の要素を持つ配列（またはポインター）または10個のメンバーを持つ構造体（構造体へのポインターを介してアクセス）があり、要素/メンバーにアクセスしている場合、最初に1回だけ追加の命令が必要になります。その後、すべての要素/メンバーアクセスは1つの命令になります。

于 2013-08-02T21:46:45.820 に答える
2

ここであなたの質問に対する良い答えを得ていますが、あなたは学んでいるので、そのレベルでの効率はめったに目立たないことを指摘する価値があります。

最高のパフォーマンスを得るためにプログラムを調整するときは、プログラムの構造におけるより大きな問題を見つけて修正することに少なくとも同じくらい注意を払う必要があります。それらが修正された後、低レベルの最適化はさらに違いを生む可能性があります。

これを行う方法の例を次に示します。

于 2010-02-21T21:27:58.983 に答える
2

以前は、ポインタは配列よりも高速でした。確かに、C言語が設計されたとき、ポインターはかなり高速でした。しかし、最近では、配列がより制限されているため、オプティマイザーは通常、ポインターを使用する場合よりも配列を最適化するためのより良い仕事をすることができます。

最新のプロセッサの命令セットも、アレイアクセスの最適化に役立つように設計されています。

つまり、最近では、特にインデックス変数を使用するループで使用する場合、配列の方が高速になることがよくあります。

もちろん、リンクリストなどのポインターを使用することもできますが、インデックス変数を使用するのではなく、配列内でポインターをウォークスルーするという昔の最適化は、最適化されていない可能性があります。

于 2010-02-21T21:37:35.877 に答える
1

「ポインタバージョンは一般的に高速になります」とは、ほとんどの場合、配列と添え字（コンパイラが配列の先頭からアドレスをシフトします）。ただし、最新のプロセッサと最適化コンパイラでは、通常の場合の配列アクセスはポインタアクセスよりも遅くはありません。

特にあなたの場合、同じ結果を得るには、最適化をオンにする必要があります。

于 2010-02-21T12:04:48.500 に答える
1

0は定数として定義されているため、a [0]も定数であり、コンパイラーはコンパイル時にそれがどこにあるかを認識します。「通常の」場合、コンパイラはベース+オフセットから要素アドレスを計算する必要があります（オフセットは要素サイズに従ってスケーリングされます）。

OTOH、pは変数であり、間接参照には追加の移動が必要です。

一般的に、配列インデックスは内部的にポインタ演算として処理されるため、K＆Rが何をしようとしていたのかわかりません。

于 2010-02-21T12:05:03.480 に答える
1

ほとんどの人がすでに詳細な回答をしているので、直感的な例を示します。配列とポインタをより大規模に使用する場合、ポインタを使用する効率はより重要になります。たとえば、大きなlong intデータセットをいくつかのサブセットに並べ替えて並べ替えてから、それらをマージする場合です。

long int * testData = calloc(N, sizeof(long int));

2017年の毎日のN8GRAMマシンの場合、最大400000000に設定できます。これは、この元のデータセットに約1.5Gのメモリを使用することを意味します。また、を使用している場合は、を使用MPIしてデータをすばやく分離できます

MPI_Scatterv(testData, partitionLength, partitionIndex, MPI_LONG, MPI_IN_PLACE, N/number_of_thread, MPI_LONG, 0, MPI_COMM_WORLD);

単純に、同一の各部分の長さとしてparitionLength格納するポインタとして扱うことができ、インデックスを非現実的に見つめるN/number_of_threadsを格納するポインタとして扱うことができます。4コアのCPUがあり、ジョブを4つのスレッドにのみ分割するとします。参照によって間違いなく迅速な意味で仕事をします。ただし、配列を使用している場合、このルーチンは、最初にパーティションポイントを見つけるために、配列に対してポインター演算を実行する必要があります。これはポインタほど直接的ではありません。また、パーティション化されたデータセットをマージする場合は、N/number_of_threadpartitionIndexMPIK-way merge加速する。4つのソートされたデータセットを格納するための一時スペースが必要です。ここで、ポインタを使用する場合は、4つのアドレスを格納するだけで済みます。ただし、配列を使用すると、4つのサブ配列全体が格納されるため、効率的ではありません。MPI_Barrierプログラムがスレッドセーフであることを確認するために使用していない場合はMPI、メモリの実装が悪いと不平を言うことさえあります。配列メソッドとポインターメソッドで8スレッドの400000000の長い値をソートするための32Gマシンを入手しました。それぞれ、11.054980と13.182739を入手しました。また、サイズを1000000000に増やすと、配列を使用している場合、並べ替えプログラムが正常に実行されません。そのため、多くの人がCのスカラーを除くすべてのデータ構造にポインターを使用しています。

于 2017-05-03T22:55:01.373 に答える
0

私は、配列の議論よりも速いptrに少し驚いています。ここでは、これが当てはまらないという証拠は、最初はAbhijithのasmコードによって与えられています。

mov eax、dord ptr _a; //adress_aから値を直接ロードします

vs

mov eax、dword ptr _p; //アドレス/pの値をeaxにロードします

と

mov ecx、dword ptr [eax]; //ロードされたアドレスを使用して値にアクセスし、ecxに入れます

配列は固定アドレスを表すため、CPUは直接アクセスできますが、ptrでは、CPUが値にアクセスするために逆参照する必要があります。

配列オフセットを計算する必要があるため、コードの2番目のバッチは比較できません。これを行うには、ptrに対して、少なくとも1/2の命令が必要になります。

コンパイラがコンパイル時に推測できるもの（固定アドレス、オフセットなど）は、パフォーマンスの高いコードの鍵となります。反復コードの比較と変数への割り当て：

配列：

; 2791：tmp = buf_ai [l];

mov eax, DWORD PTR _l$[ebp]
mov ecx, DWORD PTR _buf_ai$[ebp+eax*4]
mov DWORD PTR _tmp$[ebp], ecx

vs

PTR

; 2796：tmp2 = * p;

mov eax, DWORD PTR _p$[ebp]
mov ecx, DWORD PTR [eax]
mov DWORD PTR _tmp2$[ebp], ecx

プラス

; 2801：++ p;

mov eax, DWORD PTR _p$[ebp]
add eax, 4
mov DWORD PTR _p$[ebp], eax

これは、配列のアドレスを使用して同時に値を取得するのと比較して、最初にアドレスをロードするためのものです。

よろしくお願いします

于 2018-06-06T11:12:44.493 に答える
0

配列とポインターの効率：ベクトル化の場合

gccのようなコンパイラを使用している場合は、自動ベクトル化の利点を活用するために、ポイント上で配列を使用することは非常に理にかなっています。

基本ブロックベクトル化（別名SLP）は、フラグ-ftree-slp-vectorizeによって有効になり、ループベクトル化と同じプラットフォーム依存フラグが必要です。基本ブロックSLPは、デフォルトで-O3で有効になっており、-ftree-vectorizeが有効になっている場合に有効になります。

ベクトル化できないループ

現在ベクトル化できないループの例：

例1：カウントできないループ：


while (*p != NULL) {
  *q++ = *p++;
}

ベクトル化可能なループ

「機能」は、例で示されているベクトル化機能を示します。

例1：

int a[256], b[256], c[256];
foo () {
  int i;

  for (i=0; i<256; i++){
    a[i] = b[i] + c[i];
  }
}

結論

したがって、多くの人がポインタまたは配列の方が優れていると言うでしょうが、いつものように、最良のものは次のとおりです。

  • 可能な限り最高のフラグを使用してコードをコンパイルするには
  • コンパイラエクスプローラを使用して、生成されたバイトコードを検査します
  • 最後に、実際の実行速度をベンチマークします。
于 2021-03-02T21:21:50.150 に答える