М.М. Краснов Метапрограммирование шаблонов C++ в задачах математической физики ИПМ им. М.В. Келдыша Москва 2017 К 78 Краснов Михаил Михайлович Метапрограммирование шаблонов C++ в задачах математической физики. – М.: ИПМ им. М.В. Келдыша, 2017. – 84 с. Рассматривается применение метапрограммирования шаблонов языка C++ для упрощения записи алгоритмов и для переноса части вычислений (различных целочисленных констант, например, биномиальных коэффициентов) на стадию компиляции, что теоретически позволяет ускорить выполнение программ и может быть весьма актуальным для численного решения задач математической физики. Метапрограммирование шаблонов позволяет автоматизировать некоторые сложные вычисления, такие, например, как раскрытие скобок в сложных выражениях и вычисление символьных производных от формул. Это помогает избавиться от трудно обнаруживаемых ошибок, возникающих при проведении подобных вычислений вручную (на бумаге) из-за невнимательности. Для математиков-программистов, занимающихся численным моделированием, и студентов вузов старших курсов, желающих глубже изучить возможности языка C++ для решения численных задач. Рецензенты: Лацис Алексей Оттович, д.ф.-м.н. Гаранжа Владимир Анатольевич, д.ф.-м.н., профессор РАН Издание осуществлено при поддержке Российского научного фонда, проект № 4 Электронная версия книги в формате PDF доступна по адресу © ИПМ им. М.В. Келдыша, 2017 Оглавление 1. Введение ........................................................................................ 5 2. Простейшие метафункции ........................................................... 8 2.1. Факториал ................................................................................ 9 2.2. Биномиальные коэффициенты .............................................. 9 2.3. Интеграл от одночлена ......................................................... 10 2.4. Вычисление типа значения итератора ................................ 10 2.5. Упражнения ........................................................................... 12 3. На стыке компиляции и исполнения......................................... 13 4. Более сложные примеры ............................................................ 14 4.1. Простые числа ....................................................................... 14 4.2. Ошибка при компиляции ..................................................... 16 4.3. Упражнения ........................................................................... 18 5. Цикл времени компиляции ........................................................ 18 5.1. Вычисление интеграла от бинома. ...................................... 18 5.2. Автоматическое раскрытие скобок. Матрица масс........... 21 6. Механизмы метапрограммирования шаблонов ....................... 30 6.1. Шаблонный полиморфизм и CRTP..................................... 30 6.2. Шаблоны выражений............................................................ 31 7. Размерные величины .................................................................. 35 8. Символьное дифференцирование ............................................. 38 8.1. Реализация выражений ......................................................... 40 8.2. Метод Ньютона ..................................................................... 48 8.3. Решение уравнения с одной переменной ........................... 48 8.4. Решение системы нелинейных уравнений ......................... 49 8.5. Решение задачи на нахождение экстремальной точки ..... 53 8.6. Численное моделирование ................................................... 55 8.7. Заключение ............................................................................ 56 9. Сеточно-операторный подход к программированию ............. 57 9.1. Введение ................................................................................ 57 9.2. Краткий обзор работ ............................................................. 58 9.3. Общее описание сеточно-операторного подхода .............. 60 9.3.1. 9.3.2. 9.3.3. 9.3.4. 9.3.5. 9.3.6. 9.3.7. Назначение .................................................................... 60 Типы обрабатываемых данных ................................... 62 Поддержка автоматического дифференцирования ... 63 Сеточная функция......................................................... 65 Вычисляемый объект.................................................... 66 Сеточный оператор ....................................................... 66 Сеточный вычислитель ................................................ 66 9.3.8. Исполнители .................................................................. 66 9.3.9. Индексаторы.................................................................. 67 . Общий вид запуска вычислений ................................. 69 . Примеры ........................................................................ 71 9.4. Принципы реализации .......................................................... 71 9.4.1. Общая информация ...................................................... 71 9.4.2. Шаблоны выражений ................................................... 71 9.4.3. Размерные величины .................................................... 72 9.4.4. Объекты-заместители ................................................... 72 9.4.5. Контекст исполнения ................................................... 74 9.4.6. Исполнение на CUDA .................................................. 76 9.4.7. Обмен данными между основным процессором и графическим ускорителем ............................................... 77 9.4.8. Использование пула нитей........................................... 78 9.5. Заключение ............................................................................ 79 10. Заключение .................................................................................. 80 11. Список литературы ..................................................................... 81 1. Введение Под метапрограммированием в языке C++ подразумеваются вычисления на стадии компиляции. Основным инструментом для этого являются шаблоны классов, называемые в этом случае (в случае их использования для вычислений на стадии компиляции) метафункциями. Параметрами таких метафункций служат параметры шаблонов классов, а значения метафункций (их может быть несколько) хранятся в статических (static) переменных или определениях типов (typedef-ах) класса. Язык C++ накладывает определённые ограничения на то, что может быть передано в качестве параметров шаблонов, и на типы статических переменных, значения которых могут быть вычислены на стадии компиляции. Это могут быть константы целочисленных типов и произвольные типы (как встроенные в язык простые типы, так и классы). В частности, нельзя передавать в качестве параметров шаблонов и вычислять на стадии компиляции константы вещественных типов, а также шаблоны классов. Если статическая переменная не целочисленного типа (например, double), то её значение может быть вычислено только на стадии исполнения и на стадии компиляции недоступно. Целочисленных типов в языке C++ довольно много. К ним относятся булевский тип (bool), символьные типы (char и unsigned char), а также знаковые и беззнаковые целые типы разных размеров (short, int, long, long long). Таким образом, метапрограммирование оперирует целочисленными константами и произвольными типами. В остальном метафункции не имеют никаких ограничений по возможностям для вычислений. Язык метапрограммирования (если его рассматривать как самостоятельную часть языка C++) является полным в том смысле, в каком полной является машина Тьюринга или лямбда-исчисление, т.е. на нём можно реализовать любую вычислимую функцию. Этот язык можно также рассмотреть с точки зрения функциональных языков программирования. Он является чисто функциональным языком, в нём отсутствует оператор присваивания значений переменным, переменные возможны только в качестве параметров метафункций. Как и в других чисто функциональных языках программирования (LISP, Haskell), единственно возможный способ организации циклов – это рекурсия. При подстановке значений параметров в шаблон класса получается класс. При этом для разных наборов значений параметров компилятор создаёт разные классы. Кроме того, для некоторых конкретных значений параметров можно создавать «особые» классы, имеющие другую реализацию, чем общий шаблон класса. Такие «особые» классы называются специализациями классов. Специализации классов могут быть частичными (когда конкретные значения указываются для части параметров) или полными (когда конкретные значения указы- ваются для всех параметров). Под полным шаблоном класса подразумевается совокупность основного определения шаблона класса и всех его специализаций. В частности, специализации классов используются для организации рекурсивных циклов. В рекурсивных функциях важно вовремя завершить рекурсию, в метапрограммировании для этого как раз и служат специализации классов для предельных значений параметров шаблонов. Шаблоны (классов и функций) – один из самых сложных элементов языка C++. Они появились в языке не сразу и первоначально были задуманы для того, чтобы можно было писать универсальные коллекции (которые могут хранить значения произвольных типов) и алгоритмы (например, алгоритм сортировки набора объектов произвольного типа). Метапрограммирование – другое, не менее важное применение шаблонов. Для полноценного освоения всех возможностей шаблонов автор отсылает любознательного читателя к описанию и многочисленным учебникам по языку C++ (например, [1-6]), а также хорошей книге Дэвида Абрахамса и Алексей Гуртового (см. [7]). Цель настоящей работы – показать на конкретных примерах, как метапрограммирование шаблонов может помочь вынести часть вычислений на стадию компиляции и, таким образом, ускорить (иногда существенно) выполнение программ, что бывает особенно важно при численном решении задач математической физики, которые могут считаться весьма долго (по многу часов и даже дней). Таким образом, данная работа рассчитана в первую очередь на математиков, решающих задачи численного моделирования и готовых к глубокому освоению возможностей языка C++ ради повышения эффективности выполнения своих программ. Кроме того, применения метапрограммирования шаблонов может упростить решение некоторых логически сложных задач и уменьшить вероятность ошибок в программах, связанных с невнимательностью. Такие ошибки часто бывает очень трудно найти. В качестве примеров таких задач можно привести автоматическое раскрытие скобок в сложных выражениях и символьное дифференцирование произвольных выражений. Одним из самых интересных применений метапрограммирования шаблонов (см. [8]) являются шаблоны выражений (expression templates, см. [9]). При этом средствами языка C++ реализуется некоторый (обычно несложный) проблемно-ориентированный язык (Domain Specific Language, DSL) для написания выражений той или иной природы. В качестве примера использования шаблонов выражений можно привести символьное дифференцирование. Существует весьма распространённое мнение, что объектноориентированное программирование не может быть эффективно применено в численном моделировании, в частности, из-за того, что «программы, написанные на голом C, считаются быстрее, чем написанные на C++, особенно с использованием объектно- ориентированного программирования». Автор не согласен с данным мнением и в данной работе, как и в других своих работах, пытается показать, что «правильное» использование возможностей языка C++ не только не замедляет работу программ, но позволяет уменьшить как время написания и отладки программ, так и время их исполнения за счёт выноса части вычислений на стадию компиляции. В этой жизни за всё приходится платить. Здесь платой является необходимость освоения этих самых новых возможностей языка C++, порой весьма непростых и непривычных. Но игра стоит свеч. Всякое знание расширяет возможности. Время, затраченное на освоение новых методов программирования, вернётся за счёт сокращения времени на написание и отладку программ. Кроме того, программы могут начать работать быстрее. Важным вопросом является переносимость программ. Все мы хотим, чтобы наши программы работали под любыми операционными системами, чтобы можно было, например, писать и отлаживать программу на небольших сетках на домашнем компьютере под Microsoft Windows и Microsoft Visual Studio, а затем запускать её на кластере, где стоит Linux и или gcc, или Intel C++. Наверное, в наше время уже не осталось систем, где нет компилятора с языка C++, причём с поддержкой шаблонов. Так что проблем с переносимостью при использовании метапрограммирования шаблонов быть не должно. Это относится, в частности, и к программированию для графических ускорителей CUDA: компилятор nvcc для CUDA также поддерживает шаблоны. Немного сложнее обстоит дело с версией языка C++. Язык постоянно развивается, особенно в последние годы. Выход новых версий языка планируется каждые 3 года. Первым таким существенным изменением после 1998 года (когда были введены шаблоны) и 2003 года (касалось в основном не языка, а библиотеки, в частности в библиотеку были введены элементы метапрограммирования) была версия языка от 2011 года (т.н. C++11). Позже вышел стандарт языка C++14, ожидаются новые стандарты C++17 и C++20. Все современные версии компиляторов (включая Microsoft C++, Intel C++, gcc и nvcc) поддерживают версию языка C++11 (и даже C++14), но, к сожалению, на многих кластерах компиляторы не обновляются (или обновляются редко), и, если программа использует возможности новых версий языка, проблема переносимости может возникнуть. С другой стороны, в новых стандартах языка появились как новые языковые конструкции, так и новые библиотечные функции (в том числе метафункции), облегчающие применение метапрограммирования шаблонов. Если Ваш компилятор не поддерживает стандарт языка C++11, то для восполнения недостающих конструкций можно использовать библиотеку boost (см. [10]). Boost многие годы является своеобразным «полигоном», на котором обкатываются новые возможности языка C++, прежде всего его стандартной библиотеки. Вошедшие в стандартную библиотеку языка C++ новых версий конструкции, как правило, перекочёвывают туда из библиотеки boost. Причём под влиянием библиотеки boost меняется не только стандартная библиотека, но и сам язык. В частности, в языке появилось переменное количество параметров шаблонов классов (variadic templates). Некоторые задачи с использованием возможностей языка C++11 можно решить более элегантно, чем с использованием библиотеки boost. В дальнейшем изложении основные конструкции будут показываться для языка C++11, а дополнительно будет показано, как это можно сделать с помощью библиотеки boost. Несколько слов по поводу графических ускорителей CUDA (см. [11, 12]). Как уже говорилось выше, компилятор для CUDA поддерживает шаблоны, и никаких проблем с использованием метапрограммирования нет. Более того, начиная с версии 7.0 компилятор nvcc поддерживает стандарт языка C++11. Но это не сильно помогает, так как для переноса программы на CUDA её всё равно нужно сильно переписать. Так можно ли написать программу один раз так, чтобы компилировать и запускать её можно было в том числе и на CUDA? Существует несколько решений этой задачи, один из них – стандарт OpenACC (см. [13]). Этот подход аналогичен OpenMP (см. [14]), т.е. решение заключается в автоматическом распараллеливании витков цикла. Применительно к OpenACC это означает, что исходные данные будут скопированы на CUDA, там параллельно обработаны, а затем результаты будут скопированы обратно в главный (host) процессор. Такой подход не представляется оптимальным. Автором предлагается альтернативный, т.н. «сеточно-операторный» подход к программированию, в котором при работе с CUDA данные изначально расположены в памяти CUDA, и копирование «туда-сюда» не требуется. Исходные данные при необходимости копируются в память CUDA в начале работы программы, а в конце работы копируются обратно в главный процессор. Сеточно-операторный подход к программированию также основывается на шаблонном метапрограммировании и будет изложен в данной работе. Далее в работе будут показаны многочисленные примеры использования метапрограммирования шаблонов, от простейших до достаточно сложных. Все примеры будут сопровождаться подробными пояснениями. 2. Простейшие метафункции В данном разделе мы покажем простейшие метафункции, которые в дальнейшем будут использоваться для более сложных вычислений. Как уже говорилось, метафункция с точки зрения языка C++ – это шаблон класса, параметры метафункции – это параметры этого шаблона класса, в качестве них могут передаваться или целочислен- ные константы, значения которых известны во время компиляции, или типы. 2.1. Факториал Пусть число N известно во время компиляции. Тогда значение N! во время компиляции можно вычислить с помощью следующей метафункции: template struct factorial { static const unsigned value = N * factorial::value; template<> struct factorial<0> { static const unsigned value = 1; // Пример обращения: const unsigned f5 = factorial<5>::value; // 120 Первый шаблон класса factorial является общим случаем и реализует рекурсивный вызов по известному правилу. Второй класс – это т.н. «полная специализация» шаблона класса и служит для завершения рекурсии. Напомним, чем полная специализация шаблона класса отличается от частичной. В полной специализации задаются конкретные значения всех параметров шаблона класса (в данном случае одного). Таким образом, полная специализация задаёт определение одного конкретного класса, при этом список параметров шаблона пуст (как в данном случае). При частичной специализации список параметров шаблона не пустой. Результат метафункции хранится в static const переменной value типа unsigned. Если число N окажется слишком большим, то результат в переменную типа unsigned не поместится. В этом случае компилятор выдаст ошибку. Но в реальности в численных методах слишком большие числа для факториала не встречаются, и таких проблем не возникает. 2.2. Биномиальные коэффициенты Пусть числа N и K известны во время компиляции. Тогда биномиальные коэффициенты в соответствие с известной формулой могут быть вычислены с помощью следующей метафункции: template struct C { static const unsigned value = factorial::value / factorial::value / factorial::value; // Пример обращения: const unsigned i = C<5, 2>::value; // 10