在C++中强制执行语句顺序

Question

假设我有一些我想以固定顺序执行的语句.我想使用优化级别为2的g ++,因此可以重新排序某些语句.有什么工具可以强制执行某些语句排序？

请考虑以下示例.

using Clock = std::chrono::high_resolution_clock;

auto t1 = Clock::now(); // Statement 1
foo();                  // Statement 2
auto t2 = Clock::now(); // Statement 3

auto elapsedTime = t2 - t1;

在这个例子中,重要的是语句1-3以给定的顺序执行.但是,编译器不能认为语句2独立于1和3并执行如下代码？

using Clock=std::chrono::high_resolution_clock;

foo();                  // Statement 2
auto t1 = Clock::now(); // Statement 1
auto t2 = Clock::now(); // Statement 3

auto elapsedTime = t2 - t1;

Answer 1

在与C++标准委员会讨论之后,我想尝试提供更全面的答案.除了是C++委员会的成员之外,我还是LLVM和Clang编译器的开发人员.

从根本上说,没有办法在序列中使用屏障或某些操作来实现这些转换.根本问题在于实现完全已知诸如整数加法之类的操作语义.它可以模拟它们,它知道它们不能被正确的程序观察到,并且总是可以随意移动它们.

我们可以尝试防止这种情况,但它会产生非常负面的结果并最终会失败.

首先,在编译器中防止这种情况的唯一方法是告诉它所有这些基本操作都是可观察的.问题是,这将排除绝大多数编译器优化.在编译器内部,我们基本上没有很好的机制来模拟时间是可观察的,但没有别的.我们甚至没有一个很好的模型来说明什么操作需要时间.例如,将32位无符号整数转换为64位无符号整数需要花费时间吗？它在x86-64上花费零时间,但在其他架构上它需要非零时间.这里没有一般正确的答案.

但是,即使我们通过一些英雄来阻止编译器重新排序这些操作,也不能保证这就足够了.考虑在x86机器上执行C++程序的有效且一致的方法:DynamoRIO.这是一个动态评估程序机器代码的系统.它可以做的一件事是在线优化,它甚至能够在时间之外推测性地执行整个范围的基本算术指令.这种行为并不是动态评估器所独有的,实际的x86 CPU也会推测(数量少得多)指令并动态重新排序.

基本的实现是,算术不可观察(即使在时间级别)这一事实渗透到计算机的各个层面.对于编译器,运行时,甚至硬件来说都是如此.强制它是可观察的会严重限制编译器,但它也会大大限制硬件.

但所有这一切都不应该让你失去希望.当您想要执行基本的数学运算时,我们已经研究了可靠的技术.通常,这些在进行微基准测试时使用.我在CppCon2015上谈了这个:https://youtu.be/nXaxk27zwlk

其中显示的技术也由各种微基准库提供,例如Google:https://github.com/google/benchmark#preventing-optimisation

这些技术的关键是关注数据.您使计算的输入对优化程序不透明,并且计算结果对优化程序不透明.完成后,您可以可靠地计时.让我们看看原始问题中示例的实际版本,但是foo实现完全可见的定义.我还DoNotOptimize从Google Benchmark库中提取了一个(非便携式)版本,您可以在此处找到它:https://github.com/google/benchmark/blob/master/include/benchmark/benchmark_api.h#L208

#include <chrono>

template <class T>
__attribute__((always_inline)) inline void DoNotOptimize(const T &value) {
  asm volatile("" : "+m"(const_cast<T &>(value)));
}

// The compiler has full knowledge of the implementation.
static int foo(int x) { return x * 2; }

auto time_foo() {
  using Clock = std::chrono::high_resolution_clock;

  auto input = 42;

  auto t1 = Clock::now();         // Statement 1
  DoNotOptimize(input);
  auto output = foo(input);       // Statement 2
  DoNotOptimize(output);
  auto t2 = Clock::now();         // Statement 3

  return t2 - t1;
}

