Подтвердить что ты не робот

Что делают компиляторы с разветвлением во время компиляции?

EDIT: В качестве примера я использовал случай if if else, который иногда может быть разрешен во время компиляции (например, когда задействованы статические значения, cf <type_traits>). Адаптация ответов ниже для других типов статического ветвления (например, нескольких ветвей или ветвей с несколькими критериями) должна быть простой. Обратите внимание, что разветвление во время компиляции с использованием шаблона-мета-программирования не является темой здесь.


В типичном коде, подобном этому

#include <type_traits>

template <class T>
T numeric_procedure( const T& x )
{
    if ( std::is_integral<T>::value )
    {
        // Integral types
    }
    else
    {
        // Floating point numeric types
    }
}

будет ли компилятор оптимизировать выражение if/else, когда я буду определять конкретные типы шаблонов позже в моем коде?

Простой альтернативой было бы написать что-то вроде этого:

#include <type_traits>

template <class T>
inline T numeric_procedure( const T& x )
{
    return numeric_procedure_impl( x, std::is_integral<T>() );
}

// ------------------------------------------------------------------------

template <class T>
T numeric_procedure_impl( const T& x, std::true_type const )
{
    // Integral types
}

template <class T>
T numeric_procedure_impl( const T& x, std::false_type const )
{
    // Floating point numeric types
}

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

4b9b3361

Ответ 1

TL; DR

Есть несколько способов получить различное поведение во время выполнения в зависимости от параметра шаблона. Производительность не должна быть вашей главной задачей, но гибкость и ремонтопригодность должны. Во всех случаях различные тонкие обертки и постоянные условные выражения будут оптимизированы на любом подходящем компиляторе для сборок релизов. Ниже небольшое резюме с различными компромиссами (вдохновленный этим ответом @AndyProwl).

Время выполнения, если

Ваше первое решение - это простое время выполнения, if:

template<class T>
T numeric_procedure(const T& x)
{
    if (std::is_integral<T>::value) {
        // valid code for integral types
    } else {
        // valid code for non-integral types,
        // must ALSO compile for integral types
    }
}

Это просто и эффективно: любой достойный компилятор оптимизирует мертвую ветку.

Есть несколько недостатков:

  • на некоторых платформах (MSVC) постоянное условное выражение выдает ложное предупреждение компилятора, которое затем нужно игнорировать или отключать.
  • Но что еще хуже, на всех соответствующих платформах обе ветки оператора if/else должны фактически компилироваться для всех типов T, даже если известно, что одна из ветвей не используется. Если T содержит разные типы членов в зависимости от его природы, вы получите ошибку компилятора, как только попытаетесь получить к ним доступ.

Диспетчерская метка

Ваш второй подход известен как диспетчеризация тегов:

template<class T>
T numeric_procedure_impl(const T& x, std::false_type)
{
    // valid code for non-integral types,
    // CAN contain code that is invalid for integral types
}    

template<class T>
T numeric_procedure_impl(const T& x, std::true_type)
{
    // valid code for integral types
}

template<class T>
T numeric_procedure(const T& x)
{
    return numeric_procedure_impl(x, std::is_integral<T>());
}

Он работает нормально, без затрат времени выполнения: временная std::is_integral<T>() и вызов однострочной вспомогательной функции будут оптимизированы на любой приличной платформе.

Основной (незначительный ИМО) недостаток заключается в том, что у вас есть шаблон с 3 вместо 1 функции.

SFINAE

Точно связана с диспетчеризацией тегов SFINAE (ошибка замены не является ошибкой)

template<class T, class = typename std::enable_if<!std::is_integral<T>::value>::type>
T numeric_procedure(const T& x)
{
    // valid code for non-integral types,
    // CAN contain code that is invalid for integral types
}    

template<class T, class = typename std::enable_if<std::is_integral<T>::value>::type>
T numeric_procedure(const T& x)
{
    // valid code for integral types
}

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

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

Частичная специализация

Другой подход заключается в использовании помощника шаблона класса с оператором приложения функции и его частичной специализации.

template<class T, bool> 
struct numeric_functor;

template<class T>
struct numeric_functor<T, false>
{
    T operator()(T const& x) const
    {
        // valid code for non-integral types,
        // CAN contain code that is invalid for integral types
    }
};

template<class T>
struct numeric_functor<T, true>
{
    T operator()(T const& x) const
    {
        // valid code for integral types
    }
};

template<class T>
T numeric_procedure(T const& x)
{
    return numeric_functor<T, std::is_integral<T>::value>()(x);
}

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

Основным недостатком является немного большая котельная плита, если вы хотите специализироваться только на одном бинарном условии.

Если constexpr (C++ 1z предложение)

Это перезагрузка неудачных ранее предложений для static if (который используется в языке программирования D).

template<class T>
T numeric_procedure(const T& x)
{
    if constexpr (std::is_integral<T>::value) {
        // valid code for integral types
    } else {
        // valid code for non-integral types,
        // CAN contain code that is invalid for integral types
    }
}

