Предпочтительный способ вычислений во времени компиляции
От: sergii.p  
Дата: 29.08.19 15:09
Оценка: :)
собственно в C++, есть два способа делать одно и то же.
Например посчитать факториал можно с помощью инстанциирования шаблонов:

template<int Val>
struct factorial: std::integral_constant<int, Val * factorial<Val - 1>>{};

template<>
struct factorial<0>: std::integral_constant<int, 1>{};


Здесь при расчёте factorial<5> последовательно инстанциируются шаблоны factorial<5>, factorial<4>, factorial<3>, factorial<2>, factorial<1> и factorial<0>. Некоторые умные люди говорят, что это бьёт по времени компиляции (точнее по памяти компилятора). На каждый инстанс надо завести память и эту память компилятор освободить никак не сможет до окончания компиляции. С другой стороны, скорость вычислений потенциально может вырасти за счёт кэширования. Хотя, насколько я знаю, большинство компиляторов действуют по другому алгоритму и инстанциируют по-жадному всё что видят. То есть вроде как плюсов получается совсем нет, одни накладные расходы.

Другой способ в constexpr функциях

constexpr int factorial(int val)
{
    if(val == 0) {
        return 1;
    }
    else {
        return val * factorial(val - 1);
    }
}


здесь вроде как никаких инстанциирований нет. Кэширует ли компилятор значения функции factorial? Как-то очень сомневаюсь. Но в принципе и так неплохо, раз нам удалось сократить количество инстанциирований (операции не из дешёвых).

Вроде выбор напрашивается. Надо предпочитать constexpr функции. Но если смотреть реализации stl, то получается многие идут по первому пути (н-р реализация наибольшего общего делителя _gcd из std::ratio для gcc и msvc). Значит есть какие-то проблемы с constexpr подходом. Так вот какие?
Re: Предпочтительный способ вычислений во времени компиляции
От: kov_serg Россия  
Дата: 29.08.19 15:11
Оценка: +1 :)
Здравствуйте, sergii.p, Вы писали:

SP>собственно в C++, есть два способа делать одно и то же.

SP>Например посчитать факториал можно с помощью инстанциирования шаблонов:

SP>Другой способ в constexpr функциях


Есть еще третий способ вычисления до компиляции
Re: Предпочтительный способ вычислений во времени компиляции
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 29.08.19 17:24
Оценка: +2
Здравствуйте, sergii.p, Вы писали:


SP>Вроде выбор напрашивается. Надо предпочитать constexpr функции. Но если смотреть реализации stl, то получается многие идут по первому пути (н-р реализация наибольшего общего делителя _gcd из std::ratio для gcc и msvc). Значит есть какие-то проблемы с constexpr подходом. Так вот какие?


constexpr не было до C++11, в подходах инерция и нет причины менять сейчас.
The God is real, unless declared integer.
Re: Предпочтительный способ вычислений во времени компиляции
От: swingus  
Дата: 11.09.19 22:43
Оценка: 7 (1) +1
Но экономней всего:



#include <utility>
#include <iostream>

template <std::size_t Zero, std::size_t... Vals>
int constexpr fact_impl(std::index_sequence<Zero, Vals...>)
{
    return (... * Vals);
}


template <std::size_t Val>
int constexpr factorial() { return fact_impl(std::make_index_sequence<Val>{}); }

int main()
{    
    std::cout << factorial<5>() << "\n";
}




Здравствуйте, sergii.p, Вы писали:
Re[2]: Предпочтительный способ вычислений во времени компиля
От: rg45 СССР  
Дата: 12.09.19 14:22
Оценка: +1
Здравствуйте, swingus, Вы писали:


S>Но экономней всего:


  Оригинальный пример
S>
S>#include <utility>
S>#include <iostream>

S>template <std::size_t Zero, std::size_t... Vals>
S>int constexpr fact_impl(std::index_sequence<Zero, Vals...>)
S>{
S>    return (... * Vals);
S>}


S>template <std::size_t Val>
S>int constexpr factorial() { return fact_impl(std::make_index_sequence<Val>{}); }

S>int main()
S>{    
S>    std::cout << factorial<5>() << "\n";
S>}
S>


S>


Только факториал пяти равен 120, а не 24 А попытка получить факториал от единицы или нуля у тебя приводит к ошибке компиляции.

Исправленная версия:

http://coliru.stacked-crooked.com/a/6c27e0cf39b312d0

template <std::size_t... Vals>
int constexpr fact_impl(std::index_sequence<Vals...>)
{
    return (1 * ... * (Vals + 1));
}

template <std::size_t Val>
int constexpr factorial() { return fact_impl(std::make_index_sequence<Val>{}); }


Можно чуть по-другому (тест на внимательность — найдите три отличия):

http://coliru.stacked-crooked.com/a/e3d5c43f5e52b7dc

template <std::size_t... Vals>
int constexpr fact_impl(std::index_sequence<0, Vals...>)
{
    return (1 * ... * Vals);
}

