Введение в метапрограммирование шаблона на C++
ОГЛАВЛЕНИЕ
Данная статья объясняет, как использовать классы-шаблоны C++ для выработки кода, генерируемого во время компиляции.
Предыстория
Недавно создавалась программа, использовавшая большую таблицу поиска для производства ряда вычислений. Содержимое таблицы зависело от большого числа параметров, которые пришлось настраивать для достижения оптимальной работы кода. И всегда при изменении одного параметра приходилось заново вычислять всю таблицу...
Была написана функция, выгружавшая содержимое таблицы в стандартный вывод. Таким образом программу можно было компилировать с новым набором параметров, вырезать и вставлять таблицу с экрана в исходный код и, наконец, перекомпилировать весь проект. Первые 20 раз делать это было нормально. Затем выяснилось, что должен быть способ лучше. Он был: следовало взяться за метопрограммирование шаблона.
Что такое метапрограммирование шаблона (TMP)
Метапрограммирование шаблона – техника абстрактного программирования, использующая очень раннее связывание. Компилятор действует как интерпретатор или "виртуальная машина", генерирующая команды, образующие конечную программу. Метапрограммирование применяется для статической конфигурации, адаптивных программ, оптимизации и многого другого.
Разные виды меташаблонов
Различают два вида меташаблонов – те, которые вычисляют постоянное значение, и те, которые вырабатывают код. Разница в том, что первый вид никогда не должен вырабатывать команды, исполняемые во время выполнения.
Шаблоны, вычисляющие значение
Допустим, надо вычислить количество битов, установленных в байте. Функция, делающая это во время выполнения, может выглядеть так:
int bits_set(unsigned char byte)
{int count = 0;
for (int i = 0; i < 8; i++)
if ( (0x1L << i) & byte )
count++;
return count;
}
Если байт известен во время компиляции, компилятор может сделать это с помощью TMP:
template< unsigned char byte > class BITS_SET
{
public:
enum {
B0 = (byte & 0x01) ? 1:0,
B1 = (byte & 0x02) ? 1:0,
B2 = (byte & 0x04) ? 1:0,
B3 = (byte & 0x08) ? 1:0,
B4 = (byte & 0x10) ? 1:0,
B5 = (byte & 0x20) ? 1:0,
B6 = (byte & 0x40) ? 1:0,
B7 = (byte & 0x80) ? 1:0
};
public:
enum{RESULT = B0+B1+B2+B3+B4+B5+B6+B7};
};
enum используется для временных переменных и для результата, так как они проще в применении, и перечислители имеют тип const int. Другой способ – использовать static const int:s в классе в качестве альтернативы.
Теперь можно использовать BITS_SET<15>::RESULT и получить константу 4 в коде. В этом случае компилятор вычисляет строку enum{RESULT = B0+B1+B2+B3+B4+B5+B6+B7}; в enum{RESULT = 1+1+1+1+0+0+0+0}; и, наконец, в enum{RESULT = 4};.
Кроме того, можно рассчитать значение с помощью петли. С TMP мы полагаемся на рекурсию в определении шаблона. Следующий код представляет собой факториальной калькулятор во время компиляции
template< int i >
class FACTOR{
public:
enum {RESULT = i * FACTOR<I-1>::RESULT};
};
class FACTOR< 1 >{
public:
enum {RESULT = 1};
};
Например, если написать следующее:
int j = FACTOR< 5 >::RESULT;
где-то в коде компилятор сгенерирует нечто вроде следующий строки кода на ассемблере:
; int j = FACTOR< 5 >::RESULT;
mov DWORD PTR _j$[ebp], 120 ; 00000078H – постоянное значение!
Как это работает? Когда создается экземпляр FACTOR<5>, определение этого класса зависит от FACTOR<4>, которое в свою очередь зависит от FACTOR<3> и так далее. Компилятор должен создать все эти классы, пока не достигнута специализация шаблона FACTOR<1>. Это значит, что компилятор делает всю рекурсию, тогда как конечная программа лишь содержит константу.
Шаблоны, разворачивающие циклы/специализирующие функции
Шаблонные метапрограммы могут генерировать полезный код при интерпретации компилятором, например, сильно встроенный алгоритм, циклы которого разворачиваются. Результатом обычно является большой прирост скорости приложения.
Например, посмотрим на следующий код, вычисляющий сумму чисел 1..1000:
int sum = 0;
for (int i = 1 ; i <= 1000; i++)
sum += i;
В действительности выполняется 2000 сложений, а не 1000 (так как i увеличивается на one для каждого цикла). При сложении производится тысяча пробных операций над переменной i. Другой способ – написать код следующим образом:
int sum = 0;
sum += 1;
sum += 2;
...
sum += 1000;
Так шаблонная метапрограмма разворачивает цикл. Теперь производится ровно тысяча сложений, но этот метод также имеет выигрыш. Увеличивается размер кода, то есть теоретически производительность может пострадать из-за роста числа ошибок отсутствия страницы. Однако на практике код часто вызывается много раз и уже загружен в кэш.
Разворачивание цикла
Разворачивание цикла легко определяется с помощью рекурсивных шаблонов, подобно вычислению значения:
template< int i >
class LOOP{
public:
static inline void EXEC(){
cout << "A-" << i << " ";
LOOP< i-1 >::EXEC();
cout << "B-" << i << " ";
}
};
class LOOP< 0 >{
public:
static inline void EXEC(){
cout << "A-" << i;
cout << "\n";
cout << "B-" << i;
}
};
Вывод LOOP< 8 >::EXEC() показан ниже:
A-8 A-7 A-6 A-5 A-4 A-3 A-2 A-1 A-0
B-0 B-1 B-2 B-3 B-4 B-5 B-6 B-7 B-8
В итоговом двоичном коде нет цикла. Цикл разворачивается, порождая следующий код:
cout << "A-" << 8 << " ";
cout << "A-" << 7 << " ";
...
cout << "A-" << 0;
cout << "\n";
cout << "B-" << 0;
...
cout << "B-" << 7 << " ";
cout << "B-" << 8 << " ";
В классе LOOP< 0 > есть несвязанный, но интересный момент. Посмотрите, как LOOP< 0 >::EXEC() использует i. Этот идентификатор был объявлен в шаблоне LOOP< int i >, но все еще доступен из "специального случая" LOOP< 0 >. Неясно, является ли это стандартным поведением C++.
Кроме циклов, могут строиться другие операторы:
Оператор IF
template< bool Condition >
class IF {
public:
static inline void EXEC(){
cout << "Statement is true";
}
};
class IF< false > {
public:
static inline void EXEC(){
cout << "Statement is false";
}
};
Оператор SWITCH
template< int _case >
class SWITCH {
public:
static inline void EXEC(){
cout << " SWITCH - default ";
}
};
class SWITCH< 1 > {
public:
static inline void EXEC(){
cout << " SWITCH - 1 ";
}
};
class SWITCH< 2 > {
public:
static inline void EXEC(){
cout << " SWITCH - 2 ";
}
};
...
Пример использования двух классов:
SWITCH< 2 > myTwoSwitch; // хранить для отложенного выполнения
myTwoSwitch.EXEC();
IF< false >::EXEC();
myTwoSwitch.EXEC();
Вывод будет: " SWITCH - 2 Statement is false SWITCH - 2 "
Использование мета-меташаблонов
Можно определить обобщённый шаблон для особого вида операции, такого как оператор if или for. Это называется мета-меташаблон, так как операция определяется в классе за пределами самого шаблона. Даже если он полезен, он сильно затрудняет понимание кода в сложных случаях. И компиляторы смогут полностью использовать такие конструкции лишь через несколько лет. Пока лучше использовать специализированные шаблоны, но для простых случаев мета-меташаблоны полезны. Простой пример данной конструкции – оператор if - дан ниже:
template< bool Condition, class THEN, class ELSE > struct IF
{
template< bool Condition > struct selector
{typedef THEN SELECT_CLASS;};
struct selector< false >
{typedef ELSE SELECT_CLASS;};
typedef selector< Condition >::SELECT_CLASS RESULT;
};
Пример применения:
struct THEN
{
static int func()
{cout << "Inside THEN";
return 42;
}
};
struct ELSE
{
static int func()
{cout << "Inside ELSE";
return 0;
}
};
int main(int argc, char* argv[])
{
int result = IF< 4 == sizeof(int), THEN, ELSE >::RESULT::func();
cout << " - returning: " << result;
}
В 32-битной архитектуре пример распечатает "Inside THEN - returning: 42" в стандартный вывод. Имейте в виду, что если бы func() не была определена в ELSE, это было бы простое утверждение времени компиляции, прерывающее компиляцию на 4 != sizeof(int).
Реальный пример
В качестве примера включен маленький класс, производящий общие вычисления CRC (циклические избыточные коды – набор простых хэш-алгоритмов). Класс использует набор параметров, определенных #define:d вверху заголовка. CRC выбраны для данной статьи, потому что алгоритмы CRC обычно используют таблицу поиска на базе набора параметров, делая пример похожим на исходную задачу.
Класс генерирует таблицу поиска с 256 записями во время компиляции. Реализация весьма проста, и комментариев в исходниках достаточно для объяснения использования класса. Иногда использовались макросы, где TMP было возможным решением. Причина в читабельности, являющейся важным фактором при выборе используемой техники.
Более подробное объяснение алгоритмов CRC ищите в книге Росса Н. Вильямса "Руководство по алгоритмам обнаружения ошибок CRC". В пример включена дословная копия текста.
При компиляции учтите, что исходники используют много динамической памяти компьютера. Предел распределения памяти увеличивается опцией компилятора '/Zm400'. Недостаток TMP в том, что оно доводит компьютер до предела.
Соглашения по программированию
Компилятор терпеть не может, когда его неправильно используют, как описано выше. И он будет сопротивляться. Предупреждения и ошибки будут варьироваться от загадочных до C1001 – внутренняя ошибка компилятора. Меташаблонную программу нельзя отлаживать как исполняемую программу.
Поэтому использовать четкие соглашения по программированию с TMP важней, чем с другими техниками программирования. Ниже даны полезные правила.
Общие советы
Так как шаблонные метапрограммы отчасти похожи на макросы, имена классов TMP пишутся заглавными буквами. Также задавайте максимально осмысленные имена. Основная причина для этого в том, что открытые переменные/функции обычно имеют неосмысленные имена (смотрите ниже). Класс TMP определяет операцию, а не функции-члены или переменные члены.
Ограничивайте класс TMP до одной операции. Шаблонное метапрограммирование достаточно сложно без попыток обобщить класс, чтобы он поддерживал несколько операций. Это приведет лишь к раздуванию кода.
Имена переменных/функций
В классе TMP определяется одна из двух возможных открытых операций:
• RESULT для шаблонов, вычисляющих значение
• EXEC() для разворачивания цикла/упрощения функции.
Обычно одна функция или одна переменная-член – единственный элемент, который шаблонная метапрограмма должна предоставлять программисту. Давайте типу операции одно имя для всех возможных классов. Другое преимущество в том, что можно посмотреть на шаблонный класс и сразу увидеть, является ли он шаблонной метапрограммой или простым шаблонным классом.
Надо ли использовать TMP в программе?
Шаблонное метапрограммирование – прекрасная техника при верном применении. В то же время оно может привести к раздуванию кода и падению производительности. Ниже даны проверенные правила, когда применять TMP.
Используйте TMP, когда:
• Макроса недостаточно. Нужно нечто более сложное, чем макрос, что должно разворачиваться перед компиляцией.
• Используется рекурсивная функция с заранее заданным числом циклов. При этом издержек вызовов функций и установки переменных стека можно избежать, и время выполнения значительно уменьшается.
• Используются циклы, которые можно развернуть во время компиляции. К примеру, алгоритмы хэша, такие как MD5 и SHA1, содержат строго определенные циклы обработки блоков, которые можно развернуть с помощью TMP.
• При вычислении постоянных значений. Если в программе есть константы, зависящие от других констант, для них подойдет TMP.
• Когда программа должны переноситься на другие платформы. В этом случае TMP может быть альтернативой макросам.
Не используйте TMP, когда:
• Когда макрос подходит. В большинстве случаев макроса достаточно. Макрос проще понять, чем TMP.
• Нужна маленькая исполняемая программа. Шаблоны вообще, а особенно TMP, увеличивают размер кода.
• Программа уже долго компилируется. TMP существенно увеличивает время компиляции.
• Жесткие сроки. Как сказано выше, компилятор недружелюбен при работе с шаблонными метапрограммами. Если вносимые изменения не являются простыми, вы избежите нескольких часов мучений.