Шаблон метапрограммирования - до сих пор не понимаю :( - PullRequest
30 голосов
/ 03 августа 2009

У меня проблема ... Я не понимаю шаблонное метапрограммирование.

Проблема в следующем: я много читаю. Но это не имеет особого смысла для меня: /

Факт № 1 : Метапрограммирование шаблонов быстрее

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}

Так что эта метапрограмма быстрее ... из-за константного литерала.

НО : Где в реальном мире у нас есть постоянные литералы?

Большинство используемых мной программ реагируют на ввод пользователя.

ФАКТ №. 2 : Шаблон метапрограммирования может обеспечить лучшую поддержку.

Да. Факторный пример может быть поддерживаемым ... но когда дело доходит до сложных функций, я и большинство других программистов на C ++ не могут читать функции.

А параметры отладки плохие (или, по крайней мере, я не знаю, как отлаживать).

Где смысл шаблонного метапрограммирования?

Ответы [ 11 ]

27 голосов
/ 04 августа 2009

Как факториал не является реалистичным примером рекурсии в нефункциональных языках, так и не является реалистичным примером метапрограммирования шаблонов. Это просто стандартный пример, к которому люди стремятся показать рекурсию.

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

Вот действительно хорошее руководство со страниц документации по бусту (на самом деле оно взято из блестящей книги , которую стоит прочитать).

http://www.boost.org/doc/libs/1_39_0/libs/mpl/doc/tutorial/representing-dimensions.html

15 голосов
/ 04 августа 2009

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

SSE swizzles ('shuffles') может быть замаскирован только как байтовый литерал (непосредственное значение), поэтому мы создали шаблонный класс 'mask merger', который объединяет маски во время компиляции, когда происходит многократное перемешивание:

template <unsigned target, unsigned mask>
struct _mask_merger
{
    enum
    {
        ROW0 = ((target >> (((mask >> 0) & 3) << 1)) & 3) << 0,
        ROW1 = ((target >> (((mask >> 2) & 3) << 1)) & 3) << 2,
        ROW2 = ((target >> (((mask >> 4) & 3) << 1)) & 3) << 4,
        ROW3 = ((target >> (((mask >> 6) & 3) << 1)) & 3) << 6,

        MASK = ROW0 | ROW1 | ROW2 | ROW3,
    };
};

Это работает и производит замечательный код без сгенерированных накладных расходов кода и небольшого дополнительного времени компиляции.

9 голосов
/ 04 августа 2009

После рекомендации Александреску Modern C ++ Design .

Шаблоны действительно блестят, когда вы пишете библиотеку, в которой есть фрагменты, которые могут быть собраны комбинаторно в подходе «выберите Foo, Bar и Baz», и вы ожидаете, что пользователи будут использовать эти фрагменты в некоторой форме, которая исправлено во время компиляции. Например, я стал соавтором библиотеки интеллектуального анализа данных, которая использует шаблонное метапрограммирование, чтобы позволить программисту решить, что DecisionType использовать (классификация, ранжирование или регрессия), чего ожидать InputType (числа с плавающей запятой, целые числа, перечисляемые значения и т. Д.) И что KernelMethod использовать (это вещь для интеллектуального анализа данных). Затем мы реализовали несколько разных классов для каждой категории, так что было несколько десятков возможных комбинаций.

Реализация 60 отдельных классов для этого потребовала бы много раздражающего, трудно поддерживаемого дублирования кода. Шаблонное метапрограммирование означало, что мы могли реализовать каждый концепт как единицу кода и предоставить программисту простой интерфейс для создания комбинаций этих концепций во время компиляции.

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

Я также однажды написал несколько простых генераторов псевдослучайных чисел во время компиляции просто для того, чтобы связываться с головами людей, но на самом деле это не считается ИМО.

9 голосов
/ 04 августа 2009

так что эта метапрограмма быстрее ... из-за константного литерала. НО: где в реальном мире у нас есть постоянные литералы? Большинство программ, которые я использую, реагируют на ввод пользователя.

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

