क्या फारो पूंछ-कॉल अनुकूलन प्रदान करता है?

Question

Pharo में Integer>>#factorial के कार्यान्वयन है:

factorial 
     "Answer the factorial of the receiver." 

     self = 0 ifTrue: [^ 1]. 
     self > 0 ifTrue: [^ self * (self - 1) factorial]. 
     self error: 'Not valid for negative integers' 

यह एक पूंछ पुनरावर्ती परिभाषा। हालांकि, मैं वर्कस्पेस में त्रुटि के बिना 10000 factorial का मूल्यांकन कर सकता हूं।

क्या फ़ारो किसी भी परिस्थिति में पूंछ-कॉल अनुकूलन करता है, क्या यह कुछ अन्य अनुकूलन कर रहा है, या क्या यह वास्तव में गहरे ढेर का उपयोग कर रहा है?

Answer 1

यह वास्तव में गहरी ढेर है। या बल्कि, बिल्कुल कोई ढेर नहीं।

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

इन सभी संदर्भ वस्तुओं को आवंटित करना महंगा है। गति के लिए, आधुनिक वीएम (जैसे कि फारो में इस्तेमाल किए गए कोग वीएम) वास्तव में आंतरिक रूप से एक स्टैक का उपयोग करते हैं, जिसमें लिंक किए गए पेज होते हैं, इसलिए यह मनमाने ढंग से भी बड़ा हो सकता है। संदर्भ ऑब्जेक्ट केवल मांग पर बनाए जाते हैं (उदा। डीबगिंग करते समय) और छिपे हुए स्टैक फ्रेम और इसके विपरीत देखें। दृश्यों के पीछे यह मशीनरी काफी जटिल है, लेकिन सौभाग्य से स्मॉलटाक प्रोग्रामर से छिपी हुई है।

Answer 2

फारो के निष्पादन मॉडल में कोई रहस्य नहीं है। पुनरावर्ती टुकड़ा

^ self * (self - 1) factorial 

कि दूसरी ifTrue: अंदर होता है bytecodes की निम्न क्रम को संकलित करता है:

39 <70> self     ; receiver of outer message * 
40 <70> self     ; receiver of inner message - 
41 <76> pushConstant: 1  ; argument of self - 1 
42 <B1> send: -    ; subtract 
43 <D0> send: factorial  ; send factorial (nothing special here!) 
44 <B8> send: *    ; multiply 
45 <7C> returnTop    ; return 

ध्यान दें कि लाइन में 43 विशेष कुछ नहीं होता। कोड सिर्फ factorial भेजता है वैसे ही, चयनकर्ता कोई अन्य था। विशेष रूप से हम देख सकते हैं कि यहां ढेर का कोई विशेष हेरफेर नहीं है।

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

अद्यतन

दिलचस्प है, गैर पुनरावर्ती संस्करण

factorial2 
    | f | 
    f := 1. 
    2 to: self do: [:i | f := f * i]. 
    ^f 

एक छोटा सा धीमी है कि पुनरावर्ती एक (Pharo)। कारण यह होना चाहिए कि बढ़ते i से जुड़े ओवरहेड रिकर्सिव प्रेषण तंत्र से थोड़ा अधिक है।

यहाँ भाव मैंने कोशिश कर रहे हैं:

[25000 factorial] timeToRun 
[25000 factorial2] timeToRun