हुड के तहत सी # में इंडेक्सर्स: डॉव जोन्स की तुलना में बेहतर इंडेक्सिंग

शुभ दिन। इस लेख में, मैं विभिन्न प्रकारों में अनुक्रमकों से परिचित होने का प्रस्ताव करता हूं। आइए इन इंडेक्सर्स के लिए कोडांतरक भाषा कोड और इसकी गति में प्रत्येक निर्देश की विशेषताओं को देखें। मैं कुछ स्पष्ट निष्कर्ष भी पेश करूंगा। लेकिन क्या वास्तव में अपनी विशेष स्थिति में उपयोग करने के लिए आप पर निर्भर है कि गति या इसके विपरीत सुविधा का त्याग करना है या नहीं।

मैट्रिक्स

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

नीचे गहराई से, केवल वैचारिक अवधारणाओं को खोदे बिना शब्दावली का संक्षिप्त सारांश है। मेरा लक्ष्य एक सामान्य समझ के लिए हर चीज का यथासंभव सरल वर्णन करना था।

माइक्रो-ऑपरेशन (यूओपी) एक निश्चित ऑपरेशन है, जिसमें प्रत्येक निर्देश होते हैं। माइक्रो-ऑपरेशंस की अवधारणा का उपयोग विलय, कैशिंग और रीऑर्डरिंग जैसे अनुकूलन के लिए किया जाता है। इसलिए, उदाहरण के लिए, MOV निर्देश में 1 माइक्रो-ऑपरेशन होता है, जबकि दो रजिस्टरों पर XCHG इंस्ट्रक्शन में 3 माइक्रो-ऑपरेशन होते हैं (दृष्टिकोण "अस्थायी चर" के माध्यम से होता है, अर्थात, एक आंतरिक रजिस्टर, अपडेट के लिए धन्यवाद leotsarev ), XCHG निर्देश रजिस्टर और मेमोरी में 8 माइक्रो-ऑपरेशन होते हैं।

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

विलंबता उपायों की संख्या है जिसके बाद इस निर्देश में उपयोग किया गया डेटा किसी अन्य निर्देश द्वारा उपयोग के लिए उपलब्ध होगा।

थ्रूपुट (पारस्परिक प्रवाह) - एक निर्देश को निष्पादित करने के लिए आवश्यक घड़ी चक्रों की संख्या, बशर्ते कि समान निर्देशों के एक क्रम को निष्पादित किया जाता है और वे स्वतंत्र डेटा के साथ काम करते हैं।

इन संकेतकों के आधार पर, आप निर्देशों के एक विशेष सेट के प्रदर्शन का मूल्यांकन कर सकते हैं। कृपया ध्यान दें कि हम केवल "मूल्यांकन" कर सकते हैं, वास्तविक प्रदर्शन कई कारकों पर निर्भर करता है, जैसे हिट या मिस कैश, डेटा निर्भरता, आदि।

ये आंकड़े इंटेल प्रोसेसर आर्किटेक्चर स्काईलेक-एक्स के लिए हैं। यह मेरे इंटेल कोर i7-6700 प्रोसेसर से मेल खाती है।

यह भी याद रखने योग्य है कि 64 बिट सिस्टम के लिए फास्टकॉल 2 नहीं, बल्कि रजिस्टरों में 4 पैरामीटर (आरएक्स, आरडीएक्स, आर 8, आर 9) प्रदान करता है।

संख्या में सूचकांक

1. ऐरे इंडेक्सर

हम निम्नलिखित तरीकों पर एक उदाहरण के रूप में विचार करेंगे:

public int IndexerArray(int index, int[] array) { return array[index]; } 

इस स्निपेट के लिए कोडांतरक भाषा कोड पर विचार करें।

 1. cmp edx,dword ptr [r8+8] 2. jae 00007ff9`07288c78 3. movsxd rax,edx 4. mov eax,dword ptr [r8+rax*4+10h] 

पहली पंक्ति यह जांचती है कि क्या सूचकांक सरणी की सीमा से आगे जाता है। दूसरी पंक्ति एक अपवाद फेंकता है अगर यह बाहर निकलता है। अगला, हम सरणी में तत्व की स्थिति की गणना करते हैं। सरणी में पहले फ़ील्ड सेवा की जानकारी हैं, इसलिए हमें उन्हें (अतिरिक्त 10h = 16 बाइट्स) छोड़ना होगा।

2. पसंदीदा सूची <>

स्याही कोड:

 public int IndexerList(int index, List<int> list) { return list[index]; } 

विधानसभा भाषा कोड:

 1. cmp edx,dword ptr [r8+10h] 2. jae M00_L00 3. mov rax,qword ptr [r8+8] 4. cmp edx,dword ptr [rax+8] 5. jae 00007ff9`07268f56 6. movsxd rdx,edx 7. mov eax,dword ptr [rax+rdx*4+10h] ret M00_L00 call System.ThrowHelper.ThrowArgumentOutOfRange_IndexException() 