Существует множество реальных применений, с некоторыми из которых вы уже знакомы, даже если не понимаете этого.

Один из моих любимых примеров - итераторы. Да, в основном они разработаны с использованием общего программирования, но метапрограммирование шаблонов полезно, в частности, в одном месте:

Для исправления указателей, чтобы их можно было использовать в качестве итераторов. Итератор должен предоставить несколько типов typedef, таких как value_type. Указатели этого не делают.

Таким образом, код, подобный следующему (в основном идентичен тому, что вы найдете в Boost.Iterator)

template <typename T>
struct value_type {
  typedef typename T::value_type type;
};

template <typename T>
struct value_type<T*> {
  typedef T type;
};

- это очень простая шаблонная метапрограмма, но она очень полезна. Это позволяет вам получить тип значения любого типа итератора T, будь то указатель или класс, просто с помощью value_type<T>::type.

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

Трюки типа boost::enable_if тоже могут быть очень ценными. У вас перегружена функция, которая должна быть включена только для определенного набора типов. Вместо определения перегрузки для каждого типа вы можете использовать метапрограммирование, чтобы указать условие и передать его в enable_if.

Earwicker уже упомянул еще один хороший пример - структуру для выражения физических единиц и измерений. Это позволяет вам выражать вычисления, как с физическими единицами, и обеспечивает тип результата. Умножение метров на метры дает количество квадратных метров. Шаблон метапрограммирования можно использовать для автоматического получения нужного типа.

Но в большинстве случаев метапрограммирование шаблонов используется (и полезно) в небольших, изолированных случаях, в основном для сглаживания неровностей и исключительных случаев, чтобы набор типов выглядел и вел себя единообразно, позволяя вам более широко использовать общее программирование эффективно

5 голосов
/ 04 августа 2009

Факторный пример примерно так же полезен для реального TMP, как "Hello, world!" предназначен для обычного программирования: он демонстрирует несколько полезных приемов (рекурсия вместо итерации, «еще-если-тогда» и т. д.) в очень простом, относительно простом для понимания примере, который не имеет большого значения для каждого из вас. день кодирования. (Когда в последний раз вам нужно было написать программу, которая выдает «Hello, world»?)

TMP - это выполнение алгоритмов во время компиляции, и это подразумевает несколько очевидных преимуществ:

  • Поскольку сбой этих алгоритмов означает, что ваш код не компилируется, сбойные алгоритмы никогда не попадают к вашему клиенту и, следовательно, не могут его потерпеть. Для меня за последнее десятилетие это было самое важное преимущество, которое привело меня к внедрению TMP в кодекс компаний, в которых я работал.
  • Поскольку результатом выполнения программ-метаданных шаблонов является обычный код, который затем компилируется компилятором, применяются все преимущества алгоритмов генерации кода (уменьшенная избыточность и т. Д.).
  • Конечно, поскольку они выполняются во время компиляции, эти алгоритмы не потребуют времени выполнения и, следовательно, будут работать быстрее. TMP в основном касается вычислений во время компиляции с несколькими, в основном небольшими, встроенными функциями, расположенными между ними, поэтому у компиляторов есть широкие возможности для оптимизации получающегося кода.

Конечно, есть и недостатки:

  • Сообщения об ошибках могут быть ужасными.
  • Там нет отладки.
  • Код часто трудно читать.

Как всегда, вам просто придется сопоставлять преимущества и недостатки в каждом случае.

Что касается более полезного примера : Как только вы освоите списки типов и оперируете с ними базовыми алгоритмами времени компиляции, вы можете понять следующее:

typedef 
    type_list_generator< signed char
                       , signed short
                       , signed int
                       , signed long
                       >::result_type
    signed_int_type_list;

typedef 
    type_list_find_if< signed_int_type_list
                     , exact_size_predicate<8>
                     >::result_type
    int8_t;

typedef 
    type_list_find_if< signed_int_type_list
                     , exact_size_predicate<16>
                     >::result_type
    int16_t;

