इनलाइन कैशिंग
इनलाइन कैशिंग कुछ भाषा रन-टाइम प्रणाली द्वारा नियोजित संकलक अनुकूलन है, और यह सबसे पहले स्मॉलटाक के लिए विकसित किया गया था।[1]
इनलाइन कैशिंग का लक्ष्य सीधे कॉल साइट पर पिछले विधि लुकअप के परिणामों को याद करके रनटाइम विधि को आवश्यक गति देना है। इनलाइन कैशिंग गतिशील टाइपिंग भाषाओं के लिए विशेष रूप से उपयोगी है, जहाँ अधिकांश विधि आवश्यक रनटाइम पर होती है और जहाँ आभासी विधि तालिकाओं का अधिकांश उपयोग नहीं किया जा सकता है।
रनटाइम विधि बाध्यकारी
निम्नलिखित ईसीएमए स्क्रिप्ट फ़ंक्शन एक ऑब्जेक्ट प्राप्त करता है, इसकी टूस्ट्रिंग-विधि को आमंत्रित करता है और उस पृष्ठ पर परिणाम प्रदर्शित करता है जिसमें स्क्रिप्ट एम्बेड की गई है।
function dump(obj) {
document.write(obj.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
