Прогнозирование отрасли бесплатно?

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

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

  1. Второй подход будет быстрее?

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

Замечания:

В первом случае процессор не имеет никакой возможности, кроме как отбросить первые несколько этапов конвейера 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

8

Решение

Есть две части к этому:

Во-первых, оптимизирует ли это компилятор?

Давайте запустим эксперимент:

test.cc

#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;
}
}

test2.h

void doA(int& x);
void doB(int& x);

test2.cc

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:

Как мы можем знать, если процессоры выполняют эту оптимизацию, если дан первый код?

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

6

Другие решения

Раньше центральные процессоры явно поддерживали что-то вроде этого — после инструкции ветвления всегда выполнялась бы следующая инструкция, независимо от того, была ли выполнена ветвь или нет (посмотрите «слот задержки ветвления»).

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

5

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector