Обеспечение порядка операторов в 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;
6 ответов
Я хотел бы попытаться дать более исчерпывающий ответ после того, как это было обсуждено с комитетом по стандартам C++. Помимо того, что я являюсь членом комитета C++, я также являюсь разработчиком компиляторов LLVM и Clang.
По сути, нет способа использовать барьер или какую-либо операцию в последовательности для достижения этих преобразований. Основная проблема заключается в том, что операционная семантика чего-то вроде целочисленного сложения полностью известна реализации. Он может имитировать их, он знает, что они не могут быть обнаружены правильными программами, и всегда может их перемещать.
Мы могли бы попытаться предотвратить это, но это привело бы к крайне негативным результатам и в конечном итоге провалилось.
Во-первых, единственный способ предотвратить это в компиляторе - сообщить ему, что все эти основные операции являются наблюдаемыми. Проблема заключается в том, что это исключит подавляющее большинство оптимизаций компилятора. Внутри компилятора у нас практически нет хороших механизмов для моделирования того, что время можно наблюдать, и ничего более. У нас даже нет хорошей модели того, какие операции занимают время. Например, занимает ли время преобразование 32-разрядного целого числа без знака в 64-разрядное целое число без знака? На x86-64 это занимает нулевое время, но на других архитектурах это занимает ненулевое время. Здесь нет общего правильного ответа.
Но даже если нам удастся с помощью некоторой героики помешать компилятору переупорядочить эти операции, нет никаких гарантий, что этого будет достаточно. Рассмотрим правильный и соответствующий способ выполнения вашей программы на C++ на компьютере с архитектурой x86: DynamoRIO. Это система, которая динамически оценивает машинный код программы. Единственное, что он может сделать, - это онлайн-оптимизация, и он даже способен умозрительно выполнять весь спектр базовых арифметических инструкций вне времени. И это поведение не уникально для динамических вычислителей, фактический процессор x86 также будет спекулировать (гораздо меньшим числом) инструкций и динамически их переупорядочивать.
Суть в том, что тот факт, что арифметика не поддается наблюдению (даже на временном уровне), пронизывает все слои компьютера. Это верно для компилятора, среды выполнения и часто даже для аппаратного обеспечения. Принудительное обнаружение этого может существенно ограничить компилятор, но также существенно ограничить аппаратное обеспечение.
Но все это не должно заставлять вас терять надежду. Если вы хотите рассчитать время выполнения основных математических операций, мы хорошо изучили методы, которые работают надежно. Как правило, они используются при выполнении микро-бенчмаркинга. Я рассказал об этом на CppCon2015: https://youtu.be/nXaxk27zwlk
Методы, показанные там, также предоставляются различными библиотеками микро-тестов, такими как Google: https://github.com/google/benchmark
Ключ к этим методам заключается в том, чтобы сосредоточиться на данных. Вы делаете входные данные для вычисления непрозрачными для оптимизатора, а результат вычисления - непрозрачными для оптимизатора. Как только вы это сделаете, вы можете рассчитать время надежно. Давайте посмотрим на реалистичную версию примера в оригинальном вопросе, но с определением 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()с нулевыми побочными эффектами, но вы выигрываете, вы проигрываете.
Нет, не может. Согласно стандарту C++ [intro.execution]:
14 Каждое вычисление значения и побочный эффект, связанный с полным выражением, упорядочивается перед каждым вычислением значения и побочным эффектом, связанным со следующим полным выражением, которое будет оценено.
Полное выражение - это в основном утверждение, оканчивающееся точкой с запятой. Как видно из приведенного выше правила, операторы должны быть выполнены по порядку. Именно в пределах утверждений компилятору разрешено более свободное управление (т. Е. При некоторых обстоятельствах ему разрешается оценивать выражения, составляющие оператор, в порядке, отличном от слева направо или в другом конкретном случае).
Обратите внимание, что условия для применения правила "как будто" здесь не выполняются. Неразумно думать, что любой компилятор сможет доказать, что переупорядочение вызовов для получения системного времени не повлияет на наблюдаемое поведение программы. Если бы было обстоятельство, при котором два вызова для получения времени могли бы быть переупорядочены без изменения наблюдаемого поведения, было бы крайне неэффективно создать компилятор, который анализирует программу с достаточным пониманием, чтобы иметь возможность с уверенностью вывести это.
Нет.
Иногда по правилу "как будто" операторы могут быть переупорядочены. Это не потому, что они логически независимы друг от друга, а потому, что эта независимость позволяет осуществлять такое переупорядочение без изменения семантики программы.
Перемещение системного вызова, который получает текущее время, очевидно, не удовлетворяет этому условию. Компилятор, который сознательно или неосознанно делает это, не соответствует требованиям и действительно глуп.
В общем, я не ожидал бы, что какое-либо выражение, которое приведет к тому, что системный вызов будет "угадан" даже агрессивно оптимизирующим компилятором. Он просто недостаточно знает, что делает этот системный вызов.
noinline функция + встроенный черный ящик сборки + полные зависимости данных
Это основано на /questions/22940630/obespechenie-poryadka-operatorov-v-c/22940637#22940637, но поскольку я не видел четкого обоснования того, почему::now() не может быть переупорядочен там, я бы предпочел быть параноиком и поместить его в функцию noinline вместе с asm.
Таким образом, я уверен, что переупорядочения не произойдет, поскольку 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;
}
Скомпилируйте и запустите:
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, x86 RDTSC (не уверен, что это больше репрезентативно) и, возможно, другими счетчиками производительности.
Связанные темы:
Протестировано с GCC 8.3.0, Ubuntu 19.04.