[解決済み] C++で文の順序を強制する

質問

私が一定の順序で実行したいいくつかのステートメントを持っているとします。 があるとします。私は最適化レベル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から独立していると考え、次のようにコードを実行することはできないのでしょうか？ 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;

どのように解決するのですか？

C++標準化委員会で議論された後、もう少し包括的な回答を提供することを試みたいと思います。C++ 委員会のメンバーであることに加え、私は LLVM および Clang コンパイラの開発者でもあります。

根本的に、これらの変換を実現するために、バリアやシーケンス内の何らかの操作を使用する方法はありません。根本的な問題は、整数の加算のようなものの演算セマンティクスが 完全に既知 であることです。実装はそれらをシミュレートでき、正しいプログラムによって観察できないことを知っており、常に自由にそれらを動かすことができます。

これを防ごうとすることもできますが、極めて否定的な結果をもたらし、最終的には失敗するでしょう。

まず、コンパイラーでこれを防ぐ唯一の方法は、これらの基本的な操作のすべてが観察可能であることを伝えることです。問題は、その場合、コンパイラーの最適化の圧倒的大多数が妨げられるということです。コンパイラの内部では、基本的に タイミング が観測可能であることをモデル化するための良いメカニズムはありません。の良いモデルさえ持っていません。 どのような操作に時間がかかるか . たとえば、32 ビットの符号なし整数を 64 ビットの符号なし整数に変換するのには時間がかかるのでしょうか？x86-64では0時間ですが、他のアーキテクチャでは0時間ではありません。ここでは一般的に正しい答えはありません。

しかし、たとえコンパイラーがこれらの操作を並べ替えるのを防ぐために何らかの英雄的行為に成功したとしても、これで十分であるという保証はどこにもありません。x86 マシン上で C++ プログラムを実行するための有効かつ準拠した方法を考えてみましょう。DynamoRIOです。これは、プログラムの機械語コードを動的に評価するシステムです。できることの1つはオンライン最適化で、基本的な演算命令の全範囲をタイミング外で投機的に実行することさえ可能です。そして、この動作は動的評価器特有のものではなく、実際の x86 CPU も (はるかに少ない数の) 命令を推測して動的に並べ替えたりします。

本質的な認識は、演算が (タイミングレベルでも) 観察可能ではないという事実は、コンピュータの各層に浸透しているものだということです。これは、コンパイラー、ランタイム、そしてしばしばハードウェアにさえも当てはまります。観測可能であることを強制することは、コンパイラーを劇的に制約することになりますが、ハードウェアも劇的に制約することになります。

しかし、これらすべてによって希望を失ってはいけません。基本的な数学的演算の実行時間を計りたい場合、私たちは信頼できるよく研究された技術を持っています。典型的には、これらは マイクロ ベンチマーキング . CppCon2015でこれについての講演をしました。 https://youtu.be/nXaxk27zwlk

そこで示されている技術は、Google のようなさまざまなマイクロ ベンチマーク ライブラリでも提供されています。 https://github.com/google/benchmark#preventing-optimization

これらのテクニックの鍵は、データに注目することです。計算への入力をオプティマイザに不透明なものにし、計算の結果をオプティマイザに不透明なものにするのです。それができれば、確実に時間を計ることができます。元の質問の例の現実的なバージョンを見てみましょう。ただし、定義が foo の定義が実装から完全に見えるようにしてあります。また、（移植性のない）バージョンを抽出して、その中の DoNotOptimize を Google Benchmark ライブラリから抽出したものです。 https://github.com/google/benchmark/blob/v1.0.0/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 とマークされ、それらのマーカーの周りでのみタイミングが計算されます。データを使って計算を挟み込むので、2つのタイミングの間に留まることが保証され、なおかつ計算自体の最適化も認められています。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 のように、一定の入力があるにもかかわらず、それをタイミングの外に移動させたり、完全に排除したりすることなく、1 つの命令にしています。

これが役に立つことを願っています。C++標準化委員会は、以下のようなAPIを標準化する可能性を検討しています。 DoNotOptimize のような API を標準化する可能性を検討しています。