快速查找C数组中是否存在一个值?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (79)

我有一个具有时间关键ISR的嵌入式应用程序,需要遍历256个数组(最好是1024,但最小为256),并检查一个值是否与数组内容匹配。 布尔将被设置为true,情况就是如此。 MCU是NXP LPC4357,ARM Cortex M4内核,编译器是GCC。

我已经组合了优化级别2(3较慢)并将函数放入RAM而不是闪存。 我也使用指针算术和for循环,它不是向下计数(检查i!= 0是否快于检查i <256)。 总而言之,我最终需要12.5us的持续时间,而这个持续时间必须大幅减少才可行。 这是我现在使用的(伪)代码:

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代码,并且很好地知道执行需要多少周期。编译器可能不会使用某些指令(例如LDM)来加快速度,而且它不太可能足够聪明地展开循环。

这里有一种方法,它结合了我在评论中提到的三种想法:循环展开、缓存预取和使用多加载(MultipleLoad,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

最新情况:我使用gcc 4.8(来自AndroidNDK9C)生成以下输出,并使用优化-O2。以下是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个时钟。它很好地使用了地址来知道何时退出循环,但是编译器能够做的所有神奇的事情在这段代码中都找不到。

更新2:我给了微软的VisualStudio 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(SurfaceRT,SurfaceRT 2)上运行我的代码和微软编译的ARM代码。我对一个循环进行了1000000次迭代,但没有找到匹配项,所以所有东西都在缓存中,而且很容易测量。

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

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

用户回答回答于

优化它有一个诀窍:

  • 如果数组中的最后一个条目包含您要查找的值,则返回true
  • 将要查找的值写入数组中的最后一个条目
  • 迭代数组,直到遇到要查找的值
  • 如果您在数组中的最后一个条目之前遇到过它,那么返回true
  • 返回假
bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    uint32_t x = theArray[SIZE-1];
    if (x == compareVal)
        return true;
    theArray[SIZE-1] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    theArray[SIZE-1] = x;
    return i != SIZE-1;
}

这将产生每次迭代一个分支,而不是每个迭代两个分支。

最新情况:

如果允许将数组分配给SIZE+1,然后可以去掉“最后一项交换”部分:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    theArray[SIZE] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    return i != SIZE;
}

还可以消除嵌入在theArray[i],而是使用以下方法:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t *arrayPtr;
    theArray[SIZE] = compareVal;
    for (arrayPtr = theArray; *arrayPtr != compareVal; arrayPtr++);
    return arrayPtr != theArray+SIZE;
}

如果编译器还没有应用它,那么这个函数肯定会应用它。另一方面,这可能会使优化器更难展开循环,因此必须在生成的程序集代码中验证这一点.

扫码关注云+社区