यहां स्पष्ट रूप से अधिक निर्देश हैं। यह स्पष्ट रूप से देखा जाता है कि शीट इंडेक्स सरणी इंडेक्स को लपेटता है। एक दिलचस्प बात यह है कि सरणी की सीमाओं से परे जाने की जाँच दो बार की जाती है। इसलिए, पहला निर्देश जांचता है कि क्या सूचकांक शीट की सीमाओं से परे है। यदि ऐसा होता है, तो हम एक बहुत स्पष्ट कॉल के लिए (निर्देश 2) कूदते हैं, अगर यह सरणी की सीमाओं से परे जाता है तो एक अपवाद को फेंक देता है। यह बॉर्डर चेक शीट के आंतरिक क्षेत्र का उपयोग करता है, जो क्रम में दूसरा (10h (16) ऑफ़सेट प्रकार की शुरुआत से, 8 से पॉइंटर से तालिका तालिका और आंतरिक सरणी से लिंक करने के लिए 8 - पहला फ़ील्ड) है। तीसरी पंक्ति में, हम rax में आंतरिक सरणी के पते को दर्ज करते हैं - पहला फ़ील्ड (सादृश्य द्वारा, 8 बाइट्स का ऑफ़सेट विधि तालिका का एक संकेतक है)। यह पहले से परिचित अनुभाग द्वारा पीछा किया जाता है - सरणी के लिए सूचकांक संदर्भ (लाइनें 4 - 7)। यहां, सीमाओं की जांच करने के लिए, सरणी के आंतरिक क्षेत्र का उपयोग किया जाता है।
मैंने उन चीजों को हटाने की कोशिश की, जो सीधे अनुक्रमण से संबंधित नहीं हैं, लेकिन यहां यह सेवानिवृत्त होने के लायक है, ताकि यह न लगे कि शीट तत्व के लिए प्रत्येक कॉल के अंत में एक अपवाद होगा: डी

वैसे, ताकि आप अटकल के साथ पीड़ा न दें, कृपया संदर्भ के द्वारा शीट के कार्यान्वयन के साथ खुद को परिचित करें। अहस्ताक्षरित किलों को टाइप करने का उपयोग तुलनाओं की संख्या को कम करने के लिए किया जाता है।

नतीजतन, हमें सूचकांक को सफलतापूर्वक एक्सेस करने के लिए 7 निर्देश मिलते हैं, जो कि सरणी में 3 से अधिक है।

न्यू - स्पैन <>

बहुवचन:

 public int IndexerSpan(int index, Span<int> span) { return span[index]; } 

