2010-08-18 22 views
29

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

इसके अलावा, मानक से पूंछ कॉल अनुकूलन छोड़ने के लिए तर्क क्या था?

+2

संबंधित: http://stackoverflow.com/questions/2250727/regarding-stack-reuse-of-a-function-calling-itself –

उत्तर

24

"सी पूंछ कॉल उन्मूलन नहीं करता" जैसे वक्तव्य कोई समझ नहीं आता है। जैसा कि आपने स्वयं को सही ढंग से नोट किया है, इस तरह की चीजें पूरी तरह कार्यान्वयन पर निर्भर करती हैं। और हां, कोई भी सभ्य कार्यान्वयन आसानी से पूंछ-पुनरावृत्ति को चक्र के बराबर बदल सकता है। बेशक, सी कंपाइलर्स सामान्य रूप से अनुकूलन के बारे में कोई गारंटी नहीं देते हैं और कोड के प्रत्येक विशेष टुकड़े में क्या अनुकूलन नहीं होंगे। आपको इसे संकलित करना और खुद के लिए देखना है।

5

अंतिम प्रश्न का उत्तर देने के लिए: मानक निश्चित रूप से अनुकूलन के बारे में कोई बयान नहीं देना चाहिए। ऐसे वातावरण हो सकते हैं जहां इसे लागू करने में कम या ज्यादा मुश्किल हो।

+11

मानक के लिए यह गलत होगा कि लूप लगातार निरंतर स्मृति में चलें? (जबकि लूप में आवंटन को छोड़कर) क्या मानक के लिए यह गलत होगा कि पूंछ रिकर्सिव फ़ंक्शन निरंतर मेमोरी में चलें? – Jules

+2

मेरा मानना ​​है कि योजना को पूंछ-कॉल अनुकूलन की आवश्यकता है, लेकिन योजना एक मुख्य रूप से कार्यात्मक भाषा है, जो नियंत्रण संरचना के रूप में भारी बारिश का उपयोग करती है। सी कार्यक्रम कम रिकर्सिव होते हैं, और निरंतर उपयोग में पुनरावृत्त संरचनाएं होती हैं। –

1

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

+0

केवल उन कॉल पैटर्न की आवश्यकता होती है जो एक निश्चित आवश्यकता को पूरा करते हैं, निरंतर मेमोरी स्पेस का उपयोग करना बेहद आसान होगा। यही कारण है कि कैसे एक भाषा बर्ताव करता है का हिस्सा है, और प्रभाव अगर आप पूंछ कभी लौट (एक कार्यक्रम के रूप में मैं संकलक TCO पर निर्भर लिखा करता है) के बिना लाखों लोगों की है और एक कार्यक्रम में लाखों बार कॉल कर सकते हैं। –

3

मुझे लगता है कि पूंछ कॉल अनुकूलन को केवल की गारंटी की आवश्यकता है जहां रिकर्सन की अनुमानित या आवश्यक है; अर्थात, उन भाषाओं में जो कार्यात्मक प्रोग्रामिंग शैली को प्रोत्साहित या लागू करते हैं। (इस तरह की भाषाओं के साथ, आप पाएंगे कि for या while लूप या तो दृढ़ता से निराश हो जाते हैं, जो कि सुरुचिपूर्ण, या शायद भाषा से पूरी तरह से अनुपस्थित हैं, इसलिए आप इन सभी कारणों और शायद अधिक के लिए रिकर्सन का सहारा ले सकते हैं।)

सी प्रोग्रामिंग भाषा (आईएमएचओ) स्पष्ट रूप से को कार्यात्मक प्रोग्रामिंग के साथ दिमाग में डिजाइन किया गया था। सभी प्रकार के लूप संरचनाएं होती हैं जिन्हें आम तौर पर रिकर्सन के पक्ष में उपयोग किया जाता है: for, do .. while, while। ऐसी भाषा में, मानक में पूंछ कॉल अनुकूलन को निर्धारित करने के लिए अधिक समझदारी नहीं होगी, क्योंकि यह कामकाजी कार्यक्रमों की गारंटी के लिए कड़ाई से जरूरी नहीं है।

कंट्रास्ट यह फिर से एक कार्यात्मक प्रोग्रामिंग भाषा while छोरों नहीं है कि के साथ: इसका मतलब यह है तो आप करेंगे जरूरत प्रत्यावर्तन; जो बदले में है कि भाषा को यह सुनिश्चित करना चाहिए कि, कई पुनरावृत्तियों के साथ, ढेर अतिप्रवाह एक समस्या नहीं बनेंगे; इस प्रकार ऐसी भाषा के लिए आधिकारिक मानक पूंछ कॉल अनुकूलन निर्धारित करना चुन सकता है।


पी.एस .: नोट पूंछ कॉल अनुकूलन के लिए मेरी तर्क में मामूली दोष। अंत में, मैं ढेर अतिप्रवाह का उल्लेख करता हूं। लेकिन कौन कहता है कि फ़ंक्शन कॉल को हमेशा स्टैक की आवश्यकता होती है? कुछ प्लेटफार्मों पर, फ़ंक्शन कॉल को पूरी तरह से अलग तरीके से कार्यान्वित किया जा सकता है, और स्टैक ओवरफ़्लो कभी भी समस्या नहीं होगी। एक मानक में पूंछ कॉल अनुकूलन निर्धारित करने के खिलाफ यह एक और तर्क होगा। (लेकिन मुझे गलत मत समझो, मैं इस तरह के अनुकूलन की योग्यता देख सकता हूं, यहां तक ​​कि ढेर के बिना भी!)

