c++ - सी++ 0x में "जबकि(1);" को अनुकूलित करना




optimization loops (6)

क्या किसी के पास यह अच्छी व्याख्या है कि यह अनुमति देने के लिए क्यों जरूरी था?

हां, हंस बोहेम एन1528 में इसके लिए एक तर्क प्रदान करता है : अनंत लूप के लिए अपरिभाषित व्यवहार क्यों? , हालांकि यह डब्ल्यूजी 14 दस्तावेज है, तर्क भी सी ++ पर लागू होता है और दस्तावेज़ डब्लूजी 14 और डब्लूजी 21 दोनों को संदर्भित करता है:

चूंकि एन 150 9 सही तरीके से बताता है, वर्तमान मसौदा अनिवार्य रूप से अनिश्चित व्यवहार को अनंत लूप को 6.8.5p6 में देता है। ऐसा करने के लिए एक बड़ा मुद्दा यह है कि यह कोड को संभावित रूप से गैर-टर्मिनिंग लूप में स्थानांतरित करने की अनुमति देता है। उदाहरण के लिए, मान लीजिए कि हमारे पास निम्न लूप हैं, जहां गिनती और गिनती वैश्विक चर हैं (या उनका पता लिया गया है), और पी एक स्थानीय चर है, जिसका पता नहीं लिया गया है:

for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

क्या इन दो लूपों को विलय किया जा सकता है और निम्न लूप द्वारा प्रतिस्थापित किया जा सकता है?

for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}

अनंत लूप के लिए 6.8.5 पी 6 में विशेष छूट के बिना, यह अस्वीकृत कर दिया जाएगा: यदि पहला लूप समाप्त नहीं होता है क्योंकि क्यू परिपत्र सूची में अंक इंगित करता है, मूल कभी गिनती 2 को नहीं लिखता है। इस प्रकार यह एक और थ्रेड के साथ समानांतर में चलाया जा सकता है जो count2 को एक्सेस या अपडेट करता है। यह अब परिवर्तित संस्करण के साथ सुरक्षित नहीं है जो अनंत लूप के बावजूद count2 का उपयोग करता है। इस प्रकार परिवर्तन संभावित रूप से डेटा रेस पेश करता है।

इस तरह के मामलों में, यह बहुत ही असंभव है कि एक कंपाइलर लूप समाप्ति साबित करने में सक्षम होगा; यह समझना होगा कि क्यू अंक एक विश्वकोश सूची में इंगित करता है, जो मुझे लगता है कि अधिकांश मुख्यधारा के कंपाइलरों की क्षमता से परे है, और अक्सर पूरी प्रोग्राम जानकारी के बिना असंभव है।

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

एक पूर्णांक लूप वैरिएबल के साथ स्पष्ट रूप से फॉर-लूप भी होते हैं जिसमें संकलक को समाप्त करने के लिए यह मुश्किल होगा, और संकलक के लिए 6.8.5p6 के बिना लूप को पुन: स्थापित करना मुश्किल होगा। कुछ भी पसंद है

for (i = 1; i != 15; i += 2)

या

for (i = 1; i <= 10; i += j)

संभालने के लिए nontrivial लगता है। (पूर्व मामले में, समाप्ति को साबित करने के लिए कुछ बुनियादी संख्या सिद्धांत की आवश्यकता होती है, बाद के मामले में, हमें ऐसा करने के लिए जे के संभावित मूल्यों के बारे में कुछ पता होना चाहिए। हस्ताक्षर किए गए पूर्णांक के लिए लपेटें-आसपास इस तर्क को और जटिल कर सकते हैं। )

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

सी के साथ एक बड़ा अंतर यह है कि सी 11 उन अभिव्यक्तियों को नियंत्रित करने के लिए अपवाद प्रदान करता है जो निरंतर अभिव्यक्तियां हैं जो सी ++ से भिन्न होती हैं और आपके विशिष्ट उदाहरण को सी 11 में अच्छी तरह से परिभाषित करती हैं।

अपडेट किया गया, नीचे देखें!

मैंने सुना है और पढ़ा है कि सी ++ 0x एक कंपाइलर को निम्न स्निपेट के लिए "हैलो" प्रिंट करने की अनुमति देता है

#include <iostream>

int main() {
  while(1) 
    ;
  std::cout << "Hello" << std::endl;
}

यह स्पष्ट रूप से धागे और अनुकूलन क्षमताओं के साथ कुछ करने के लिए है। मुझे लगता है कि यह कई लोगों को आश्चर्यचकित कर सकता है।

क्या किसी के पास यह अच्छी व्याख्या है कि यह अनुमति देने के लिए क्यों जरूरी था? संदर्भ के लिए, हालिया सी ++ 0 एक्स ड्राफ्ट 6.5/5 पर कहता है

