c++ - 性能问题 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 个值的数组，你分配六个整数，然后执行以下操作

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 的结果:

调试:

• 无 block :25.109
• block :19.703

发布:

• 无 block :0
• block 数: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 的更复杂测试不会影响整体速度。