कंस्ट्रैक्स फ़ंक्शन मूल्यांकन कर सकते हैं पूंछ रिकर्सन ऑप्टिमाइज़ेशन

Question

मुझे आश्चर्य है कि लंबे लूप के लिए हम सी ++ 11 में कॉन्टेक्सप्र के लिए पूंछ रिकर्सन का लाभ उठा सकते हैं?

Answer 1

[implimits] में नियमों के अनुसार, एक कार्यान्वयन को constexpr गणनाओं पर रिकर्सन गहराई सीमा डालने की अनुमति है। दो कंपाइलर जिनके पास constexpr कार्यान्वयन (जीसीसी और क्लैंग) दोनों मानक हैं, मानक द्वारा सुझाए गए 512 रिकर्सिव कॉल के डिफ़ॉल्ट का उपयोग करके ऐसी सीमा लागू करते हैं। इन दोनों कंपाइलरों के साथ-साथ मानक के सुझावों का पालन करने वाले किसी भी अन्य कार्यान्वयन के लिए, पूंछ रिकर्सन ऑप्टिमाइज़ेशन अनिवार्य रूप से ज्ञानी नहीं होगा (जब तक कि संकलक अन्य रिकर्सन सीमा तक पहुंचने से पहले क्रैश न हो)।

एक कार्यान्वयन इसके बजाय केवल कॉल गिनने का चयन कर सकता है जिसके लिए यह अपनी रिकर्सन गहराई सीमा में पूंछ-रिकर्सन ऑप्टिमाइज़ेशन लागू नहीं कर सकता है, या ऐसी सीमा प्रदान नहीं कर सकता है। हालांकि, ऐसा कार्यान्वयन संभवतः अपने उपयोगकर्ताओं के लिए असंतोष कर रहा है, क्योंकि यह या तो क्रैश होने की संभावना होगी (एक स्टैक ओवरफ़्लो के कारण) या constexpr मूल्यांकनों को समाप्त करने में विफल रहता है जो गहराई से या असीमित रूप से भर्ती करते हैं।

पुनरावृत्ति गहराई सीमा तक पहुंचने पर क्या होता है इसके संबंध में, पब्बी का उदाहरण एक दिलचस्प बिंदु उठाता है। [expr.const]p2 निर्दिष्ट करता है कि

एक constexpr समारोह या एक constexpr निर्माता की एक मंगलाचरण कि कार्यान्वयन-de फाई नेड प्रत्यावर्तन सीमाएं पार हो जाएंगी (अनुबंध बी देखें);

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

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) { 
    return n ? f(n-1,s+n) : s; 
} 
constexpr unsigned long long k = f(0xffffffff); 

जीसीसी का कहना है:

depthlimit.cpp:4:46: in constexpr expansion of ‘f(4294967295ull, 0ull)’ 
depthlimit.cpp:2:23: in constexpr expansion of ‘f((n + -1ull), (s + n))’ 
depthlimit.cpp:2:23: in constexpr expansion of ‘f((n + -1ull), (s + n))’ 
[... over 500 more copies of the previous message cut ...] 
depthlimit.cpp:2:23: in constexpr expansion of ‘f((n + -1ull), (s + n))’ 
depthlimit.cpp:4:46: error: constexpr evaluation depth exceeds maximum of 512 (use -fconstexpr-depth= to increase the maximum) 

और बजना का कहना है:

depthlimit.cpp:4:30: error: constexpr variable 'k' must be initialized by a constant expression 
constexpr unsigned long long k = f(0xffffffff); 
          ^ ~~~~~~~~~~~~~ 
depthlimit.cpp:2:14: note: constexpr evaluation exceeded maximum depth of 512 calls 
    return n ? f(n-1,s+n) : s; 
      ^
depthlimit.cpp:2:14: note: in call to 'f(4294966784, 2194728157440)' 
depthlimit.cpp:2:14: note: in call to 'f(4294966785, 2190433190655)' 
depthlimit.cpp:2:14: note: in call to 'f(4294966786, 2186138223869)' 
depthlimit.cpp:2:14: note: in call to 'f(4294966787, 2181843257082)' 
depthlimit.cpp:2:14: note: in call to 'f(4294966788, 2177548290294)' 
depthlimit.cpp:2:14: note: (skipping 502 calls in backtrace; use -fconstexpr-backtrace-limit=0 to see all) 
depthlimit.cpp:2:14: note: in call to 'f(4294967291, 17179869174)' 
depthlimit.cpp:2:14: note: in call to 'f(4294967292, 12884901882)' 
depthlimit.cpp:2:14: note: in call to 'f(4294967293, 8589934589)' 
depthlimit.cpp:2:14: note: in call to 'f(4294967294, 4294967295)' 
depthlimit.cpp:4:34: note: in call to 'f(4294967295, 0)' 
constexpr unsigned long long k = f(0xffffffff); 
           ^

ताकि मूल्यांकन होने की आवश्यकता नहीं है हम कोड को संशोधित करते हैं अनुवाद समय पर:

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) { 
    return n ? f(n-1,s+n) : s; 
} 
int main(int, char *[]) { 
    return f(0xffffffff); 
} 

तो दोनों कंपाइलर इसे स्वीकार करते हैं, और कोड उत्पन्न करते हैं जो रनटाइम पर परिणाम की गणना करता है। -O0 के साथ निर्माण करते समय, यह कोड स्टैक ओवरफ़्लो के कारण विफल रहता है। -O2 के साथ निर्माण करते समय, कंपाइलर्स के ऑप्टिमाइज़र कोड को पुनर्नवीनीकरण और कोड फ़ंक्शन का सही उपयोग करने के लिए परिवर्तित करते हैं (लेकिन ध्यान दें कि यह पूंछ रिकर्सन constexpr मूल्यांकन से संबंधित नहीं है)।

