19

我决定要对特定函数进行基准测试,所以我天真地编写了这样的代码:

#include <ctime>
#include <iostream>

int SlowCalculation(int input) { ... }

int main() {
    std::cout << "Benchmark running..." << std::endl;
    std::clock_t start = std::clock();
    int answer = SlowCalculation(42);
    std::clock_t stop = std::clock();
    double delta = (stop - start) * 1.0 / CLOCKS_PER_SEC;
    std::cout << "Benchmark took " << delta << " seconds, and the answer was "
              << answer << '.' << std::endl;
    return 0;
}

一位同事指出我应该声明startandstop变量volatile以避免代码重新排序。例如,他建议优化器可以像这样有效地重新排序代码:

    std::clock_t start = std::clock();
    std::clock_t stop = std::clock();
    int answer = SlowCalculation(42);

起初我怀疑这种极端的重新排序是否被允许,但经过一些研究和实验,我知道它是允许的。

但是 volatile 感觉不是正确的解决方案。volatile 不只是用于内存映射 I/O 吗?

尽管如此,我补充说volatile,不仅基准测试花费的时间明显更长,而且每次运行都非常不一致。如果没有 volatile(并且幸运地确保代码没有被重新排序),基准测试始终需要 600-700 毫秒。使用 volatile,通常需要 1200 毫秒,有时甚至超过 5000 毫秒。两个版本的反汇编列表显示除了寄存器选择不同之外几乎没有区别。这让我想知道是否有另一种方法可以避免代码重新排序而不会产生如此巨大的副作用。

我的问题是:

在这样的基准测试代码中防止代码重新排序的最佳方法是什么?

我的问题类似于这个(关于使用 volatile 避免省略而不是重新排序)、这个(没有回答如何防止重新排序)和这个(争论问题是代码重新排序还是死代码)消除)。虽然这三个人都在这个确切的话题上,但没有人真正回答我的问题。

更新:答案似乎是我的同事弄错了,这样的重新排序不符合标准。我赞成所有这么说的人,并将赏金授予马克西姆。

我见过一个案例(基于此问题中的代码),其中 Visual Studio 2010 按照我的说明重新排序了时钟调用(仅在 64 位版本中)。我试图做一个最小的案例来说明这一点,以便我可以在 Microsoft Connect 上提交错误。

对于那些说 volatile 应该慢得多的人,因为它强制读取和写入内存,这与发出的代码不太一致。在我对这个问题的回答中,我展示了带有和不带有 volatile 的代码的反汇编。在循环内部,所有内容都保存在寄存器中。唯一的显着差异似乎是寄存器选择。我不太了解 x86 程序集,无法知道为什么非易失性版本的性能始终如一地快,而易失性版本的性能却不一致(有时甚至非常慢)。

4

8 回答 8

18

一位同事指出,我应该将 start 和 stop 变量声明为 volatile 以避免代码重新排序。

对不起,但你的同事错了。

编译器不会对定义在编译时不可用的函数的调用重新排序。简单地想象一下,如果编译器将这些调用重新排序forkexec或者围绕这些调用移动代码,将会产生怎样的欢笑。

换句话说,任何没有定义的函数都是编译时内存屏障,也就是说,编译器不会移动调用之前的后续语句或调用之后的先前语句。

在您的代码调用中,std::clock最终调用定义不可用的函数。

我不能推荐足够多的原子武器:C++ 内存模型和现代硬件,因为它讨论了关于(编译时)内存屏障的误解以及volatile许多其他有用的东西。

尽管如此,我添加了 volatile 并发现基准测试不仅花费了更长的时间,而且每次运行都非常不一致。如果没有 volatile(并且幸运地确保代码没有被重新排序),基准测试始终需要 600-700 毫秒。使用 volatile,通常需要 1200 毫秒,有时甚至超过 5000 毫秒

不确定是否volatile应该归咎于此。

