我有一个具有时间要求严格的ISR的嵌入式应用程序,该应用程序需要循环访问大小为256(最好为1024,但最小为256)的数组,并检查值是否与数组内容匹配。在这种情况下,bool将设置为true。

该微 Controller 是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代码,并使编译器生成良好的输出,但是最终可能会浪费大量时间来调整输出。编译器(尤其是来自Microsoft的编译器)在过去的几年中已经取得了长足的进步,但是它们仍不如您耳边的编译器那么聪明,因为您正在处理的是特定情况,而不仅仅是一般情况。编译器可能未使用某些指令(例如LDM)来加快速度,因此不太可能聪明地展开循环。这是一种结合我在注释中提到的3个想法的方法:循环展开,缓存预取和使用多加载(ldm)指令。每个数组元素的指令周期数约为3个时钟,但这并未考虑内存延迟。

工作原理: ARM的CPU设计在一个时钟周期内执行大多数指令,但这些指令是在流水线中执行的。 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

更新:
评论中有很多怀疑者认为我的经历是轶事/毫无值(value),需要证明。我使用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之后的停顿时钟。每个阵列元素至少需要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:
我在Tegra 3和Tegra 4(Surface RT,Surface RT 2)上运行了我的代码和Microsoft编译的ARM代码。我对一个循环进行了1000000次迭代,但找不到匹配项,因此所有内容都在缓存中,并且很容易测量。
             My Code       MS Code
Surface RT    297ns         562ns
Surface RT 2  172ns         296ns

在这两种情况下,我的代码运行速度几乎都快一倍。大多数现代ARM CPU可能会给出相似的结果。

10-06 05:15
查看更多