Обеспечение порядка операторов в C ++

Предположим, у меня есть ряд операторов, которые я хочу выполнить в фиксированном порядке. Я хочу использовать g ++ с уровнем оптимизации 2, чтобы некоторые операторы можно было переупорядочить. Какие инструменты нужны, чтобы обеспечить определенный порядок высказываний?

Рассмотрим следующий пример.

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;

Я хотел бы попытаться дать более исчерпывающий ответ после обсуждения этого вопроса с комитетом по стандартам C ++. Помимо того, что я являюсь членом комитета C ++, я также занимаюсь разработкой компиляторов LLVM и Clang.

По сути, нет возможности использовать барьер или какую-либо операцию в последовательности для достижения этих преобразований. Основная проблема заключается в том, что операционная семантика чего-то вроде сложения целых чисел полностью известна реализации. Он может имитировать их, знает, что они не могут быть замечены правильными программами, и всегда может перемещать их.

Мы могли бы попытаться предотвратить это, но это привело бы к крайне негативным результатам и в конечном итоге потерпело бы неудачу.

Во-первых, единственный способ предотвратить это в компиляторе - сказать ему, что все эти базовые операции наблюдаемы. Проблема в том, что это помешает подавляющему большинству оптимизаций компилятора. Внутри компилятора, мы по существу не хорошие механизмы для модели , что время наблюдается , но ничего. У нас даже нет хорошей модели того, какие операции требуют времени . Например, требуется ли время для преобразования 32-разрядного целого числа без знака в 64-разрядное целое число? На x86-64 это занимает нулевое время, но на других архитектурах это ненулевое время. Здесь нет общего правильного ответа.

Но даже если нам удастся героически помешать компилятору переупорядочить эти операции, нет никакой гарантии, что этого будет достаточно. Рассмотрим допустимый и соответствующий способ выполнения вашей программы C ++ на машине x86: DynamoRIO. Это система, которая динамически оценивает машинный код программы. Одна вещь, которую он может сделать, - это онлайн-оптимизация, и он даже способен спекулятивно выполнять весь диапазон основных арифметических инструкций вне времени. И это поведение не является уникальным для динамических оценщиков, фактический процессор x86 также будет спекулировать (гораздо меньшее количество) инструкций и динамически их переупорядочивать.

Существенное осознание состоит в том, что тот факт, что арифметика не наблюдаема (даже на уровне синхронизации), пронизывает все уровни компьютера. Это верно для компилятора, среды выполнения и часто даже для оборудования. Принуждение к тому, чтобы он был наблюдаемым, резко ограничил бы компилятор, но также резко ограничил бы аппаратное обеспечение.

Но все это не должно лишать вас надежды. Если вы хотите рассчитать время выполнения основных математических операций, мы хорошо изучили методы, которые работают надежно. Обычно они используются при микротестировании . Я говорил об этом на CppCon2015: https://youtu.be/nXaxk27zwlk

Показанные там методы также предоставляются различными библиотеками микротестов, такими как Google: https://github.com/google/benchmark#preventing-optimization

Ключ к этим методам - ​​сосредоточиться на данных. Вы делаете входные данные для вычислений непрозрачными для оптимизатора, а результат вычислений - для оптимизатора. Как только вы это сделаете, вы сможете точно рассчитать время. Давайте посмотрим на реалистичный вариант примера в исходном вопросе, но с определением, 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, и только вокруг этих маркеров вычисляются тайминги. Поскольку вы используете данные для фиксации вычислений, гарантируется, что они останутся между двумя временными интервалами, но при этом само вычисление может быть оптимизировано. Результирующая сборка x86-64, созданная недавней сборкой Clang / LLVM, выглядит так:

% ./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здесь.

Резюме:

