简单的()循环基准测试与任何循环绑定需要相同的时间

Question

我愿意编写一个代码,让我的CPU执行一些操作,看看他花了多少时间来解决它们.我想做一个从i = 0到i <5000的循环,然后将i乘以一个常数和时间.我最终得到了这个代码,它没有错误,但即使我更改循环i <49058349083或者如果i <2它需要相同的时间,它只需要0.024秒来执行代码.是什么错误？

PD:我昨天开始学习C++我很抱歉,如果这是一个非常容易回答的问题,但我找不到解决方案

#include <iostream>
#include <ctime>

using namespace std;

int main () {
    int start_s=clock();

    int i;
    for(i=0;i<5000;i++){
        i*434243;
    }

    int stop_s=clock();
    cout << "time: "<< (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000;

    return 0;
}

Answer 1

顺便说一句，如果你真的做到了i<49058349083，gcc 和 clang 会在 32 位int（包括 x86 和 x86-64）系统上创建一个无限循环。49058349083 大于INT_MAX. 大文字数字被隐式提升为足够大的类型以容纳它们，因此您有效地做到了 (int64_t)i < 49058349083LL，这对于 的任何可能值都是正确的int i。

有符号溢出是 C++ 中的未定义行为，循环内部没有副作用的无限循环也是如此（例如系统调用），所以我检查了 Godbolt 编译器资源管理器，看看它是如何在启用优化的情况下真正编译的。有趣的事实：i*10当条件是始终为真的比较而不是像42.

像这样的循环在根本上是有缺陷的。

您可以使用 Google 的基准测试包对完整的非内联函数进行微基准测试（您将如何对函数的性能进行基准测试？），但是要通过将某些内容放入重复循环中来学习任何有用的东西，您必须了解很多关于编译器如何编译的信息到 asm，正是您要测量的内容，以及如何让优化器使 asm 类似于您在某些实际使用上下文中从代码中获得的内容。例如，通过使用内联 asm 要求它在寄存器中获得某个结果，或者通过分配给一个volatile变量（这也有进行存储的开销）。

如果这听起来比您希望的要复杂得多，那就太糟糕了，这是有充分理由的。

这是因为编译器是极其复杂的机器部件，通常可以从源代码中生成相当高效的可执行文件，这些可执行文件的编写是为了清楚地表达人类读者正在发生的事情，而不是避免冗余工作或看起来像高效的机器语言实现（这就是您的 CPU 实际运行）。

微基准测试很难- 除非您了解代码的编译方式以及您真正测量的内容，否则您无法获得有意义的结果。

优化编译器旨在创建一个可执行文件，该可执行文件产生与 C++ 源代码相同的结果，但运行速度尽可能快。性能不是可观察的结果，因此使程序更高效总是合法的。这是“as-if”规则：“as-if”规则究竟是什么？

您希望您的编译器不浪费时间和未使用的代码大小计算结果。在编译器将一个函数内联到调用者之后，通常会发现它计算的一些东西没有被使用。编写良好的 C++ 代码有很多可以丢弃的工作是正常的，包括完全优化临时变量；这不是一件坏事，不这样做的编译器会很糟糕。

请记住，您正在为 C++ 抽象机编写代码，但编译器的工作是将其转换为 CPU 的汇编语言（或机器代码）。汇编语言与 C++ 完全不同。（而现代高性能 CPU 也可以乱序执行指令，同时遵循他们自己的“as-if”规则来保留编译器生成的代码按程序顺序运行的错觉。但 CPU 不能丢弃工作，只能重叠它。）

在一般情况下int * int，您不能对C++ 中的二元运算符进行微基准测试，即使只是为了您自己的桌面（在其他硬件/不同编译器上更不用说）。不同上下文中的不同用法将编译为不同的代码。即使您可以创建某个循环版本来测量有用的东西，它也不一定能告诉您foo = a * b其他程序中的成本有多高。另一个程序可能会遇到乘法延迟而不是吞吐量的瓶颈，或者将乘法与附近的其他一些操作a或b或任何数量的事情结合起来。

不要禁用优化

您可能认为仅禁用优化（例如gcc -O0代替gcc -O3）会很有用。但是这样做的唯一方法也引入了反优化，例如在每个 C++ 语句之后将每个值存储回内存，以及为下一个语句从内存重新加载变量。这使您可以在调试已编译程序时修改变量值，甚至跳转到同一函数中的新行，并且仍然可以通过查看 C++ 源获得预期的结果。

支持这种级别的干扰会给编译器带来巨大的负担。存储/重新加载（存储转发）在典型的现代 x86 上有大约 5 个周期的延迟。这意味着反优化循环最多只能每 ~6 个时钟周期运行一次迭代，而对于像looptop: dec eax /jnz looptop循环计数器位于寄存器中的紧密循环，则需要 1 个周期。

没有太多中间立场：编译器没有选项可以让 asm 看起来像 C++ 源代码，而是将值保存在跨语句的寄存器中。无论如何，这不会有用或没有意义，因为这不是它们在启用完全优化的情况下编译的方式。（gcc -Og可能有点像这样。）

花时间修改 C++ 以使其运行得更快完全-O0是在浪费时间：C 循环优化帮助最终分配（禁用编译器优化）。

注意：反优化调试模式 ( -O0) 是大多数编译器的默认模式。它也是“编译快速”模式，因此可以很好地查看您的代码是否完全编译/运行，但对于基准测试无用。生成的编译器生成的 asm 的运行速度取决于硬件，但不会告诉您有关优化代码运行速度的任何信息。（例如，在没有优化的情况下编译时，添加冗余分配的答案会加快代码速度是一些相当微妙的英特尔 Sandybridge 系列存储转发延迟行为，直接由存储/重新加载和循环计数器上的循环瓶颈在内存中引起。请注意，问题的第一个版本是询问为什么这样做会使 C 更快，这正确地被否决了，因为基准测试-O0很愚蠢。当我将它编辑成一个 x86 asm 问题时，它才变成了一个有趣的问题，这很有趣，因为更大但更快的 asm，而不是因为它来自gcc -O0任何特定的源更改。）

这甚至没有提到 C++ 标准库函数，如std::sort或std::vector::push_back，它依赖于优化器来内联大量对微小帮助器/包装器函数的嵌套调用。

编译器如何优化

（我将展示 C++ 代码的转换。请记住，编译器实际上是在转换程序逻辑的内部表示，然后生成 asm。您可以将转换后的 C++ 视为 asm 的伪代码，其中i++表示 x86inc eax指令或其他东西。大多数 C/C++ 语句可以映射到 1 条或几条机器指令。因此，这是一种描述实际编译器生成的 asm 可能正在执行的逻辑的有用方法，而无需实际将其写入 asm。）

从未使用过的结果不必首先计算。 可以完全去除没有副作用的循环。或者分配给全局变量的循环（可观察到的副作用）可以优化为仅执行最后一次分配。例如

// int gsink;  is a global.  
// "sink" is the opposite of a source: something we dump results into.
for (int i=0 ; i<n ; i++) {
    gsink = i*10;
}

就优化编译器而言，等效于以下代码：

if ( 0 < n ) {      // you might not have noticed that your loop could run 0 times
    gsink = (n-1)*10; // but the compiler isn't allowed to do gsink=0 if n<1
}

如果gsink是本地或文件范围内static没有读取它的内容，则编译器可以完全优化它。但是编译器在编译包含该代码的函数时无法“看到”当前 C++ 源文件（“编译单元”）之外的代码，因此它无法更改函数返回时可观察到的副作用，gsink = n*10;.

没有读取 的中间值，gsink因为没有对非内联函数的函数调用。（因为它不是atomic<int>，编译器可以假设没有其他线程或信号处理程序读取它；这将是数据竞争未定义行为。）

使用volatile，让编译器做了一些工作。

如果它是 global volatile int gsink，将值放入内存的实际存储将是一个可观察到的副作用（这就是volatileC++ 中的意思）。但这是否意味着我们可以通过这种方式对乘法进行基准测试？不，它没有。编译器必须保留的副作用只是将最终值放置在内存中。如果它可以比i * 10每次循环更便宜地计算它，它就会这样做。

这个循环也会产生与 相同的赋值结果序列gsink，因此是优化编译器的有效选项。 将独立乘法转换为循环携带的加法称为“强度降低”优化。

volatile int gsink;

int i10 = 0;   // I could have packed this all into a for() loop
int i=0;       // but this is more readable
while (i<n) {
    gsink = i10;
    i10 += 10;
    i++;
}

编译器可以i完全删除并i10 < n*10用作循环条件吗？（当然，将upperbound = n*10计算提升到循环之外。）

这不会总是给出相同的行为，因为n*10可能会溢出，所以INT_MAX/10如果以这种方式实现，循环可以在大多数时候运行。但是C++ 中的有符号溢出是未定义行为，并且i*10循环体在任何溢出的程序中都会n*10溢出，因此编译器可以安全地引入一个n*10而不会改变任何合法/定义良好的程序的行为。 请参阅每个 C 程序员应该了解的关于未定义行为的内容。

（实际上，最多i*10只计算最多，并且可能会溢出而不会。gcc实际上更像是使用无符号数学，当为x86编译时。x86是2的补码机，所以无符号和有符号是相同的二元运算，并检查而不是签名小于是安全的，即使是 INT_MIN。）in-1n*10(n-1)*10while(i10 != n*10)!=(unsigned)n*10UL == 0x8000000UL

有关查看编译器 asm 输出的更多信息以及 x86 asm 的全面入门介绍，请参阅 Matt Godbolt 的 CppCon2017 演讲“我的编译器最近为我做了什么？打开编译器的盖子”。 （以及相关：如何从 GCC/clang 程序集输出中去除“噪音”？）。有关当前 x86 CPU 性能的更多信息，请参阅http://agner.org/optimize/。

此函数的编译器输出来自gcc7.3 -O3，在 Godbolt 编译器资源管理器上为 x86-64 编译：

volatile int gvsink;

void store_n(int n) {
    for(int i=0 ; i<n; i++) {
        gvsink = i*10;
    }
}

store_n(int):          # n in EDI  (x86-64 System V calling convention)
    test    edi, edi
    jle     .L5                   # if(n<=0) goto end

    lea     edx, [rdi+rdi*4]      # edx = n * 5
    xor     eax, eax              # tmp = 0
    add     edx, edx              # edx = n * 10

.L7:                                   # do {
    mov     DWORD PTR gvsink[rip], eax   # gvsink = tmp
    add     eax, 10                      # tmp += 10
    cmp     eax, edx
    jne     .L7                        # } while(tmp != n*10)
.L5:
    rep ret

最佳/惯用的 asm 循环结构是 a do{}while()，因此编译器总是尝试制作这样的循环。（这并不意味着您必须以这种方式编写源代码，但是您可以让编译器在无法证明这一点的情况下避免检查零迭代。）

如果我们使用unsigned int，溢出将被明确定义为环绕，因此编译器无法使用 UB 作为借口以您意想不到的方式编译您的代码。（现代 C++不是一种宽容的语言。优化编译器对那些不小心避免任何 UB 的程序员非常不利，这可能会变得非常微妙，因为很多东西都是未定义的行为。为 x86 编译 C++ 不像编写 x86 程序集. 但幸运的是，有一些编译器选项gcc -fsanitize=undefined可以在运行时检测和警告 UB。不过，您仍然必须检查您关心的每个可能的输入值。）

void store_n(unsigned int n) {
    for(unsigned int i=0 ; i<n; i++) {
        gvsink = i*10;
    }
}

store_n(unsigned int):
    test    edi, edi
    je      .L9            # if (n==0) return;
    xor     edx, edx       # i10 = 0
    xor     eax, eax       # i = 0
.L11:                      # do{
    add     eax, 1         #    i++
    mov     DWORD PTR gvsink[rip], edx
    add     edx, 10        #    i10 += 10
    cmp     edi, eax       
    jne     .L11           # } while(i!=n)
.L9:
    rep ret

Clang 使用两个单独的计数器进行编译，用于有符号和无符号。Clang 的代码更像是

i10 = 0;
do {
    gvsink = i10;
    i10 += 10;
} while(--n != 0);

因此它将n寄存器倒数到零，避免了单独的cmp指令，因为添加/子指令还设置了 CPU 可以分支的条件代码标志。（默认情况下，Clang 展开小循环，生成i10, i10 + 10, i10 + 20, 直到i10 + 70它可以存储的寄存器中，同时只运行一次循环开销指令。不过，在典型的现代 CPU 上展开并没有太多收获。一家商店每个时钟周期是一个瓶颈，每个时钟（在 Intel CPU 上）从前端发送到内核的乱序部分也是一个瓶颈。

让编译器相乘：

我们如何停止这种强度降低的优化？替换*10为* variable不起作用，然后我们只得到添加寄存器而不是添加立即常量的代码。

我们可以把它变成一个像 那样的数组循环a[i] = b[i] * 10;，但是我们也会依赖于内存带宽。此外，这可以使用 SIMD 指令自动矢量化，我们可能希望也可能不想测试这些指令。

我们可以做一些类似的事情tmp *= i;（使用未签名，以避免签名溢出 UB）。但这使得每次迭代中乘法的输出成为下一次的输入。因此，我们将对乘法延迟进行基准测试，而不是吞吐量。（CPU是流水线，例如可以开始一个新的乘法每个时钟周期，但单一的结果乘还没有准备好，直到3个时钟周期后，所以你至少需要tmp1*=i，tmp2*=i以及tmp3*=i保持整数乘法单元在充满工作的英特尔 Sandybridge 系列 CPU 上。

这又回到了必须确切地知道您正在测量什么才能在这个细节级别上制作有意义的微基准的问题。

如果这个答案超出您的想象，请坚持对整个功能进行计时！ 如果不了解周围的上下文，以及它在 asm 中的工作原理，就不可能对单个 C 算术运算符或表达式说太多。

如果您了解缓存，您就可以相当体面地了解内存访问和数组与链表，而不会涉及太多 asm 级别的细节。这是可以理解的C ++详细的一定程度的表现不知道太多关于ASM（超出它存在的事实，以及编译器优化重）。但是，您对 asm、CPU 性能调优以及编译器的工作方式了解得越多，事情就越有意义。

PS：

任何基于编译时常量值的计算都可以（并且希望是）在编译时完成。这称为“不断传播”。对优化器隐藏常量（例如通过将它们作为命令行参数（atoi(argv[1])，或使用其他技巧）输入它们可以使编译器生成的微基准测试代码看起来更像真实用例，如果该用例也看不到（但请注意，在其他文件中定义的常量通过链接时优化变得可见，这对于具有许多跨源文件边界相互调用且未在标头 ( .h) 中定义的小函数的项目来说非常有用）他们可以正常内联的地方。）

乘以 16（或任何其他 2 的幂）将使用移位，因为这比实际的乘法指令更有效。这对分裂来说是一件大事，尤其是。请参阅为什么用于测试 Collat​​z 猜想的 C++ 代码比手写程序集运行得更快？，以及为什么 GCC 在实现整数除法时使用乘以奇怪的数字？.

其他在二进制表示中只设置了几位的乘法常量可以通过一些 shift+add 来完成，通常比通用乘法指令具有更低的延迟。请参见示例如何在 x86 中仅使用 2 个连续的 leal 指令将寄存器乘以 37？.

这些优化中的无是可能的a * b或a / b如果既不输入在编译时是已知的。

另请参阅：如何对 C++ 代码的性能进行基准测试？，尤其是指向Chandler Carruth 的 CppCon 2015 演讲的链接： “调整 C++：基准、CPU 和编译器！天哪！” .

因为值得一提两次：Matt Godbolt 的 CppCon2017 演讲“我的编译器最近为我做了什么？打开编译器的盖子”。 这是一个足够温和的介绍，初学者可能可以很好地遵循它来查看他们的循环是如何编译的，看看它是否被优化掉了。

Answer 2

由于 for 循环体：

i*434243;

它什么也不做，所以假设您在启用优化标志的情况下编译代码，编译器会将其清除。

将其更改为：

int a = i*434243;

可能会在除 之外的任何其他方面进行优化-O0，所以我不建议这样做。

而且，这将导致Undefined Behaviour，因为溢出，因为您使用的常量值相对较大，并且i不断增加。

我建议你这样做：

int a = i * i;
cout << a << "\n";