c - 2 डी सरणी पर पुनरावृत्त करने के लिए नेस्टेड लूप का कौन सा ऑर्डरिंग अधिक कुशल है




performance for-loop (7)

  1. सरणी के लिए [100] [100] - वे दोनों समान हैं, यदि एल 1 कैश बड़ा है तो 100 * 100 * आकार (int) == 10000 * आकार (int) == [आमतौर पर] 40000. सैंडी ब्रिज में नोट - एक अंतर देखने के लिए 100 * 100 पूर्णांक पर्याप्त तत्व होना चाहिए, क्योंकि एल 1 कैश केवल 32k है।

  2. कंपाइलर शायद इस कोड को अनुकूलित करेंगे

  3. कोई कंपाइलर अनुकूलन मानना ​​नहीं है, और मैट्रिक्स L1 कैश में फिट नहीं है - कैश प्रदर्शन [आमतौर पर] के कारण पहला कोड बेहतर है। हर बार जब कैश में कोई तत्व नहीं मिलता है - आपको कैश मिस मिलता है - और रैम या एल 2 कैश [जो बहुत धीमे होते हैं] पर जाने की आवश्यकता होती है। रैम से कैश [कैश भरने] के तत्वों को लेना [आमतौर पर 8/16 बाइट्स] में किया जाता है - इसलिए पहले कोड में, आपको 1/4 की सबसे मिस दर मिलती है [16 बाइट कैश ब्लॉक, 4 बाइट्स इन्सट्स मानते हुए] दूसरे कोड में यह असंबद्ध है, और यह भी हो सकता है 1. दूसरे कोड स्नैप में - तत्व जो पहले से ही कैश में थे [कैश में डाले गए आसन्न तत्वों के लिए भरें] - बाहर निकाले गए थे, और आपको एक अनावश्यक कैश मिस मिलती है।

    • यह इलाके के सिद्धांत से निकटता से संबंधित है , जो कैश सिस्टम को लागू करते समय सामान्य धारणा का उपयोग किया जाता है। पहला कोड इस सिद्धांत का पालन करता है जबकि दूसरा नहीं करता है - तो पहले के कैश प्रदर्शन दूसरे के बेहतर होंगे।

निष्कर्ष: सभी कैश कार्यान्वयन के लिए मुझे पता है - पहला तो दूसरा नहीं बदतर होगा। वे वही हो सकते हैं - यदि कोई कैश नहीं है या सभी सरणी पूरी तरह से कैश में फिट बैठती हैं - या कंपाइलर अनुकूलन के कारण।

2 डी सरणी पर फिर से शुरू करने के लिए नेस्टेड लूप के निम्न क्रम में से कौन सा ऑर्डर समय (कैश प्रदर्शन) के मामले में अधिक कुशल है? क्यूं कर?

int a[100][100];

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
       a[i][j] = 10;    
   }
}

या

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
      a[j][i] = 10;    
   }
}

आपके दूसरे स्निपेट में, प्रत्येक पुनरावृत्ति में j में परिवर्तन निम्न स्थानिक इलाके के साथ एक पैटर्न पैदा करता है। याद रखें कि दृश्यों के पीछे, एक सरणी संदर्भ गणना करता है:

( ((y) * (row->width)) + (x) ) 

एक सरलीकृत एल 1 कैश पर विचार करें जिसमें हमारे सरणी की केवल 50 पंक्तियों के लिए पर्याप्त स्थान है। पहले 50 पुनरावृत्तियों के लिए, आप 50 कैश मिस के लिए अपरिहार्य लागत का भुगतान करेंगे, लेकिन फिर क्या होता है? 50 से 99 तक प्रत्येक पुनरावृत्ति के लिए, आप अभी भी मिश कैश करेंगे और एल 2 (और / या रैम, आदि) से प्राप्त करना होगा। फिर, x 1 और y बदल जाता है, जिससे एक और कैश मिस हो जाता है क्योंकि आपके सरणी की पहली पंक्ति को कैश से निकाल दिया गया है, और बहुत आगे।

