इनलाइन कैशिंग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
== रनटाइम विधि बाध्यकारी == | == रनटाइम विधि बाध्यकारी == | ||
निम्नलिखित [[ECMAScript]] फ़ंक्शन एक ऑब्जेक्ट प्राप्त करता है, इसकी toString-विधि को आमंत्रित करता है और उस पृष्ठ पर परिणाम प्रदर्शित करता है जिसमें स्क्रिप्ट एम्बेड की गई है। | निम्नलिखित [[ECMAScript]] फ़ंक्शन एक ऑब्जेक्ट प्राप्त करता है, इसकी toString-विधि को आमंत्रित करता है और उस पृष्ठ पर परिणाम प्रदर्शित करता है जिसमें स्क्रिप्ट एम्बेड की गई है।<syntaxhighlight lang="d"> | ||
function dump(obj) { | |||
document.write(obj.toString()); | |||
} | |||
</syntaxhighlight> | |||
चूंकि ऑब्जेक्ट का प्रकार निर्दिष्ट नहीं है और संभावित विधि ओवरलोडिंग के कारण, यह समय से पहले तय करना असंभव है कि toString-विधि का कौन सा ठोस कार्यान्वयन लागू किया जा रहा है। इसके बजाय, रनटाइम पर डायनेमिक लुकअप किया जाना चाहिए। लैंग्वेज रनटाइम में जो कैशिंग के किसी रूप को नियोजित नहीं करते हैं, यह लुकअप हर बार एक विधि लागू होने पर किया जाता है। चूंकि विधियों को इनहेरिटेंस (कंप्यूटर विज्ञान) से नीचे कई चरणों में परिभाषित किया जा सकता है, एक गतिशील लुकअप एक महंगा ऑपरेशन हो सकता है। | चूंकि ऑब्जेक्ट का प्रकार निर्दिष्ट नहीं है और संभावित विधि ओवरलोडिंग के कारण, यह समय से पहले तय करना असंभव है कि toString-विधि का कौन सा ठोस कार्यान्वयन लागू किया जा रहा है। इसके बजाय, रनटाइम पर डायनेमिक लुकअप किया जाना चाहिए। लैंग्वेज रनटाइम में जो कैशिंग के किसी रूप को नियोजित नहीं करते हैं, यह लुकअप हर बार एक विधि लागू होने पर किया जाता है। चूंकि विधियों को इनहेरिटेंस (कंप्यूटर विज्ञान) से नीचे कई चरणों में परिभाषित किया जा सकता है, एक गतिशील लुकअप एक महंगा ऑपरेशन हो सकता है। | ||
| Line 20: | Line 22: | ||
== मोनोमोर्फिक इनलाइन कैशिंग == | == मोनोमोर्फिक इनलाइन कैशिंग == | ||
यदि कोई विशेष कॉल साइट अक्सर विभिन्न प्रकार की वस्तुओं को देखती है, तो इनलाइन कैशिंग के प्रदर्शन लाभ को कॉल साइट की स्थिति में लगातार परिवर्तन से प्रेरित ओवरहेड द्वारा आसानी से समाप्त किया जा सकता है। निम्नलिखित उदाहरण मोनोमोर्फिक इनलाइन कैशिंग के लिए सबसे खराब स्थिति का गठन करता है: | यदि कोई विशेष कॉल साइट अक्सर विभिन्न प्रकार की वस्तुओं को देखती है, तो इनलाइन कैशिंग के प्रदर्शन लाभ को कॉल साइट की स्थिति में लगातार परिवर्तन से प्रेरित ओवरहेड द्वारा आसानी से समाप्त किया जा सकता है। निम्नलिखित उदाहरण मोनोमोर्फिक इनलाइन कैशिंग के लिए सबसे खराब स्थिति का गठन करता है:<syntaxhighlight lang="d"> | ||
var values = [1, "a", 2, "b", 3, "c", 4, "d"]; | |||
for (var i in values) { | |||
document.write(values[i].toString()); | |||
} | |||
</syntaxhighlight> | |||
दोबारा, विधि टूस्ट्रिंग को उस ऑब्जेक्ट पर लागू किया जाता है जिसका प्रकार पहले से ज्ञात नहीं है। हालांकि इससे भी महत्वपूर्ण बात यह है कि आस-पास के लूप के प्रत्येक पुनरावृत्ति के साथ वस्तु का प्रकार बदल जाता है। मोनोमोर्फिक इनलाइन कैशिंग का एक सहज कार्यान्वयन इसलिए निरंतर अनियमित और मोनोमोर्फिक राज्यों के माध्यम से चक्रित होगा। ऐसा होने से रोकने के लिए, मोनोमॉर्फिक इनलाइन कैशिंग के अधिकांश कार्यान्वयन एक तीसरे राज्य का समर्थन करते हैं जिसे अक्सर मेगामॉर्फिक राज्य कहा जाता है। यह स्थिति तब दर्ज की जाती है जब किसी विशेष कॉल साइट ने विभिन्न प्रकार की पूर्व निर्धारित संख्या देखी हो। एक बार जब कोई कॉल साइट मेगामॉर्फिक स्थिति में प्रवेश कर जाती है, तो यह वैसा ही व्यवहार करेगी जैसा कि उसने गैर-प्रारंभिक स्थिति में किया था, इस अपवाद के साथ कि वह फिर कभी मोनोमोर्फिक स्थिति में प्रवेश नहीं करेगी (मोनोमोर्फिक इनलाइन कैशिंग के कुछ कार्यान्वयन मेगामॉर्फिक कॉल साइटों को वापस गैर-प्रारंभिक होने के लिए बदल देंगे) एक निश्चित समय बीत जाने के बाद या एक बार पूर्ण [[कचरा संग्रह (कंप्यूटर विज्ञान)]] चक्र किया जाता है)। | दोबारा, विधि टूस्ट्रिंग को उस ऑब्जेक्ट पर लागू किया जाता है जिसका प्रकार पहले से ज्ञात नहीं है। हालांकि इससे भी महत्वपूर्ण बात यह है कि आस-पास के लूप के प्रत्येक पुनरावृत्ति के साथ वस्तु का प्रकार बदल जाता है। मोनोमोर्फिक इनलाइन कैशिंग का एक सहज कार्यान्वयन इसलिए निरंतर अनियमित और मोनोमोर्फिक राज्यों के माध्यम से चक्रित होगा। ऐसा होने से रोकने के लिए, मोनोमॉर्फिक इनलाइन कैशिंग के अधिकांश कार्यान्वयन एक तीसरे राज्य का समर्थन करते हैं जिसे अक्सर मेगामॉर्फिक राज्य कहा जाता है। यह स्थिति तब दर्ज की जाती है जब किसी विशेष कॉल साइट ने विभिन्न प्रकार की पूर्व निर्धारित संख्या देखी हो। एक बार जब कोई कॉल साइट मेगामॉर्फिक स्थिति में प्रवेश कर जाती है, तो यह वैसा ही व्यवहार करेगी जैसा कि उसने गैर-प्रारंभिक स्थिति में किया था, इस अपवाद के साथ कि वह फिर कभी मोनोमोर्फिक स्थिति में प्रवेश नहीं करेगी (मोनोमोर्फिक इनलाइन कैशिंग के कुछ कार्यान्वयन मेगामॉर्फिक कॉल साइटों को वापस गैर-प्रारंभिक होने के लिए बदल देंगे) एक निश्चित समय बीत जाने के बाद या एक बार पूर्ण [[कचरा संग्रह (कंप्यूटर विज्ञान)]] चक्र किया जाता है)। | ||
Revision as of 16:27, 2 March 2023
इनलाइन कैशिंग कुछ रन-टाइम सिस्टम द्वारा नियोजित एक संकलक अनुकूलन है, और पहले स्मॉलटाक के लिए विकसित किया गया था।[1]
इनलाइन कैशिंग का लक्ष्य सीधे कॉल साइट पर पिछले विधि लुकअप के परिणामों को याद करके गतिशील प्रेषण को गति देना है। इनलाइन कैशिंग गतिशील टाइपिंग भाषाओं के लिए विशेष रूप से उपयोगी है, जहाँ अधिकांश विधि बाइंडिंग रनटाइम पर होती है और जहाँ वर्चुअल विधि तालिकाओं का अक्सर उपयोग नहीं किया जा सकता है।
रनटाइम विधि बाध्यकारी
निम्नलिखित ECMAScript फ़ंक्शन एक ऑब्जेक्ट प्राप्त करता है, इसकी toString-विधि को आमंत्रित करता है और उस पृष्ठ पर परिणाम प्रदर्शित करता है जिसमें स्क्रिप्ट एम्बेड की गई है।
function dump(obj) {
document.write(obj.toString());
}
चूंकि ऑब्जेक्ट का प्रकार निर्दिष्ट नहीं है और संभावित विधि ओवरलोडिंग के कारण, यह समय से पहले तय करना असंभव है कि toString-विधि का कौन सा ठोस कार्यान्वयन लागू किया जा रहा है। इसके बजाय, रनटाइम पर डायनेमिक लुकअप किया जाना चाहिए। लैंग्वेज रनटाइम में जो कैशिंग के किसी रूप को नियोजित नहीं करते हैं, यह लुकअप हर बार एक विधि लागू होने पर किया जाता है। चूंकि विधियों को इनहेरिटेंस (कंप्यूटर विज्ञान) से नीचे कई चरणों में परिभाषित किया जा सकता है, एक गतिशील लुकअप एक महंगा ऑपरेशन हो सकता है।
बेहतर प्रदर्शन प्राप्त करने के लिए, कई भाषा रनटाइम कुछ प्रकार के गैर-इनलाइन कैशिंग को नियोजित करते हैं जहां सीमित संख्या में विधि लुकअप के परिणाम एक सहयोगी डेटा संरचना में संग्रहीत होते हैं। यह प्रदर्शन को बहुत बढ़ा सकता है, बशर्ते कि निष्पादित प्रोग्राम कैश फ्रेंडली हों (अर्थात सीमित तरीकों का एक सेट है जिसे बार-बार लागू किया जाता है)। इस डेटा संरचना को आमतौर पर प्रथम-स्तरीय विधि लुकअप कैश कहा जाता है।[1]
इनलाइन कैशिंग
इनलाइन कैशिंग की अवधारणा अनुभवजन्य अवलोकन पर आधारित है कि किसी विशेष कॉल साइट पर होने वाली वस्तुएँ अक्सर एक ही प्रकार की होती हैं। उन मामलों में, विधि लुकअप इनलाइन के परिणाम को संग्रहीत करके, यानी सीधे कॉल साइट पर प्रदर्शन को बहुत बढ़ाया जा सकता है। इस प्रक्रिया को सुविधाजनक बनाने के लिए, कॉल साइटों को अलग-अलग राज्यों को सौंपा गया है। प्रारंभ में, एक कॉल साइट को अप्रारंभीकृत माना जाता है। एक बार जब भाषा रनटाइम एक विशेष गैर-प्रारंभिक कॉल साइट पर पहुंच जाता है, तो यह गतिशील लुकअप करता है, परिणाम को कॉल साइट पर संग्रहीत करता है और इसकी स्थिति को मोनोमोर्फिक में बदल देता है। यदि भाषा रनटाइम उसी कॉल साइट पर फिर से पहुंचता है, तो यह कैली को इससे प्राप्त करता है और बिना किसी और लुकअप के सीधे इसे आमंत्रित करता है। इस संभावना को ध्यान में रखते हुए कि एक ही कॉल साइट पर विभिन्न प्रकार की वस्तुएं हो सकती हैं, भाषा रनटाइम को कोड में गार्ड (कंप्यूटिंग) भी सम्मिलित करना पड़ता है। आमतौर पर, इन्हें कॉल साइट के बजाय कॉल साइट की बजाय शाखा भविष्यवक्ता के बेहतर उपयोग के लिए डाला जाता है और प्रत्येक कॉल साइट पर प्रस्तावना बनाम कई प्रतियों में एक प्रति के कारण जगह बचाने के लिए डाला जाता है। यदि एक कॉल साइट जो मोनोमोर्फिक स्थिति में है, उसकी अपेक्षा के अलावा किसी अन्य प्रकार का सामना करती है, तो उसे वापस गैर-प्रारंभिक स्थिति में बदलना होगा और फिर से एक पूर्ण गतिशील लुकअप करना होगा।
विहित कार्यान्वयन [1] कॉल निर्देश के बाद स्थिरांक का एक रजिस्टर लोड है। असिंचित स्थिति को अनलिंक्ड कहा जाता है। रजिस्टर को संदेश चयनकर्ता (आमतौर पर किसी वस्तु का पता) के साथ लोड किया जाता है और कॉल रन-टाइम रूटीन के लिए होता है, जो वर्तमान रिसीवर की कक्षा में संदेश को देखेगा, ऊपर प्रथम-स्तरीय विधि लुकअप कैश का उपयोग करके . रन-टाइम रूटीन तब निर्देशों को फिर से लिखता है, वर्तमान रिसीवर के प्रकार के साथ रजिस्टर को लोड करने के लिए लोड निर्देश को बदलता है, और लक्ष्य विधि की प्रस्तावना को कॉल करने के लिए कॉल निर्देश, अब कॉल साइट को लक्ष्य विधि से जोड़ता है। प्रस्तावना के तुरंत बाद निष्पादन जारी रहता है। एक बाद का निष्पादन प्रस्तावना को सीधे बुलाएगा। प्रस्तावना तब वर्तमान रिसीवर के प्रकार को प्राप्त करती है और इसकी तुलना रजिस्टर में करती है; यदि वे सहमत हैं कि रिसीवर एक ही प्रकार का है और विधि निष्पादित होती रहती है। यदि नहीं, तो प्रस्तावना फिर से रन-टाइम को कॉल करती है और विभिन्न रणनीतियाँ संभव हैं, एक नए रिसीवर प्रकार के लिए कॉल-साइट को फिर से जोड़ना।
प्रथम-स्तरीय विधि लुकअप कैश के लिए कम से कम एक प्रकार की तुलना और एक चयनकर्ता तुलना के बजाय एक प्रकार की तुलना करने और प्रत्यक्ष कॉल का उपयोग करने से प्रदर्शन लाभ प्राप्त होता है (जो निर्देश प्रीफ़ेच और पाइप-लाइनिंग से लाभान्वित होगा) विधि-लुकअप या व्यवहार्य प्रेषण में अप्रत्यक्ष कॉल के विपरीत।
मोनोमोर्फिक इनलाइन कैशिंग
यदि कोई विशेष कॉल साइट अक्सर विभिन्न प्रकार की वस्तुओं को देखती है, तो इनलाइन कैशिंग के प्रदर्शन लाभ को कॉल साइट की स्थिति में लगातार परिवर्तन से प्रेरित ओवरहेड द्वारा आसानी से समाप्त किया जा सकता है। निम्नलिखित उदाहरण मोनोमोर्फिक इनलाइन कैशिंग के लिए सबसे खराब स्थिति का गठन करता है:
var values = [1, "a", 2, "b", 3, "c", 4, "d"];
for (var i in values) {
document.write(values[i].toString());
}
दोबारा, विधि टूस्ट्रिंग को उस ऑब्जेक्ट पर लागू किया जाता है जिसका प्रकार पहले से ज्ञात नहीं है। हालांकि इससे भी महत्वपूर्ण बात यह है कि आस-पास के लूप के प्रत्येक पुनरावृत्ति के साथ वस्तु का प्रकार बदल जाता है। मोनोमोर्फिक इनलाइन कैशिंग का एक सहज कार्यान्वयन इसलिए निरंतर अनियमित और मोनोमोर्फिक राज्यों के माध्यम से चक्रित होगा। ऐसा होने से रोकने के लिए, मोनोमॉर्फिक इनलाइन कैशिंग के अधिकांश कार्यान्वयन एक तीसरे राज्य का समर्थन करते हैं जिसे अक्सर मेगामॉर्फिक राज्य कहा जाता है। यह स्थिति तब दर्ज की जाती है जब किसी विशेष कॉल साइट ने विभिन्न प्रकार की पूर्व निर्धारित संख्या देखी हो। एक बार जब कोई कॉल साइट मेगामॉर्फिक स्थिति में प्रवेश कर जाती है, तो यह वैसा ही व्यवहार करेगी जैसा कि उसने गैर-प्रारंभिक स्थिति में किया था, इस अपवाद के साथ कि वह फिर कभी मोनोमोर्फिक स्थिति में प्रवेश नहीं करेगी (मोनोमोर्फिक इनलाइन कैशिंग के कुछ कार्यान्वयन मेगामॉर्फिक कॉल साइटों को वापस गैर-प्रारंभिक होने के लिए बदल देंगे) एक निश्चित समय बीत जाने के बाद या एक बार पूर्ण कचरा संग्रह (कंप्यूटर विज्ञान) चक्र किया जाता है)।
पॉलिमॉर्फिक इनलाइन कैशिंग
कॉल साइटों से बेहतर ढंग से निपटने के लिए जो अक्सर सीमित संख्या में विभिन्न प्रकारों को देखते हैं, कुछ भाषा रनटाइम पॉलीमॉर्फिक इनलाइन कैशिंग नामक तकनीक का उपयोग करते हैं।[2] पॉलीमॉर्फिक इनलाइन कैशिंग के साथ, एक बार एक कॉल साइट जो अपने मोनोमोर्फिक अवस्था में होती है, वह अपने दूसरे प्रकार को देखती है, न कि गैर-प्रारंभिक स्थिति में वापस आने के बजाय यह पॉलीमॉर्फिक नामक एक नए राज्य में बदल जाती है। एक बहुरूपी कॉल साइट यह तय करती है कि वर्तमान में प्रस्तुत किए जाने वाले प्रकार के आधार पर कौन सी ज्ञात विधियों का एक सीमित सेट है। दूसरे शब्दों में, बहुरूपी इनलाइन कैशिंग के साथ, एक ही कॉल साइट पर एकाधिक विधि लुकअप परिणाम रिकॉर्ड किए जा सकते हैं। चूंकि किसी प्रोग्राम में प्रत्येक कॉल साइट संभावित रूप से सिस्टम में प्रत्येक प्रकार को देख सकती है, आमतौर पर प्रत्येक कॉल साइट पर कितने लुकअप परिणाम रिकॉर्ड किए जाते हैं, इसकी ऊपरी सीमा होती है। एक बार उस ऊपरी सीमा तक पहुँचने के बाद, कॉल साइट्स मेगामॉर्फिक हो जाती हैं और कोई और इनलाइन कैशिंग नहीं की जाती है।
विहित कार्यान्वयन [2]एक जंप टेबल है जिसमें एक प्रस्तावना होती है जो रिसीवर के प्रकार को प्राप्त करती है और निरंतर तुलना और सशर्त कूद की एक श्रृंखला होती है जो प्रत्येक रिसीवर प्रकार के लिए प्रासंगिक विधि में प्रस्तावना के बाद कोड पर कूदती है। जब एक मोनोमोर्फिक कॉल-साइट एक अलग प्रकार का सामना करती है तो जंप टेबल को आम तौर पर एक विशेष कॉल-साइट के लिए आवंटित किया जाता है। जंप-टेबल का एक निश्चित आकार होगा और बढ़ने में सक्षम होगा, नए प्रकार के मामलों को जोड़ते हुए मामलों की कुछ छोटी अधिकतम संख्या जैसे 4, 6 या 8 तक सामने आती है। एक बार जब यह एक नए रिसीवर प्रकार के लिए अपने अधिकतम आकार के निष्पादन तक पहुँच जाता है अंत में गिर जाएगा और रन-टाइम में प्रवेश करेगा, आमतौर पर प्रथम-स्तरीय विधि कैश से शुरू होने वाली विधि लुकअप करने के लिए।
अवलोकन कि एक साथ, मोनोमोर्फिक और पॉलीमॉर्फिक इनलाइन कैश प्रति-कॉल-साइट रिसीवर प्रकार की जानकारी को प्रोग्राम निष्पादन के अनुकूलन के दुष्प्रभाव के रूप में एकत्र करते हैं[2]स्व (प्रोग्रामिंग भाषा) में अनुकूली अनुकूलन के विकास के लिए नेतृत्व किया, जहां रन-टाइम सट्टा इनलाइनिंग निर्णयों को निर्देशित करने के लिए इनलाइन कैश में प्रकार की जानकारी का उपयोग करके कार्यक्रम में हॉट स्पॉट का अनुकूलन करता है।
मेगामॉर्फिक इनलाइन कैशिंग
यदि एक रन-टाइम मोनोमॉर्फिक और पॉलीमॉर्फिक इनलाइन कैशिंग दोनों का उपयोग करता है तो स्थिर स्थिति में केवल अनलिंक किए गए प्रेषण पॉलीमॉर्फिक इनलाइन कैश के गिरने वाले छोरों से होते हैं। चूंकि ऐसे प्रेषण धीमे होते हैं इसलिए अब इन साइटों को अनुकूलित करना लाभदायक हो सकता है। किसी विशेष कॉल-साइट के लिए प्रथम-स्तरीय विधि लुकअप करने के लिए कोड बनाकर मेगामॉर्फिक इनलाइन कैश को लागू किया जा सकता है। इस योजना में एक बार एक पॉलीमॉर्फिक इनलाइन कैश के अंत में एक प्रेषण बंद हो जाता है, कॉल साइट के चयनकर्ता के लिए विशिष्ट मेगामॉर्फिक कैश बनाया जाता है (या यदि कोई पहले से मौजूद है तो साझा किया जाता है), और इसे कॉल करने के लिए भेजने वाली साइट को फिर से जोड़ा जाता है। सामान्य प्रथम-स्तरीय विधि लुकअप जांच की तुलना में कोड काफी अधिक कुशल हो सकता है क्योंकि चयनकर्ता अब एक स्थिर है, जो रजिस्टर दबाव को कम करता है, लुकअप और प्रेषण के लिए कोड को रन-टाइम में कॉल किए बिना निष्पादित किया जाता है, और प्रेषण कर सकता है शाखा भविष्यवक्ता से लाभ।
अनुभवजन्य माप [3] दिखाते हैं कि बड़े स्मॉलटॉक कार्यक्रमों में सक्रिय विधियों में सभी भेजने वाली साइटों में से लगभग 1/3 अनलिंक रहती हैं, और शेष 2/3 में से 90% मोनोमोर्फिक, 9% पॉलीमॉर्फिक और 1% (0.9%) मेगामॉर्फिक हैं।
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 1.2 L. Peter Deutsch, Allan M. Schiffman, "Efficient implementation of the smalltalk-80 system", POPL '84: Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, January 1984
- ↑ 2.0 2.1 2.2 Hölzle, U., Chambers, C., AND Ungar, D. 1991. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In Proceedings of the ECOOP ’91 Conference. Lecture Notes in Computer Science, vol. 512. Springer-Verlag, Berlin.
- ↑ PICs [was v8 first impressions] on the Strongtalk mailing list
