Hãy nhìn vào một lợi ích cụ thể của các mẫu biểu: ETS có thể được sử dụng để tránh temporaries vector có kích thước trong bộ nhớ xảy ra trong các nhà khai thác quá tải như:mẫu biểu và 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;
}
Trong C++ 11 câu lệnh return của hàm này áp dụng các ngữ nghĩa di chuyển. Không có bản sao của vectơ. Đó là một chiến thắng.
Tuy nhiên, nếu tôi nhìn vào một biểu thức đơn giản như
d = a + b + c;
Tôi thấy rằng các chức năng trên được gọi hai lần (cho cả operator+
) trong khi việc chuyển nhượng cuối cùng có thể được thực hiện với ngữ nghĩa di chuyển.
Tổng cộng 2 vòng được thực hiện. Có nghĩa là tôi tạm thời đọc và đọc lại nó ngay sau đó. Đối với các vectơ lớn, điều này rơi ra khỏi bộ nhớ cache. Đó là tồi tệ hơn so với các mẫu biểu hiện. Họ có thể làm toàn bộ điều chỉ trong vòng 1. ETS có thể thực thi mã tương đương ở trên để:
for(int i=0 ; i < vec_length ; ++i)
d[i] = a[i] + b[i] + c[i];
tôi đã tự hỏi liệu lambdas cùng với ngữ nghĩa di chuyển hoặc bất kỳ tính năng mới khác có thể làm tốt như ETS. Có suy nghĩ gì không?
Edit:
Về cơ bản, sử dụng kỹ thuật ET trình biên dịch xây dựng một cây phân tích cú pháp tương tự như khái niệm đại số với nó hệ thống kiểu. Cây này bao gồm các nút bên trong và các nút lá. Các nút bên trong thể hiện các phép toán (phép cộng, phép nhân, v.v.) và các nút lá đại diện cho các tham chiếu đến các đối tượng dữ liệu.
Tôi đã cố gắng nghĩ về toàn bộ quá trình tính toán trong thời trang của máy xếp chồng : Thực hiện thao tác từ ngăn xếp hoạt động và kéo các đối số kế tiếp từ ngăn xếp đối số và đánh giá hoạt động. Đặt kết quả trở lại trên ngăn xếp đang chờ thao tác.
Đại diện cho hai đối tượng khác nhau (stack hoạt động và dữ liệu lá stack) Tôi đi kèm với nhau một std::tuple
cho các hoạt động và một std::tuple
cho các dữ liệu rời thành một std::pair<>
. Ban đầu tôi đã sử dụng số std:vector
nhưng dẫn đến chi phí thời gian chạy.
Toàn bộ quá trình được thực hiện theo hai giai đoạn: Khởi tạo máy ngăn xếp nơi ngăn xếp hoạt động và đối số được khởi tạo. Và giai đoạn đánh giá được kích hoạt bằng cách gán các vùng chứa được ghép nối cho vectơ.
Tôi tạo ra một lớp Vec
nắm giữ một tin array<int,5>
(các payload) và các tính năng mà một nhà điều hành phân công quá tải mà mất các "khái niệm".
Các toàn cầu operator*
bị quá tải cho tất cả các kết hợp của việc Vec
và "khái niệm" để cho phép việc xử lý đúng cũng trong trường hợp nơi chúng tôi có nhiều hơn chỉ là a*b
.(Lưu ý, tôi chuyển sang cho dụ giáo dục này cho phép nhân - về cơ bản để nhanh chóng phát các imull
trong lắp ráp.)
gì được thực hiện đầu tiên trước khi đánh giá bắt đầu được "chiết xuất" các giá trị ra khỏi tham gia Vec
đối tượng và khởi tạo đối số ngăn xếp. Điều đó là cần thiết để không có các loại đối tượng khác nhau nằm ở xung quanh: Các vectơ có thể lập chỉ mục và các kết quả không thể lập chỉ mục. Đây là nội dung của Extractor
. Điều tốt đẹp một lần nữa: Variadic mẫu được sử dụng mà trong trường hợp này kết quả trong không có thời gian chạy trên không (tất cả điều này được thực hiện tại thời gian biên dịch).
Toàn bộ điều hoạt động. Biểu thức được đánh giá độc đáo (tôi cũng đã thêm phần bổ sung, nhưng điều đó được bỏ lại ở đây để phù hợp với mã). Bên dưới bạn có thể thấy đầu ra của bộ kết hợp. Chỉ cần định nghĩa thô, chính xác như bạn muốn nó là: En-par với kỹ thuật ET.
Ảnh chụp nhanh. Các tính năng ngôn ngữ mới của C++ 11 cung cấp các mẫu variadic (cùng với siêu lập trình mẫu) mở ra khu vực tính toán thời gian biên dịch. Tôi đã chỉ ra ở đây cách các lợi ích của Các mẫu có thể được sử dụng để tạo mã tốt như với kỹ thuật truyền thống 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;
}
Assembler được tạo ra với g++-4.6 -O3
(tôi đã phải đặt một số phụ thuộc thời gian chạy vào khởi tạo vector để trình biên dịch không tính toán toàn bộ điều tại thời gian biên dịch và bạn thực sự thấy 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)
Bạn nên tra cứu [copy elision and RVO] (http://en.wikipedia.org/wiki/Copy_elision). Ngoài ra, chuyển một trong các vectơ theo giá trị thay vì tạo bản sao 'tmp' của riêng bạn có thể hữu ích. – juanchopanza
Đi qua giá trị không thể trợ giúp (bản sao vẫn được tạo). (N) RVO không giúp loại bỏ vòng lặp bổ sung – ritter
@Frank: bạn có chắc chắn không? Đây là một ứng cử viên mạnh mẽ cho RVO. – akappa