आइए नज़र: टिकट स्मृति में वेक्टर आकार temporaries जो की तरह अतिभारित ऑपरेटरों में पाए जाते हैं से बचने के लिए इस्तेमाल किया जा सकता:अभिव्यक्ति टेम्पलेट्स और सी ++ 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 इस समारोह का रिटर्न स्टेटमेंट चाल semantics लागू होता है। वेक्टर की कोई प्रति नहीं। यह एक जीत है।
हालांकि, अगर मैं की तरह
d = a + b + c;
एक सरल अभिव्यक्ति को देखो मुझे लगता है कि इसके बाद के संस्करण समारोह में दो बार फोन किया जाता है (दोनों operator+ के लिए) जबकि अंतिम असाइनमेंट चाल अर्थ विज्ञान के साथ किया जा सकता है।
कुल 2 लूप निष्पादित किए जाते हैं। इसका मतलब है कि मैंने एक अस्थायी रूप से बाहर रखा और इसे बाद में वापस पढ़ा। बड़े वैक्टरों के लिए यह कैश से बाहर आता है। यह अभिव्यक्ति टेम्पलेट्स से भी बदतर है। वे पूरी चीज सिर्फ 1 पाश में कर सकते हैं।
for(int i=0 ; i < vec_length ; ++i)
d[i] = a[i] + b[i] + c[i];
मैं सोच रहा था कि क्या इस कदम अर्थ विज्ञान या किसी अन्य नई सुविधा के साथ lambdas एक साथ टिकट के रूप में रूप में अच्छा कर सकते हैं: टिकट उपरोक्त कोड बराबर करने के लिए निष्पादित कर सकते हैं। कोई विचार?
संपादित करें:
मूल रूप से, एट तकनीक का उपयोग कर संकलक एक पार्स पेड़ कि बीजीय अभिव्यक्ति जैसा दिखता है के साथ यह प्रकार प्रणाली है बनाता है। इस पेड़ में आंतरिक नोड्स और पत्ता नोड होते हैं। आंतरिक नोड्स संचालन (जोड़, गुणा, आदि) का प्रतिनिधित्व करते हैं और पत्ती नोड डेटा ऑब्जेक्ट्स के संदर्भ का प्रतिनिधित्व करते हैं।
मैंने स्टैक मशीन के फैशन में पूरी गणना प्रक्रिया के बारे में सोचने की कोशिश की: ऑपरेशन स्टैक से ऑपरेशन करें और तर्क स्टैक से अगले तर्क और ऑपरेशन का मूल्यांकन करें। परिणाम को ऑपरेशन के लिए इंतजार कर रहे स्टैक पर वापस रखें।
इन दो अलग अलग वस्तुओं (आपरेशन ढेर और डेटा पत्ती ढेर) मैं कार्यों के लिए एक std::tuple और एक std::tuple एक साथ बंडल के लिए डेटा एक std::pair<> में छोड़ देता है प्रतिनिधित्व करने के लिए। प्रारंभ में मैं ने std:vector का उपयोग किया लेकिन इसके परिणामस्वरूप रनटाइम ओवरहेड हुआ।
पूरी प्रक्रिया दो चरणों में जाती है: स्टैक मशीन प्रारंभिकरण जहां ऑपरेशन और तर्क स्टैक प्रारंभ किया गया है। और मूल्यांकन चरण जो वेक्टर में जोड़े गए कंटेनर असाइन करके ट्रिगर किया जाता है।
मैं एक वर्ग Vec जो एक निजी array<int,5> ( पेलोड) रखती है और जो एक ओवरलोड असाइनमेंट ऑपरेटर कि "अभिव्यक्ति" दिखाती है बनाया।
वैश्विक operator* Vec और "अभिव्यक्ति" लेने जहां हम सिर्फ a*b से अधिक सही से निपटने के भी मामले में सक्षम करने के लिए के सभी संयोजनों के लिए ओवरलोड हो गया है।(सूचना, मैं गुणा करने के लिए इस शैक्षिक उदाहरण के लिए बंद - मूल रूप से जल्दी से पहचानना कोडांतरक में imull।)
क्या मूल्यांकन करने से पहले किया जाता है शुरू होता है है शामिल Vec से बाहर मूल्यों "को निकालने" ऑब्जेक्ट्स और तर्क स्टैक प्रारंभ करना। यह आवश्यक था कि के आसपास विभिन्न प्रकार की वस्तुएं न हों: इंडेक्स करने योग्य वैक्टर और गैर-अनुक्रमणीय परिणाम। यह Extractor है। अच्छी बात फिर से: वैराडिक टेम्पलेट्स का उपयोग किया जाता है जो इस मामले में कोई रन-टाइम ओवरहेड नहीं होता है (यह सब संकलन समय पर किया जाता है)।
पूरी बात काम करती है। अभिव्यक्ति का अच्छी तरह से मूल्यांकन किया गया है (मैं भी जोड़ा जोड़ा गया है, लेकिन कोड को फिट करने के लिए यहां छोड़ा गया है)। के नीचे आप असेंबलर आउटपुट देख सकते हैं। बस कच्चे compuation, ठीक है जैसे आप यह होना चाहते हैं: ईटी तकनीक के साथ एन-पैरा।
उपशॉट। सी ++ 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 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)
आपको [कॉपी एलिजन और आरवीओ] (http://en.wikipedia.org/wiki/Copy_elision) देखना चाहिए। साथ ही, अपनी खुद की 'tmp' प्रतिलिपि बनाने के बजाय मूल्यों में से एक को पास करने से मदद मिल सकती है। – juanchopanza
मूल्य से गुजरने से मदद नहीं मिल सकती है (एक प्रतिलिपि अभी भी बनाई गई है)। (एन) आरवीओ अतिरिक्त लूप – ritter
@ फ्रैंक को खत्म करने में मदद नहीं करता है: क्या आप निश्चित हैं? यह आरवीओ के लिए एक मजबूत उम्मीदवार है। – akappa