让我们看的表达模板之一特别的益处:ET的可用于避免在存储器矢量大小的临时对象中出现的过载操作符,如:表达模板和C++ 11
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个循环。意思是我暂时放了一张,然后马上阅读。对于大型媒体而言,这会脱离缓存。这比表达式模板更糟糕。他们可以在一个循环中完成整个事情。专家组可以执行上述的等效代码:
for(int i=0 ; i < vec_length ; ++i)
d[i] = a[i] + b[i] + c[i];
我想用移动语义或任何其他新的功能lambda表达式一起是否能够像外星人一样好。有什么想法吗?
编辑:
基本上,使用ET技术编译器生成解析树 类似于代数表达式与它的 类型系统。该树由内部节点和叶节点组成。内部节点表示操作(加法,乘法等)和叶节点表示对数据对象的引用。
我试图用一个 堆栈机器的方式来思考整个计算过程:从操作堆栈中取一个操作并从参数堆栈中取出下一个参数并评估操作。 将结果放回堆栈等待操作。
为了表示这两个不同的对象(操作堆栈和数据 叶栈)我捆绑在一起的操作的std::tuple
和 std::tuple
用于数据离开成std::pair<>
。最初,我 使用std:vector
,但导致运行时间开销。
整个过程分两个阶段:初始化操作和参数堆栈的堆栈机初始化 。并且通过将配对的容器 分配给矢量来触发评估阶段。
我创建的类Vec
保持的私人array<int,5>
(所述 有效载荷),并且设有一个重载的赋值运算符 取“表达”。
全球operator*
超载为采取 Vec
和“表达”,使正确处理同样的情况下 我们已经不仅仅是a*b
更多的所有组合。(请注意,我换这个 教育为例,乘法 - 基本上可以快速识别 的imull
在汇编。)
什么是评估前先进行启动的“提取”的 值了参与Vec
的对象并初始化参数 堆栈。这是必要的,以避免不同类型的对象围绕着:可转位向量和不可索引的结果。这就是 Extractor
的用途。再好的事情:在这种情况下使用的变量模板导致没有运行时开销(所有这些都在编译时间 完成)。
整件事情奏效。该表达式很好地评估(我也 添加了,但这是遗漏在这里,以适应代码)。在 以下,您可以看到汇编器输出。只是原始计算,就像你想要的那样:与ET技术相提并论。
Upshot。 C++ 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
instaructions。)
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)
您应该查看[copy elision and RVO](http://en.wikipedia.org/wiki/Copy_elision)。此外,通过值传递其中一个向量而不是制作自己的'tmp'副本可能会有所帮助。 – juanchopanza 2012-08-04 13:39:15
按价值传递无法帮助(仍然复制)。 (N)RVO无助于消除额外的循环 – ritter 2012-08-04 13:43:41
@Frank:你确定吗?这是RVO的强有力候选人。 – akappa 2012-08-04 13:47:43