Кажется, нет гарантированного способа предотвратить переупорядочение, но пока не включена оптимизация времени компоновки / полной программы, размещение вызываемой функции в отдельном модуле компиляции кажется довольно хорошей ставкой . (По крайней мере, с 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 () в качестве внешней функции:

#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

Переупорядочивание может выполняться компилятором или процессором.

Большинство компиляторов предлагают специфичный для платформы метод предотвращения переупорядочения инструкций чтения-записи. В gcc это

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

( Подробнее здесь )

Обратите внимание, что это только косвенно предотвращает операции переупорядочения, если они зависят от операций чтения / записи.

На практике я еще не встречал системы, в которой системный вызов Clock::now()бы имел такой же эффект, как и такой барьер. Чтобы убедиться, вы можете осмотреть получившуюся сборку.

Однако нередко тестируемая функция оценивается во время компиляции. Чтобы обеспечить «реалистичное» выполнение, вам может потребоваться получить входные данные для foo()ввода-вывода или volatileчтения.

Другой вариант - отключить встраивание для foo()- опять же, это зависит от компилятора и обычно не переносится, но будет иметь тот же эффект.

В gcc это будет __attribute__ ((noinline))

@Ruslan поднимает фундаментальный вопрос: насколько реалистично это измерение?

На время выполнения влияет множество факторов: один - это фактическое оборудование, на котором мы работаем, другой - одновременный доступ к общим ресурсам, таким как кеш, память, диск и ядра процессора.

Итак, что мы обычно делаем для получения сопоставимых таймингов: убедитесь, что они воспроизводимы с малой погрешностью. Это делает их несколько искусственными.

Производительность выполнения «горячего кеша» и «холодного кеша» может легко отличаться на порядок - но на самом деле это будет что-то среднее («теплый»?)

Язык 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 );
}

который упаковывает нулевую лямбду и использует динамическую библиотеку для ее запуска в контексте, который компилятор не может понять.

Внутри динамической библиотеки мы делаем:

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

что довольно просто.

Теперь, чтобы изменить порядок вызовов execute, он должен понимать динамическую библиотеку, чего он не может во время компиляции вашего тестового кода.

Он все еще может устранить foo()s с нулевыми побочными эффектами, но что-то вы выигрываете, некоторые теряете.

Нет, не может. Согласно стандарту C ++ [intro.execution]:

14 Каждое вычисление значения и побочный эффект, связанный с полным выражением, упорядочивается перед каждым вычислением значения и побочным эффектом, связанным со следующим оцениваемым полным выражением.

Полное выражение - это, по сути, оператор, заканчивающийся точкой с запятой. Как видите, в приведенном выше правиле указано, что операторы должны выполняться по порядку. Именно внутри операторов компилятору предоставляется больше свободы действий (т.е. при некоторых обстоятельствах ему разрешается оценивать выражения, составляющие оператор, в порядке, отличном от слева направо или в каком-либо другом порядке).

Обратите внимание, что условия применения правила «как если бы» здесь не выполняются. Неразумно думать, что какой-либо компилятор сможет доказать, что изменение порядка вызовов для получения системного времени не повлияет на наблюдаемое поведение программы. Если бы возникла ситуация, при которой два вызова для получения времени можно было бы переупорядочить без изменения наблюдаемого поведения, было бы крайне неэффективно создавать компилятор, который анализирует программу с достаточным пониманием, чтобы иметь возможность сделать это с уверенностью.

Нет.

Иногда по правилу «как если бы» можно изменить порядок операторов. Это происходит не потому, что они логически независимы друг от друга, а потому, что эта независимость позволяет такому переупорядочиванию происходить без изменения семантики программы.

Очевидно, что перемещение системного вызова, который получает текущее время, не удовлетворяет этому условию. Компилятор, который сознательно или неосознанно делает это, несовместим и действительно глуп.

В общем, я бы не ожидал, что какое-либо выражение, приводящее к системному вызову, будет "второстепенным" даже агрессивно оптимизирующим компилятором. Ему просто недостаточно информации о том, что делает этот системный вызов.

noinline функция + встроенный черный ящик сборки + полные зависимости данных

Это основано на https://stackoverflow.com/a/38025837/895245, но поскольку я не видел четкого обоснования того, почему ::now()нельзя переупорядочить там, я бы предпочел быть параноиком и поместить его в функцию noinline вместе с как м.

Таким образом, я уверен, что переупорядочение не может произойти, поскольку noinline«связывает» ::nowзависимость между данными и данными.

main.cpp

#include <chrono>
#include <iostream>
#include <string>