+0

हालांकि कार्यान्वित किया गया, फ़ंक्शन कॉल के सामान्य मामले को हमेशा कुछ राज्यों को सहेजने और पुनर्स्थापित करने की आवश्यकता होगी। इसलिए, हमेशा ऐसे कार्य होंगे जैसे कि बहुत से नेस्टेड फ़ंक्शन कॉल इस स्थिति को संग्रहीत करने के लिए उपलब्ध स्मृति को भरते हैं। इसके लिए पारंपरिक डेटा संरचना एक निश्चित स्मृति ब्लॉक में एक ढेर है लेकिन इसे अलग-अलग किया जा सकता है। पूंछ कॉल उन्मूलन इस बचत और कुछ कार्यों के लिए बहाल करने के लिए, लेकिन एक nontrivial कार्य है जो अपने आप में दो बार कॉल दूसरी कॉल के लिए राज्य की दुकान करने की आवश्यकता होगी बच सकते हैं। – jilles

+0

@ जेलीज़: बिल्कुल, पूंछ कॉल अनुकूलन स्मृति को संरक्षित रखने में मदद कर सकता है इससे कोई फर्क नहीं पड़ता कि फंक्शन कॉल कैसे काम करते हैं।हालांकि, सीपीयू स्टैक की एक विशेषता यह है कि यह आमतौर पर क्षमता में अपेक्षाकृत सीमित है; उदा। ढेर स्मृति। यही कारण है कि मैंने स्टैक ओवरफ्लो का उल्लेख किया, लेकिन अधिक सामान्य स्मृति की स्थिति नहीं; मैंने माना कि आपको कम करने के लिए लगभग अविश्वसनीय रूप से रिकर्सन की आवश्यकता होगी उदा। 2 जीबी मेमोरी। – stakx

3

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

चूंकि पूंछ कॉल अनुकूलन हमेशा वांछनीय नहीं है, इसलिए इसे संकलक लेखकों को जरूरी नहीं समझता है।

0

ऐसी स्थितियां हैं, जहां पूंछ कॉल अनुकूलन संभावित रूप से एबीआई को तोड़ देगा या कम से कम एक अर्थपूर्ण संरक्षण के तरीके में लागू करना बहुत कठिन होगा। उदाहरण के लिए साझा पुस्तकालयों में स्थिति स्वतंत्र कोड के बारे में सोचें: कुछ प्लेटफ़ॉर्म प्रोग्राम को मुख्य स्मृति को सहेजने के लिए गतिशील रूप से लिंक करने की अनुमति देते हैं जब विभिन्न विभिन्न अनुप्रयोग समान कार्यक्षमता पर निर्भर करते हैं। ऐसे मामलों में, लाइब्रेरी को एक बार लोड किया जाता है और प्रोग्राम की वर्चुअल मेमोरी में मैप किया जाता है जैसे कि यह सिस्टम पर एकमात्र एप्लीकेशन था। यूनिक्स पर और कुछ अन्य प्रणालियों पर, यह पुस्तकालयों के लिए स्थिति स्वतंत्र कोड का उपयोग करके हासिल किया जाता है, ताकि संबोधित एक निश्चित पता स्थान के बजाय ऑफसेट से संबंधित हो। हालांकि, कई प्लेटफ़ॉर्म पर, स्वतंत्र कोड की स्थिति को पूंछ कॉल अनुकूलित नहीं किया जाना चाहिए। इसमें शामिल समस्या यह है कि कार्यक्रम के माध्यम से नेविगेट करने के लिए ऑफसेट को रजिस्टरों में रखा जाना चाहिए; इंटेल 32-बिट पर, %ebx का उपयोग किया जाता है जो एक कैली सहेजा गया रजिस्टर है; अन्य प्लेटफॉर्म उस धारणा का पालन करते हैं। सामान्य कॉल का उपयोग करके फ़ंक्शंस के विपरीत, पूंछ कॉलों को तैनात करने वाले लोगों को कैलरी सेव किए गए रजिस्टरों को सबराउटिन पर ब्रांच करने से पहले पुनर्स्थापित करना होता है, न कि जब वे स्वयं लौटते हैं। आम तौर पर, यह कोई समस्या नहीं है, क्योंकि इस बिंदु पर, शीर्ष कॉलिंग फ़ंक्शन %ebx में संग्रहीत मूल्य की परवाह नहीं करता है, लेकिन स्वतंत्र कोड स्थिति प्रत्येक कूद, कॉल या शाखा कमांड पर इस मान पर निर्भर करती है।

अन्य समस्याएं ऑब्जेक्ट उन्मुख भाषाओं (सी ++) में क्लीन-अप लंबित हो सकती हैं, जिसका अर्थ है कि फ़ंक्शन में अंतिम कॉल वास्तव में अंतिम कॉल नहीं है - क्लीन-अप हैं। इसलिए, जब यह मामला होता है तो संकलक आमतौर पर अनुकूलित नहीं होता है।

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

शायद अधिक तकनीकी कारणों के बारे में सोच सकते हैं। ये कुछ विचार हैं।

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