typedef 
    type_list_find_if< signed_int_type_list
                     , exact_size_predicate<32>
                     >::result_type
    int32_t;

Это (немного упрощенный) реальный код, который я написал несколько недель назад. Он выберет подходящие типы из списка типов, заменив #ifdef оргий, распространенных в переносимом коде. Он не требует обслуживания, работает без адаптации на каждой платформе, на которую может понадобиться перенести код, и выдает ошибку компиляции, если текущая платформа не имеет нужного типа.

Другой пример:

template< typename TFunc, typename TFwdIter >
typename func_traits<TFunc>::result_t callFunc(TFunc f, TFwdIter begin, TFwdIter end);

Учитывая функцию f и последовательность строк, это будет анализировать сигнатуру функции, преобразовывать строки из последовательности в нужные типы и вызывать функцию с этими объектами. И это в основном ТМП внутри.

3 голосов
/ 04 августа 2009

TMP не обязательно означает более быстрый или более обслуживаемый код. Я использовал библиотеку boost spirit для реализации простого синтаксического анализатора выражений SQL, который создает структуру дерева оценки. Хотя время разработки сократилось, так как у меня было некоторое знакомство с TMP и lambda, кривая обучения представляет собой кирпичную стену для разработчиков "C с классами", и производительность не такая хорошая, как у традиционных LEX / YACC.

Я считаю шаблонное мета-программирование просто еще одним инструментом в моем поясе инструментов. Когда это работает для вас, используйте его, если нет, используйте другой инструмент.

3 голосов
/ 04 августа 2009

Вот один тривиальный пример, двоичный преобразователь констант из предыдущего вопроса здесь, на StackOverflow:

C ++ двоичная константа / литерал

template< unsigned long long N >
struct binary
{
  enum { value = (N % 10) + 2 * binary< N / 10 > :: value } ;
};
template<>
struct binary< 0 >
{
  enum { value = 0 } ;
};
3 голосов
/ 04 августа 2009

Скотт Мейерс (Scott Meyers) работает над применением ограничений кода с использованием TMP.

Это довольно хорошее чтение:
http://www.artima.com/cppsource/codefeatures.html

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

2 голосов
/ 04 августа 2009

значения 'static const' также работают. И указатели на член. И не забывайте мир типов (явных и выведенных) в качестве аргументов во время компиляции!

НО: где в реальном мире у нас есть постоянные литералы?

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

double innerLoop(const bool b, const vector<double> & v)
{
    // some logic involving b

    for (vector::const_iterator it = v.begin; it != v.end(); ++it)
    {
        // significant logic involving b
    }

    // more logic involving b
    return ....
}

Подробности не важны, но использование 'b' широко распространено в реализации.

Теперь, с помощью шаблонов, вы можете немного реорганизовать его:

template <bool b> double innerLoop_B(vector<double> v) { ... same as before ... }
double innerLoop(const bool b, const vector<double> & v)
{ return b ? innerLoop_templ_B<true>(v) : innerLoop_templ_B<false>(v) ); }

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

Рассмотрим возможности, когда 'b' основано на обнаружении процессора. Вы можете запустить по-разному оптимизированный набор кода в зависимости от обнаружения во время выполнения. Все из одного исходного кода, или вы можете специализировать некоторые функции для некоторых наборов значений.

В качестве конкретного примера я однажды увидел код, который должен был объединить некоторые целочисленные координаты. Система координат «a» была одним из двух разрешений (известных во время компиляции), а система координат «b» была одним из двух разных разрешений (также известных во время компиляции). Целевая система координат должна быть наименьшим общим кратным из двух исходных систем координат. Библиотека использовалась для вычисления LCM во время компиляции и создания кода для различных возможностей.

2 голосов
/ 04 августа 2009

TMP можно использовать от чего угодно, например от обеспечения корректности размеров (обеспечение того, что масса не может быть разделена на время, но расстояние может быть разделено на время и присвоение переменной скорости), для оптимизации операций матрицы путем удаления временных объектов и объединения циклов, когда много Матрицы участвуют.

...