Answer 2

मैंने देखा है कि जीसीसी इस अनुकूलन को निष्पादित करता है। यहां एक उदाहरण दिया गया है:

constexpr unsigned long long fun1(unsigned long long n, unsigned long long sum = 0) { 
    return (n != 0) ? fun1(n-1,sum+n) : sum; 
} 
fun1(0xFFFFFFFF); 

-O2 पर काम करता है, अन्यथा क्रैश होता है।

हैरानी की बात है, यह भी इस के अनुकूलन है:

constexpr unsigned long long fun2(unsigned long long n) { 
    return (n != 0) ? n + fun2(n-1) : 0; 
} 

मैं गैर conspexpr प्रपत्र के disassembly की जाँच है और मुझे लगता है कि यह एक पाश में अनुकूलित किया जा रहा है इस बात की पुष्टि कर सकते हैं।

लेकिन यह नहीं:

constexpr unsigned long long fun3(unsigned long long n) { 
    return (n != 0) ? n + fun3(n-1) + fun3(n-1) : 0; 
} 

तो निष्कर्ष में, जीसीसी एक पाश ही यह गैर consexpr कार्यों के लिए करता है में अनुकूलित करेंगे। कम से कम-ओ 2 और ऊपर का प्रयोग करें।

Answer 3

मुझे नहीं लगता कि यह क्यों संभव नहीं हो सकता है, हालांकि यह कार्यान्वयन विस्तार की गुणवत्ता है।

यह, उदाहरण के लिए टेम्पलेट्स के लिए Memoization उपयोग करने के लिए इतना है कि compilers नहीं रह पर गला घोंटना परंपरागत किया गया है:

template <size_t N> 
struct Fib { static size_t const value = Fib <N-1>::value + Fib<N-2>::value; }; 

template <> 
struct Fib<1> { static size_t const value = 1; } 

template <> 
struct Fib<0> { static size_t const value = 0; } 

लेकिन इसके बजाय पहले से ही गणना की मूल्य memoize हे करने के लिए अपने मूल्यांकन की जटिलता को कम करने के लिए (एन) ।

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

स्टैंडर्ड 5.19 [expr.const] में कहते हैं:

2/ए सशर्त अभिव्यक्ति एक कोर निरंतर अभिव्यक्ति है जब तक कि यह एक संभावित का मूल्यांकन उपसूचक (3.2) के रूप में निम्न में से एक [शामिल ...]:

• एक कॉन्स्टेक्स फ़ंक्शन या कॉन्स्टेक्सर कन्स्ट्रक्टर का एक आमंत्रण जो कार्यान्वयन परिभाषित सीमाओं से अधिक होगा (अनुलग्नक बी देखें);

और पढ़ने अनुलग्नक बी:

2/सीमा मात्रा है कि नीचे या दूसरों वर्णित शामिल विवश कर सकते हैं। प्रत्येक मात्रा के बाद ब्रैकेट किए गए नंबर को उस मात्रा के लिए न्यूनतम के रूप में अनुशंसित किया जाता है। हालांकि, ये मात्रा केवल दिशानिर्देश हैं और अनुपालन निर्धारित नहीं करते हैं।

• रिकर्सिव कॉन्स्टेक्स फ़ंक्शन इनवोकेशंस [512]।

पूंछ रिकर्सन ब्रूश नहीं किया गया है।

Answer 4

मुझे यकीन नहीं है कि मैं समझ रहा हूं कि आप क्या पूछ रहे हैं।यदि यह से संबंधित है, तो संकलक पूंछ रिकर्सन को लूप में परिवर्तित कर देगा, यह निर्दिष्ट नहीं है, चाहे फ़ंक्शन constexpr है या नहीं। यदि यह है कि रिकर्सिव फ़ंक्शन constexpr हो सकता है, तो मुझे नहीं लगता कि पूंछ रिकर्सन प्रासंगिक है। अगर मैं सही ढंग मानक पढ़ें:

constexpr unsigned ack(unsigned m, unsigned n) 
{ 
    return m == 0 
     ? n + 1 
     : n == 0 
     ? ack(m - 1, 1) 
     : ack(m - 1, ack(m, n - 1)); 
} 

(एक वैध constexpr है, हालांकि मैं उम्मीद संकलक के बारे में एक लेकिन सभी के लिए संसाधनों की कमी सबसे छोटी n और m शिकायत, कम से कम यदि समारोह में प्रयोग किया जाता है एक संदर्भ जिसके लिए निरंतर अभिव्यक्ति की आवश्यकता होती है)।

Answer 5

"टेल कॉल" शायद शुरुआत करने के लिए एक गलत नाम है। constexpr फ़ंक्शंस गणितीय कार्यों के बहुत करीब हैं। गणितीय कार्य के लिए, निम्न दो कार्य समान हैं:

constexpr unsigned long long fun1(unsigned long long n) { 
    if (n == 0) return 0 ; 
    return n + fun1(n-1); 
} 
constexpr unsigned long long fun2(unsigned long long n) { 
    if (n != 0) return n + fun2(n-1); 
    return 0; 
} 

अभी तक एक प्रक्रियात्मक प्रोग्रामिंग दृष्टिकोण से वे निश्चित रूप से नहीं कर रहे हैं। केवल पहला ही पूंछ कॉल अनुकूलन के लिए उधार देने लगता है।