报告的运行时间取决于基准测试的运行方式。确保禁用 CPU 频率缩放,以便它不会打开涡轮模式或在运行过程中切换频率。此外,微基准测试应作为实时优先级进程运行,以避免调度噪音。可能是在另一次运行期间,某些后台文件索引器开始与您的基准测试竞争 CPU 时间。有关更多详细信息,请参阅内容。

一个好的做法是测量多次执行函数所需的时间并报告 min/avg/median/max/stdev/total 时间数。高标准偏差可能表明没有进行上述准备工作。第一次运行通常是最长的,因为 CPU 缓存可能是冷的,它可能需要许多缓存未命中和页面错误,并且还会在第一次调用时解析来自共享库的动态符号(惰性符号解析是 Linux 上的默认运行时链接模式,例如),而后续调用将以更少的开销执行。

于 2013-02-25T16:35:12.663 回答
2

防止重新排序的常用方法是编译障碍,即asm volatile ("":::"memory");(使用 gcc)。这是一条什么都不做的 asm 指令,但我们告诉编译器它将破坏内存,因此不允许在其中重新排序代码。这样做的成本只是删除重新排序的实际成本,这显然不是改变优化级别等其他地方所建议的情况。

我相信_ReadWriteBarrier微软的东西是等价的。

根据 Maxim Yegorushkin 的回答,重新排序不太可能是您的问题的原因。

于 2013-02-25T17:10:09.207 回答
2

相关问题:如何阻止编译器将一个微小的重复计算提升出循环

我在任何地方都找不到这个 - 所以在提出问题 11 年后添加我自己的答案;)。

对变量使用 volatile 不是您想要的。这将导致编译器每次都从 RAM 中加载和存储这些变量(假设必须保留该变量的副作用:aka - 对 I/O 寄存器有益)。当您进行基准标记时,您对测量从记忆中获取某些内容或将其写在那里需要多长时间不感兴趣。通常你只希望你的变量在 CPU 寄存器中。

volatile如果您在没有得到优化的循环之外分配给它一次(例如对数组求和),则可以使用它作为打印结果的替代方法。(就像问题中的长期运行函数一样)。但不在一个小循环内;这将引入存储/重新加载指令和存储转发延迟。


我认为提交编译器不将基准代码优化到地狱的唯一方法是使用asm. 这使您可以欺骗编译器,使其认为它对您的变量内容或用法一无所知,因此它必须每次都做所有事情,就像您的循环要求它做的那样频繁。

例如,如果我想对m & -mm 的位置进行基准测试uint64_t,我可以尝试:

uint64_t const m = 0x0000080e70100000UL;
for (int i = 0; i < loopsize; ++i)
{
  uint64_t result = m & -m;
}

编译器显然会说:我什至不打算计算它;因为你没有使用结果。又名,它实际上会这样做:

for (int i = 0; i < loopsize; ++i)
{
}

然后你可以尝试:

uint64_t const m = 0x0000080e70100000UL;
static uint64_t volatile result;
for (int i = 0; i < loopsize; ++i)
{
  result = m & -m;
}

编译器说,好的 - 所以你希望我每次都写结果并做

uint64_t const m = 0x0000080e70100000UL;
uint64_t tmp = m & -m;
static uint64_t volatile result;
for (int i = 0; i < loopsize; ++i)
{
  result = tmp;
}

result loopsize正如您所要求的,花费大量时间写入时间的内存地址。

最后,您也可以使mvolatile,但结果在汇编中看起来像这样:

507b:   ba e8 03 00 00          mov    $0x3e8,%edx
  # top of loop
5080:   48 8b 05 89 ef 20 00    mov    0x20ef89(%rip),%rax        # 214010 <m_test>
5087:   48 8b 0d 82 ef 20 00    mov    0x20ef82(%rip),%rcx        # 214010 <m_test>
508e:   48 f7 d8                neg    %rax
5091:   48 21 c8                and    %rcx,%rax
5094:   48 89 44 24 28          mov    %rax,0x28(%rsp)
5099:   83 ea 01                sub    $0x1,%edx
509c:   75 e2                   jne    5080 <main+0x120>

