Шаблоны выражений и C++11
Давайте рассмотрим одно конкретное преимущество шаблонов выражений. :ET можно использовать, чтобы избежать временных файлов с размером вектора -в памяти, которые возникают в перегруженных операторах, таких как:
template<typename T>
std::vector<T> operator+(const std::vector<T>& a, const std::vector<T>& b)
{
std::vector<T> tmp; // vector-sized temporary
for_each(...);
return tmp;
}
В C++11 оператор возврата этой функции применяет семантику перемещения. Нет копии вектора. Это победа.
Однако, если я посмотрю на простое выражение вроде
d = a + b + c;
Я вижу, что вышеуказанная функция вызывается дважды (для обоихoperator+)в то время как окончательное назначение может быть выполнено с помощью семантики перемещения.
Всего выполняется 2 петли. Означает, что я выложил временный и сразу же прочитал его обратно. Для больших векторов это выпадает из кеша. Это хуже, чем шаблоны выражений. Они могут сделать все это всего за 1 цикл. ET могут выполнять приведенный выше код, эквивалентный:
for(int i=0 ; i < vec_length ; ++i)
d[i] = a[i] + b[i] + c[i];
Мне было интересно, могут ли лямбды вместе с семантикой перемещения или любой другой новой функцией работать так же хорошо, как ET. есть идеи?
Изменить:
По сути, используя технику ET, компилятор строит дерево синтаксического анализа. которое напоминает алгебраическое выражение с его система типов. Это дерево состоит из внутренних узлов и конечных узлов. внутренние узлы представляют операции (сложения, умножения и т. д. )и конечные узлы представляют ссылки на объекты данных.
Я попытался представить себе весь вычислительный процесс в виде стековая машина :Взять операцию из стека операций и извлечь следующие аргументы из стека аргументов и оценить операцию. Поместите результат обратно в стек, ожидая операции.
Для представления этих двух разных объектов (стек операций и данные стек листьев )Я собрал вместе std::tupleдля операций и std::tupleдля данных уходит в std::pair<>. Изначально я использовал std:vector, но это привело к накладным расходам во время выполнения.
Весь процесс проходит в две фазы :Инициализация машины стека где инициализируются операции и стек аргументов. И этап оценки, который запускается путем назначения парных контейнеров к вектору.
Я создал класс Vec, который содержит частныйarray<int,5>(в полезной нагрузки )и имеет перегруженный оператор присваивания, который принимает «выражение».
Глобальный operator*перегружен для всех комбинаций взятия Vecи «выражение», чтобы обеспечить правильную обработку также в случае где у нас больше, чем просто a*b. (Заметьте, я переключился на это образовательный пример умножения -в основном, чтобы быстро определить imullв ассемблере.)
Что делается в первую очередь перед началом оценки, так это «извлечение» значения из задействованных Vecобъектов и инициализация аргумента куча. Это было необходимо для того, чтобы не лежали разного рода предметы. вокруг :индексируемых векторов и не -индексируемых результатов. Это то, что Extractorдля. Снова хорошая вещь :Используются шаблоны Variadic, которые в этом случае не приводит к -накладным расходам времени (все это делается в время компиляции ).
Все работает. Выражение хорошо оценивается (Я также добавлено дополнение, но оно здесь не указано, чтобы соответствовать коду ). Ниже вы можете увидеть вывод ассемблера. Просто необработанное вычисление,точно так же, как ты хотите, чтобы это было :En -наравне с техникой ET.
Результат. Новые языковые возможности C++11 предлагают вариативное шаблоны, которые (вместе с мета шаблоном -программированием )открывают область вычисления времени компиляции. Я показал здесь, как преимущества вариативные шаблоны могут использоваться для создания кода так же хорошо, как и с традиционная техника ЭТ.
#include<algorithm>
#include<iostream>
#include<vector>
#include<tuple>
#include<utility>
#include<array>
template<typename Target,typename Tuple, int N, bool end>
struct Extractor {
template < typename... Args >
static Target index(int i,const Tuple& t, Args &&... args)
{
return Extractor<Target, Tuple, N+1,
std::tuple_size<Tuple>::value == N+1>::
index(i, t, std::forward<Args>(args)..., std::get<N>(t).vec[i] );
}
};
template < typename Target, typename Tuple, int N >
struct Extractor<Target,Tuple,N,true>
{
template < typename... Args >
static Target index(int i,Tuple const& t,
Args &&... args) {
return Target(std::forward<Args>(args)...); }
};
template < typename... Vs >
std::tuple<typename std::remove_reference<Vs>::type::type_t...>
extract(int i, const std::tuple<Vs...>& tpl)
{
return Extractor<std::tuple<typename std::remove_reference<Vs>::type::type_t...>,
std::tuple<Vs...>, 0,
std::tuple_size<std::tuple<Vs...> >::value == 0>::index(i,tpl);
}
struct Vec {
std::array<int,5> vec;
typedef int type_t;
template<typename... OPs,typename... VALs>
Vec& operator=(const std::pair< std::tuple<VALs...>, std::tuple<OPs...> >& e) {
for( int i = 0 ; i < vec.size() ; ++i ) {
vec[i] = eval( extract(i,e.first), e.second );
}
}
};
template<int OpPos,int ValPos, bool end>
struct StackMachine {
template<typename... OPs,typename... VALs>
static void eval_pos( std::tuple<VALs...>& vals, const std::tuple<OPs...> & ops )
{
std::get<ValPos+1>( vals ) =
std::get<OpPos>(ops).apply( std::get<ValPos>( vals ),
std::get<ValPos+1>( vals ) );
StackMachine<OpPos+1,ValPos+1,sizeof...(OPs) == OpPos+1>::eval_pos(vals,ops);
}
};
template<int OpPos,int ValPos>
struct StackMachine<OpPos,ValPos,true> {
template<typename... OPs,typename... VALs>
static void eval_pos( std::tuple<VALs...>& vals,
const std::tuple<OPs...> & ops )
{}
};
template<typename... OPs,typename... VALs>
int eval( const std::tuple<VALs...>& vals, const std::tuple<OPs...> & ops )
{
StackMachine<0,0,false>::eval_pos(const_cast<std::tuple<VALs...>&>(vals),ops);
return std::get<sizeof...(OPs)>(vals);
}
struct OpMul {
static int apply(const int& lhs,const int& rhs) {
return lhs*rhs;
}
};
std::pair< std::tuple< const Vec&, const Vec& >, std::tuple<OpMul> >
operator*(const Vec& lhs,const Vec& rhs)
{
return std::make_pair( std::tuple< const Vec&, const Vec& >( lhs, rhs ),
std::tuple<OpMul>( OpMul() ) );
}
template<typename... OPs,typename... VALs>
std::pair< std::tuple< const Vec&, VALs... >, std::tuple<OPs...,OpMul> >
operator*(const Vec& lhs,const std::pair< std::tuple< VALs... >, std::tuple<OPs...> >& rhs)
{
return std::make_pair( std::tuple_cat( rhs.first, std::tuple< const Vec& >(lhs) ),
std::tuple_cat( rhs.second, std::tuple<OpMul>( OpMul() ) ) );
}
template<typename... OPs,typename... VALs>
std::pair< std::tuple< const Vec&, VALs... >, std::tuple<OPs...,OpMul> >
operator*(const std::pair< std::tuple< VALs... >, std::tuple<OPs...> >& lhs,
const Vec& rhs)
{
return std::make_pair( std::tuple_cat( lhs.first, std::tuple< const Vec& >(rhs) ),
std::tuple_cat( lhs.second, std::tuple<OpMul>( OpMul() ) ) );
}
int main()
{
Vec d,c,b,a;
for( int i = 0 ; i < d.vec.size() ; ++i ) {
a.vec[i] = 10+i;
b.vec[i] = 20+i;
c.vec[i] = 30+i;
d.vec[i] = 0;
}
d = a * b * c * a;
for( int i = 0 ; i < d.vec.size() ; ++i )
std::cout << d.vec[i] << std::endl;
}
Ассемблер создан с помощьюg++-4.6 -O3(Мне пришлось добавить некоторую зависимость во время выполнения в векторную инициализацию, чтобы компилятор не вычислял все это во время компиляции, и вы действительно видели инструкции imull.)
imull %esi, %edx
imull 32(%rsp), %edx
imull %edx, %esi
movl 68(%rsp), %edx
imull %ecx, %edx
movl %esi, (%rsp)
imull 36(%rsp), %edx
imull %ecx, %edx
movl 104(%rsp), %ecx
movl %edx, 4(%rsp)
movl 72(%rsp), %edx
imull %ecx, %edx
imull 40(%rsp), %edx
imull %ecx, %edx
movl 108(%rsp), %ecx
movl %edx, 8(%rsp)
movl 76(%rsp), %edx
imull %ecx, %edx
imull 44(%rsp), %edx
imull %ecx, %edx
movl 112(%rsp), %ecx
movl %edx, 12(%rsp)
movl 80(%rsp), %edx
imull %ecx, %edx
imull %eax, %edx
imull %ecx, %edx
movl %edx, 16(%rsp)