46

मैं सी का एक बहुत देखते हैं ++ कोड है कि इस तरह दिखता है:सी ++ iterators और पाश अनुकूलन

for(const_iterator it = list.begin(), 
    const_iterator ite = list.end(); 
    it != ite; ++it) 

के रूप में अधिक संक्षिप्त संस्करण के लिए विरोध:

for(const_iterator it = list.begin(); 
    it != list.end(); ++it) 

के बीच गति में कोई अंतर नहीं होगा इन दो सम्मेलनों? List.end() को केवल एक बार बुलाया जाने के बाद से पहले थोड़ा तेज होगा। लेकिन चूंकि इटेटरेटर कॉन्स है, ऐसा लगता है कि कंपाइलर इस परीक्षण को लूप से बाहर खींच देगा, दोनों के लिए समकक्ष असेंबली उत्पन्न करेगा।

+2

'ite' के लिए घोषणा एक वाक्यविन्यास त्रुटि होगी, इसलिए आपका पहला संस्करण "(const_iterator i = list.begin(), e = list.end(); i! = E; ++ i)" के लिए बन जाता है। यह दूसरे रूप की तुलना में केवल कुछ और वर्ण हैं, इसलिए मैं इसे डिफ़ॉल्ट रूप से उपयोग करता हूं। – Bklyn

+2

अब सी ++ 11 में 'इसके लिए (ऑटो इसे: सूची)' भी है जो अनिवार्य रूप से दूसरा है। लेकिन बहुत अच्छा है। – Cramer

+0

@ क्रैमर रेंज-तत्वों पर लूप के लिए आधारित है, इटेटरेटर पदों पर नहीं, इसलिए समकक्ष '(कॉन्स ऑटो और एलिमेंट: सूची) ' – boycy

उत्तर

29

मैं सिर्फ रिकार्ड के लिए उल्लेख करेंगे कि सी ++ मानक जनादेश कि किसी भी कंटेनर प्रकार पर begin() और end() बुला (होना यह vector, list, map आदि) केवल निरंतर समय रखना चाहिए। प्रैक्टिस में, यदि आप अनुकूलन के साथ संकलित करते हैं तो इन कॉलों को लगभग एक सूचक तुलना में निश्चित रूप से रेखांकित किया जाएगा।

ध्यान दें कि यह गारंटी आवश्यक रूप से अतिरिक्त विक्रेता-आपूर्ति वाले "कंटेनर" के लिए नहीं है जो वास्तव में मानक के अध्याय 23 में रखे कंटेनर होने की औपचारिक आवश्यकताओं का पालन नहीं करती है (उदाहरण के लिए एकल-लिंक्ड सूची slist) ।

+0

++ जो मैं सुनता हूं और देखता हूं, कभी-कभी संकेतक/अक्सर कॉल-फ्री कोड में रेखांकित नहीं होते हैं, और यदि वे लगातार समय लेते हैं, तो समय कमजोर पिग्गी हो सकता है। बेशक, यह ठीक हो सकता है, जब तक कि आप तनाव की स्थिति में न आएं, और फिर यह आपकी सबसे बड़ी लागत हो सकती है। नैतिक: संभावना से अवगत रहें। –

+0

@ माइक: शिंग यिप एक अच्छा बिंदु बनाता है - इनलाइनिंग केवल उसी अनुवाद इकाई (जैसे हेडर फ़ाइल के माध्यम से) में शामिल फ़ंक्शंस के लिए वास्तविक रूप से हो सकती है। मैं एक कोड स्निपेट देखने के लिए चिंतित हूं जहां एक एसटीएल कंटेनर का अंत() (पुनरुत्पादित) हाल ही में (<5 वर्ष पुराना) कंपाइलर द्वारा रेखांकित नहीं किया जा रहा है। –

+2