除了请求的寄存器计算之外,从内存读取两次并写入一次。

因此,正确的方法是

for (int i = 0; i < loopsize; ++i)
{
  uint64_t result = m & -m;
  asm volatile ("" : "+r" (m) : "r" (result));
}

这会产生汇编代码(来自 Godbolt 编译器资源管理器上的 gcc8.2):

 # gcc8.2 -O3 -fverbose-asm
    movabsq $8858102661120, %rax      #, m
    movl    $1000, %ecx     #, ivtmp_9     # induction variable tmp_9
.L2:
    mov     %rax, %rdx      # m, tmp91
    neg     %rdx            # tmp91
    and     %rax, %rdx      # m, result
       # asm statement here,  m=%rax   result=%rdx
    subl    $1, %ecx        #, ivtmp_9
    jne     .L2
    ret     

在循环内完全执行三个请求的汇编指令,加上循环开销的 sub 和 jne。

这里的诀窍是通过使用asm volatile1并告诉编译器

  1. "r"输入操作数:它使用 的值result作为输入,因此编译器必须在寄存器中实现它。
  2. "+r"输入/输出操作数:m保留在同一个寄存器中,但(可能)被修改。
  3. volatile:它有一些神秘的副作用和/或不是输入的纯函数;编译器必须与源代码一样多次执行它。这迫使编译器将您的测试片段单独留在循环中。请参阅gcc 手册的 Extended Asm#Volatile部分。

脚注 1:volatile这里需要 ,否则编译器会将其变成一个空循环。非易失性 asm(具有任何输出操作数)被认为是其输入的纯函数,如果结果未使用,则可以优化掉。或 CSEd 如果多次使用相同的输入,则仅运行一次。


下面的一切都不是我的——我不一定同意。——卡罗伍德

如果您使用过asm volatile ("" : "=r" (m) : "r" (result)); (带有"=r"只写输出),编译器可能会为mand选择相同的寄存器result,从而创建一个循环携带的依赖链来测试计算的延迟,而不是吞吐量。

从那里,你会得到这个asm:

5077:   ba e8 03 00 00          mov    $0x3e8,%edx
507c:   0f 1f 40 00             nopl   0x0(%rax)    # alignment padding
  # top of loop
5080:   48 89 e8                mov    %rbp,%rax    # copy m
5083:   48 f7 d8                neg    %rax         # -m
5086:   48 21 c5                and    %rax,%rbp    # m &= -m   instead of using the tmp as the destination.
5089:   83 ea 01                sub    $0x1,%edx
508c:   75 f2                   jne    5080 <main+0x120>

这将每 2 或 3 个周期运行 1 次迭代(取决于您的 CPU 是否具有 mov-elimination)。没有循环携带依赖项的版本可以在 Haswell 及更高版本和 Ryzen 上以每个时钟周期运行 1 次。这些 CPU 的 ALU 吞吐量可以在每个时钟周期运行至少 4 微秒。

这个 asm 对应于 C++,如下所示:

for (int i = 0; i < loopsize; ++i)
{
  m = m & -m;
}

通过用只写输出约束误导编译器,我们创建了看起来不像源代码的 asm(看起来它每次迭代都从一个常量计算一个新结果,而不是使用结果作为下一次迭代的输入迭代..)

您可能想要对延迟进行微基准测试,以便您可以更轻松地检测编译的好处-mbmi-march=haswell让编译器在一条指令中使用blsi %rax, %rax和计算。m &= -m;但是,如果 C++ 源代码与 asm 具有相同的依赖项,则更容易跟踪您正在执行的操作,而不是欺骗编译器引入新的依赖项。

