Я только что наткнулся на эту вещь, и мне действительно любопытно, могут ли современные процессоры (текущие, может быть и мобильные (встроенные)) на самом деле не иметь затрат на ветвление в ситуации ниже.
1. Допустим, у нас есть это:
x += a; // let's assume they are both declared earlier as simple ints
if (flag)
do A // let's assume A is not the same as B
else
do B // and of course B is different than A
2. По сравнению с этим:
if (flag)
{
x += a
do A
}
else
{
x += a
do B
}
Если предположить, A
а также B
полностью различаются в терминах инструкций конвейера (выборка, декодирование, выполнение и т. д.):
Второй подход будет быстрее?
Достаточно ли умены процессоры, чтобы сказать, что независимо от того, что это за флаг, следующая инструкция одна и та же (поэтому им не придется отбрасывать этапы конвейера для него из-за предсказания пропадания ветки)?
В первом случае процессор не имеет никакой возможности, кроме как отбросить первые несколько этапов конвейера A
или сделать B
если прогноз мисс ветки случился, потому что они разные. Я вижу второй пример как-то с задержкой ветвления, например: «Я собираюсь проверить этот флаг, даже если я не знаю флаг, я могу приступить к следующей инструкции, потому что она такая же, независимо от того, что это за флаг, у меня уже есть следующая инструкция, и это нормально для мне использовать это. «
РЕДАКТИРОВАТЬ:
Я провел некоторые исследования, и у меня есть хорошие результаты. Как бы вы объяснили это поведение? Извините за последнее изменение, но, насколько я вижу, у меня были некоторые проблемы с кэшем, надеюсь, это более точные результаты и примеры кода.
Вот код, скомпилированный с gcc версии 4.8.2 (Ubuntu 4.8.2-19ubuntu1) с использованием -O3.
Случай 1.
#include <stdio.h>
extern int * cache;
extern bool * b;
extern int * x;
extern int * a;
extern unsigned long * loop;
extern void A();
extern void B();
int main()
{
for (unsigned long i = 0; i < *loop; ++i)
{
++*cache;
*x += *a;
if (*b)
{
A();
}
else
{
B();
}
}
delete b;
delete x;
delete a;
delete loop;
delete cache;
return 0;
}
int * cache = new int(0);
bool * b = new bool(true);
int * x = new int(0);
int * a = new int(0);
unsigned long * loop = new unsigned long(0x0ffffffe);
void A() { --*x; *b = false; }
void B() { ++*x; *b = true; }
Дело 2
#include <stdio.h>
extern int * cache;
extern bool * b;
extern int * x;
extern int * a;
extern unsigned long * loop;
extern void A();
extern void B();
int main()
{
for (unsigned long i = 0; i < *loop; ++i)
{
++*cache;
if (*b)
{
*x += *a;
A();
}
else
{
*x += *a;
B();
}
}
delete b;
delete x;
delete a;
delete loop;
delete cache;
return 0;
}
int * cache = new int(0);
bool * b = new bool(true);
int * x = new int(0);
int * a = new int(0);
unsigned long * loop = new unsigned long(0x0ffffffe);
void A() { --*x; *b = false; }
void B() { ++*x; *b = true; }
Существует почти незаметная разница между версиями -O3 обоих подходов, но без -O3 второй случай работает немного быстрее, по крайней мере, на моей машине.
Я тестировал без -O3 и с циклом = 0xfffffffe.
Лучшие времена:
alin @ ubuntu: ~ / Desktop $ time ./1
реальный 0m20.231s
пользователь 0m20.224s
sys 0m0.020s
alin @ ubuntu: ~ / Desktop $ time ./2
реальный 0m19.932s
пользователь 0m19.890s
sys 0m0.060s
Есть две части к этому:
Во-первых, оптимизирует ли это компилятор?
Давайте запустим эксперимент:
#include <random>
#include "test2.h"
int main() {
std::default_random_engine e;
std::uniform_int_distribution<int> d(0,1);
int flag = d(e);
int x = 0;
int a = 1;
if (flag) {
x += a;
doA(x);
return x;
} else {
x += a;
doB(x);
return x;
}
}
void doA(int& x);
void doB(int& x);
void doA(int& x) {}
void doB(int& x) {}
test2.cc и test2.h существуют исключительно для того, чтобы компилятор не мог оптимизировать все. Компилятор не может быть уверен, что побочный эффект отсутствует, поскольку эти функции существуют в другом модуле перевода.
Теперь скомпилируем в сборку:
gcc -std=c++11 -S test.cc
И давайте перейдем к интересной части сборки:
call _ZNSt24uniform_int_distributionIiEclISt26linear_congruential_engineImLm16807ELm0ELm2147483647EEEEiRT_
movl %eax, -40(%rbp); <- setting flag
movl $0, -44(%rbp); <- setting x
movl $1, -36(%rbp); <- setting a
cmpl $0, -40(%rbp); <- first part of if (flag)
je .L2; <- second part of if (flag)
movl -44(%rbp), %edx <- setting up x
movl -36(%rbp), %eax <- setting up a
addl %edx, %eax <- adding x and a
movl %eax, -44(%rbp) <- assigning back to x
leaq -44(%rbp), %rax <- grabbing address of x
movq %rax, %rdi <- bookkeeping for function call
call _Z3doARi <- function call doA
movl -44(%rbp), %eax
jmp .L4
.L2:
movl -44(%rbp), %edx <- setting up x
movl -36(%rbp), %eax <- setting up a
addl %edx, %eax <- perform the addition
movl %eax, -44(%rbp) <- move it back to x
leaq -44(%rbp), %rax <- and so on
movq %rax, %rdi
call _Z3doBRi
movl -44(%rbp), %eax
.L4:
Итак, мы видим, что компилятор не оптимизировал его. Но мы также не просили об этом.
g++ -std=c++11 -S -O3 test.cc
а потом интересная сборка:
main:
.LFB4729:
.cfi_startproc
subq $56, %rsp
.cfi_def_cfa_offset 64
leaq 32(%rsp), %rdx
leaq 16(%rsp), %rsi
movq $1, 16(%rsp)
movq %fs:40, %rax
movq %rax, 40(%rsp)
xorl %eax, %eax
movq %rdx, %rdi
movl $0, 32(%rsp)
movl $1, 36(%rsp)
call _ZNSt24uniform_int_distributionIiEclISt26linear_congruential_engineImLm16807ELm0ELm2147483647EEEEiRT_RKNS0_10param_typeE
testl %eax, %eax
movl $1, 12(%rsp)
leaq 12(%rsp), %rdi
jne .L83
call _Z3doBRi
movl 12(%rsp), %eax
.L80:
movq 40(%rsp), %rcx
xorq %fs:40, %rcx
jne .L84
addq $56, %rsp
.cfi_remember_state
.cfi_def_cfa_offset 8
ret
.L83:
.cfi_restore_state
call _Z3doARi
movl 12(%rsp), %eax
jmp .L80
Это немного выходит за рамки моей способности четко показывать соотношение 1: 1 между сборкой и кодом, но по вызовам doA и doB вы можете сказать, что установка является общей и выполняется вне оператора if. (Выше линии jne .L83). Так что да, компиляторы выполняют эту оптимизацию.
Часть 2:
Как мы можем знать, если процессоры выполняют эту оптимизацию, если дан первый код?
Я на самом деле не знаю способ проверить это. Так что, я не знаю. Я бы оценил это как правдоподобное, учитывая, что существует неуместное и умозрительное исполнение. Но доказательство в пудинге, и у меня нет способа проверить этот пудинг. Поэтому я не хочу подавать иск так или иначе.
Раньше центральные процессоры явно поддерживали что-то вроде этого — после инструкции ветвления всегда выполнялась бы следующая инструкция, независимо от того, была ли выполнена ветвь или нет (посмотрите «слот задержки ветвления»).
Я уверен, что современные процессоры просто сбрасывают весь конвейер из-за ошибочного прогноза ветки. Нет смысла пытаться выполнить оптимизацию, которую вы предлагаете во время выполнения, когда компилятор может легко сделать это во время компиляции.