Как и во время выполнения if, все находится в одном месте, но главное преимущество здесь в том, что ветвь else будет полностью отброшена компилятором, когда известно, что оно не будет принято. Большим преимуществом является то, что вы сохраняете весь код локально и не должны использовать маленькие вспомогательные функции, как при диспетчеризации тегов или частичной специализации шаблонов.

Concepts-Lite (C++ 1z предложение)

Concepts-Lite - это готовящаяся Техническая спецификация, которая должна стать частью следующего основного выпуска C++ (C++ 1z, с z==7 в качестве наилучшего предположения).

template<Non_integral T>
T numeric_procedure(const T& x)
{
    // valid code for non-integral types,
    // CAN contain code that is invalid for integral types
}    

template<Integral T>
T numeric_procedure(const T& x)
{
    // valid code for integral types
}

Этот подход заменяет ключевое слово class или typename в скобках template< > именем концепции, описывающим семейство типов, для которых должен работать код. Это можно рассматривать как обобщение методов диспетчеризации тегов и SFINAE. Некоторые компиляторы (gcc, Clang) имеют экспериментальную поддержку этой функции. Прилагательное Lite относится к несостоявшемуся предложению Concepts C++ 11.

Ответ 2

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

То есть:

int foo() {
  #if 0
    return std::cout << "this isn't going to work\n";
  #else
    return 1;
  #endif
}

будет работать нормально, потому что препроцессор удаляет мертвую ветвь до того, как компилятор увидит ее, но:

int foo() {
  if (std::is_integral<double>::value) {
    return std::cout << "this isn't going to work\n";
  } else {
    return 1;
  }
}

не будет. Несмотря на то, что оптимизатор может отбросить первую ветвь, она все равно не скомпилируется. Здесь используется справка enable_if и SFINAE, потому что вы можете выбрать допустимый (компилируемый) код и недопустимый (не компилируемый) код. Невозможность компиляции не является ошибкой.

Ответ 3

Компилятор может быть достаточно умным, чтобы увидеть, что он может заменить тело оператора if двумя различными реализациями функций и просто выбрать правильный. Но с 2014 года я сомневаюсь, что есть какой-то компилятор, который достаточно умен, чтобы сделать это. Возможно, я ошибаюсь. С другой стороны, std::is_integral достаточно прост, что я думаю, что он будет оптимизирован.

Ваша идея перегрузки по результату std::is_integral является одним из возможных решений.

Другим и более чистым решением IMHO является использование std::enable_if (вместе с std::is_integral).

Ответ 4

Кредит @MooingDuck и @Casey

template<class FN1, class FN2, class ...Args>
decltype(auto) if_else_impl(std::true_type, FN1 &&fn1, FN2 &&, Args&&... args)
{
    return fn1(std::forward<Args>(args)...);
}

template<class FN1, class FN2, class ...Args>
decltype(auto) if_else_impl(std::false_type, FN1 &&, FN2 &&fn2, Args&&... args)
{
    return fn2(std::forward<Args>(args)...);
}

#define static_if(...) if_else_impl(__VA_ARGS__, *this)

И обычай прост как:

static_if(do_it,
    [&](auto& self){ return 1; },
    [&](auto& self){ return self.sum(2); }
);

Работает как статический, если - компилятор идет только к ветке "true".


P.S. Вы должны иметь self = *this и вызывать из него члены, из-за gcc bug. Если у вас есть вложенные лямбда-вызовы, вы не можете использовать this-> вместо self.

Ответ 5

Чтобы ответить на заглавный вопрос о том, как компиляторы обрабатывают if(false):

Они оптимизируют постоянные условия ветвления (и мертвый код)

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

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

например, clang++ -O0 ("режим отладки") все еще оценивает if(constexpr_function()) во время компиляции и обрабатывает его как if(false) или if(true). Другие компиляторы только оценивают во время компиляции, если они вынуждены (путем сопоставления с шаблоном).


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

Любой не страшный компилятор может оптимизировать мертвый код за условием постоянной времени компиляции (Википедия: Удаление мертвого кода). Это часть базовых ожиданий, которые люди ожидают от реализации C++ в реальном мире; это одна из самых основных оптимизаций, и все компиляторы в реальном использовании делают это для простых случаев, таких как constexpr.

Часто постоянное распространение (особенно после встраивания) создает условия времени компиляции, даже если в исходном коде они явно не были такими. Одним из наиболее очевидных случаев является оптимизация сравнения на первых итерациях a for (int i=0; i<n; i++) чтобы он мог превратиться в нормальный asm-цикл с условной ветвью внизу (как цикл do{}while while в C++), если n постоянно или доказуемо > 0. (Да, реальные компиляторы выполняют оптимизацию диапазона значений, а не только постоянное распространение.)