// noinline ensures that the ::now() cannot be split from the __asm__
template <class T>
__attribute__((noinline)) auto get_clock(T& value) {
    // Make the compiler think we actually use / modify the value.
    // It can't "see" what is going on inside the assembly string.
    __asm__ __volatile__ ("" : "+g" (value));
    return std::chrono::high_resolution_clock::now();
}

template <class T>
static T foo(T niters) {
    T result = 42;
    for (T i = 0; i < niters; ++i) {
        result = (result * result) - (3 * result) + 1;
    }
    return result;
}

int main(int argc, char **argv) {
    unsigned long long input;
    if (argc > 1) {
        input = std::stoull(argv[1], NULL, 0);
    } else {
        input = 1;
    }

    // Must come before because it could modify input
    // which is passed as a reference.
    auto t1 = get_clock(input);
    auto output = foo(input);
    // Must come after as it could use the output.
    auto t2 = get_clock(output);
    std::cout << "output " << output << std::endl;
    std::cout << "time (ns) "
              << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count()
              << std::endl;
}

GitHub вверх по течению .

Скомпилируйте и запустите:

g++ -ggdb3 -O3 -std=c++14 -Wall -Wextra -pedantic -o main.out main.cpp
./main.out 1000
./main.out 10000
./main.out 100000

Единственным незначительным недостатком этого метода является то, что мы добавляем одну дополнительную callqинструкцию к inlineметоду. objdump -CDпоказывает, что mainсодержит:

    11b5:       e8 26 03 00 00          callq  14e0 <auto get_clock<unsigned long long>(unsigned long long&)>
    11ba:       48 8b 34 24             mov    (%rsp),%rsi
    11be:       48 89 c5                mov    %rax,%rbp
    11c1:       b8 2a 00 00 00          mov    $0x2a,%eax
    11c6:       48 85 f6                test   %rsi,%rsi
    11c9:       74 1a                   je     11e5 <main+0x65>
    11cb:       31 d2                   xor    %edx,%edx
    11cd:       0f 1f 00                nopl   (%rax)
    11d0:       48 8d 48 fd             lea    -0x3(%rax),%rcx
    11d4:       48 83 c2 01             add    $0x1,%rdx
    11d8:       48 0f af c1             imul   %rcx,%rax
    11dc:       48 83 c0 01             add    $0x1,%rax
    11e0:       48 39 d6                cmp    %rdx,%rsi
    11e3:       75 eb                   jne    11d0 <main+0x50>
    11e5:       48 89 df                mov    %rbx,%rdi
    11e8:       48 89 44 24 08          mov    %rax,0x8(%rsp)
    11ed:       e8 ee 02 00 00          callq  14e0 <auto get_clock<unsigned long long>(unsigned long long&)>

Итак, мы видим, что это fooбыло встроено, но get_clockне было, и окружаем его.

get_clock сам по себе, однако, чрезвычайно эффективен, состоящий из одной оптимизированной инструкции по вызову листа, которая даже не касается стека:

00000000000014e0 <auto get_clock<unsigned long long>(unsigned long long&)>:
    14e0:       e9 5b fb ff ff          jmpq   1040 <std::chrono::_V2::system_clock::now()@plt>

Поскольку точность часов сама по себе ограничена, я думаю, что маловероятно, что вы сможете заметить временные эффекты одного дополнительного jmpq. Обратите внимание, что он callтребуется независимо от того, что он ::now()находится в общей библиотеке.

Вызов ::now()из встроенной сборки с зависимостью данных

Это было бы наиболее эффективное решение, преодолевающее даже лишнее, jmpqупомянутое выше.

К сожалению, это чрезвычайно сложно сделать правильно, как показано на: Вызов printf в расширенном встроенном ASM

Однако, если ваше измерение времени может быть выполнено непосредственно во встроенной сборке без вызова, тогда можно использовать этот метод. Это относится, например, к инструкциям gem5 magic Instrumentation , x86 RDTSC (не уверен, что это более репрезентативно) и, возможно, другим счетчикам производительности.

Связанные темы:

• Законно ли оптимизатору C ++ изменять порядок вызовов функции clock ()?

Протестировано с GCC 8.3.0, Ubuntu 19.04.