nickolaym 2 мар 2021 в 04:07

Мемоизация в compile time вычислениях в C++

7 мин

9.3K

Программистам на 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 ? 1 : 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 (unsigned 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.3	gcc 10.1	clang 11.0.0
class template (CT)	CT::F	899	899	1024
class template (CT)	CT::G	1798	1798	2048
expression template (ET)	ET::F	899	899	702
expression template (ET)	ET::G	1796	1796	1402
constexpr (CE)	CE::F	512	35	26
constexpr (CE)	CE::G	1022	41	26

Полный код теста.

#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-2) + g(n-1);
}

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<41> << 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 гигабайт памяти и загнал мой ноутбук в своп, после чего эксперимент пришлось прекратить.

Теги:

Хабы:

Мемоизация в compile time вычислениях в C++

Как вычислить эту формулу в compile time?

Перейдём, наконец, к мемоизации.

Обратили внимание на два разных максимальных параметра?

GodBolt

Выводы?

Кстати о "выжрать всю память"

Публикации

Истории

Работа

Ближайшие события