Метапрограммирование в C++

    Метапрограммирование — это «программирование программ», то есть написание некой промежуточной программы, результатом которой будет некая часть другой программы. Самый просто пример метапрограммирования — это шаблоны C++. Вместо написания десяти одинаковых функций для разных типов, мы пишем шаблон, и компилятор сам соберет нам эти десять функций.

    Другой неявный пример метапрограммирования — это precomputing, вычисления, которые проводятся на этапе компиляции. Если в коде вы напишете
    int i = 2+2*2;
    компилятор (вернее, прекомпилятор), вычислит это значение и передаст компилятору уже готовое
    int i = 6;
    Прекомпилятор пытается вычислить все возможное на этапе компиляции, чтобы разгрузить ран-тайм, в том числе и раскрыть шаблоны. Именно это его свойство позволяет писать очень интересные precomputing штучки, которые будут вычислины на этапе компиляции.

    Конкретный пример — это реализация CRC32. Не вдаваясь в детали, приведу ее алгоритм:

    unsigned long Crc32(unsigned char *buf, unsigned long len)
    {
      unsigned long crc_table[256];
      unsigned long crc;

      for (int i = 0; i < 256; i++)
      {
        crc = i;
        for (int j = 0; j < 8; j++)
          crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;

        crc_table[i] = crc;
      }

      crc = 0xFFFFFFFFUL;

      while (len--)
        crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);

      return crc ^ 0xFFFFFFFFUL;
    };
    * This source code was highlighted with Source Code Highlighter.


    Для этого алгоритма нужна таблица из 256 чисел. Логично было бы не вычислять ее при каждом вызове функции, да и вообще, так как таблица определена заранее, записать ее в виде
    long crc_table[256] = {"0x12345678", ... }
    Но это как-то неслишком круто. Посему было решено вынести ее вычисление в compile-time средствами метапрограммирования.

    Рассмотрим функцию вычисления таблицы поближе. Она состоит из четырех составляющих:
    1. вычисления значения полинома: crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;
    2. цикла, повторяющего вычисления «рекурсивно» 8 раз, то есть применяющего первое выражение последовательно для одного и того же алгортима: for (int j = 0; j < 8; j++)
    3. сохранения вычисленного значения в таблице: crc_table[i] = crc
    4. и цикла для всей таблицы: for (int i = 0; i < 256; i++)


    Будем создавать наше вычисление по шагам.
    Первый шаг — создание шаблона, который по данному t вычислит значение полинома. Это неслишком сложно:
    template <unsigned long t> struct Polynome  { static const unsigned long value = t&1 ? (t>>1)^0xedb88320 : t>>1   }; };


    Данный шаблон принимает на вход unsigned long параметр и превращает его в структуру с определенной внутри константой value.

    Следющий шаг — выполнение этого кода в цикле. Для этого определим такой шаблон:

    template <unsigned long t, int i> struct For { static const unsigned long value = For<Polynome<t>::value, i-1 >::value; };

    Здесь начинается магия.

    Мы определили шаблон, который получает два параметра — t, собственно вычисляемое значение, и i — счетчик. Этот шаблон создает структуру с единственной константой value внутри, которая вычисляется… через значение этого же шаблона! Мы получаем рекурсию — шаблон определеятся через самого себя. Для завершения рекурсии, мы воспользуемся частичной специализацией шаблона:

    template <unsigned long t> struct For<t,0>  { static const unsigned long value = Polynome<t>::value;         };


    И, наконец, само вычисление — вызов шаблона For с определенным количество итераций:

    template < unsigned long t> struct Hash    { static const unsigned long value = For<t,7>::value;           };


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

    Все это очень напоминает вычисление рекурсивных функций в функциональном программировании:

    polynom x = x & 1 ? (x >> 1) ^ 0xEDB88320UL : x >> 1

    for x t = polynom(f x t-1)
    for x 0 = polynom(x)

    hash x = for x 7

    (Не уверен в точности написания, но суть, думаю, понята)

    Третий и четвертый шаги — создать таблицу вычисленных значений. Опять-таки воспользуемся шаблоном со счетчиком:

    template<int r, int t> struct Table : Table<r+1, t-1>
    {
      Table() { values[t]=Hash<t>::value; }
    };

    template<int r> struct Table<r,0>
    {
      unsigned long values[r+1];
      Table() { values[0]=Hash<0>::value; }
      unsigned long operator[](int i) {  return values[i];}
    };
    * This source code was highlighted with Source Code Highlighter.


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

    Последний шаг — это, собственно, объявление самой таблицы

    typedef Table<0,255> CRC_TABLE;

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

    Вот так это все выглядит в собранном виде

    template <unsigned long t> struct Polynome  { static const unsigned long value = t&1 ? (t>>1)^0xedb88320 : t>>1;   };
    template <unsigned long t, int i> struct For { static const unsigned long value = For<Polynome<t>::value,i-1 >::value; };
    template <unsigned long t> struct For<t,0>  { static const unsigned long value = Polynome<t>::value;         };
    template <unsigned long t> struct Hash    { static const unsigned long value = For<t,7>::value;           };

    template<int r, int t> struct Table : Table<r+1, t-1>
    {
      Table() { values[t]=Hash<t>::value; }
    };
    template<int r> struct Table<r,0>
    {
      int values[r+1];
      Table() { values[0]=Hash<0>::value; }
      int operator[](int i) {  return values[i];}
    };

    typedef Table<0,255> CRC_TABLE;

    class Crc32Hasher
    {
      CRC_TABLE crc_table;
    public:
      unsigned long GetHashCode(const void* pObj, size_t length){
       const char* buf = (const char*)pObj;
       unsigned long crc32=0xffffffff;
       for (size_t i=0; i<length; i++)
        crc32=crc_table[(crc32^(*buf++))&0xff]^(crc32>>8);
       crc32=crc32^0xffffffff;
       return crc32; 
      }
    };
    * This source code was highlighted with Source Code Highlighter.


    Для заинтересовавшихся — советую почитать Андрей Александреску «Современное проектирование на С++» ISBN: 5-8459-0351-3
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 55
      +2
      Очень интересный способ. Но на его написание (ИМХО) уйдёт больше времени, чем на вычисление массива первой функцией и его вывода в буфер обмена.
      ↑Ненормальное программирование↑
        +2
        Ну, на написание данной вещи действительно ушло много времени. Но теперь есть навык, такое же можно писать очень быстро. Но, как вы правильно замтеили, это же блог «Ненормальное программирование».
          0
          Когда от приложения требуется добиться высокой производительности, то проще программисту потратить n-ое кол-во времени, чем приложение потратит на его выполнение в целом. Давно использую данный подход в php, очень доволен. Правда не знал как он называется. Хотя конечно на С++ реализовать такой подход значительно сложнее.
          –3
          А чем это выгодно? Программа стартует на несколько миллисекунд быстрее, зато нагородили кучу темплейтов ради такой простой вещи.
            +4
            Эти темплейты закрываются внутри пространства имен и снаружи не видны. Вообще говоря это — proof of concept, ничего более.
              0
              а более реалистичный пример можно? с одно стороны метапрограммирование — это прекрасное упражнение для мозгов, но с другой — я не понимаю, где оно может дать серьезные бенефиты.

              у template metaprogramming есть на мой взгляд лишь один плюс перед подходом основанном на кодогенерации: шаблоны являются частью языка. На мой взгляд этот плюс убивается мозговзрывающей сложностью более или менее серьезного шаблона.
                0
                Имхо, это самый реалистичный пример, который я нашел. Не могу вспомнить другие распространенные примеры, где нужен precomputing.
                • НЛО прилетело и опубликовало эту надпись здесь
            +5
            Прерасный пример! :) Замечательный!
            И дело не в том, сколько ДАННЫЙ пример выигрывает или сколько ДАННЫЙ пример экономит.
            Это замечательный пример того, как вычисления можно перенести на стадию компиляции!
              0
              Класс! Отдельное спасибо автору за указание книги, где о таком пишут.

              Правда, страшно представить отладку такого нагромождения темплейтов. Там одну букву не так поставишь, оно такого насчитает… и внутрь не заглянешь step-by-step, ещё и темплейты с их способностью выдавать 20 errors на одну опечатку. Программирование тут, может, и ненормальное, но отладка (особенно, если применить для чего-то более сложного) уже за гранью ненормального. «Madness? This is SPARTAAA!!!» :)
                +2
                спасибо, люблю магию :)
                  +1
                  Жесть!!! Мы в микроконтроллерах все CRC табличным способом считали, да еще и выискивали где бы микросекунду сэкономить :-)
                  • НЛО прилетело и опубликовало эту надпись здесь
                      +4
                      На самом деле всё выглядит столь ужасно потому, что метапрограммирование в C++ не добавили, а открыли. Случайно. В языках где про него изначально думали (D, Scala, разнообразные диалекты Lisp'а) всё горазло менее страшно. Но принцип тот же: программа порождает программу.
                      • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          Ну там добавят немножко новых возможностей. Основная, cамая вкусная, фича классических языков с поддержкой метапрограммирования всё так же далека: язык метапрограммирования не является вариантом языка программирования. Он совершенно иной! А должен быть тем же — ну пусть с небольшими ограничениями. Вот тогда метопрограммирование становится удобным инструментом, а не игрушкой для фанатов…
                          +1
                          В Scala (пока) нет метапрограммирования.
                          0
                          люблю такой стиль программирования (вернее ненавижу:) пришлось как-то развивать/улучшать систему для расчетов генераторов для ветрянных электростанций. Генераторов таких (медленновертящихся, без «коробки передач») никто не делал, программист-дипломант до меня наворотил там целый язык из макросов и шаблонов для описания формул. Бедные инженеры для изменения формулы правили код, потом компилировали его (занимало примерно 10 минут) а потом тестировали свою формулу. И так весь день, ругались постоянно, так как настройка была сплошной потерей времени. Ну и мне пришлось повозиться, беда.

                          В общем, в этом деле нужно чувство меры, и не всегда время потраченное на компиляцию оправдывает быстроту работы программы, не говоря уже о проблеме «ремонтопригодности» такой штуки.
                            0
                            Это да. Такие вещи, серпя сердце, можно применять только в хорошо известных алгоритмах — как в данном случае. Сам бы за такое давал по пальцам. Но эти знания, почерпнутые из книги Александреску, подвигли меня на изучение хотя бы основ функционального программирования, и эти знания мне очень пригодились при переходе на C# 3.5, LINQ, лямбды и иже с ними.
                              0
                              Ага, функциональное программирование это вещь:) Но лично для меня даже в лиспе (а именно доктор схеме) ламда была не совсем «читабельна».
                              На данный момент реализация в груви мне лично нравится больше всего, синтакс (лично мне) хорошо понятен, хотя на данный момент я с груви не работаю.
                                +1
                                а SICP уже читали?
                                на русском можно скачать здесь — sicp.sergeykhenkin.com/
                              0
                              Интересное решение, а как изменилось время компиляции?
                                0
                                Естественно упала. На пару-тройку секунд.
                                  +2
                                  Как раз после прочтения книги Александреску появилось чуство что С++ не мое.
                                  Потому что жутко не нравится время компиляции и совсем не радует его увеличение библиотеками Loki, Boost. С STL приходиться мириться.

                                  После довольно жуткого проекта с временем полного ребилда пять минут и убитой архитектурой (ребилдить приходилось часто) переметнулся к динамическим языкам.
                                  Теперь занимаюсь Python, Ruby, PHP, JavaScript.

                                  PS: Кодогенерация есть в Qt — qmake. Интересно почему такие системы не получили распространения?
                                  Имхо, кодогенерация шаблонами не гибка, многословна и даже не кеширует результат.

                                  PSS: Python + Qt — отличная связка.
                                    0
                                    А я сижу на динамических языках и очень грущу о С++ и C# :)

                                    Кстати, а зачем вообще нужен полный ребилд? У нас так только night builds собирались для автотестов.
                                      0
                                      Делаете так:
                                      — создаете один большой хидер, в который включаете все хидеры проекта
                                      — маскируете невнятным раскидыванием функциональности и ложным именованием

                                      Готово! Теперь при попытках развивать проект будет ребилдится весь проект.
                                –1
                                Кстати да, тоже советую всем почитать книгу Андрея Александреску «Современное проектирование на С++».
                                К счастью, у большинства людей эта книга отбивает желание писать сложные шаблоны :) Зато дает навык их понимания.
                                Книга сложная, но правильная. И кроме сложных случаев метапрограммирования, там есть еще отличные примеры более простых шаблонов, например Policy-based дизайн классов.
                                  –2
                                  Да, меня в свое время поразили возможности, открываемые шаблонами в C++. Пример замечательный.
                                    0
                                    Помнится, игрался я в школе с метапрограммированием
                                    www.everfall.com/paste/id.php? c29q3eov4cjj — определитель матрицы N*N compile-time
                                    www.everfall.com/paste/id.php? zakx0n2nwaaa — мультиметоды (для N <= 32 аргументов, а не только для 2)

                                    Вообще, язык метапрограммирования в Си++ — чистый функциональный, но, к сожалению, без карринга и лямбд.
                                    В новом стандарте должны ввести concept/concept_map — в чистом виде type classes из Haskell
                                      0
                                      Твои примеры — это страшно. В продакшн-коде такое увидеть — не дай бог.
                                        0
                                        Я ж не дурак такое в продакш совать
                                        Просто интересно было, насколько это реально
                                      +5
                                      Метапрограммирование слабо применимо в коммерческой разработке, если конечно же код пишет не Александреску :)
                                      — Это увеличивает время компиляции. Т.е. сначала я трачу деньги компании на поиск не тривиального решения времени комспиляции, затем я трачу деньги компании на перекомпиляции всего этого добра.
                                      — Это увеличивает сложность проекта, т.е. после ухода человека проектировавшего ЭТО, сложно будет найти настолько же подкованного.
                                      — Применение подобных приемов в языке, который не был спроектирован для этого — не самое лучшее занятие.

                                      Более того, это действительно не продуктивно. Я прочел Александреску два раза, причем оба раза некоторые вещи я читал до посинения и полного понимания. В итоге через два года я практически ничего не помню, и понимания кода выше мне дается с большим трудом, может потому, что было мало практики. Но для сравнения, QT после года использования я не забыл и прекрасно помнил. Так что сложность таки сказывается.
                                        +3
                                        Давнишний тред на rsdn про метапрограммирование — читать и помнить.
                                          0
                                          А вот пример для определения простых чисел: sharpc.livejournal.com/23950.html

                                          Только, хочу обратить внимание на слова автора и свой личный опыт: если «разворачивание» метаконструкций будет достаточно долгим, то компилятор выдаст ошибку.
                                            0
                                            Ты выбрал не самый эффективный способ. Перебор можно ограничить до sqrt(N), уменьшишь количество шаблонов.
                                            0
                                            (вернее, прекомпилятор)


                                            Какой такой «прекомпилятор»?
                                              0
                                              пропроцессор.
                                                0
                                                сомневаюсь, что препроцессор таким занимается.
                                                  0
                                                  Та часть компилятора, которая отвечает за шаблоны и константы. :)
                                                    0
                                                    Именно он этим и занимается.
                                                      0
                                                      да ну? может потрудитесь доказать?

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

                                                        0
                                                        у препроцессора свой метапрограмминг :)

                                                        #define tType uint64_t
                                                        #define tName(n) myname_#n
                                                        #include «t/MetaProg.tpl»

                                                        … t/MetaProg.tpl
                                                        struct tName(mystruct) {
                                                        tType x;
                                                        };
                                                        void tName(myfun)() {
                                                        что-нибудь делаем;
                                                        }
                                                        #undef tType
                                                        #undef tName
                                                          0
                                                          ага, ага, Boost.Preprocessor и прочие радости жизни.

                                                          но к вычислению константных выражений это всё отношения не имеет.
                                                +7
                                                Класс! Побольше бы именно таких топиков, а не «Oh shi, это же новый айфон!».
                                                Автор, спасибо Вам.
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                    0
                                                    Александреску — просто немного другая книга. Она же не только метапрограммированию посвящена.
                                                    А книга by Abrahams, Gurtovoy — это чистое метопрограммирование, причём явно с упором на Boost.MPL (что логично и правильно, они ведь авторы библиотеки).
                                                    0
                                                    Спасибо, занимательно. Но если мне не изменяет мой склероз, конкретно этот пример соптимизирует компилятор ((= По крайней мере GCC.
                                                      0
                                                      Отличный пост! Хорошо что не перевелись ещё computer science! Скажем да шаблону и нет былокодингу :)

                                                        0
                                                        «цикла, повторяющего вычисления «рекурсивно» 7 раз» — исправьте
                                                          0
                                                          Еще одно уточнение: таблица все же заполняется в runtime, но значения таки считаются на этапе компиляции. Статья понравилась, спасибо.
                                                            0
                                                            Таблица тоже заполняется в компайлтайм, потому как инициализация константная и инлайнится.
                                                              0
                                                              Видимо, я невнимательно ищу… Где именно там «константная инициализация»?
                                                                0
                                                                Мм. Действительно. Давно писалось — мне казалось, что я проверял, что таблица заполняется в компайл-тайм. Нет под рукой дизассемблера проверить.
                                                          0
                                                          ОМГ!

                                                          P.S.
                                                          За код и пояснения — примите благодарность :)
                                                            0
                                                            Самое интересное, что GCC и Comeau это не компилируют. Они считают что:
                                                            identifier «values» is undefined
                                                            Table() { values[t]=Hash:: value; }

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

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