Шаблоны выражений

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

Шаблоны выражений были изобретены независимо Тоддом Вельдхейзеном и Дэвидом Вандевурдом; имя им дал Вельдхейзен. Это популярный метод реализации программного обеспечения линейной алгебры .

Мотивация и пример

Рассмотрим библиотеку, представляющую векторы и операции над ними. сложение двух векторов u и v Одной из распространенных математических операций является поэлементное для получения нового вектора. Очевидная реализация этой операции на C++ будет перегруженной operator+ который возвращает новый векторный объект:

/// @brief class representing a mathematical 3D vector
class Vec : public std::array<double, 3> {
  public:
    using std::array<double, 3>::array; 
    // inherit constructor (C++11)
    // see https://en.cppreference.com/w/cpp/language/using_declaration
};


/// @brief sum 'u' and 'v' into a new instance of Vec
Vec operator+(Vec const &u, Vec const &v) {
    Vec sum;
    for (size_t i = 0; i < u.size(); i++) {
        sum[i] = u[i] + v[i];
    }
    return sum;
}

Пользователи этого класса теперь могут писать Vec x = a + b; где a и b оба являются экземплярами Vec.

Проблема с этим подходом заключается в том, что более сложные выражения, такие как Vec x = a + b + c реализуются неэффективно. Реализация сначала создает временный Vec держать a + b, затем производит еще один Vec с элементами c добавлено. Даже при оптимизации возвращаемого значения это приведет к выделению памяти как минимум дважды и потребует двух циклов.

Отложенная оценка решает эту проблему и может быть реализована на C++, позволяя operator+ вернуть объект вспомогательного типа, скажем VecSum, который представляет собой неоцененную сумму двух Vecs, или вектор с VecSumи т. д. Выражения большего размера эффективно строят деревья выражений , которые оцениваются только тогда, когда присваиваются фактическому значению. Vec переменная. Но для проведения оценки требуется обход таких деревьев, что само по себе является дорогостоящим.

Шаблоны выражений реализуют отложенную оценку с использованием деревьев выражений, которые существуют только во время компиляции. Каждое задание на Vec, такой как Vec x = a + b + c, генерирует новый Vec конструктор, если это необходимо для создания экземпляра шаблона. Этот конструктор работает на трех Vec; он выделяет необходимую память и затем выполняет вычисления. Таким образом, выполняется только одно выделение памяти.

Пример реализации шаблонов выражений:

Пример реализации шаблонов выражений выглядит следующим образом. Базовый класс VecExpression представляет любое векторное выражение. Он создан на основе фактического типа выражения. E будет реализован в соответствии с любопытным повторяющимся шаблоном шаблона . Существование базового класса типа VecExpression не является строго необходимым для работы шаблонов выражений. Он будет просто служить типом аргумента функции, чтобы отличать выражения от других типов (обратите внимание на определение Vec конструктор и operator+ ниже).

template <typename E>
class VecExpression {
  public:
    static constexpr bool is_leaf = false;

    double operator[](size_t i) const {
        // Delegation to the actual expression type. This avoids dynamic polymorphism (a.k.a. virtual functions in C++)
        return static_cast<E const&>(*this)[i];
    }
    size_t size() const { return static_cast<E const&>(*this).size(); }
};

Логическое значение is_leaf есть здесь, чтобы отметить VecExpressions, которые являются «листами», т. е. фактически содержат данные. Vec Класс — это лист, который хранит координаты полностью вычисленного векторного выражения и становится подклассом VecExpression.

class Vec : public VecExpression<Vec> {
    std::array<double, 3> elems;

  public:
    static constexpr bool is_leaf = true;

    decltype(auto) operator[](size_t i) const { return elems[i]; }
    decltype(auto) &operator[](size_t i)      { return elems[i]; }
    size_t size()               const { return elems.size(); }

    // construct Vec using initializer list 
    Vec(std::initializer_list<double> init) {
        std::copy(init.begin(), init.end(), elems.begin());
    }

    // A Vec can be constructed from any VecExpression, forcing its evaluation.
    template <typename 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, copy otherwise
  typename std::conditional<E1::is_leaf, const E1&, const E1>::type _u;
  typename std::conditional<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) operator[](size_t i) const { return _u[i] + _v[i]; }
    size_t size()               const { return _v.size(); }
};
  
template <typename E1, typename E2>
VecSum<E1, E2>
operator+(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 имеет тип

VecSum<VecSum<Vec, Vec>, Vec>

так Vec x = a + b + c вызывает шаблон Vec конструктор Vec(VecExpression<E> const& expr) с его аргументом шаблона E будучи этим типом (что означает VecSum<VecSum<Vec, Vec>, Vec>). Внутри этого конструктора тело цикла

elems[i] = expr[i];

эффективно расширяется (следуя рекурсивным определениям operator+ и operator[]по этому типу)

elems[i] = a.elems[i] + b.elems[i] + c.elems[i];

без временного Vec необходимые объекты и только один проход через каждый блок памяти.

Основное использование:

int main() {
    Vec v0 = {23.4,  12.5,  144.56};
    Vec v1 = {67.12, 34.8,  90.34};
    Vec v2 = {34.90, 111.9, 45.12};
    
    // Following assignment will call the ctor of Vec which accept type of 
    // `VecExpression<E> const&`. Then expand the loop body to 
    // 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;

    // To avoid creating any extra storage, other than v0, v1, v2
    // one can do the following (Tested with C++11 on GCC 5.3.0)
    auto sum = v0 + v1 + v2;
    for (size_t i = 0; i < sum.size(); ++i)
        std::cout << sum[i] << std::endl;
    // Observe that in this case typeid(sum) will be VecSum<VecSum<Vec, Vec>, Vec>
    // and this chaining of operations can go on.
}

Приложения

Шаблоны выражений оказались особенно полезными авторами библиотек для линейной алгебры, то есть для работы с векторами и матрицами чисел. Среди библиотек, использующих шаблон выражений, — Dlib , Armadillo , Blaze , Блиц++ , Увеличьте uBLAS, Собственный , БУМ, Стэн Математическая библиотека , и кстензор. Шаблоны выражений также могут ускорить автоматического дифференцирования на C++. реализацию как показано в библиотеке Adept .

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

См. также

• Оптимизирующий компилятор – компилятор, оптимизирующий сгенерированный код.