एक लूप कि, एक बयान के मामले में फॉर-इन-स्टेटमेंट के बाहर,

  • पुस्तकालय I / O कार्यों के लिए कोई कॉल नहीं करता है, और
  • अस्थिर वस्तुओं का उपयोग या संशोधित नहीं करता है, और
  • कोई सिंक्रनाइज़ेशन ऑपरेशंस (1.10) या परमाणु संचालन नहीं करता है (खंड 2 9)

कार्यान्वयन द्वारा समाप्त करने के लिए माना जा सकता है। [नोट: इसका उद्देश्य कंपाइलर ट्रांसफॉर्मेशन को अनुमति देना है, जैसे रिक्त लूप को हटाने, भले ही समाप्ति सिद्ध न हो। - अंत नोट]

संपादित करें:

यह अंतर्दृष्टि लेख उस मानक पाठ के बारे में बताता है

दुर्भाग्य से, "अपरिभाषित व्यवहार" शब्द का उपयोग नहीं किया जाता है। हालांकि, किसी भी समय मानक कहता है "संकलक पी मान सकता है," यह निहित है कि एक कार्यक्रम जिसमें संपत्ति नहीं है- पी ने अर्थशास्त्र को अपरिभाषित किया है।

क्या यह सही है, और क्या संकलक को उपरोक्त कार्यक्रम के लिए "अलविदा" प्रिंट करने की अनुमति है?

यहाँ एक और अधिक अंतर्दृष्टि धागा है , जो कि सी में समान परिवर्तन के बारे में है, लड़के ने ऊपर दिए गए लेख को पूरा किया। अन्य उपयोगी तथ्यों के अलावा, वे एक समाधान प्रस्तुत करते हैं जो सी ++ 0x पर भी लागू होता है ( अपडेट : यह अब n3225 के साथ काम नहीं करेगा - नीचे देखें!)

endless:
  goto endless;

एक कंपाइलर को इसे अनुकूलित करने की अनुमति नहीं है, ऐसा लगता है, क्योंकि यह एक पाश नहीं है, लेकिन एक कूद है। एक और लड़का सी ++ 0x और सी201 एक्स में प्रस्तावित परिवर्तन का सारांश देता है

एक लूप लिखकर, प्रोग्रामर या तो जोर दे रहा है कि लूप दृश्य व्यवहार के साथ कुछ करता है (I / O निष्पादित करता है, अस्थिर वस्तुओं तक पहुंचता है, या सिंक्रनाइज़ेशन या परमाणु संचालन करता है), या यह अंततः समाप्त हो जाता है। यदि मैं किसी साइड इफेक्ट्स के साथ अनंत लूप लिखकर उस धारणा का उल्लंघन करता हूं, तो मैं कंपाइलर से झूठ बोल रहा हूं, और मेरे प्रोग्राम का व्यवहार अपरिभाषित है। (यदि मैं भाग्यशाली हूं, तो संकलक मुझे इसके बारे में चेतावनी दे सकता है।) भाषा दृश्यमान व्यवहार के बिना एक अनंत लूप व्यक्त करने का एक तरीका प्रदान नहीं करती है (अब प्रदान नहीं करती है?)।

3.1321 को एन 3225 के साथ अपडेट करें: समिति ने टेक्स्ट को 1.10 / 24 पर ले जाया और कहा

कार्यान्वयन यह मान सकता है कि कोई भी थ्रेड अंततः निम्न में से एक कार्य करेगा:

  • समाप्त कर दें,
  • लाइब्रेरी I / O फ़ंक्शन पर कॉल करें,
  • एक अस्थिर वस्तु का उपयोग या संशोधित करें, या
  • सिंक्रनाइज़ेशन ऑपरेशन या परमाणु ऑपरेशन करें।

goto चाल अब और काम नहीं करेगी!


प्रासंगिक मुद्दा यह है कि संकलक को कोड को पुन: व्यवस्थित करने की अनुमति है जिसका दुष्प्रभाव संघर्ष नहीं करता है। निष्पादन का आश्चर्यजनक क्रम तब भी हो सकता है जब संकलक अनंत लूप के लिए गैर-टर्मिनल मशीन कोड उत्पन्न करता हो।

मेरा मानना ​​है कि यह सही दृष्टिकोण है। भाषा का नमूना निष्पादन के आदेश को लागू करने के तरीकों को परिभाषित करता है। यदि आप एक अनंत लूप चाहते हैं जिसे चारों ओर फिर से व्यवस्थित नहीं किया जा सकता है, तो इसे लिखें:

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");

मुझे लगता है कि यह इंगित करने लायक है कि लूप जो असीमित होंगे, इस तथ्य को छोड़कर कि वे गैर-अस्थिर, गैर-सिंक्रनाइज़ किए गए चर के माध्यम से अन्य धागे के साथ बातचीत करते हैं, अब एक नए कंपाइलर के साथ गलत व्यवहार कर सकते हैं।

