Введение в метапрограммирование шаблона на 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).