कैश इलाके सरणी प्रदर्शन के लिए क्यों मायने रखता है?

Question

निम्नलिखित blog में जुड़ा हुआ सूचियों से अधिक सरणियों का लाभ के बारे में एक बयान है:

सरणी बेहतर कैश इलाके कि प्रदर्शन में एक बहुत बड़ा अंतर कर सकते हैं।

इसका क्या अर्थ है? मुझे समझ में नहीं आता कि कैसे कैश इलाके एक बड़ा प्रदर्शन लाभ प्रदान कर सकता है।

Answer 1

मेरा उत्तर about spatial and temporal locality देखें।

विशेष रूप से, सरणी संगत स्मृति ब्लॉक होते हैं, इसलिए उनमें से बड़े हिस्से को पहली पहुंच पर कैश में लोड किया जाएगा। यह सरणी के भविष्य के तत्वों तक पहुंचने के लिए अपेक्षाकृत तेज़ बनाता है। दूसरी ओर लिंक्ड सूचियां आवश्यक रूप से स्मृति के संगत ब्लॉक में नहीं हैं, और अधिक कैश मिस का कारण बन सकती हैं, जो उन्हें एक्सेस करने में लगने वाले समय को बढ़ाती है।

एक सरणी data निम्नलिखित संभव स्मृति लेआउट और बड़े structs

Address  Contents  | Address  Contents 
ffff 0000 data[0]  | ffff 1000 l_data 
ffff 0040 data[1]  | .... 
ffff 0080 data[2]  | ffff 3460 l_data->next 
ffff 00c0 data[3]  | .... 
ffff 0100 data[4]  | ffff 8dc0 l_data->next->next 
          | ffff 8e00 l_data->next->next->next 
          | .... 
          | ffff 8f00 l_data->next->next->next->next 

अगर हम इस सरणी के माध्यम से लूप करना चाहता था की लिंक्ड सूची l_data पर विचार करें, ffff 0000 तक पहली पहुँच हमें की आवश्यकता होगी करने के लिए स्मृति में जाने के लिए पुनर्प्राप्त करें (सीपीयू चक्रों में एक बहुत धीमी ऑपरेशन)। हालांकि, पहली पहुंच के बाद बाकी सरणी कैश में होगी, और बाद में पहुंच बहुत तेज होगी। लिंक्ड सूची के साथ, ffff 1000 की पहली पहुंच के लिए हमें स्मृति में जाने की भी आवश्यकता होगी। दुर्भाग्यवश, प्रोसेसर सीधे इस स्थान के आस-पास स्मृति को कैश करेगा, ffff 2000 तक सभी तरह से कहें। जैसा कि आप देख सकते हैं, यह वास्तव में सूची के किसी भी अन्य तत्व को कैप्चर नहीं करता है, जिसका अर्थ है कि जब हम l_data->next तक पहुंचने के लिए जाते हैं, तो हमें फिर से स्मृति में जाना होगा।

Answer 2

आमतौर पर, जब आप किसी सरणी का उपयोग करते हैं तो आप एक-दूसरे के पास मौजूद वस्तुओं तक पहुंचते हैं। अनुक्रमिक रूप से एक सरणी का उपयोग करते समय यह विशेष रूप से सच है।

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

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