性能问题 C++ - 在数组中搜索

Question

我有两个搜索特定值的整数数组版本。

第一个版本是直接的。

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;
}

这个版本应该更快 - 每次迭代数组时不需要检查数组边界。

现在有一个“问题”。在调试中，将这些函数运行100K次在一个100K元素的数组上，第二个版本大约快了2倍。但是在发布版中，第一个版本约快了6000倍。问题是为什么。

可以在http://eubie.sweb.cz/main.cpp找到展示这一点的程序。

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

- Daniel Bencik

---

你使用的编译器和平台是什么？ - Skizz

我知道这不是重点，但至少要提一下std::find。 - Jon

在调试优化中，通常关闭优化，在发布时开启。你的第一个方法是静态的，因此编译器可以积极地进行优化，而你的第二个方法是动态的，因此编译器对其进行的优化较少。 - AndersK

只是随便想想。第一个for循环有2个关系运算符，而第二个for循环只有1个。 - tuxuday

std::find 不够好吗？ - Puppy

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的更复杂的测试不会影响总体速度。

- Skizz

---

有人不禁要想，为什么编译器会在发现FindWithoutBlock每次返回相同值后，还要用一个常数REPCOUNT来测试返回值呢？ - Skizz

Skizz，谢谢。然而，编译器如何知道每次都将返回ARRLEN？我的意思是，如果Val为5，则不会返回ARRLEN。因此，为了进行这种优化，编译器必须假定Arr1具有来自主函数的常量内容，并且必须检查其中是否列出了SearchVal = 1M。可以从编译器期望这样的优化吗？ - Daniel Bencik

@DanielBencik：编译器不知道返回值是什么，只知道每次都是相同的值（因为没有任何东西写入数组）。 - Skizz

最近我读到了一种很好的编写类型限定符的方法。与通常的"volatile int *"不同，写成"int volatile *"。这样可以口头上从右往左读出类型，这里我们有一个指向易失性整数的指针。 - user82238

使用 volatile 来愚弄优化器只意味着你的结果是无关紧要的，而不是你已经证明了相对函数运行时间的任何事情。 - Puppy

Answer 2

首先，令人作呕的C语言垃圾。 std::find 和迭代器？

但是，其次，编译器的优化器是针对第一种形式而不是第二种形式编写的。例如，它可以被内联、展开或矢量化，而第二种形式则不能。

在一般情况下，需要考虑缓存问题。您正在访问数组的末尾，然后转到开头- 这可能会导致缓存未命中。然而，在第一个块中，您只是按顺序愉快地遍历整个数组- 更具有缓存一致性。

- Puppy

---

我也考虑了缓存未命中，但这不可能是造成巨大差异的原因。如果内联是与inline关键字引起的相同的事情，那么我不认为这会导致速度不匹配。我尝试将两个函数都设置为内联，结果（速度）是相同的。然而，我的编译器优化知识非常有限，所以我很乐意接受任何新信息。 - Daniel Bencik

@Daniel：为什么不呢？随意触碰额外的缓存行会非常慢。 - Puppy

你是完全正确的。尝试将块设置在主函数中而不是函数本身中，现在两者运行速度相同。令人失望的是，减少一半的操作并没有产生任何速度提升。 - Daniel Bencik

由于C而不是C++？这不是我计划在现实生活中使用的东西，我想看看不必检查边界的影响，而这是我无法使用STL做到的。 - Daniel Bencik

@DeadMG：因为你对编译器做出了假设并发表了那样的评论，所以我给你打负分。这完全没有必要。代码没有任何问题。编译后的输出结果是编译器能够提供的最好的。C语言也没有任何问题（整个Linux内核都是用C语言编写的）。 - Skizz

Answer 3

这更像是一条扩展评论而不是答案。Skizz已经用“Aha！FindWithoutBlock函数只被调用了一次！”回答了这个问题。 测试驱动程序 我通常倾向于将测试驱动程序和测试文章的代码放在不同的文件中。首先，您不会交付测试驱动程序。另外，像您所做的那样合并它们会让优化器执行您真正不想做的事情，比如只调用该函数一次而不是100,000次。将它们分开可以让您为驱动程序和测试文章使用不同的优化级别。我倾向于编译未经优化的驱动程序，以便执行相同操作100K次的循环确实被执行100K次。另一方面，测试文章是使用预期发布的优化编译的。 getchar()的使用 在测试CPU利用率时，在测试循环内部使用任何I/O通常是一个坏主意。[删除了有误的分析的其余部分]更新：当要查找的项在数组中时，您的测试代码调用getchar。即使您的测试代码确保不会找到该项（因此不会调用getchar），仍然不建议进行该调用。请改用快速且无害的方法。 C与C++ 您的代码看起来更像是C±而不是C++。您使用malloc而不是new，您混合使用C和C++ I/O，并且您没有使用C++库，例如std::find。对于从C到C++转移的人来说，这是很常见的。了解类似std::find的东西是好的。这使您可以完全消除FindWithoutBlock函数。 过早优化 使用FindWithBlock公式的唯一原因是因为此搜索是瓶颈。那么这真的是瓶颈吗？FindWithoutBlock公式（甚至更好的是std::find）可以说是更好的选择，因为您不需要修改数组，因此可以将数组参数标记为const。由于您正在修改数组，因此无法使用FindWithBlock标记数组。