在这里,我们确保输入数据和输出数据在计算周围被标记为不可优化foo,并且仅在这些标记周围计算时序.因为您正在使用数据来计算计算,所以它保证保持在两个时间之间,但允许计算本身进行优化.最近构建的Clang/LLVM生成的x86-64程序集是:

% ./bin/clang++ -std=c++14 -c -S -o - so.cpp -O3
        .text
        .file   "so.cpp"
        .globl  _Z8time_foov
        .p2align        4, 0x90
        .type   _Z8time_foov,@function
_Z8time_foov:                           # @_Z8time_foov
        .cfi_startproc
# BB#0:                                 # %entry
        pushq   %rbx
.Ltmp0:
        .cfi_def_cfa_offset 16
        subq    $16, %rsp
.Ltmp1:
        .cfi_def_cfa_offset 32
.Ltmp2:
        .cfi_offset %rbx, -16
        movl    $42, 8(%rsp)
        callq   _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, %rbx
        #APP
        #NO_APP
        movl    8(%rsp), %eax
        addl    %eax, %eax              # This is "foo"!
        movl    %eax, 12(%rsp)
        #APP
        #NO_APP
        callq   _ZNSt6chrono3_V212system_clock3nowEv
        subq    %rbx, %rax
        addq    $16, %rsp
        popq    %rbx
        retq
.Lfunc_end0:
        .size   _Z8time_foov, .Lfunc_end0-_Z8time_foov
        .cfi_endproc


        .ident  "clang version 3.9.0 (trunk 273389) (llvm/trunk 273380)"
        .section        ".note.GNU-stack","",@progbits

在这里,您可以看到编译器将调用优化foo(input)为单个指令addl %eax, %eax,但不会将其移出时间或尽管输入不变而完全消除它.

希望这会有所帮助,C++标准委员会正在研究标准化API的可能性DoNotOptimize.

Answer 2

摘要:

似乎没有保证的方法来阻止重新排序,但只要未启用链接时/全程序优化,将被调用函数定位在单独的编译单元中似乎是一个相当不错的选择.(至少对于GCC,虽然逻辑表明这也可能与其他编译器一样.)这是以函数调用为代价的 - 内联代码根据定义在同一个编译单元中并且可以重新排序.

原始答案:

GCC重新排序-O2优化下的调用:

#include <chrono>
static int foo(int x)    // 'static' or not here doesn't affect ordering.
{
    return x*2;
}
int fred(int x)
{
    auto t1 = std::chrono::high_resolution_clock::now();
    int y = foo(x);
    auto t2 = std::chrono::high_resolution_clock::now();
    return y;
}

GCC 5.3.0:

g++ -S --std=c++11 -O0 fred.cpp :

_ZL3fooi:
        pushq   %rbp
        movq    %rsp, %rbp
        movl    %ecx, 16(%rbp)
        movl    16(%rbp), %eax
        addl    %eax, %eax
        popq    %rbp
        ret
_Z4fredi:
        pushq   %rbp
        movq    %rsp, %rbp
        subq    $64, %rsp
        movl    %ecx, 16(%rbp)
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, -16(%rbp)
        movl    16(%rbp), %ecx
        call    _ZL3fooi
        movl    %eax, -4(%rbp)
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movq    %rax, -32(%rbp)
        movl    -4(%rbp), %eax
        addq    $64, %rsp
        popq    %rbp
        ret

但:

g++ -S --std=c++11 -O2 fred.cpp :

_Z4fredi:
        pushq   %rbx
        subq    $32, %rsp
        movl    %ecx, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        call    _ZNSt6chrono3_V212system_clock3nowEv
        leal    (%rbx,%rbx), %eax
        addq    $32, %rsp
        popq    %rbx
        ret

现在,用foo()作为extern函数:

#include <chrono>
int foo(int x);
int fred(int x)
{
    auto t1 = std::chrono::high_resolution_clock::now();
    int y = foo(x);
    auto t2 = std::chrono::high_resolution_clock::now();
    return y;
}

g++ -S --std=c++11 -O2 fred.cpp :

