Шаблоны выражений
Шаблоны выражений — это C++ метод метапрограммирования шаблонов , который создает структуры, представляющие вычисления во время компиляции, где выражения оцениваются только по мере необходимости для создания эффективного кода для всего вычисления. [1] Таким образом, шаблоны выражений позволяют программистам обойти обычный порядок вычислений языка C++ и добиться таких оптимизаций, как слияние циклов .
Шаблоны выражений были изобретены независимо Тоддом Вельдхейзеном и Дэвидом Вандевурдом; [2] [3] имя им дал Вельдхейзен. [3] Это популярный метод реализации программного обеспечения линейной алгебры . [1]
Мотивация и пример
[ редактировать ]Рассмотрим библиотеку, представляющую векторы и операции над ними. сложение двух векторов u и v Одной из распространенных математических операций является поэлементное для получения нового вектора. Очевидная реализация этой операции на C++ будет перегруженной operator+ который возвращает новый векторный объект:
трехмерных векторов /// Класс @brief, представляющий математический класс Vec : public std :: array < double , 3 > { public : using std :: array < double , 3 >:: array ; // наследуемый конструктор (C++11) // см. https://en.cppreference.com/w/cpp/language/using_declaration }; /// @brief суммируем 'u' и 'v' в новый экземпляр Vec Vec оператора + ( Vec const & u , Vec const & v ) { Vec sum ; for ( size_t я = 0 ; я < u . size (); я ++ ) { сумма [ я ] знак равно ты [ я ] + v [ я ]; } вернуть сумму ; } Пользователи этого класса теперь могут писать Vec x = a + b; где a и b оба являются экземплярами Vec.
Проблема с этим подходом заключается в том, что более сложные выражения, такие как Vec x = a + b + c реализуются неэффективно. Реализация сначала создает временный Vec держать a + b, затем производит еще один Vec с элементами c добавлено. Даже при оптимизации возвращаемого значения это приведет к выделению памяти как минимум дважды и потребует двух циклов.
Отложенная оценка решает эту проблему и может быть реализована на C++, позволяя operator+ вернуть объект вспомогательного типа, скажем VecSum, который представляет собой неоцененную сумму двух Vecs, или вектор с VecSumи т. д. Выражения большего размера эффективно строят деревья выражений , которые оцениваются только при присвоении фактическому значению. Vec переменная. Но для проведения оценки требуется обход таких деревьев, что само по себе является дорогостоящим. [4]
Шаблоны выражений реализуют отложенную оценку с использованием деревьев выражений, которые существуют только во время компиляции. Каждое задание на Vec, такой как Vec x = a + b + c, генерирует новый Vec конструктор, если это необходимо для создания экземпляра шаблона. Этот конструктор работает на трех Vec; он выделяет необходимую память и затем выполняет вычисления. Таким образом, выполняется только одно выделение памяти.
Пример реализации шаблонов выражений:
Пример реализации шаблонов выражений выглядит следующим образом. Базовый класс VecExpression представляет любое векторное выражение. Он создан на основе фактического типа выражения. E будет реализован в соответствии с любопытным повторяющимся шаблоном шаблона . Существование базового класса типа VecExpression не является строго необходимым для работы шаблонов выражений. Он будет просто служить типом аргумента функции, чтобы отличать выражения от других типов (обратите внимание на определение Vec конструктор и operator+ ниже).
шаблон < имя типа E > class VecExpression { public : static constexpr bool is_leaf = false ; double оператор []( size_t i ) const { // Делегирование фактическому типу выражения. Это позволяет избежать динамического полиморфизма (он же виртуальные функции в C++) return static_cast < E const &> ( * this )[ i ]; } size_t size () const { return static_cast < E const &> ( * this ). размер (); } }; логическое значение is_leaf есть здесь, чтобы отметить VecExpressions, которые являются «листами», то есть фактически содержат данные. Vec Класс — это лист, который хранит координаты полностью вычисленного векторного выражения и становится подклассом VecExpression.
класс Vec : public VecExpression <Vec> { std :: array < double , 3 > elems ; public : static constexpr bool is_leaf = true ; decltype ( авто ) оператор []( size_t i ) const { return elems [ i ]; } decltype ( авто ) и оператор []( size_t i ) { return elems [ i ]; } size_t size () const { return elems . размер (); } используя список инициализаторов Vec ( std :: initializer_list <double> :: copy init ) { std ) ( Vec , init.begin ( // создаем ), ( init.end , ) ( elems.begin ) ; } // Vec может быть создан из любого VecExpression, принудительно вычислив его. шаблон < имя_типа E > Vec ( VecExpression < E > const & expr ) { for ( size_t i = 0 ; i != expr . size (); ++ i ) { elems [ i ] = expr [ i ]; } } }; Сумма двух Vecs представлен новым типом, VecSum, шаблон которого основан на типах левой и правой частей суммы, так что его можно применять к произвольным парам Vec выражения. Перегруженный operator+ служит синтаксическим сахаром для VecSum конструктор. В данном случае вмешивается тонкость: чтобы при суммировании двух VecExpressionс, VecSum необходимо сохранить константную ссылку на каждый VecExpression если это лист, в противном случае это временный объект, который необходимо скопировать для правильного сохранения.
template < typename E1 , typename E2 > class VecSum : public VecExpression < VecSum < E1 , E2 > > { // cref if Leaf, иначе копируем typename std :: Conditional < E1 :: is_leaf , const E1 & , const E1 >:: введите _у ; имя типа std :: условное < E2 :: is_leaf , const E2 & , const E2 >:: type _v ; public : static constexpr bool is_leaf = false ; VecSum ( E1 const & u , E2 const & v ) : _u ( u ), _v ( v ) { Assert ( u . size () == v . size ()); } decltype ( auto ) оператор []( size_t i ) const { return _u [ i ] + _v [ i ]; } size_t size () const { return _v . размер (); } }; template < имя типа E1 , имя типа E2 > VecSum < E1 , E2 > оператор + ( VecExpression < E1 > const & u , VecExpression < E2 > const & v ) { return VecSum < E1 , E2 > ( * static_cast < const E1 *> ( & u ), * static_cast < const E2 *> ( & v )); } С учетом приведенных выше определений выражение a + b + c имеет тип
ItemSum < ItemSum < Предмет , Предмет > , Предмет > так Vec x = a + b + c вызывает шаблон Vec конструктор Vec(VecExpression<E> const& expr) с его аргументом шаблона E будучи этим типом (что означает VecSum<VecSum<Vec, Vec>, Vec>). Внутри этого конструктора тело цикла
элементы [ я ] = выражение [ я ]; эффективно расширяется (следуя рекурсивным определениям operator+ и operator[]по этому типу)
элементы [ я ] знак равно а . элементы [ я ] + б . элементы [ я ] + с . элементы [ я ]; без временного Vec необходимые объекты и только один проход через каждый блок памяти.
Основное использование:
int main () { Vec v0 = { 23,4 , 12,5 , 144,56 }; Век v1 = { 67,12 , 34,8 , 90,34 }; Век v2 = { 34,90 , 111,9 , 45,12 }; // Следующее присваивание вызовет вектор Vec, который принимает тип // `VecExpression<E> const&`. Затем расширьте тело цикла до // a.elems[i] + b.elems[i] + c.elems[i] Vec sum_of_vec_type = v0 + v1 + v2 ; for ( size_t i = 0 ; i < sum_of_vec_type . size (); ++ i ) std :: cout << sum_of_vec_type [ i ] << std :: endl ; // Чтобы избежать создания дополнительного хранилища, кроме v0, v1, v2 // можно сделать следующее (проверено на C++11 в GCC 5.3.0) auto sum = v0 + v1 + v2 ; for ( size_t i = 0 ; i < sum . size (); ++ i ) std :: cout << sum [ i ] << std :: endl ; // Обратите внимание, что в этом случае typeid(sum) будет VecSum<VecSum<Vec, Vec>, Vec> // и эта цепочка операций может продолжаться. } Приложения
[ редактировать ]Шаблоны выражений оказались особенно полезными авторами библиотек для линейной алгебры, то есть для работы с векторами и матрицами чисел. Среди библиотек, использующих шаблон выражений, — Dlib , Armadillo , Blaze , [5] Блиц++ , [6] Увеличьте uBLAS, [7] Собственный , [8] ПУМА, [9] Стэн Математическая библиотека , [10] и кстензор. [11] Шаблоны выражений также могут ускорить автоматического дифференцирования на C++. реализацию [12] как показано в библиотеке Adept .
Помимо векторной математики, платформа синтаксического анализатора Spirit использует шаблоны выражений для представления формальных грамматик и их компиляции в анализаторы.
См. также
[ редактировать ]- Оптимизирующий компилятор – компилятор, оптимизирующий сгенерированный код.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Мацузаки, Киминори; Эмото, Кенто (2009). Реализация параллельных скелетов, оснащенных слиянием, с помощью шаблонов выражений . Учеб. Международный симп. по реализации и применению функциональных языков. стр. 72–89.
- ^ Вандевурде, Дэвид; Джосуттис, Николай (2002). Шаблоны C++: Полное руководство . Эддисон Уэсли . ISBN 0-201-73484-2 .
- ^ Перейти обратно: а б Вельдхейзен, Тодд (1995). «Шаблоны выражений» . Отчет С++ . 7 (5): 26–31. Архивировано из оригинала 10 февраля 2005 года.
- ^ Абрахамс, Дэвид; Гуртовой, Алексей (2004). Метапрограммирование шаблонов C++: концепции, инструменты и методы из Boost и за его пределами . Пирсон Образование. ISBN 9780321623911 .
- ^ Битбакет
- ^ «Руководство пользователя Blitz++» (PDF) . Проверено 12 декабря 2015 г.
- ^ «Библиотека базовой линейной алгебры Boost» . Проверено 25 октября 2015 г.
- ^ Геннебо, Гаэль (2013). Eigen: библиотека линейной алгебры C++ (PDF) . Еврографика/CGLibs.
- ^ Вельдхейзен, Тодд (2000). Как раз тогда, когда вы думали, что ваш маленький язык безопасен: «Шаблоны выражений» на Java . Международный симп. Генеративная и компонентная разработка программного обеспечения. CiteSeerX 10.1.1.22.6984 .
- ^ «Стэн документация» . Проверено 27 апреля 2016 г.
- ^ «Многомерные массивы с трансляцией и ленивыми вычислениями» . Проверено 18 сентября 2017 г.
- ^ Хоган, Робин Дж. (2014). «Быстрое автоматическое дифференцирование в обратном режиме с использованием шаблонов выражений на C++» (PDF) . АКМ Транс. Математика. Программное обеспечение . 40 (4): 26:1–26:16. дои : 10.1145/2560359 . S2CID 9047237 .