पहले स्निपेट में यह समस्या नहीं है। यह पंक्ति-प्रमुख क्रम में सरणी का उपयोग करता है, जो बेहतर इलाके को प्राप्त करता है - आपको प्रति पंक्ति केवल एक बार कैश मिस के लिए भुगतान करना पड़ता है (यदि प्रति पंक्ति लूप शुरू होने पर कैश में आपकी सरणी की पंक्ति मौजूद नहीं है)।

ऐसा कहा जा रहा है, यह एक बहुत ही वास्तुकला-निर्भर प्रश्न है, इसलिए आपको निष्कर्ष निकालने के लिए विनिर्देशों (एल 1 कैश आकार, कैश लाइन आकार इत्यादि) को ध्यान में रखना होगा। आपको निष्कर्ष निकालने के लिए ठोस डेटा रखने के लिए दोनों तरीकों को मापना चाहिए और हार्डवेयर घटनाओं का ट्रैक रखना चाहिए।


आम तौर पर, बेहतर इलाके (अधिकांश उत्तरदाताओं द्वारा देखा गया) लूप # 1 प्रदर्शन के लिए केवल पहला फायदा है।

दूसरा (लेकिन संबंधित) लाभ यह है कि # 1 की तरह लूप के लिए - कंपाइलर आमतौर पर स्ट्रिंग -1 मेमोरी एक्सेस पैटर्न के साथ कोड को ऑटो-वेक्टरिज़ करने में सक्षम होता है (स्ट्रैड -1 का मतलब है कि सरणी तत्वों में एक-एक करके संगत पहुंच है हर अगले पुनरावृत्ति)। इसके विपरीत, # 2 की तरह लूप के लिए , ऑटो-वेक्टरिज़ेशन सामान्य रूप से ठीक काम नहीं करेंगे, क्योंकि मेमोरी में कॉन्टिग्यूस ब्लॉक के लिए कोई लगातार चरण -1 पुनरावर्तक पहुंच नहीं है।

खैर, मेरा जवाब सामान्य है। बहुत सरल लूपों के लिए बिल्कुल # 1 या # 2 की तरह, यहां तक ​​कि सरल आक्रामक कंपाइलर ऑप्टिमाइज़ेशन भी इस्तेमाल किए जा सकते हैं (किसी भी अंतर को ग्रेडिंग) और संकलक सामान्य रूप से बाहरी लूप के लिए स्ट्रिंग -1 के साथ # 2 ऑटो-वेक्टरिज़ करने में सक्षम होंगे (विशेष रूप से # प्रगमा सिम या इसी तरह)।


इस प्रकार का माइक्रो-ऑप्टिमाइज़ेशन प्लेटफॉर्म-निर्भर है इसलिए उचित निष्कर्ष निकालने में सक्षम होने के लिए आपको कोड को प्रोफ़ाइल करने की आवश्यकता होगी।


पहला विकल्प बेहतर है क्योंकि हम पहले लूप के अंदर a[i] in a temp variable स्टोर कर सकते हैं और फिर उसमें जे इंडेक्स की तलाश कर सकते हैं। इस अर्थ में इसे कैश वैरिएबल के रूप में कहा जा सकता है।


पहली विधि थोड़ा बेहतर है, क्योंकि कोशिकाओं को एक दूसरे के बगल में ले जाने के लिए असाइन किया जा रहा है।

पहली विधि:

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment

दूसरी विधि:

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment

cache line bouncing बारे में यह एक क्लासिक समस्या है

ज्यादातर समय में पहला बेहतर होता है, लेकिन मुझे लगता है कि बिल्कुल सही जवाब है: आईटी डिप्लेंडर , अलग-अलग आर्किटेक्चर शायद अलग-अलग परिणाम।







cpu-cache