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

    Программистам на 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

    CT::G

    1798

    1798

    2048

    expression template
    (ET)

    ET::F

    899

    899

    702

    ET::G

    1796

    1796

    1402

    constexpr
    (CE)

    CE::F

    512

    35

    26

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

    Комментарии 13

      0
      А могли бы сделать рекурсивные макросы с определением глубины рекурсии.
        0

        Если на шаблонах и функциях рекурсия пишется естественным способом (компилятор берёт на себя арифметику и ветвление), то на препроцессоре придётся как-то исхитряться.


        Вот, казалось бы, BOOST_PP, практически промышленная библиотека, — а и то имеет внутренние ограничения "потомучто марамучто". Там нельзя сделать препроцессорный массив из более чем 20 элементов, потому что у разработчиков на 21-м нумерованном макросе контрол-вэ сломалось.

          –2
          Могли бы сделать нормальные синтаксические макросы. Да хоть встроить в компилятор любой скриптовый язык — хоть тот же JavaScript — и сделать API к синтаксическому дереву.
            +2
            Кодогенерация это интересно, но если для написания кода на одном языке вам нужен код на другом языке — это повод задуматься, а всё правильно ли Вы делаете.
              –3

              У каждого языка своя ниша и специализация. C++ явно небезопасен для того, чтобы на нем писать плагины к компилятору. А у js уже есть успешный опыт работы с древовидной DOM языка HTML.
              Те же шаблоны C++ это по сути отдельный язык, лишь частично пересекающийся с C++. Вы не примените там if, while, for, не выделите память оператором new, не воспользуетесь классами какого нибудь Qt или WxWidgets.
              Проблема а том, что этот язык получился случайно и не очень то удобен для программирования.

                0
                Полностью с вами согласен. Я про то, что нужно разделять сущности. Т.е. здесь мы не пишем код, а работаем с AST. Ну и инструменты надо брать соответствующие: или пользоваться языками, в которые прямая манипуляция с AST заложена, например, лисп или тикль, или писать плагин для компилятора, или глумиться над рантаймом. А вот написание кода и работу с его представлением в одном файле смешивать как-то не стоит.

                Я плохо говорю на плюсах, но в С на макросах можно реализовать if, while, for в boost.preprocessor или в Р99. Хотя это жуткое извращение заставлять фактически рефал-машину изображать из себя императивный ЯП.
                  0

                  Ох, если бы рефал-машину…
                  Вот если бы в качестве обязательного этапа трансляции был не cpp, а m4, например… (то это был бы ацкий ад).

                    0
                    Ох, если бы рефал-машину…
                    У меня такие ассоциации: иммутабельность, чистота, подстановка. Собсно, из-за изначально заложенных подводных граблей при любой реализации for на макросах вылазит ужас типа
                    #define EVAL1024(x) (EVAL512(x), EVAL512(x))
                    а while разворачивается в аналог prototheads/Duff's device через макросы FOR (см.выше) и __line__
                    Вот если бы в качестве обязательного этапа трансляции был не cpp, а m4
                    Спасибо, мы ещё помним sendmail. Аж по шкварнику мурашки пробежали.
                  –1

                  Шаблоны задумывались как гигиенические макросы, а внезапно получилось то, что получилось.


                  А если мы добавим настоящие гигиенические макросы в стиле немерле или темплит-хаскела, то это вообще взрыв мозга получится.
                  Потому что найдутся способы и их тоже вывернуть мясом наружу, как это сделали с шаблонами.

            +2
            У вас в коде ошибка:
            constexpr unsigned f(unsigned n) {
              return n < 2 ? f(n-1) + f(n-2);
            }
            
              0

              Ага, спасибо, поправил. В работающем коде, разумеется, этого уже нет :)

            • НЛО прилетело и опубликовало эту надпись здесь
                +1

                Не, конечно, в разных контекстах одно и то же синтаксическое дерево будет резолвиться по-разному.
                Даже без новомодных концептов:


                #include <iostream>
                
                char f(...);
                const int a = sizeof(f(0));  // 1
                short f(short);
                const int b = sizeof(f(0));  // 2
                int f(int);
                const int c = sizeof(f(0));  // 4
                
                int main() {
                  std::cout << a << " " << b << " " << c << std::endl;
                }

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

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое