डेटा संरचना की इलाके का क्या अर्थ है?

Question

मैं निम्नलिखित लेख पढ़ रहा था,

What Every Programmer Should Know About Compiler Optimizations

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

कि अगर मैं कक्षा में डेटा के सदस्यों के अनुक्रम (लेआउट) को बदलने मतलब यह है, यह प्रदर्शन को प्रभावित कर सकते हैं?

तो, से प्रदर्शन में

class One 
{ 
int data0; 
abstract-data-type data1; 
}; 

Differes,

class One 
{ 
abstract-data-type data0; 
int data1; 
}; 

अगर यह सही है, अंगूठे का नियम है, जबकि वर्ग या डेटा संरचना को परिभाषित क्या है?

Answer 1

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

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

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

_{वर्तमान x86-64 आर्किटेक्चर (कोर i7) पर एक एकल कैश लाइन 64 बाइट्स है।}

Answer 2

मैं डेटा/संरचना इलाके पर एक विशेषज्ञ नहीं हूँ, लेकिन यह आप अपना डेटा कैसे सब सीपीयू से अधिक इस तरह लगातार इंतजार कर द्वारा अपने कार्यक्रम धीमा से स्मृति का सीपीयू कैशिंग बिट्स से बचने के लिए व्यवस्थित से है एक स्मृति लाने के लिए।

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

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

सारांश: यह मूल रूप से कैसे आप स्मृति का उपयोग करने के संबंध में अपने डेटा लेआउट देखभाल का मतलब है।

Answer 3

कक्षा के सदस्यों को क्रमबद्ध करें कि आप कितनी बार उन्हें एक्सेस करेंगे। यह कैश लाइन की "हॉटनेस" को अधिकतम करता है जिसमें आपकी कक्षा का सिर होता है, जिससे शेष कैश की संभावना बढ़ जाती है। एक अन्य कारक जिसे आप परवाह करते हैं वह पैकिंग है - संरेखण के कारण, जिस क्रम में सदस्यों को घोषित किया जाता है, उसे पुन: व्यवस्थित कर सकता है जिससे आपकी कक्षा के आकार में कमी आ सकती है जो बदले में कैश दबाव को कम कर देगी।

(उनमें से कोई भी, निश्चित हैं निश्चित रूप से। अंगूठे का ये नियम की रूपरेखा के लिए एक विकल्प नहीं हैं।)