3 разных/одинаковых способа выполнения времени компиляции N-factorial в C++

Я пытаюсь поиграть с метапрограммированием шаблонов, constexpr и if constexpr, и придумал 3 разных способа выполнения N-рекурсивной/N-факторной операции.

Все три примера я нашел здесь на SO или в результате поиска в сети, а затем изменил их, чтобы они делали то же самое

В первом примере используется метапрограммирование шаблонов: пример 1

template<int N>
struct NGenerator
{
    static const int result = N + NGenerator<N-1>::result;
};

template<>
struct NGenerator<0>
{
    static const int result = 1; 
};

static int example1 = NGenerator<5>::result;

Второй все еще использует шаблон, но я добавил constexpr: пример 2

template<int N>
constexpr int example2() 
{
return N + example2<N - 1>();
}


template<>
constexpr int example2<0>() 
{ 
    return 1;
}

static int ex2 = example2<5>();

В третьем я удалил шаблон и использовал «только» constexpr: пример 3

constexpr int generator(int n)
{
    return (n <= 1) ? 1 : n + generator(n - 1);
}

static int ex3 = generator(5);

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

Мой вопрос: в чем разница между тремя? Какой из них наиболее предпочтителен?

И, наконец, я хотел бы реализовать "if constexpr", но не смог, поэтому мой обходной путь состоял в том, чтобы сделать "if-statement" в примере 3, что на самом деле не так. истинное выражение if, но самое близкое, что я мог бы получить во время компиляции if - если это каким-либо образом то же самое, в чем я не уверен.


c++ constexpr template-meta-programming compile-time if-constexpr
person badaboomskey    schedule 29.12.2019    source источник
comment
Мой вопрос - в чем разница между тремя? - Проверяли ли вы вывод своих компиляторов на наличие оптимизированной сборки? Это должно окончательно ответить на вопрос.   -  person Jesper Juhl    schedule 29.12.2019
comment
Привет @JesperJuhl - извините за вопрос, но как мне это сделать?   -  person badaboomskey    schedule 29.12.2019
comment
Единственная разница, вероятно, в том, насколько быстро он компилируется. Кроме того, я предлагаю другой подход: использовать простой цикл. Они разрешены в функциях constexpr в современном C++.   -  person HolyBlackCat    schedule 29.12.2019
comment
Вы бы сделали это, либо сказав своему компилятору остановиться после создания сборки и просто сбросить этот ASM в файл (у всех основных компиляторов есть опции для этого), либо вы могли бы разобрать сгенерированный исполняемый файл и посмотреть на окончательный сгенерированный код. Такие инструменты, как nm и objdump, могут оказаться полезными.   -  person Jesper Juhl    schedule 29.12.2019
comment
Для этого вы можете использовать godbolt.org.   -  person t.niese    schedule 29.12.2019
comment
Не связано, но первые два примера возвращают 16, а третий возвращает 15!   -  person Olaf Dietsche    schedule 29.12.2019
comment
@OlafDietsche: это действительно не N-факториал + вместо *.   -  person Jarod42    schedule 29.12.2019
comment
@t.niese спасибо, я пытаюсь использовать это сейчас, но, добавляя все три примера один за другим, компилятор говорит мне, что компилятор генерации ASM вернул: 0, и сборка не сгенерирована ..   -  person badaboomskey    schedule 29.12.2019

Ответы (2)


arrow_upward
2
arrow_downward

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

По моему опыту, constexpr функции компилируются быстрее.

Все 3, вероятно, будут запомнены компилятором; но нешаблонная функция constexpr будет извергать меньше символов (шума).

Лучше всего этого была бы функция constexpr с циклом.

Компиляторы могут выполнять большинство опций во время выполнения, поскольку вы не настаивали на оценке времени компиляции. Замените static int на constexpr int.

person Yakk - Adam Nevraumont    schedule 29.12.2019
comment
Итак, каждый раз, когда это возможно - шаблон constexpr ›? Я не думал о последней части - что компиляторы могут делать это во время выполнения из-за оценки. Я использую static int, так что я могу увеличивать его каждый раз, когда он вызывается. Когда я использую constexpr int, он говорит мне, что выражение должно быть модифицируемым lvalue. - person badaboomskey; 29.12.2019

arrow_upward
1
arrow_downward

Пример 1 гарантированно выполняется во время компиляции.

constexpr функции (пример 2 и пример 3) могут вызываться в контексте, отличном от constexpr, и, таким образом, вычисляться во время выполнения (компилятор все равно может оптимизировать его для вычисления во время компиляции с правилом «как если бы»).

Я бы сделал что-то вроде:

constexpr std::size_t factorial(std::size_t n)
{
    std::size_t res = 1;
    for (std::size_t i = 1; i < n; ++i) {
        res *= i;
    }
    return res;
}

template <std::size_t N>
static constexpr std::size_t Factorial = factorial(5);

static std::size_t ex4 = Factorial<5>;

C++20 добавляет consteval, чтобы разрешить только оценку constexpr.

person Jarod42    schedule 29.12.2019
comment
спасибо за пример, ценю! Но в чем именно разница между вашим примером и моим номером 3? Также я не думал, что вы можете запустить обычный цикл for во время компиляции. Можно ли сделать if constexpr в вашем примере? - person badaboomskey; 30.12.2019
comment
В C++11 функции constexpr очень ограничены. начиная с С++ 14, вы можете делать гораздо больше (как для цикла). Большая разница с вашим в том, что я использую его позже в постоянном выражении. std::cout << factorial(5) будет вызовом времени выполнения, а не вызовом времени компиляции (если только он не оптимизирован компилятором). тогда как constexpr auto fact5 = factorial(5); std::cout << fact5; будет выполнять вычисление fact5 во время компиляции. - person Jarod42; 30.12.2019