于 2019-01-17T22:14:39.473 回答
1

您可以制作两个 C 文件,SlowCalculationg++ -O3(高级优化)编译,一个基准测试用g++ -O1(较低级别,仍然优化 - 这可能足以用于该基准测试部分)。

根据手册页-O2,代码的重新排序发生在-O3优化级别。

由于优化发生在编译期间,而不是链接期间,因此基准测试端不应受到代码重新排序的影响。

假设您正在使用g++- 但在另一个编译器中应该有等效的东西。

于 2013-02-23T16:29:22.420 回答
1

在 C++ 中执行此操作的正确方法是使用,例如

class Timer
{
    std::clock_t startTime;
    std::clock_t* targetTime;

public:
    Timer(std::clock_t* target) : targetTime(target) { startTime = std::clock(); }
    ~Timer() { *target = std::clock() - startTime; }
};

并像这样使用它:

std::clock_t slowTime;
{
    Timer timer(&slowTime);
    int answer = SlowCalculation(42);
}

请注意,我实际上并不相信您的编译器会像这样重新排序。

于 2013-02-25T17:22:11.577 回答
1

Volatile 确保了一件事,而且只有一件事:从 volatile 变量中读取的内容每次都会从内存中读取——编译器不会假定该值可以缓存在寄存器中。同样,写入将被写入内存。编译器不会将它保存在寄存器中“一段时间,然后再将其写入内存”。

为了防止编译器重新排序,您可以使用所谓的编译器围栏。MSVC 包括 3 个编译器栅栏:

_ReadWriteBarrier() - 全栅栏

_ReadBarrier() - 负载的两侧围栏

_WriteBarrier() - 商店的两侧围栏

ICC 包括 __memory_barrier() 完整围栏。

完整的栅栏通常是最好的选择,因为在这个级别上不需要更细的粒度(编译器栅栏在运行时基本上是无成本的)。

语句重新排序(大多数编译器在启用优化时都会这样做),这也是某些程序在使用编译器优化编译时无法操作操作的主要原因。

建议阅读http://preshing.com/20120625/memory-ordering-at-compile-time以了解我们在编译器重新排序等方面可能面临的潜在问题。

于 2013-02-26T11:06:44.030 回答
1

我能想到几种方法。这个想法是创建编译时间障碍,以便编译器不会重新排序一组指令。

避免重新排序的一种可能方法是强制编译器无法解析的指令之间的依赖关系(例如,将指针传递给函数并在以后的指令中使用该指针)。我不确定这将如何影响您对基准测试感兴趣的实际代码的性能。

另一种可能性是使函数SlowCalculation(42);成为extern函数(在单独的 .c/.cpp 文件中定义此函数并将文件链接到主程序)并将 和 声明startstop全局变量。我不知道编译器的链接时间/过程间优化器提供了哪些优化。

此外,如果您在 O1 或 O0 编译,编译器很可能不会打扰重新排序指令。您的问题与(编译时间障碍 - 编译器代码重新排序 - gcc 和 pthreads)有些相关

于 2013-02-28T02:09:14.123 回答
0

你的同事描述的重新排序只是打破了 1.9/13

之前排序是由单个线程 (1.10) 执行的评估之间的不对称、传递、成对关系,这会在这些评估之间产生偏序。给定任意两个评估 A 和 B,如果 A 在 B 之前排序,那么 A 的执行将在 B 的执行之前。如果 A 没有在 B 之前排序并且 B 没有在 A 之前排序,那么 A 和 B 是 unsequenced 。[注意:未排序评估的执行可以重叠。—尾注] 当 A 在 B 之前排序或 B 在 A 之前排序时,评估 A 和 B 的排序不确定,但未指定哪个。[注意:不确定顺序的评估不能重叠,但可以先执行。——尾注]

所以基本上你不应该在不使用线程时考虑重新排序。

于 2013-02-25T17:18:12.810 回答