- David Hammen

---

糟糕，当项在数组中时，getchar会被调用。但是，如果找到该项（因为它需要不预先提示用户输入），使用getchar将产生疯狂的结果，所以这并不是世界上最好的主意。 - Skizz

哎呀，你说得对。即使这个调用没有被执行，我仍然不喜欢它存在的想法。我会修改我的回答。 - David Hammen

Answer 4

我观察到的是，在第一种情况下，编译器在运行时知道循环的大小（例如 < ArrLen）。而在第二种情况下，编译器无法知道。

- user82238

---

运行时没有编译器！另外，了解数组大小的更多信息有什么帮助呢？慢的部分是内存测试。 - Skizz

@Skazz：编译器可以发出代码，以便在运行时根据数组的大小采取不同的代码路径。如果您知道数组很小，可以将所有内容预加载到缓存中，然后运行循环。 - user82238

@MatthieuM。从多年来微软编译器所产生的结果来看，似乎循环展开很少被使用。当你看整个系统时，这是有道理的。在8086时代，循环展开帮助很大，但那时内存访问不是瓶颈。如今，访问内存是一个瓶颈，包括读取要执行的代码。这意味着更大的代码运行速度较慢，或者换句话说，紧密循环比展开循环更快。即使进行更多的分支，CPU中的微码也会做一些聪明的事情来减少条件分支的影响。 - Skizz

@Skizz：预取在页面边界处停止。我不是指C代码中的粗糙预取，而是以更微妙的方式，通过触碰内存（可能在代码流程中较早的位置）来引导预取器在需要时按照您的意愿执行。 - user82238

@Skazz：第一次加载会比较慢，因为预取器还不知道该预取什么。为什么不在进入循环前的几百个周期内先发出第一个元素和第二个元素的加载请求呢？ - user82238

Answer 5

第一个 for 循环每次迭代包含两个条件，而第二个 for 循环每次迭代只包含一个条件。对于大量的迭代，这种差异应该会显示出来，因为第二个条件和迭代器递增之间存在原始依赖关系。但我仍然认为加速不应该那么高。

- prathmesh.kallurkar

Answer 6

你的编译器很聪明。

如果你使用LLVM Try Out页面，你将获得以下生成的IR：

define i32 @FindWithoutBlock(i32* nocapture %Arr, i32 %ArrLen, i32 %Val) nounwind uwtable readonly

define i32 @FindWithBlock(i32* nocapture %Arr, i32 %ArrLen, i32 %Val) nounwind uwtable

唯一的区别是第一个函数上有readonly属性：

来自语言参考页面：

readonly

此属性表示该函数不会通过任何指针参数（包括byval参数）进行写入，也不会修改对调用方函数可见的任何状态（例如内存、控制寄存器等）。它可能会解引用指针参数并读取在调用方中设置的状态。只要使用相同的参数集和全局状态调用只读函数，它就始终返回相同的值（或以相同方式取消异常）。它不能通过调用C++异常抛出方法来取消异常。

这意味着，潜在地，优化器可以意识到该函数将始终返回相同的计算结果（对于给定的循环），并将其提升到循环外部。

- Matthieu M.

Answer 7

在第一个例子中，每次迭代都会检查两个条件：i < ArrLen 和 Arr[i] == Val。而在第二个例子中，只需要检查一个条件。这就是为什么第一个循环比第二个循环慢一倍。

使用GCC时，我无法观察到相同的行为：第一个循环仍然较慢。

使用-O0编译选项：

Without block: 25.83
With block: 20.35

使用-O3：

Without block: 6.33
With block: 4.75

我猜编译器以某种方式推断出数组中没有 SearchVal，因此没有理由调用搜索它的函数。

- Alex Bakulin

---

哎呀，这很奇怪。我使用的是Visual Studio 2010和Windows 7。这里有些非常可疑的事情，因为当我在VTune中分析代码时，我发现没有时间被用于调用FindWithoutBlock()函数。 - Daniel Bencik

将我的猜测作为答案的补充。 - Alex Bakulin

@Daniel：这被称为“内联”。 - Puppy