性能问题C++ - 通过数组搜索

Question

我有两个版本通过int数组搜索特定的值.

第一个版本是直接版本

int FindWithoutBlock(int * Arr, int ArrLen, int Val)
{
    for ( int i = 0; i < ArrLen; i++ )
        if ( Arr[i] == Val )
          return i;
 return ArrLen;
}

第二个版本应该更快.传递的数组需要比前一种情况大一个元素.假设有5个值的数组,则分配6个整数然后执行以下操作

int FindWithBlock(int * Arr, int LastCellIndex, int Val)
{
    Arr[LastCellIndex]  = Val;

    int i;
    for ( i = 0 ; Arr[i] != Val; i++ );
    return i;
}

这个版本应该更快 - 你不需要通过Arr每次迭代检查数组边界.

现在是"问题".在Debug中的100K元素阵列上运行这些函数100K次时,第二个版本大约快2倍.然而,在Release中,第一个版本的速度提高了大约6000倍.问题是为什么.

可以在http://eubie.sweb.cz/main.cpp找到演示此功能的程序

任何见解都非常感谢.丹尼尔

Answer 1

以下是使用DevStudio 2005的结果:

调试:

• 没有阻止:25.109
• 使用块:19.703

发布:

• 没有块:0
• 使用块:6.046

从命令行运行它非常重要,而不是从DevStudio中运行,DevStudio会影响应用程序的性能.

了解实际情况的唯一方法是查看汇编代码.这是发布中生成的汇编程序: -

FindWithoutBlock:
00401000  xor         eax,eax 
00401002  cmp         dword ptr [ecx+eax*4],0F4240h 
00401009  je          FindWithoutBlock+1Ah (40101Ah) 
0040100B  add         eax,1 
0040100E  cmp         eax,186A0h 
00401013  jl          FindWithoutBlock+2 (401002h) 
00401015  mov         eax,186A0h 
0040101A  ret              

请注意,编译器已删除ArrLen参数并将其替换为常量!它也将它作为一种功能.

这是编译器对其他函数(FindWithBlock)所做的事情: -

004010E0  mov         dword ptr [esp+38h],186A0h 
004010E8  mov         ebx,0F4240h 
004010ED  mov         dword ptr [esi+61A80h],ebx 
004010F3  xor         eax,eax 
004010F5  cmp         dword ptr [esi],ebx 
004010F7  je          main+0EFh (40110Fh) 
004010F9  lea         esp,[esp] 
00401100  add         eax,1 
00401103  cmp         dword ptr [esi+eax*4],ebx 
00401106  jne         main+0E0h (401100h) 
00401108  cmp         eax,186A0h 
0040110D  je          main+0F5h (401115h) 
0040110F  call        dword ptr [__imp__getchar (4020D0h)] 
00401115  sub         dword ptr [esp+38h],1 
0040111A  jne         main+0CDh (4010EDh) 

这里,功能已经内联.这lea esp,[esp]只是一个7字节的nop来对齐下一条指令.代码将索引0分别检查到所有其他索引,但主循环肯定比FindWithoutBlock版本更严格.

嗯.这是调用FindWithoutBlock的代码: -

0040106F  mov         ecx,edi 
00401071  mov         ebx,eax 
00401073  call        FindWithoutBlock (401000h) 
00401078  mov         ebp,eax 
0040107A  mov         edi,186A0h 
0040107F  cmp         ebp,186A0h 
00401085  je          main+6Dh (40108Dh) 
00401087  call        dword ptr [__imp__getchar (4020D0h)] 
0040108D  sub         edi,1 
00401090  jne         main+5Fh (40107Fh) 

啊哈!FindWitoutBlock函数只被调用一次!编译器发现该函数每次都返回相同的值,并将其优化为单个调用.在FindWithBlock中,编译器不能做出相同的假设,因为您在搜索之前写入数组,因此每个调用(可能)数组都不同.

要测试这个,请添加如下volatile关键字: -

int FindWithoutBlock(volatile int * Arr, int ArrLen, int Val)
{
    for ( int i = 0; i < ArrLen; i++ )
        if ( Arr[i] == Val )
            return i;

    return ArrLen;
}

int FindWithBlock(volatile int * Arr, int LastCellIndex, int Val)
{
    Arr[LastCellIndex]  = Val;

    int i;
    for ( i = 0 ; Arr[i] != Val; i++ );

    return i;
}

这样做,两个版本都在相似的时间运行(6.040).看到内存访问是一个主要的瓶颈,FindWithoutBlock的更复杂的测试不会影响整体速度.