Некоторые компиляторы, такие как gcc и clang, удаляют мертвый код внутри if(false) даже в режиме "отладки" на минимальном уровне оптимизации, который требуется им для преобразования логики программы через их внутренние нейтральные к дуге представления и, в конечном итоге, для генерации asm, (Но режим отладки отключает любое распространение констант для переменных, которые не объявлены как const или constexpr в источнике.)

Некоторые компиляторы делают это только тогда, когда включена оптимизация; например, MSVC действительно любит быть буквальным в своем переводе C++ в asm в режиме отладки и фактически создает ноль в регистре, а ветвь в нем равна нулю или нет для if(false).

Для режима отладки GCC (-O0), constexpr функция не встраивается, если они не должны быть. (В некоторых местах язык требует константы, например, размер массива внутри структуры. GNU C++ поддерживает VLA C99, но предпочитает встроить функцию constexpr вместо фактического создания VLA в режиме отладки.)

Но нефункциональный constexpr действительно оценивается во время компиляции, не сохраняется в памяти и не проверяется.

Но, constexpr, на любом уровне оптимизации функции constexpr полностью встроены и оптимизированы, а затем if()


Примеры ( //optimized even at -O0 for+Clang, but not gcc or MSVC. partially for ICC //With optimization enabled, optimized away of+Course static+Constexpr bool always_false() { return sizeof(char)==2*sizeof(int)%3B+} void baz() {%0A++++//if+(std::is_integral::value)+f1()%3B+//optimizes for gcc%0A++++if+(always_false())+f1();%0A++++else f2(); } //+Compilers that support+C99 VLAs (like GCC) *could*+decide //not to actually inline. But in practice GCC -O0 does. int test_inline_with_opt_disabled(){%0A++++volatile int a%5B1++ always_false()];%0A++++a[0%5D+= 1;%0A++++return a[0]; } '),l:'5',n:'0',o:'C++ source #1',t:'0')),k:36.99309810000209,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g91,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'1',trim:'1'),fontScale:1.2899450879999999,lang:c++,libs:!(),options:'-O3 -Wall -std=gnu++17',source:1),l:'5',n:'0',o:'x86-64 gcc 9.1+(Editor #1,+Compiler+#1)+C++',t:'0')),k:29.673568566664592,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:vcpp_v19_20_x64,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'1',trim:'1'),fontScale:1.2899450879999999,lang:c++,libs:!(),options:'-O2 -Wall',source:1),l:'5',n:'0',o:'x64 msvc v19.20+(Editor #1,+Compiler+#2)+C++',t:'0')),k:33.33333333333333,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',m:100,n:'0',o:'',t:'0')),version:4 rel="nofollow noreferrer">из проводника компилятора Godbolt)

#include <type_traits>
void baz() {
    if (std::is_integral<float>::value) f1();  // optimizes for gcc
    else f2();
}

Все компиляторы с -O2 оптимизацией -O2 (для x86-64):

baz():
        jmp     f2()    # optimized tailcall

Качество кода в режиме отладки, обычно не актуально

GCC с отключенной оптимизацией по-прежнему оценивает выражение и устраняет мертвый код:

baz():
        push    rbp
        mov     rbp, rsp          # -fno-omit-frame-pointer is the default at -O0
        call    f2()              # still an unconditional call, no runtime branching
        nop
        pop     rbp
        ret

Чтобы увидеть gcc не встроенный что-то с отключенной оптимизацией

static constexpr bool always_false() { return sizeof(char)==2*sizeof(int); }
void baz() {
    if (always_false()) f1();
    else f2();
}
static constexpr bool always_false() { return sizeof(char)==2*sizeof(int); }
void baz() {
    if (always_false()) f1();
    else f2();
}
baz():
        push    rbp
        mov     rbp, rsp
        call    always_false()
        test    al, al              # the bool return value
        je      .L9
        call    f1()
        jmp     .L11
.L9:
        call    f2()
.L11:
        nop
        pop     rbp
        ret

MSVC braindead литерал кода с отключенной оптимизацией:

void foo() {
    if (false) f1();
    else f2();
}
;; MSVC 19.20 x86-64
void foo(void) PROC                                        ; foo
        sub     rsp, 40                             ; 00000028H
        xor     eax, eax                     ; EAX=0
        test    eax, eax                     ; set flags from EAX (which were already set by xor)
        je      SHORT [email protected]               ; jump if ZF is set, i.e. if EAX==0
        call    void f1(void)                          ; f1
        jmp     SHORT [email protected]
[email protected]:
        call    void f2(void)                          ; f2
[email protected]:
        add     rsp, 40                             ; 00000028H
        ret     0

Бенчмаркинг с отключенной оптимизацией не полезен

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

Если это не очень важно для вашего проекта, и вы просто не можете найти достаточно информации о локальных переменных или что-то с минимальной оптимизацией, например g++ -Og, заголовок этого ответа - полный ответ. Игнорировать режим отладки, беспокоиться только о качестве ассемблера в оптимизированных сборках. (Желательно с включенным LTO, если ваш проект может включить это, чтобы разрешить встраивание между файлами.)