template <std::size_t Val>
int constexpr factorial() { return fact_impl(std::make_index_sequence<Val + 1>{}); }
--
Не можешь достичь желаемого — пожелай достигнутого.
Отредактировано 12.09.2019 15:14 rg45 . Предыдущая версия . Еще …
Отредактировано 12.09.2019 15:12 rg45 . Предыдущая версия .
Отредактировано 12.09.2019 14:43 rg45 . Предыдущая версия .
Отредактировано 12.09.2019 14:28 rg45 . Предыдущая версия .
Re: Предпочтительный способ вычислений во времени компиляции
От: rg45 СССР  
Дата: 13.09.19 06:50
Оценка:
Здравствуйте, sergii.p, Вы писали:

SP>собственно в C++, есть два способа делать одно и то же.

SP>
SP>Вроде выбор напрашивается. Надо предпочитать constexpr функции. Но если смотреть реализации stl, то получается многие идут по первому пути (н-р реализация наибольшего общего делителя _gcd из std::ratio для gcc и msvc). Значит есть какие-то проблемы с constexpr подходом. Так вот какие?

Ничего не имею против функций, но вариант реализации на шаблонах структур тоже имеет право на жизнь, я считаю. Благо необходимось в шаблонной рекусии отпала во многих случаях, после появления variadic templates и fold expressions:

http://coliru.stacked-crooked.com/a/1f217aa952e79f57

template <size_t N, typename = std::make_index_sequence<N+1>>
struct Factorial;

template <size_t N, size_t...V>
struct Factorial<N, std::index_sequence<0, V...>> : std::integral_constant<size_t, (1 * ... * V)> {};

int main()
{
    std::cout << Factorial<0>::value << std::endl;
    std::cout << Factorial<1>::value << std::endl;
    std::cout << Factorial<2>::value << std::endl;
    std::cout << Factorial<3>::value << std::endl;
    std::cout << Factorial<4>::value << std::endl;
    std::cout << Factorial<5>::value << std::endl;
}
--
Не можешь достичь желаемого — пожелай достигнутого.
Отредактировано 13.09.2019 7:33 rg45 . Предыдущая версия . Еще …
Отредактировано 13.09.2019 7:30 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 7:08 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 7:03 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 7:01 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 7:00 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 6:52 rg45 . Предыдущая версия .
Re[2]: Предпочтительный способ вычислений во времени компиляции
От: sergii.p  
Дата: 13.09.19 10:30
Оценка:
Здравствуйте, rg45, Вы писали:

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


почему? Какие ваши аргументы?

R>Благо необходимось в шаблонной рекусии отпала во многих случаях, после появления variadic templates и fold expressions:


ну вот я приводил пример реализации вычисления НОД в stl. Выражения свёртки тут не помогут. К тому же это С++17. Поиграться конечно можно. Но ни одного реального проекта в своём кругу знакомых пока не знаю.
Re[3]: Предпочтительный способ вычислений во времени компиля
От: rg45 СССР  
Дата: 13.09.19 11:21
Оценка:
Здравствуйте, sergii.p, Вы писали:

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


SP>почему? Какие ваши аргументы?


Исходя из презумпции права на жизнь. Это право существует до тех пор, пока не обосновано обратное. В данном конкретном примере
Автор: rg45
Дата: 13.09.19
нет последовательного инстанцирования шаблонов, о котором ты говоришь выше. Сложность реализации соизмерима с "функциональным" вариантом. Так почему, спрашивается, нужно отказать этому варианту в праве на жизнь?

SP>ну вот я приводил пример реализации вычисления НОД в stl. Выражения свёртки тут не помогут. К тому же это С++17. Поиграться конечно можно. Но ни одного реального проекта в своём кругу знакомых пока не знаю.


Возможно, это тот случай, когда использование шаблонов классов менее оправдано, чем использование constexpr функций. В то же время, найдутся и другие задачи, которые наоборот, будет более рационально решать при помощи шаблонов классов. Например, такие задачи, при прешении которых востребованы частичная специализация и активное использование SFINAE. Конечно, большинство задач можно решить и тем, и другим способом — благодаря тому, что отсутствие частичной специализации для шаблонов функций почти всегда можно компенсировать возможностью перегузок. Просто на шаблонах классов такие задачи может оказаться решать банально проще и нагляднее.

Я бы сказал так, когда мы стакливаемся с необходимостью шаблонной рекурсии, при этом существует равноценный вариант решения на constexpr функциях, то, наверное, стоит отдавать предпочтение ему. А вообще, на мой взгляд, поиски УНВЕРСАЛЬНОГО предпочтительного решения несколько наивны.
--
Не можешь достичь желаемого — пожелай достигнутого.
Отредактировано 13.09.2019 14:28 rg45 . Предыдущая версия . Еще …
Отредактировано 13.09.2019 12:17 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 12:16 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 12:14 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 12:13 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 12:10 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 11:56 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 11:38 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 11:36 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 11:35 rg45 . Предыдущая версия .
Отредактировано 13.09.2019 11:28 rg45 . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.