c - 2 डी सरणी पर पुनरावृत्ति करते समय लूप का क्रम प्रदर्शन को प्रभावित क्यों करता है?




performance for-loop (5)

असेंबली के साथ कुछ नहीं करना। यह कैश मिस के कारण है।

सी बहुआयामी सरणी अंतिम आयाम के साथ सबसे तेज़ के रूप में संग्रहीत हैं। तो पहला संस्करण प्रत्येक पुनरावृत्ति पर कैश को याद करेगा, जबकि दूसरा संस्करण नहीं होगा। तो दूसरा संस्करण काफी तेज़ होना चाहिए।

यह भी देखें: http://en.wikipedia.org/wiki/Loop_interchange

संभावित डुप्लिकेट:
समय और कैश प्रदर्शन के मामले में इनमें से कौन सा लूप अधिक कुशल है

नीचे दो प्रोग्राम हैं जो लगभग समान हैं, सिवाय इसके कि मैंने i और j चर के चारों ओर स्विच किया है। वे दोनों अलग-अलग समय में दौड़ते हैं। क्या कोई यह समझा सकता है कि ऐसा क्यों होता है?

संस्करण 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

संस्करण 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

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


जैसा कि अन्य ने कहा है, मुद्दा सरणी में स्मृति स्थान की दुकान है: x[i][j] । यहां कुछ अंतर्दृष्टि है क्यों:

आपके पास 2-आयामी सरणी है, लेकिन कंप्यूटर में स्मृति मूल रूप से 1-आयामी है। तो जब आप अपनी सरणी इस तरह कल्पना करते हैं:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

आपका कंप्यूटर इसे एक पंक्ति के रूप में स्मृति में संग्रहीत करता है:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

दूसरे उदाहरण में, आप पहले नंबर पर लूपिंग करके सरणी का उपयोग करते हैं, यानी:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

मतलब है कि आप उन्हें सभी को मार रहे हैं। अब पहले संस्करण को देखें। आप कर रहे हैं:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

जिस तरह से सी ने स्मृति में 2-डी सरणी डाली, वैसे ही आप इसे पूरे स्थान पर कूदने के लिए कह रहे हैं। लेकिन अब किकर के लिए: यह क्यों मायने रखता है? सभी मेमोरी एक्सेस समान हैं, है ना?

नहीं: कैश की वजह से। आपकी याददाश्त से डेटा सीपीयू को थोड़ा भाग (जिसे 'कैश लाइन' कहा जाता है) में लाया जाता है, आमतौर पर 64 बाइट्स। यदि आपके पास 4-बाइट पूर्णांक हैं, तो इसका मतलब है कि आप एक साफ छोटे बंडल में लगातार 16 पूर्णांक प्राप्त कर रहे हैं। यह स्मृति के इन हिस्सों को लाने के लिए वास्तव में काफी धीमी है; आपका सीपीयू लोड करने के लिए एक कैश लाइन के लिए बहुत समय तक काम कर सकता है।

अब एक्सेस के क्रम पर वापस देखें: दूसरा उदाहरण है (1) 16 इंच का एक हिस्सा पकड़ना, (2) उन सभी को संशोधित करना, (3) 4000 * 4000/16 बार दोहराएं। यह अच्छा और तेज़ है, और सीपीयू के पास हमेशा काम करने के लिए कुछ है।

पहला उदाहरण है (1) 16 इंच का एक हिस्सा पकड़ो, (2) उनमें से केवल एक को संशोधित करें, (3) 4000 * 4000 बार दोहराएं। इसे स्मृति से "fetches" की संख्या 16 गुणा की आवश्यकता होगी। आपके सीपीयू को वास्तव में उस स्मृति को दिखाने के लिए इंतज़ार कर बैठे समय बिताना होगा, और जब यह आपके आस-पास बैठा है तो मूल्यवान समय बर्बाद कर रहे हैं।

महत्वपूर्ण लेख:

अब जब आपके पास जवाब है, तो यहां एक दिलचस्प नोट है: कोई दूसरा निहित कारण नहीं है कि आपका दूसरा उदाहरण तेज़ होना चाहिए। उदाहरण के लिए, फोरट्रान में, पहला उदाहरण तेज़ होगा और दूसरा धीमा होगा। ऐसा इसलिए है क्योंकि सी की तरह वैचारिक "पंक्तियों" में चीजों को विस्तारित करने के बजाय, फोरट्रान "कॉलम" में फैलता है, यानी:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

सी के लेआउट को 'पंक्ति-प्रमुख' कहा जाता है और फोरट्रान को 'स्तंभ-प्रमुख' कहा जाता है। जैसा कि आप देख सकते हैं, यह जानना बहुत महत्वपूर्ण है कि आपकी प्रोग्रामिंग भाषा पंक्ति-प्रमुख या स्तंभ-प्रमुख है या नहीं! अधिक जानकारी के लिए यहां एक लिंक दिया गया है: http://en.wikipedia.org/wiki/Row-major_order


यह लाइन अपराधी:

x[j][i]=i+j;

दूसरा संस्करण निरंतर स्मृति का उपयोग करता है, इस प्रकार यह काफी तेज होगा।

मैंने कोशिश की

x[50000][50000];

और संस्करण 2 के लिए वर्जन 1 बनाम 0.6 के लिए निष्पादन का समय 13 है।


मैं एक सामान्य जवाब देने की कोशिश करता हूं।

क्योंकि i[y][x] में *(i + y*array_width + x) लिए एक *(i + y*array_width + x) है (उत्तम दर्जे का int P[3]; 0[P] = 0xBEEF; ) का प्रयास करें।

जैसा कि आप y से अधिक पुनरावृत्त करते हैं, आप आकार array_width * sizeof(array_element) । यदि आपके पास अपने आंतरिक लूप में है, तो आपके पास उन हिस्सों पर array_width * array_height पुनरावृत्तियों होंगे।

आदेश को फ़्लिप करके, आपके पास केवल array_height खंड-पुनरावृत्तियों होंगे, और किसी भी खंड-पुनरावृत्ति के बीच, आपके पास केवल sizeof(array_element) array_width पुनरावृत्तियों sizeof(array_element)

वास्तव में पुराने x86-CPUs पर यह कोई फर्क नहीं पड़ता, आजकल x86 डेटा की बहुत सारी प्रीफेचिंग और कैशिंग करते हैं। आप शायद अपने धीमे पुनरावृत्ति-आदेश में कई कैश मिस उत्पन्न करते हैं





cpu-cache