_Z4fredi:
        pushq   %rbx
        subq    $32, %rsp
        movl    %ecx, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movl    %ebx, %ecx
        call    _Z3fooi
        movl    %eax, %ebx
        call    _ZNSt6chrono3_V212system_clock3nowEv
        movl    %ebx, %eax
        addq    $32, %rsp
        popq    %rbx
        ret

但是,如果这与-flto(链接时优化)相关联:

0000000100401710 <main>:
   100401710:   53                      push   %rbx
   100401711:   48 83 ec 20             sub    $0x20,%rsp
   100401715:   89 cb                   mov    %ecx,%ebx
   100401717:   e8 e4 ff ff ff          callq  100401700 <__main>
   10040171c:   e8 bf f9 ff ff          callq  1004010e0 <_ZNSt6chrono3_V212system_clock3nowEv>
   100401721:   e8 ba f9 ff ff          callq  1004010e0 <_ZNSt6chrono3_V212system_clock3nowEv>
   100401726:   8d 04 1b                lea    (%rbx,%rbx,1),%eax
   100401729:   48 83 c4 20             add    $0x20,%rsp
   10040172d:   5b                      pop    %rbx
   10040172e:   c3                      retq

Answer 3

重新排序可以由编译器或处理器完成.

大多数编译器提供特定于平台的方法来防止读写指令的重新排序.在gcc上,这是

asm volatile("" ::: "memory");

(更多信息在这里)

请注意,这只会间接阻止重新排序操作,只要它们依赖于读/写.

在实践中,我还没有看到系统调用的系统Clock::now()与这样的屏障具有相同的效果.您可以检查生成的程序集.

但是,在编译期间对被测函数进行评估并不罕见.要强制执行"实际"执行,您可能需要foo()从I/O或volatile读取中获取输入.

另一个选择是禁用内联foo()- 再次,这是编译器特定的,通常不可移植,但会产生相同的效果.

在gcc上,这将是 __attribute__ ((noinline))

@Ruslan提出了一个基本问题:这种测量有多现实？

执行时间受许多因素的影响:一个是我们运行的实际硬件,另一个是对缓存,内存,磁盘和CPU内核等共享资源的并发访问.

所以,我们平时做的就是比较的时机:要确保他们是可重复使用低误差.这使他们有点人为.

"热缓存"与"冷缓存"执行性能很容易相差一个数量级 - 但实际上,它会介于两者之间("不冷不热"？)

Answer 4

C++语言以多种方式定义可观察的内容.

如果foo()没有任何可观察的,那么它可以完全消除.如果foo()只进行一个以"本地"状态存储值的计算(无论是在堆栈上还是在某个对象中),并且编译器可以证明没有安全派生的指针可以进入Clock::now()代码,那么就没有可观察到的后果移动Clock::now()电话.

如果foo()一个文件或显示,编译器不能证明相互作用Clock::now()并没有与该文件或显示交互,那么重新排序不能这样做,因为文件或显示交互观察到的行为.

虽然您可以使用特定于编译器的黑客来强制代码不要移动(如内联汇编),但另一种方法是尝试超越您的编译器.

创建一个动态加载的库.在相关代码之前加载它.

该库暴露了一件事:

namespace details {
  void execute( void(*)(void*), void *);
}

并像这样包装它:

template<class F>
void execute( F f ) {
  struct bundle_t {
    F f;
  } bundle = {std::forward<F>(f)};

  auto tmp_f = [](void* ptr)->void {
    auto* pb = static_cast<bundle_t*>(ptr);
    (pb->f)();
  };
  details::execute( tmp_f, &bundle );
}

它包含一个nullary lambda并使用动态库在编译器无法理解的上下文中运行它.

在动态库中,我们做:

void details::execute( void(*f)(void*), void *p) {
  f(p);
}

这很简单.

现在要重新排序调用execute,它必须理解动态库,它在编译测试代码时无法理解.

它仍然可以消除foo()没有副作用的s,但你赢了一些,你输了一些.