[Ненормальное программирование, C++] Мемоизация в compile time вычислениях в C++

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 3 месяца
Сообщений: 27286

news_bot ^® написал(а)
02-Мар-2021 06:30

Цитировать

Программистам на C++ хорошо (надеюсь!) известно, что во время компиляции можно производить разнообразные вычисления. Лишь бы эти вычисления были "чистыми", без побочных эффектов. Это делается на шаблонах и на constexpr функциях.Чистое выражение означает, что, сколько бы раз мы его ни попытались вычислить, мы получим один и тот же результат. Поэтому из соображений эффективности результат желательно мемоизировать, чтобы второй раз не делать ту же работу. Но насколько хорошо это умеет делать компилятор?Для стресс-тестирования возьмём наивную формулу чисел Фибоначчи:f(n) = (n < 2) ? 1 : f(n-1) + f(n-2)Она интересна нам по нескольким причинам:

глубина рекурсии линейно зависит от n
без мемоизации она сводится к суммированию f(n) единичек, а это, напомню, экспонента по основанию золотого сечения
с мемоизацией — к запоминанию n значений

Как вычислить эту формулу в compile time?Для этого есть 3 техники.Первая, хорошо известная с давних времён (с C++98): шаблоны с целочисленными параметрами и членами-константами. (В древности использовались enum'ы, потом появились статические константы).

// для удобства и краткости записи, будем наследоваться от шаблонного типа
template<unsigned n> struct int_ { static constexpr unsigned value = n; };
template<unsigned n> struct f;
template<> struct f<0> : int_<1> {};
template<> struct f<1> : int_<1> {};
template<unsigned n> struct f : int_< f<n-1>::value + f<n-2>::value > {};
template<unsigned n> constexpr unsigned F = f<n>::value;

(будем использовать unsigned, потому что собственно значения чисел нам для опытов не нужны, а нарываться на целочисленное переполнение не хочется).Вторая техника стала доступна с С++11: это constexpr-функции.

constexpr unsigned f(unsigned n) {
return n < 2 ? f(n-1) + f(n-2);
}
template<unsigned n> constexpr unsigned F = f(n);

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

constexpr unsigned f(unsigned n) {
unsigned a = 1, b = 1;
for (i = 1; i < n; ++i) {
unsigned c = a + b;
a = b; b = c;
}
return b;
}

Но не в этот раз.Третья техника — тоже связана с шаблонами, а именно — expression template. Суть в том, что тип выражения выводится из типов аргументов. Конечно, для чисел Фибоначчи это выглядит извращением, но на expression template можно строить оптимальные планы сложных вычислений (например, цепочка из произведения нескольких матриц разного размера). Поэтому изучим и этот способ.

// снова воспользуемся типом, несущим число
template<unsigned n> struct int_ { static constexpr unsigned value = n; };
// поскольку мы делаем expression template, то введём арифметику на шаблонах:
template<unsigned x, unsigned y> auto operator + (int_<x>, int_<y>) {
return int_<x+y>{};
}
template<unsigned n> auto f(int_<n> /*arg*/) {
if constexpr (n < 2) {
return int_<1>{};
} else {
// можем написать так (expression template же!)
return f(int_<n-1>{}) + f(int_<n-2>{});
// или так - подчёркивая, что вся информация есть прямо в типе,
// и собственно вызовы нам не нужны:
return decltype( f(int_<n-1>{}) + f(int_<n-2>{}) ){};
// или так:
using t1 = decltype(f(int_<n-1>{}));
using t2 = decltype(f(int_<n-2>{}));
return int_<t1::value + t2::value>{};
}
}
template<unsigned n> constexpr unsigned F = decltype(f(int_<n>{}))::value;

Кстати, обратите внимание: вместо перегрузок / специализаций шаблона мы смогли сделать ветвление прямо внутри функции, благодаря стейтменту if constexpr, появившемуся в C++17. С шаблоном класса такой фокус не прошёл бы. Плюсик к выразительности (уравновешивает минусик: мы написали функцию, которую не вызываем; впрочем, и от шаблона класса нам нужно лишь значение его члена, а никак не структура).И ещё один штрих: наша функция не обязана быть constexpr. Можем даже отладочный вывод туда напихать.Перейдём, наконец, к мемоизации.Чтобы воплотить (instantiate) шаблон класса с данным параметром n, нам надо воплотить шаблон со значениями параметра n-1 и n-2, а их, соответственно, n-2 и n-3, и так далее до 1 и 0, а потом 2 и 1 (уже воплощены), 3 и 2 (и они тоже уже воплощены), и так далее. То есть, вторые ветки наших выражений будут обращаться к уже созданным типам.Единственное ограничение, с которым мы тут сталкиваемся — это глубина рекурсии.У gcc порог называется -ftemplate-depth по умолчанию равен 900, у clang -ftemplate-backtrace-limit— 1024. Мемоизировать тип именованного шаблона с данными параметрами — это естественно. А вот будет ли компилятор мемоизировать тип выражения? Это менее очевидно, но практика показывает: будет. Так что expression template тоже упирается в глубину рекурсии.Наконец, constexpr функции. Снова упираемся в глубину рекурсии, но это уже другой порог: gcc называет его -fconxtexpr-depth, clang — -fconstexpr-backtrace-limit, по умолчанию он равен 512.Но всё было бы хорошо, если бы не одно странное но.gcc вплоть до версии 9.3 умел мемоизировать функции! Поэтому можно было спокойно написать F<512> и даже F<1022> и почти мгновенно скомпилировать программу, выводящую соответственное число Фибоначчи.А, начиная с версии 10.1, gcc перестал это делать. Он честно вызывает функцию экспоненциальное количество раз и упирается в порог количества операций -fconstexpr-ops-limit, по умолчанию 33554432.Обратили внимание на два разных максимальных параметра?F<512> и F<1022> — откуда они взялись? Неужели можно числа Фибоначчи вычислять по-разному? Конечно, да.

template<unsigned n> struct f;
template<unsigned n> struct g;
template<> struct f<0> : int_<1> {};
template<> struct f<1> : int_<1> {};
template<unsigned n> struct f : int_< f<n-1>::value + f<n-2>::value > {};
template<> struct g<0> : int_<1> {};
template<> struct g<1> : int_<1> {};
template<unsigned n> struct g : int_< g<n-2>::value + g<n-1>::value > {};
template<unsigned n> constexpr unsigned F = f<n>::value;
template<unsigned n> constexpr unsigned G = g<n>::value;

В первом случае мы в первой ветке спускаемся на 1, во втором — на 2. И там и там мы, конечно, на каждом шаге получим все предшествующие значения и мемоизируем их, так что два раза одну работу делать не будем.Та же история и с expression template.GodBoltЯ ставил опыты на разных версиях компиляторов на сайте gcc.godbolt.orgВ частности,

gcc 10.1
clang 11.0.0 — ему труднее дались expression template
clang 9.0.0 — если ему подсунуть слишком большое значение в expression template, то он просто крешится, вместо диагностики: пытается построить мега-дерево выражения
gcc 9.3 — отлично справился с мемоизацией функции!

Максимальные значения параметров для разных способов выглядят так:компиляторgcc 9.3gcc 10.1clang 11.0.0class template
(CT)CT::F8998991024CT::G179817982048expression template
(ET)ET::F899899702ET::G179617961402constexpr
(CE)CE::F5123526CE::G5123526Полный код теста.

#include <iostream>
template<unsigned n> struct int_ { static constexpr unsigned value = n; };
template<unsigned x, unsigned y> auto operator + (int_<x>, int_<y>) {
return int_<x+y>{};
}
namespace CT { // class template
template<unsigned n> struct f;
template<> struct f<0> : int_<1> {};
template<> struct f<1> : int_<1> {};
template<unsigned n> struct f : int_<f<n-1>::value + f<n-2>::value> {};
template<unsigned n> struct g;
template<> struct g<0> : int_<1> {};
template<> struct g<1> : int_<1> {};
template<unsigned n> struct g : int_<g<n-2>::value + g<n-1>::value> {};
template<unsigned n> constexpr unsigned F = f<n>::value;
template<unsigned n> constexpr unsigned G = g<n>::value;
} // namespace CT
namespace ET { // expression template
template<unsigned n> auto f(int_<n>) {
if constexpr (n < 2) {
return int_<1>{};
} else {
return f(int_<n-1>{}) + f(int_<n-2>{});
}
}
template<unsigned n> auto g(int_<n>) {
if constexpr (n < 2) {
return int_<1>{};
} else {
return g(int_<n-2>{}) + g(int_<n-1>{});
}
}
template<unsigned n> constexpr unsigned F = decltype(f(int_<n>{}))::value;
template<unsigned n> constexpr unsigned G = decltype(g(int_<n>{}))::value;
} // namespace ET
namespace CE { // constexpr
constexpr unsigned f(unsigned n) {
return n < 2 ? 1 : f(n-1) + f(n-2);
}
constexpr unsigned g(unsigned n) {
return n < 2 ? 1 : g(n-1) + g(n-2);
}
template<unsigned n> constexpr unsigned F = f(n);
template<unsigned n> constexpr unsigned G = g(n);
} // namespace CE
int main() {
std::cout << CT::F<899> << std::endl;
std::cout << CT::G<1798> << std::endl;
std::cout << ET::F<899> << std::endl;
std::cout << ET::G<1796> << std::endl;
std::cout << CE::F<35> << std::endl;
std::cout << CE::G<35> << std::endl;
}

Выводы?Просто хотел поделиться своими наблюдениями.А также показать существующие ограничения вычислений во время компиляции. Конечно же, то, что язык шаблонов и constexpr'ов — тьюринг-полный, ещё не означает, что компилятор будет решать за вас проблему останова. Он или выдаст диагностику, или покрешится, или выжрет всю память.Причём от версии к версии компилятора поведение может различаться. Поэтому пользуйтесь возможностями, но будьте аккуратны и не доводите до крайностей.Кстати о "выжрать всю память"Если мы помешаем мемоизации — например, добавим ещё один параметр, принимающий уникальные значения, — то, в отличие от constexpr-функций, компилятор будет биться до победы... или до поражения.Функция, считающая количество операций для вычисления числа Фибоначчи

f(n, t) = n < 2 ? t+1 : f(n-1, f(n-2, t))
f(n) = f(n, 0)

На expression templates будет выглядеть вот так.

template<unsigned n, unsigned t>
auto f(int_<n>, int_<t>) {
if constexpr (n < 2) {
return int_<t+1>{};
} else {
return f(int_<n-1>{}, f(int_<n-2>{}, int_<t>{}));
}
}
int main() {
std::cout << decltype(f(int_<30>{}, int_<0>{}))::value << std::endl;
}

Для 26 — clang работал около полуминуты. Для 30 он сожрал больше 8 гигабайт памяти и загнал мой ноутбук в своп, после чего эксперимент пришлось прекратить.
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_nenormalnoe_programmirovanie (Ненормальное программирование), #_c++, #_compile_time, #_template, #_expression_template, #_constexpr, #_memoizatsija (мемоизация), #_nenormalnoe_programmirovanie (
Ненормальное программирование
), #_c++

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 17-Май 11:56
Часовой пояс: UTC + 5