एफडब्ल्यूआईडब्ल्यू अनुवाद इकाइयों में इनलाइनिंग फ़ंक्शन का नुकसान जीसीसी के ['-flto' ध्वज] (http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#index-flto-934) के साथ पुनर्प्राप्त किया जा सकता है 'लिंक-टाइम अनुकूलन' सक्षम करें। क्लैंग में एक [समान सुविधा] है (http://llvm.org/docs/GoldPlugin.html)। – boycy

11

पहला वाला शायद लगभग हमेशा तेज होगा, लेकिन अगर आपको लगता है कि इससे कोई फर्क पड़ता है, तो हमेशा प्रोफ़ाइल पहले देखें जो कि तेज़ और कितना तेज़ है।

संकलक शायद दोनों मामलों में end() पर कॉल को इनलाइन करने में सक्षम होंगे, हालांकि end() पर्याप्त जटिल है, तो यह इसे इनलाइन करने का विकल्प नहीं चुन सकता है। हालांकि, मुख्य अनुकूलन यह है कि संकलक loop-invariant code motion कर सकता है या नहीं। मुझे लगता है कि ज्यादातर मामलों में, संकलक यह सुनिश्चित नहीं कर सकता कि end() का मान लूप के पुनरावृत्ति के दौरान नहीं बदलेगा, इस मामले में प्रत्येक पुनरावृत्ति के बाद end() पर कॉल करने के अलावा कोई विकल्प नहीं है।

+0

मैं सहमत हूं। पहले पढ़ने के लिए आसान कोड लिखना बेहतर है।फिर, यदि कोई प्रदर्शन समस्याएं हैं - कोड को प्रोफाइल करें, सुनिश्चित करें कि लूप की स्थिति बाधा है, और फिर केवल तेज़ी से फिर से लिखना, लेकिन थोड़ा कम पठनीय संस्करण। –

+3

दोनों दृष्टिकोणों का समय एक अच्छा विचार है। आपको * पता नहीं है कि पहले तेज होगा, क्योंकि प्रत्येक कॉल को समाप्त करने के लिए() लगभग निश्चित रूप से एक सूचक तुलना में रेखांकित किया जाएगा। साथ ही, सी ++ मानक गारंटी देता है कि किसी भी कंटेनर पर एंड() को कॉल करना निरंतर समय का ऑपरेशन है, इसलिए यह कभी भी "पर्याप्त जटिल" नहीं हो सकता है। –

8

मैं सबसे अधिक संक्षिप्त और पठनीय विकल्प चुनूंगा। दूसरा अनुमान लगाने की कोशिश न करें कि संकलक और अनुकूलन जो यह कर सकता है। याद रखें कि आपके कोड का विशाल बहुमत समग्र प्रदर्शन पर बिल्कुल असर नहीं करेगा, इसलिए केवल अगर यह कोड के प्रदर्शन के महत्वपूर्ण भाग में है, तो क्या आप इसे प्रोफ़ाइल करने के लिए समय व्यतीत करना चाहिए और उचित रूप से कुशल स्रोत प्रतिनिधित्व का चयन करना चाहिए।

अपने उदाहरण के लिए विशेष संदर्भ के साथ, पहले संस्करण end() इटरेटर के प्रतिलिपि बना देता है, लागू जो कुछ कोड इटरेटर वस्तु के प्रति निर्माता के लिए चलाता है। एसटीएल कंटेनरों में आमतौर पर इनलाइन end() फ़ंक्शंस होते हैं, इसलिए कंपाइलर के पास दूसरे संस्करण को अनुकूलित करने का अवसर होता है, भले ही आप इसे मदद करने की कोशिश नहीं कर रहे हों। कौन सा सबसे अच्छा है? उन्हें मापो।

0

सिद्धांत रूप में संकलक दूसरे संस्करण को पहले में अनुकूलित कर सकता है (माना जाता है कि कंटेनर लूप के दौरान स्पष्ट रूप से नहीं बदलता है)।

प्रैक्टिस में, मुझे कई समान मामले मिलते हैं जब समय-महत्वपूर्ण कोड प्रोफाइलिंग करते हैं जहां मेरा कंपाइलर लूप स्थितियों से परिवर्तनीय गणना को पूरी तरह विफल करने में असफल रहा है। इसलिए, ज्यादातर मामलों में थोड़ा अधिक संक्षिप्त संस्करण ठीक है, लेकिन मैं उस मामले के लिए समझदार चीजों को संकलक पर भरोसा नहीं करता जहां मैं वास्तव में प्रदर्शन के बारे में चिंतित हूं।

+0

मुझे लगता है कि समस्या यह नहीं है कि संकलक उस अंत() को पहचानने के लिए पर्याप्त स्मार्ट है या नहीं, यह लूप से बाहर निकलता है (जिसके लिए अपेक्षाकृत स्मार्ट कंपाइलर की आवश्यकता होती है) - यह है कि कॉल को समाप्त करने के लिए() को रेखांकित किया जा सकता है (जिसके लिए इस तरह के एक स्मार्ट कंपाइलर की आवश्यकता नहीं है), क्योंकि अंत() के अंदर कोड आमतौर पर बहुत छोटा और सरल होगा, उदाहरण के लिए std :: vector या std :: सूची के लिए एक सूचक सूचकांक। –

6

आप पहले संस्करण अधिक संक्षिप्त बनाने के लिए और दोनों का सबसे अच्छा प्राप्त कर सकते हैं:

for(const_iterator it = list.begin(), ite = list.end(); 
    it != ite; ++it) 

पी.एस. इटरेटर नहीं हैं, वे एक कॉन्स्ट्रेंस के लिए इटरेटर हैं। एक बड़ा अंतर है।

43

हालांकि दो संस्करण समान नहीं हैं। दूसरे संस्करण में यह हर बार list.end() के खिलाफ इटरेटर की तुलना करता है, और list.end() लूप के दौरान बदल सकता है का मूल्यांकन करता है। अब निश्चित रूप से, आप list को const_iterator it के माध्यम से संशोधित नहीं कर सकते; लेकिन कुछ भी लूप के अंदर कोड को list पर कॉलिंग विधियों से सीधे रोकता है और इसे म्यूट कर देता है, जो (किस प्रकार की डेटा संरचना list है) अंत इटरेटर बदल सकता है।इसलिए कुछ परिस्थितियों में यह अंततः एंडरेटर को स्टोर करने के लिए गलत हो सकता है, क्योंकि जब आप इसे प्राप्त करते हैं तो यह सही अंत इटरेटर नहीं हो सकता है।

+0

+1। सूची बदलने की संभावना के बारे में अच्छा बिंदु, जिसे केवल दूसरे कोड स्निपेट द्वारा ही सही ढंग से संभाला जाएगा। –

+19

यदि सूची एक std :: वेक्टर है, उदाहरण के लिए, इसे लूप के अंदर बदलना सभी इटरेटर को अमान्य कर देगा, इस प्रकार दोनों लूप गलत हो जाएंगे। – n0rd

+0

यह असली जवाब है। –

1

मैं हमेशा पहले को पसंद करता था। हालांकि इनलाइन फ़ंक्शंस, कंपाइलर ऑप्टिमाइज़ेशन और अपेक्षाकृत छोटे कंटेनर आकार के साथ (मेरे मामले में यह आमतौर पर अधिकतम 20-25 आइटम होता है) यह वास्तव में प्रदर्शन के संबंध में कोई बड़ा अंतर नहीं बनाता है।

const_iterator it = list.begin(); 
const_iterator endIt = list.end(); 

for(; it != endIt ; ++it) 
{//do something 
} 

लेकिन हाल ही में मैं कहीं भी std::for_each का उपयोग कर रहा हूं। इसकी अनुकूलित लूपिंग जो कोड को अन्य दो की तुलना में अधिक पठनीय बनाने में मदद करती है।

std::for_each(list.begin(), list.end(), Functor()); 

मैं पाश केवल जब std::for_each नहीं किया जा सकता का उपयोग करेगा। (पूर्व के लिए: std::for_each आपको लूप को तोड़ने की अनुमति नहीं देता है जब तक कोई अपवाद नहीं फेंक दिया जाता है)।

+0

मुझे इस समारोह से अवगत नहीं था। ऐसा लगता है कि एक फंक्शन कॉल हमेशा अंतर्निहित 'के लिए' की तुलना में महत्वपूर्ण ओवरहेड होगा, हालांकि यह बहुत पठनीय है। एक मैक्रो कार्यान्वयन के साथ भी यह लूप के लिए तेज़ नहीं हो सकता है। यह मेरी इच्छा करता है कि मैं इस परियोजना के लिए अजगर का उपयोग कर सकता हूं (दुर्भाग्य से मेरा नियोक्ता सी ++ को निर्देशित करता है)। – Quantum7

+0

@ क्वांटम 7: बेशक यह एक लूप की तुलना में * तेज * नहीं हो सकता है (क्योंकि आंतरिक रूप से इसे लूप में अनुवादित किया जाता है), लेकिन यह लगभग निश्चित रूप से धीमा नहीं है। –

+0

@ क्वांटम 7 'ऐसा लगता है कि एक फ़ंक्शन कॉल हमेशा महत्वपूर्ण ओवरहेड होगा' यह स्पष्ट रूप से झूठा है; इनलाइनिंग एक चीज है जो मौजूद है। –

4

आह, लोग अनुमान लगा रहे हैं। डीबगर & में अपना कोड खोलें आप देखेंगे कि कॉल(), end() आदि शुरू करने के लिए सभी को अनुकूलित किया गया है। संस्करण 1 का उपयोग करने की कोई आवश्यकता नहीं है। विजुअल सी ++ कंपाइलर फुलोपट के साथ परीक्षण किया गया। इस मामले में

for (const_iterator it = list.begin(); it != list.end(); ++list) 
{ 
    if (moonFull()) 
     it = insert_stuff(list); 
    else 
     it = erase_stuff(list); 
} 

, आप list.end() कॉल करने के लिए लूप में की जरूरत है, और संकलक कि अनुकूलन दूर करने के लिए नहीं जा रहा है:

+5

यह कंपाइलर, कंटेनर और अनुकूलन सेटिंग्स पर निर्भर होने जा रहा है। सभी संदेह को दूर करने के लिए सबसे अच्छा। –

+2

यह प्रश्न में लूप पर निर्भर करता है। मुझे अतीत में कई मामले मिल गए हैं जहां एमएसवीसी ++ दूसरे मामले को पहले में अनुकूलित नहीं करता है, भले ही यह काफी स्पष्ट लगता है कि इसे करना चाहिए। – Peter

+0

लेकिन एक डेटा बिंदु से निष्कर्ष निकालना वास्तव में अनुमान लगाने से बेहतर नहीं है। –

6

इस उदाहरण पर विचार।

अन्य मामले जहां संकलक साबित कर सकता है कि अंत() हमेशा एक ही मूल्य लौटा रहा है, अनुकूलन हो सकता है।

अगर हम एसटीएल कंटेनरों के बारे में बात कर रहे हैं, तो मुझे लगता है कि कोई भी अच्छा कंपाइलर कई अंत() कॉल को ऑप्टिमाइज़ कर सकता है जब प्रोग्रामिंग तर्क के लिए एकाधिक अंत() कॉल की आवश्यकता नहीं होती है। हालांकि, यदि आपके पास कस्टम कंटेनर है और अंत() का कार्यान्वयन एक ही अनुवाद इकाई में नहीं है, तो ऑप्टिमाइज़ेशन लिंक समय पर होना होगा। मैं लिंक समय अनुकूलन के बारे में बहुत कम जानता हूं, लेकिन मैं शर्त लगाऊंगा कि अधिकांश लिंकर्स ऐसा अनुकूलन नहीं करेंगे।

+0

लेकिन यदि आप सूची में लूप करने के लिए एक इटरेटर का उपयोग कर रहे हैं, तो क्या आप सूची को संशोधित करने के लिए इटरेटर का भी उपयोग नहीं करना चाहिए? अन्यथा आप अजीब समवर्ती मुद्दों को प्राप्त कर सकते हैं क्योंकि डेटा और इटरेटर सिंक से बाहर हो जाते हैं। हो सकता है कि जावा में यह एक बड़ा मुद्दा है जहां इटरेटर के पास अधिक पदार्थ है। – Quantum7

+1

हां, आप सही हैं। यह insert__stuff (इसे, सूची) लिखने के लिए और अधिक समझ देगा ... लेकिन जिस बिंदु पर मैं पार करने की कोशिश कर रहा था वह तथ्य था कि सूची लूप के भीतर बदल सकती है और list.end() प्रत्येक लूप के लिए बुलाया जाना चाहिए। –

+0

+1। इनलाइनिंग के बारे में आपका बिंदु केवल तब होता है जब एक ही अनुवाद इकाई में अंत() की परिभाषा प्रकट होती है, जो मुझे सही समझ में आता है। मुझे आश्चर्य है कि क्या दूसरों का अनुभव हो रहा है जब वे कंपाइलर के बारे में शिकायत करते हैं कि वे "स्पष्ट" इनलाइनिंग अवसरों को याद करते हैं ...? –

1
  1. तनाव की स्थिति में इसका नमूना लें और देखें कि क्या आप ** इस कोड में अक्सर *** हैं।
    यदि नहीं, तो इससे कोई फर्क नहीं पड़ता।

  2. यदि आप हैं, तो डिस्सेप्लर, या सिंगल-चरण देखें।
    इस तरह आप बता सकते हैं कि कौन सा तेज़ है।

आपको इन इटरेटर से सावधान रहना होगा।
वे अच्छे मशीन कोड में अनुकूलित हो सकते हैं, लेकिन अक्सर वे पर्याप्त नहीं होते हैं, और समय हॉग बन जाते हैं।

** (कहाँ "में" यह वास्तव में इसका मतलब है, या यह से बुलाया जा रहा है।)

*** (कहाँ "अक्सर" समय के एक महत्वपूर्ण प्रतिशत का मतलब है।)

जोड़ा: न केवल कोड को निष्पादित करने के लिए प्रति सेकंड कितनी बार देखें। यह एक बार 1,000 गुना हो सकता है और अभी भी 1% से कम समय का उपयोग कर रहा है।

समय नहीं लगता कि यह कितना समय लगता है। यह एक मिलीसेकंड ले सकता है और अभी भी 1% से कम समय का उपयोग कर रहा है।

बेहतर विचार पाने के लिए आप दोनों को गुणा कर सकते हैं, लेकिन यह केवल तभी काम करता है जब वे बहुत कम नहीं होते हैं।

Sampling the call stack आपको बताएगा कि यह समय के लिए पर्याप्त समय का उपयोग करता है या नहीं।

4

कंपाइलर पहले में दूसरे को अनुकूलित करने में सक्षम हो सकता है, लेकिन यह मानता है कि दोनों बराबर हैं, यानी अंत() वास्तव में स्थिर है। थोड़ा और समस्याग्रस्त मुद्दा यह है कि संकलक यह साबित करने में असमर्थ हो सकता है कि अंतिम एलियासिंग के कारण एंडरेटर स्थिर है। हालांकि, यह मानते हुए कि कॉल() को अंत में निर्दिष्ट किया गया है, अंतर केवल एक स्मृति लोड है।

ध्यान दें कि यह मानता है कि अनुकूलक सक्षम है। यदि ऑप्टिमाइज़र सक्षम नहीं है, जैसा अक्सर डीबग बिल्ड में किया जाता है, तो दूसरे फॉर्मूलेशन में एन -1 और अधिक फ़ंक्शन कॉल शामिल होंगे। विजुअल सी ++ के मौजूदा संस्करणों में, डीबग बिल्ड्स में फ़ंक्शन प्रोलॉग/एपिलॉग चेक और भारी डीबग इटरेटर्स के कारण अतिरिक्त हिट भी होंगे। इसलिए, एसटीएल भारी कोड में, पहले मामले में डिफॉल्ट करने से डीबग बिल्ड में कोड को असमान रूप से धीमा होने से रोक सकता है।

लूप के भीतर सम्मिलन और निष्कासन एक संभावना है, जैसा कि अन्य ने इंगित किया है, लेकिन लूप की इस शैली के साथ मुझे यह असंभव लगता है। एक बात के लिए, नोड-आधारित कंटेनर - सूची, सेट, मानचित्र - किसी भी ऑपरेशन पर अंत() को अमान्य नहीं करें। दूसरा, इटरेटर वेतन वृद्धि अक्सर अमान्यकरण समस्याओं से बचने के लिए लूप स्थानांतरित करने की है:

 
    // assuming list -- cannot cache end() for vector 
    iterator it(c.begin()), end(c.end()); 
    while(it != end) { 
     if (should_remove(*it)) 
      it = c.erase(it); 
     else 
      ++it; 
    }

इस प्रकार, मैं एक पाश में बदलें-दौरान लूप कारणों के लिए अंत() कॉल करने के लिए दावा करता है और अभी भी है कि पर विचार ++ यह लूप हेडर में संदिग्ध होने के लिए।

संबंधित मुद्दे