c - 違い - 配列 ポインタ渡し




Cでは、私の配列インデックスへのアクセスは速いですか、それともポインタによるアクセスは速いですか? (6)

templatetypedefはそれをまとめました。 彼の反応に何らかの支持を加えること。 これらの関数例を見てください。

unsigned int fun1 ( unsigned int *x )
{
    unsigned int ra,rb;

    rb=0;
    for(ra=0;ra<1000;ra++) rb+=*x++;
    return(rb);
}

unsigned int fun2 ( unsigned int *x )
{
    unsigned int ra,rb;
    rb=0;
    for(ra=0;ra<1000;ra++) rb+=x[ra];
    return(rb);
}

今gccはこれを作り出しました:

00000000 fun1:
   0:   e52d4004    push    {r4}        ; (str r4, [sp, #-4]!)
   4:   e1a03000    mov r3, r0
   8:   e2804efa    add r4, r0, #4000   ; 0xfa0
   c:   e3a00000    mov r0, #0
  10:   e1a02003    mov r2, r3
  14:   e492c004    ldr ip, [r2], #4
  18:   e5931004    ldr r1, [r3, #4]
  1c:   e2823004    add r3, r2, #4
  20:   e080000c    add r0, r0, ip
  24:   e1530004    cmp r3, r4
  28:   e0800001    add r0, r0, r1
  2c:   1afffff7    bne 10 
  30:   e49d4004    pop {r4}        ; (ldr r4, [sp], #4)
  34:   e12fff1e    bx  lr

00000038 fun2:
  38:   e3a03000    mov r3, #0
  3c:   e1a02003    mov r2, r3
  40:   e790c003    ldr ip, [r0, r3]
  44:   e2833004    add r3, r3, #4
  48:   e7901003    ldr r1, [r0, r3]
  4c:   e2833004    add r3, r3, #4
  50:   e082200c    add r2, r2, ip
  54:   e3530efa    cmp r3, #4000   ; 0xfa0
  58:   e0822001    add r2, r2, r1
  5c:   1afffff7    bne 40 
  60:   e1a00002    mov r0, r2
  64:   e12fff1e    bx  lr

コードは異なりますが、最適化の機会を逃したことに驚きました。

Clang / llvmはこれを生成しました:

00000000 fun1:
   0:   e3a01000    mov r1, #0
   4:   e3a02ffa    mov r2, #1000   ; 0x3e8
   8:   e1a03001    mov r3, r1
   c:   e2522001    subs    r2, r2, #1
  10:   e490c004    ldr ip, [r0], #4
  14:   e08c3003    add r3, ip, r3
  18:   e2c11000    sbc r1, r1, #0
  1c:   e182c001    orr ip, r2, r1
  20:   e35c0000    cmp ip, #0
  24:   1afffff8    bne c 
  28:   e1a00003    mov r0, r3
  2c:   e12fff1e    bx  lr

00000030 fun2:
  30:   e3a01000    mov r1, #0
  34:   e3a02ffa    mov r2, #1000   ; 0x3e8
  38:   e1a03001    mov r3, r1
  3c:   e2522001    subs    r2, r2, #1
  40:   e490c004    ldr ip, [r0], #4
  44:   e08c3003    add r3, ip, r3
  48:   e2c11000    sbc r1, r1, #0
  4c:   e182c001    orr ip, r2, r1
  50:   e35c0000    cmp ip, #0
  54:   1afffff8    bne 3c
  58:   e1a00003    mov r0, r3
  5c:   e12fff1e    bx  lr

コンパイラがまったく同じコード、ポインタ、またはオフセットを生成したことに気付くかもしれません。 そして、コンパイラを変更することによって、ポインタと配列のインデックスを変更するよりも優れていました。 私はllvmがもう少しうまくいったかもしれないと思います、私が私のコードがこれを引き起こすために何をしたか理解するためにもう少しこれを研究する必要があるでしょう。

編集:

私はコンパイラがポインタに有利なldr rd、[rs]、#4命令を最低限使用することを望み、そしてそれがオフセットではなくポインタのようにそれを配列アドレスを破壊することができることを望んだ。配列に(そして上記の命令を使う、これは基本的にclang / llvmがしたことです)。 あるいは、それがldr rd、[rm、rn]命令を使用するような配列のことをしたならば。 基本的に、コンパイラの1つがこれらの解決策の1つを生成することを望んでいました:

funa:
    mov r1,#0
    mov r2,#1000
funa_loop:
    ldr r3,[r0],#4
    add r1,r1,r3
    subs r2,r2,#1
    bne funa_loop
    mov r0,r1
    bx lr

funb:
    mov r1,#0
    mov r2,#0
funb_loop:
    ldr r3,[r0,r2]
    add r1,r1,r3
    add r2,r2,#4
    cmp r2,#0x4000
    bne funb_loop
    mov r0,r1
    bx lr

func:
    mov r1,#0
    mov r2,#4000
    subs r2,r2,#4
func_loop:
    beq func_done
    ldr r3,[r0,r2]
    add r1,r1,r3
    subs r2,r2,#4
    b func_loop
func_done:
    mov r0,r1
    bx lr

かなりそこに着くのではなく、かなり近づいた。 これは楽しい練習でした。 上記はすべてARMアセンブラです。

一般に、(私の特定のCコードの例ではなく、必ずしもARMではありません)、レジスタベースのアドレスからロードする一般的なアーキテクチャ(ldr r0、[r1])とレジスタインデックス/オフセットのロード(ldr r0、[r1、r2])ここで、アドレスは2つのレジスタの合計です。 1つのレジスタは理想的には配列のベースアドレス、2つ目のインデックスはインデックス/オフセットです。 レジスタからの前者のロードはポインタに適しており、後者は配列に適しています。 あなたのCプログラムがポインタやインデックスを変更したり動かしたりしようとしていないのであれば、どちらの場合も静的アドレスが計算されて通常のロードが使用されることを意味します。 ポインタ/インデックスを変更するもっと興味深いケースです。

Pointer

ldr r0,[r1]
...
add r1,r1,some number

Array index

ldr r0,[r1,r2]
...
add r2,r2,some number

(必要に応じて、ロードをストアに、アドをサブに置き換えます)

いくつかのアーキテクチャは3レジスタレジスタインデックス命令を持っていないので、そこで何かをする必要があります。

array index:
mov r2,r1
...
ldr r0,[r2]
...
add r2,r2,some number

あるいは、コンパイラによっては、本当に悪い結果になる可能性があります。デバッグ用に最適化せずにコンパイルした場合、および3つのレジスタを追加する必要がないと仮定した場合には特にそうです。

array index:
mov r2,#0
...
mov r3,r1
add r3,r2
ldr r4,[r3]
...
add r2,some number

そのため、2つのアプローチが同じである可能性はかなりあります。 ARMに見られるように、それは2つの(即時のための制限内で)ポインタ命令を1つに結合することができ、それを少し速くします。 配列インデックスの解決策は、より多くのレジスタを消費します。アーキテクチャで使用可能なレジスタの数によっては、(ポインタを使用するよりも)レジスタをスタックにすばやく頻繁にスワップアウトする必要があります。 ベースアドレスを破棄しても構わない場合、一番下の行がパフォーマンスの観点から有利な点があります。 それはあなたのコードとコンパイラと関係があります。 私にとっては読みやすさが発揮され、配列の方が読みやすく、従うのが簡単だと感じます。次に、そのポインタを保持してmallocを解放するか、そのメモリをもう一度通過させる必要があります。インデックス、それが1回限りのパスで、私がベースアドレスを破壊することを気にしないのであれば、私はポインタを使います。 パフォーマンスを重視する場合は、コンパイラが生成したコードを使用して上記で説明したように、解決策をアセンブラで手動でコーディングします(推奨されるアプローチに基づいてコンパイラに最初に実行させます)。

Cでは、配列インデックスへのアクセスは速いですか、それともポインタによるアクセスは速いですか? より速いということは、私はそれがより少ないクロックサイクルを取るだろうことを意味します。 配列は定数配列ではありません。


あなたの質問に意味のある答えはありません。 言語レベルの操作には、特定の「スピード」はありません。 それだけでは、「速く」も「遅く」もできません。

CPU命令だけが速くても遅くてもよく、CPU命令だけがCPUサイクルを消費できます。 何らかの形でCPU命令から言語レベルの操作(これらのCPU命令はから生成されたもの)にこの「スピード」の概念を引き継ぐためには、コンテキストを知る必要があります。 これは、同じ言語レベルの操作で、異なるコンテキストでまったく異なるCPU命令が生成される可能性があるためです(これは、コンパイラの設定などにも依存する可能性があることも言及しません)。

つまり、実際のコードを投稿してください。 抽象的な文脈のない質問として、それは単に意味をなさない。


インデックスを介して配列にアクセスするとき、実際には2つの操作を実行しています。 加算 (インデックスをベース配列アドレスに追加する)、次にメモリアクセス (実際には結果のアドレスにあるものを読み書きする)です。 私はあなたが「ポインタによるアクセス」について話しているとき、あなたはあなたがすでにターゲット要素へのポインタを持っていることを意味すると思います。 したがって、論理的には、ポインタを使用すると「加算」部分が節約されるため、高速になるか、少なくとも遅くなることはありません。

しかしながら...

おおまかな概算として、現代のコンピュータでは、メモリアクセスは追加よりもはるかに高価です(特にキャッシュから外れた場合)ので、違いがあるとしてもわずかです。 いくつかのアーキテクチャ(例えばx86やPowerPC)では、追加とメモリアクセスは単一のオペコードに結合することができます。 配列アドレスがコンパイル時定数であるかどうか(つまり、配列は定数データではなく、グローバル変数として宣言されているのに対して、 malloc()取得されたブロックmalloc()によっても、状況は異なります。 配列を使用すると、(特にrestrictキーワードが使用restrictれている場合は)ジェネリックポインターに関して、コンパイラがより優れたコードを見つけるのに役立ちます。 コンテキストは大きな影響を及ぼします(たとえば、その時点で空きレジスタがいくつあるかなど)。

そう:

  • あなたの質問に対する絶対的な答えはありません。 あなたは努力しなければなりません。
  • 検出可能な違いがある場合(おそらくないこともあります)、どちらの方向に予測するのは難しいです。特定のコンパイラバージョンや最適化フラグ、プロセッサアーキテクチャ、モデルなど、さまざまな外部要因に依存します。メモリレイアウトなど。
  • アセンブリに関するいくらかの深い知識とコンパイルのちょっとした理論がなければ、信頼できる最適化を得ることはできません。
  • 最初に正しいコードを作ることに集中してから、最適化についてのみ心配するべきです。 現実的な条件で正しく測定されるまで、パフォーマンスの問題はありません。

一般的な部分式を明示的に削除するとうまくいく場合があります。 x86またはRISCアーキテクチャとオプティマイザの品質を使用している場合は、違いがあるかもしれません。

配列またはインデックス付き構造体を実行する必要があるルーチンを作成するときには、配列/構造体メンバのベースへのポインタを計算し、それを使用してアドレス指定します。 基本ケース

struct SOMETHING list[100];

int find_something (...)
{
  int i;

  i=0;
  while (i<(sizeof(list)/sizeof(struct SOMETHING)))
  {
    if (list[i].active && list[i].last_access+60<current_time) return i;

    ++i;
  }
  return -1;
}

洗練することができます(すなわち、コンパイラがより良いコードを生成するのを助けます):

int find_something (...)
{
  int i;
  struct SOMETHING *pList;

  i=0;
  while (i<(sizeof(list)/sizeof(struct SOMETHING)))
  {
    pList=&list[i];
    if (pList->active && pList->last_access+60<current_time) return i;

    ++i;
  }
  return -1;
}

これは説明のためだけのもので、コードの単純さはおそらく暗黙のうちにポインターを生成しますが、ルーチンがより複雑な場合はそうではないかもしれません。 "list [i]"を使う 最初の例のように(x86上で)一度アドレスを生成して格納するのに十分なレジスタを持っていないコンパイラのリスク(RISC haha​​)を実行します。 x86の場合、ポインタを格納するためにローカル変数が必要であり、明示的に指示されない限り、スタック変数を作成するコンパイラはほとんどありません。 RISCでは、コンパイラは自由に使えるレジスタをたくさん持っているので、通常は繰り返しごとに1回ポインタを作成する(そして保持する)ことが価値があると判断します。

ループをさらに洗練することができます。

  pList=list;
  i=0;
  while (i<(sizeof(list)/sizeof(struct SOMETHING)))
  {
    if (pList->active && pList->last_access+60<current_time) return i;

    pList+=1;    
    ++i;
  }

この構造は、アドレス計算のオーバーヘッドがありません。 "pList + = 1"(他の人が "++ pList"を好む場合があります)は、定数値(個々の行/メンバーのサイズに等しい)をpListに追加します。

そしてさらに:

  pList=list;
  pEndList=&list[sizeof(list)/sizeof(struct SOMETHING)];
  while (pList!=pEndList)
  {
    if (pList->active && pList->last_access+60<current_time) return pList-list;

    pList+=1;    
  }

これは、インデックスの増分を削除し、ループ内で1回の乗算と1回の除算で置き換えます(return構造内で1回だけ実行されます)。

私たちの主張は、どの構造が受け入れられるかは、それらが存在する関数のサイズと複雑さによって決定されるということです。 私はおそらくこの構造を300行の関数から始めて考えるのに十分なほど複雑ではないと考えるかもしれませんが、上のような状況では? 検索が全体処理の重要な部分である場合 スピードアップが十分大きければ?

それではどうですか? 長所と短所。 それは常に長所と短所です。 それらを最大限に活用する。 絶対? まれに(あるとしても)。


同じ。 それはすべてO(1)であり、時計の時間はごくわずかです。 あなたは基本的にメモリアドレスにアクセスしています。


最低レベルでは、これらの操作はほとんど同じものにコンパイルされる傾向があります。 特に興味があるなら、Cコンパイラにアセンブリ出力を生成させるべきです( gcc -Sようなもの)ので、特に最低でも以下に依存するのでチェックできます。

  • ターゲットプラットフォーム
  • あなたのコンパイラ。
  • 最適化レベル

違いがあったとしても(それは疑わしいですが)、そのレベルのマイクロ最適化はあなたがそれに注いだ努力の価値がほとんどないことがわかります。 アルゴリズムの改善などのマクロ最適化は、投資収益率を高めるためのものです。

このような状況では、影響が最小限になる可能性が高いので、 読みやすさを考慮して常に最適化します。





assembly