Посмотрим на одно из особых преимуществ шаблонов выражений: 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;
}
В С++ 11 оператор return этой функции применяет семантику перемещения. Нет копии вектора. Это победа.
Однако, если я посмотрю на простое выражение типа
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. Любые мысли?
Edit:
В принципе, используя технику ET, компилятор строит дерево разбора что напоминает алгебраическое выражение с его типа. Это дерево состоит из внутренних узлов и листовых узлов. внутренние узлы представляют операции (сложение, умножение и т.д.) и узлы листа представляют собой ссылки на объекты данных.
Я попытался представить весь процесс вычисления в форме стек: выполните операцию из операционного стека и потяните следующие аргументы из стека аргументов и оценить операцию. Верните результат в стек, ожидающий операции.
Чтобы представить эти два разных объекта (стек операций и данные
лист стека) Я объединил a std::tuple
для операций и
std::tuple
для данных выходит в std::pair<>
. Первоначально я
использовал a std:vector
, но это привело к превышениям времени выполнения.
Весь процесс проходит в два этапа: инициализация статической машины где инициализируются стеки операций и аргументов. И этап оценки, который инициируется назначением сопряженных контейнеров к вектору.
Я создал класс Vec
, который содержит закрытый array<int,5>
(
полезная нагрузка) и который имеет перегруженный оператор присваивания, который
принимает "выражение".
Глобальная operator*
перегружена для всех комбинаций взятия
Vec
и "expression", чтобы обеспечить правильную обработку также в случае
где у нас больше, чем просто a*b
. (Обратите внимание, я переключился на это
образовательный пример умножения - в основном, чтобы быстро определить
imull
в ассемблере.)
Что делается сначала перед началом оценки, так это "извлечение"
значения из задействованных объектов Vec
и инициализации аргумента
стек. Это было необходимо, чтобы не иметь разных видов предметов, лежащих
вокруг: индексируемые векторы и неиндексируемые результаты. Это то, что
Extractor
для. Хорошая вещь: используются шаблоны Variadic
в этом случае не будет накладных расходов во время выполнения (все это делается при
время компиляции).
Все работает. Выражение хорошо оценено (я также добавлено дополнение, но это осталось здесь, чтобы соответствовать коду). Ниже вы можете увидеть выход ассемблера. Просто необработанные вычисления, точно так же, как вы хотите, чтобы это было: En-par с техникой ET.
Upshot. Новые языковые возможности С++ 11 предлагают вариационный шаблоны, которые (наряду с мета-программированием шаблонов) открывают область вычисления времени компиляции. Я показал здесь, как преимущества вариационные шаблоны могут использоваться для создания кода так же хорошо, как с традиционная техника ET.
#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)