मैं दूसरे शब्दों में, अपने ग्लोबल्स को अस्थिर बना देता हूं - साथ ही पॉइंटर / संदर्भ के माध्यम से ऐसे लूप में दिए गए तर्क।


मुझे लगता है कि यह इस प्रकार के question , जो एक और thread संदर्भ देता है। अनुकूलन कभी-कभी खाली लूप को हटा सकता है।


मेरे लिए, प्रासंगिक औचित्य है:

इसका उद्देश्य कंपाइलर ट्रांसफॉर्मेशन को अनुमति देना है, जैसे रिक्त लूप को हटाने, भले ही समाप्ति सिद्ध न हो।

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

संपादित करें: गूंगा उदाहरण:

while (complicated_condition()) {
    x = complicated_but_externally_invisible_operation(x);
}
complex_io_operation();
cout << "Results:" << endl;
cout << x << endl;

यहां, यह एक थ्रेड के लिए complex_io_operation जबकि दूसरा लूप में सभी जटिल गणना कर रहा है। लेकिन आपके द्वारा उद्धृत किए गए खंड के बिना, संकलक को अनुकूलन करने से पहले दो चीजों को साबित करना होगा: 1) complex_io_operation() लूप के परिणामों पर निर्भर नहीं है, और 2) कि लूप समाप्त हो जाएगा । 1 प्रदान करना) बहुत आसान है, साबित करना 2) रोकना समस्या है। खंड के साथ, यह मान सकता है कि लूप समाप्त हो जाता है और समांतरता जीत प्राप्त होती है।

मैं यह भी कल्पना करता हूं कि डिजाइनरों ने माना कि जिन मामलों में असीमित लूप उत्पादन कोड में होते हैं वे बहुत दुर्लभ होते हैं और आम तौर पर इवेंट-संचालित लूप जैसी चीजें हैं जो किसी भी तरीके से I / O तक पहुंचती हैं। नतीजतन, उन्होंने दुर्लभ केस (अनंत लूप) को अधिक सामान्य केस (noninfinite, लेकिन यांत्रिक रूप से noninfinite, loops साबित करने के लिए मुश्किल) अनुकूलित करने के पक्ष में निराश किया है।

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

संपादित करें: अब आप जो अंतर्दृष्टिपूर्ण लेख लिंक करते हैं, उसके संबंध में, मैं कहूंगा कि "कंपाइलर प्रोग्राम के बारे में एक्स मान सकता है" तर्कसंगत रूप से समकक्ष है "यदि कार्यक्रम एक्स को संतुष्ट नहीं करता है, तो व्यवहार अपरिभाषित है"। हम इसे निम्नानुसार दिखा सकते हैं: मान लीजिए कि एक ऐसा कार्यक्रम मौजूद है जो संपत्ति एक्स को संतुष्ट नहीं करता है। इस कार्यक्रम का व्यवहार कहां परिभाषित किया जाएगा? मानक केवल संपत्ति को मानते हुए व्यवहार को परिभाषित करता है एक्स एक्स सच है। यद्यपि मानक स्पष्ट रूप से अपरिभाषित व्यवहार की घोषणा नहीं करता है, लेकिन उसने इसे चूक से अपरिभाषित घोषित कर दिया है।

एक समान तर्क पर विचार करें: "संकलक मान सकता है कि एक चर एक्स को अनुक्रम बिंदुओं के बीच केवल एक बार सौंपा गया है" अनुक्रम बिंदुओं के बीच एक से अधिक बार एक्स को असाइन करना "के बराबर है।


यह गैर-तुच्छ मामलों के लिए कंपाइलर के लिए निर्णायक नहीं है यदि यह एक अनंत लूप है।

विभिन्न मामलों में, ऐसा हो सकता है कि आपका ऑप्टिमाइज़र आपके कोड के लिए बेहतर जटिलता वर्ग तक पहुंच जाएगा (उदाहरण के लिए यह ओ (एन ^ 2) था और आपको ऑप्टिमाइज़ेशन के बाद ओ (एन) या ओ (1) मिलता है)।

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

एक और बात: मैंने कभी भी एक वैध उदाहरण नहीं देखा है जहां आपको एक अनंत लूप की आवश्यकता है जो कुछ भी नहीं करता है।

एक उदाहरण जो मैंने सुना है वह एक बदसूरत हैक था जिसे वास्तव में हल किया जाना चाहिए अन्यथा: यह एम्बेडेड सिस्टम के बारे में था जहां रीसेट को ट्रिगर करने का एकमात्र तरीका डिवाइस को फ्रीज करना था ताकि वॉचडॉग स्वचालित रूप से इसे पुनरारंभ कर सके।

यदि आपको कोई वैध / अच्छा उदाहरण पता है जहां आपको एक अनंत लूप की आवश्यकता है जो कुछ भी नहीं करता है, तो कृपया मुझे बताएं।





c++11