और विधानसभा भाषा में:

 1. cmp edx,dword ptr [r8+8] 2. jae 00007ff9`07278f69 3. mov rax,qword ptr [r8] 4. movsxd rdx,edx 5. mov eax,dword ptr [rax+rdx*4] 

जब स्पैन की घोषणा की गई, तो उन्होंने हमें वादा किया कि रनटाइम के समर्थन से, उन्हें बुद्धिमानी से बनाया गया था। और वे झूठ नहीं बोलते कि क्या कहना है। वास्तव में, यह केवल एक निर्देश में शास्त्रीय सरणी से भिन्न होता है, पते तक पहुंचने का एक अतिरिक्त चरण है। इस कोड को देखते हुए, मेमोरी स्थान का पता स्पैन के अंदर छिपा होता है, जहां तत्व स्थित होते हैं, जिसे हम लाइन 3 में प्राप्त करते हैं। यह एक व्यूह, लाइन या स्टैक पर मेमोरी के टुकड़े में एक विशिष्ट स्थान का पता हो सकता है।
मस्ती के लिए स्पैन इंडेक्सर से परिचय के लिए यहां क्लिक करें। आप देख सकते हैं कि पर्यावरण चर के आधार पर 2 अलग-अलग कार्यान्वयन हैं। PROJECTN UWP के लिए .NET नेटिव के पहले संस्करण का कोड नाम है। इसलिए, हम अनुक्रमणिका के दूसरे संस्करण में अधिक रुचि रखते हैं। उसे टैग किया गया है [आंतरिक] । इसके अलावा, यदि आप इस अनुक्रमणिका के कार्यान्वयन में उपयोग किए जाने वाले स्थिर असुरक्षित वर्ग को देखते हैं, तो आप जानकारी पा सकते हैं कि इस फ़ाइल में अधिकांश विधियों के कार्यान्वयन को आंतरिक के रूप में दर्शाया गया है।

[आंतरिक] विशेषता के साथ चिह्नित क्षेत्रों के लिए विधि कॉल या संदर्भ में रनटाइम का समर्थन है।

CoreCLR में , ऐसे तरीकों के निकायों को EE (निष्पादन इंजन) द्वारा असुरक्षित कोड (असुरक्षित) से बदल दिया जाता है। यदि आपको अधिक विवरण की आवश्यकता है, तो आप getILIntrinsicImplementationForUnsafe विधि से खुदाई शुरू कर सकते हैं।

यह कोरआरटी में काम कैसे करता है (जो मुझे थोड़ा रूचि देता है) की जानकारी,
आप Internal.IL.Stubs.UnsafeIntrinsics को देखना शुरू कर सकते हैं।

बरसात के ऐसे समर्थन को देखते हुए, यह समझने के लिए कि पर्दे के पीछे वास्तव में क्या होगा, यह विधानसभा भाषा के निर्देशों को देखने के लिए समझ में आता है, जो हमने किया था।


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

अब आइए उन विभिन्न तरीकों को देखने का प्रयास करें जिनके साथ हम एक दो-आयामी सरणी निर्दिष्ट कर सकते हैं: सरणियों की एक सरणी (दांतेदार सरणी) और एक बहुआयामी सरणी (बहुआयामी सरणी)।

4. बहुआयामी सरणी

तीव्र कोड:

 public int IndexerDimensionalArray(int index1, int index2, int[,] demensionalArray) { return demensionalArray[index1, index2]; } 

विधानसभा भाषा:

 1. mov eax,edx 2. sub eax,dword ptr [r9+18h] 3. cmp eax,dword ptr [r9+10h] 4. jae 00007ff9`00098fe6 5. mov edx,r8d 6. sub edx,dword ptr [r9+1Ch] 7. cmp edx,dword ptr [r9+14h] 8. jae 00007ff9`00098fe6 9. mov ecx,dword ptr [r9+14h] 10. imul rcx,rax 11. mov rax,rdx 12. add rax,rcx 13. mov eax,dword ptr [r9+rax*4+20h] 

सब कुछ सिद्धांत रूप में समझा जा सकता है - 2 सरणी की सीमाओं पर जांच करता है, फिर सूचकांक की गणना करता है और उलटता है। यह सरणी एक टुकड़े में मेमोरी में संग्रहीत होती है।

5. सरणियों का सरणी (दांतेदार सरणी)

 public int IndexerJaggedArray(int index, int index2, int[][] jaggedArray) { return jaggedArray[index][index2]; } 

कोडांतरक:

 1. cmp edx,dword ptr [r9+8] 2. jae 00007ff9`00098f95 3. movsxd rax,edx 4. mov rax,qword ptr [r9+rax*8+10h] 5. cmp r8d,dword ptr [rax+8] 6. jae 00007ff9`00098f95 7. movsxd rdx,r8d 8. mov eax,dword ptr [rax+rdx*4+10h] 

और सबसे दिलचस्प - हमारे पास बहुआयामी के लिए विशेष रूप से बनाए गए प्रकार के मुकाबले कम निर्देश हैं।


लेकिन पिछले 2 उदाहरणों के बारे में, मैं आपको सलाह देता हूं कि आप निष्कर्ष पर न जाएं। इस तथ्य के कारण कि एक द्वि-आयामी सरणी एक एकल प्रकार है, जिसे 1 बार आरंभीकृत किया जाता है, पूरे सरणी के लिए मेमोरी एक बड़े टुकड़े में आवंटित की जाती है। यह एक बेहतर कैश प्रदान करेगा, जो मूल रूप से स्थिति को बदल सकता है। सरणियों के एक सरणी में, प्रत्येक सरणी के लिए मेमोरी अलग से आवंटित की जाएगी, इसलिए यह संभावना है कि सरणियों को स्मृति में आवंटित किया जाएगा और उनके लिए सबसे उपयुक्त स्थानों में प्रवेश किया जाएगा।

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

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

मुझे उम्मीद है कि यह जानकारी आपको सही निष्कर्ष निकालने और चर्चा करने में आपकी राय का उपयोग करने में मदद करती है कि क्या उपयोग करना है।