[解決済み] C 言語の配列に値が存在するかどうかを素早く見つけるには？

質問

サイズ256（できれば1024、ただし256が最小）の配列を繰り返し処理し、値が配列の内容に一致するかどうかをチェックする必要があるタイムクリティカルなISRを持つ組み込みアプリケーションを使用しています。A bool は true に設定されます。

マイクロコントローラはNXPのLPC4357、ARM Cortex M4コアで、コンパイラはGCCです。私はすでに最適化レベル 2 (3 はより遅い) を組み合わせ、関数をフラッシュではなく RAM に配置しました。また、ポインタ演算と for ループを使い、アップカウントの代わりにダウンカウントをしています（もし i!=0 をチェックする方が i<256 ). 結局、12.5μsの時間がかかってしまいましたが、これは実現可能なように大幅に削減する必要があります。これは私が現在使用している（擬似）コードです。

uint32_t i;
uint32_t *array_ptr = &theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
    if (compareVal == *array_ptr++)
    {
         validFlag = true;
         break;
     }
}

絶対的に最速の方法は何でしょうか？インラインアセンブリの使用は許可されています。他の「あまりエレガントでない」トリックも許可されます。

どのように解決するのですか？

パフォーマンスが最も重要な状況では、C コンパイラーは、手で調整したアセンブリ言語でできることに比べて最速のコードを生成しないことがほとんどです。このような小さなルーチンでは、asm コードを書くだけで、実行にかかるサイクル数を把握することができます。Cのコードをいじってコンパイラに良い出力を出させることはできるかもしれませんが、その方法では出力を調整するのに多くの時間を浪費することになるかもしれません。コンパイラ（特にマイクロソフト社製）はここ数年で大きく進歩しましたが、一般的なケースだけでなく、あなたの特定の状況で作業しているので、あなたの耳の間のコンパイラほどにはまだ賢くはないのです。コンパイラは、これを高速化できる特定の命令（例えばLDM）を利用しないかもしれませんし、ループをアンロールするほど賢くはないでしょう。ここで、私がコメントで述べた3つのアイデアを取り入れた方法を紹介します。ループのアンロール、キャッシュプリフェッチ、マルチロード（ldm）命令の活用です。命令サイクル数は配列要素あたり約3クロックになりますが、これはメモリの遅延を考慮したものではありません。

動作原理は？ ARMのCPU設計は、ほとんどの命令を1クロックサイクルで実行しますが、命令はパイプラインで実行されます。C コンパイラーは、間に他の命令を挟むことで、パイプラインの遅延をなくそうとします。元のC言語のコードのようにタイトなループの場合、メモリから読み込んだ値をすぐに比較しなければならないので、コンパイラは遅延を隠すのに苦労することになります。私のコードでは、2組の4つのレジスタを交互に使用することで、メモリ自体の遅延とデータのフェッチにかかるパイプラインの遅延を大幅に削減しています。一般に、大きなデータセットを扱うときに、コードが利用可能なレジスタのほとんどまたはすべてを使用しない場合、最大のパフォーマンスを得ることはできません。

; r0 = count, r1 = source ptr, r2 = comparison value

   stmfd sp!,{r4-r11}   ; save non-volatile registers
   mov r3,r0,LSR #3     ; loop count = total count / 8
   pld [r1,#128]
   ldmia r1!,{r4-r7}    ; pre load first set
loop_top:
   pld [r1,#128]
   ldmia r1!,{r8-r11}   ; pre load second set
   cmp r4,r2            ; search for match
   cmpne r5,r2          ; use conditional execution to avoid extra branch instructions
   cmpne r6,r2
   cmpne r7,r2
   beq found_it
   ldmia r1!,{r4-r7}    ; use 2 sets of registers to hide load delays
   cmp r8,r2
   cmpne r9,r2
   cmpne r10,r2
   cmpne r11,r2
   beq found_it
   subs r3,r3,#1        ; decrement loop count
   bne loop_top
   mov r0,#0            ; return value = false (not found)
   ldmia sp!,{r4-r11}   ; restore non-volatile registers
   bx lr                ; return
found_it:
   mov r0,#1            ; return true
   ldmia sp!,{r4-r11}
   bx lr

更新しました。 コメントには、私の経験が逸話的/価値がないと考え、証拠を必要とする懐疑的な人がたくさんいます。私は GCC 4.8 (Android NDK 9C から) を使用して、最適化 -O2 (すべての最適化をオン) で次の出力を生成しました。 ループアンロールを含む ). 私は上記の質問で提示されたオリジナルのCコードをコンパイルしました。以下は、GCCが生成したものです。

.L9: cmp r3, r0
     beq .L8
.L3: ldr r2, [r3, #4]!
     cmp r2, r1
     bne .L9
     mov r0, #1
.L2: add sp, sp, #1024
     bx  lr
.L8: mov r0, #0
     b .L2

GCCの出力はループをアンロールしないだけでなく、LDRの後のストールで1クロックを浪費しています。配列要素ごとに少なくとも8クロックを必要とします。ループを終了するタイミングを知るためにアドレスを使用するのは良い仕事ですが、コンパイラができる魔法のようなことはこのコードではどこにも見当たりません。ターゲット プラットフォーム上でコードを実行したことはありませんが (私は所有していません)、ARM コードのパフォーマンスの経験者なら誰でも、私のコードが高速であることを確認できます。

アップデート 2。 MicrosoftのVisual Studio 2013 SP2に、このコードでもっとうまくやる機会を与えてみました。それは私の配列初期化をベクトル化するためにNEON命令を使用することができましたが、OPによって書かれた線形値検索はGCCが生成したものに似ていました（私はより読みやすくするためにラベルの名前を変更しました）。

loop_top:
   ldr  r3,[r1],#4  
   cmp  r3,r2  
   beq  true_exit
   subs r0,r0,#1 
   bne  loop_top
false_exit: xxx
   bx   lr
true_exit: xxx
   bx   lr

申し上げたように、私は OP の正確なハードウェアを所有していませんが、3 つの異なるバージョンの nVidia Tegra 3 および Tegra 4 でパフォーマンスをテストし、その結果をすぐにここに投稿する予定です。

アップデート 3。

             My Code       MS Code
Surface RT    297ns         562ns
Surface RT 2  172ns         296ns