8

我有两个版本的通过 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找到一个演示这一点的程序

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

4

7 回答 7

8

这是我使用 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 的更复杂测试不会影响整体速度。

于 2012-05-25T11:06:44.237 回答
2

一、ewwwwww恶心的C垃圾。std::find和迭代器？

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

在一般情况下，考虑缓存问题。您正在触摸数组的末尾，然后转到开头 - 这可能是缓存未命中。然而，在第一个块中，您只需要按顺序通过数组 - 更多缓存一致。

于 2012-05-25T10:48:16.357 回答
2

这更像是一个扩展的评论而不是一个答案。Skizz 已经用“啊哈！FindWithoutBlock 函数只被调用一次！ ”回答了这个问题。

测试驱动程序
我通常倾向于将测试驱动程序的代码和测试文章放在单独的文件中。一方面，您不会提供测试驱动程序。另一方面，像你做的那样组合它们可以让优化器做你真的不想做的事情，比如调用函数一次而不是 100,000 次。将它们分开可以让您对驱动程序和测试文章使用不同的优化级别。我倾向于编译未优化的驱动程序，以便真正执行 100K 次相同事情的循环执行 100K 次。另一方面，测试文章是使用预期发布的优化编译的。

使用 getchar()
在测试 CPU 利用率时，在测试循环中使用任何 I/O 通常是个坏主意。当要找到的项目不在数组中时，您的测试代码正在调用 getchar。[省略了其余的错误分析。]更新：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由于您正在修改数组，因此无法将数组标记为。

于 2012-05-25T12:33:50.263 回答
0

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

于 2012-05-25T10:29:08.787 回答
0

在第一个示例中，每次迭代都会检查两个条件：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数组，因此没有理由调用搜索它的函数。

于 2012-05-25T10:35:02.920 回答
0

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

于 2012-05-25T10:39:38.607 回答
0

你的编译器很聪明。

如果您使用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第一个函数上存在属性：

从语言参考页面：

只读

该属性表明该函数不写入任何指针参数（包括 byval 参数）或以其他方式修改调用者函数可见的任何状态（例如内存、控制寄存器等）。它可以取消引用指针参数并读取可能在调用者中设置的状态。当使用相同的参数集和全局状态调用时，只读函数总是返回相同的值（或以相同的方式展开异常）。它不能通过调用 C++ 异常抛出方法来解除异常。

这意味着，优化器可能会意识到该函数将始终返回相同的计算（对于给定的循环）并将其提升到循环之外。

于 2012-05-25T13:07:59.857 回答