कैश, इलाके में डेटा रखने के लिए तकनीकें?

Question

अल्ट्रा तेजी से कोड के लिए यह आवश्यक है कि हम रखना reference- के इलाके सीपीयू कैश में, डेटा जो बारीकी से एक साथ प्रयोग किया जाता है के रूप में ज्यादा रखें:

http://en.wikipedia.org/wiki/Locality_of_reference

क्या तकनीक है इस लक्ष्य को हासिल करने के लिए? क्या लोग उदाहरण दे सकते हैं?

मुझे जावा और सी/सी ++ उदाहरणों में रूचि है। बहुत से कैश स्वैपिंग को रोकने के लिए लोगों द्वारा उपयोग किए जाने वाले तरीकों के बारे में जानना दिलचस्प है।

अभिवादन

Answer 1

शायद यह स्पष्ट उत्तर देने के लिए शायद सामान्य है। जावा की तुलना में सी या सी ++ में दृष्टिकोण काफी अलग होंगे (जिस तरह से भाषा वस्तुओं को अलग करती है)।

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

संगत कंटेनर (सी में सादे पुरानी सरणी, सी ++ में वेक्टर) का उपयोग करें और पुनरावृत्तियों को ऊपर या नीचे जाने के लिए प्रबंधित करने का प्रयास करें, लेकिन सभी कंटेनर पर यादृच्छिक रूप से कूद नहीं है। सूची इलाके के लिए हत्यारे हैं, सूची में लगातार दो नोड्स पूरी तरह से अलग यादृच्छिक स्थानों पर हो सकते हैं।

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

यदि आप जावा में फोकस कर रहे हैं, तो कॉम्पैक्ट डेटा स्ट्रक्चर बनाएं, अगर आपके पास कोई ऑब्जेक्ट है एक स्थिति है, और इसे एक तंग लूप में एक्सेस किया जाना है, x और yPoint बनाने के बजाय अपने ऑब्जेक्ट के अंदर आदिम प्रकारों को रखने पर विचार करें और इसका संदर्भ रखें। संदर्भ प्रकारों को नया होना आवश्यक है, और इसका मतलब है कि एक अलग आवंटन, एक अतिरिक्त संकेत और कम इलाके।

Answer 2

जावा दुनिया में JIT कठिन काम करने इस लक्ष्य को हासिल करने के लिए जा रहा है, और दूसरा अनुमान को यह उल्टा होने की संभावना है की कोशिश कर रहा। This SO question जावा-विशिष्ट मुद्दों को पूरी तरह से संबोधित करता है।

Answer 3

दो आम तकनीकों में शामिल हैं:

• अतिसूक्ष्मवाद
• उपयोग कैश अनजान तकनीक अतिसूक्ष्मवाद के लिए

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

गलतफहमी आमतौर पर 50% की संभावना है, लेकिन मामूली लागतें हैं, क्योंकि वास्तव में कई नोड्स कैश-लाइन में फिट होते हैं (मान लें कि आपको प्रति केबी 128 नोड्स मिलते हैं!), और दो बच्चे नोड्स में से एक हमेशा होता है स्मृति में एक प्रत्यक्ष पड़ोसी।

कैश अनजान तकनीकों के लिए उदाहरण:Morton array indexing, जिसे जेड-ऑर्डर-वक्र-इंडेक्सिंग भी कहा जाता है। अगर आप आमतौर पर अप्रत्याशित दिशा में आस-पास के सरणी तत्वों तक पहुंचते हैं तो इस प्रकार की अनुक्रमणिका को प्राथमिकता दी जा सकती है। यह बड़ी छवि या वोक्सेल डेटा के लिए मूल्यवान हो सकता है जहां आपके पास 32 या 64 बाइट्स बड़े पिक्सल हो सकते हैं, और फिर उनमें से लाखों (सामान्य कॉम्पैक्ट कैमरा उपाय मेगापिक्सेल, सही है?) या वैज्ञानिक सिमुलेशन के लिए हजारों अरब भी हो सकते हैं।

हालांकि, दोनों तकनीकों में एक बात आम है: सबसे अधिक बार पहुँचा सामान आस-पास के क्षेत्र में तो अन्य कंप्यूटरों रखें, कम बार बातें दूर हो सकता है, harddisk करने के लिए मुख्य स्मृति से अधिक एल 1 कैश की पूरी श्रृंखला फैले एक ही कमरा, अगला कमरा, एक ही देश, दुनिया भर में, अन्य ग्रह।

Answer 4

कुछ यादृच्छिक चाल है कि मेरे दिमाग में आते हैं, और जो उनमें से कुछ मैं हाल ही में उपयोग:

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

डेटा प्रकारों को हटाना यादृच्छिक रूप से कूदने से बचें। नियमित int 4 बाइट लेगा, और यदि आप उदाहरण का प्रबंधन करते हैं। uint16_t आप 2x अधिक सामग्री कैश करेंगे

कभी-कभी आप बिटमैप्स का उपयोग कर सकते हैं, मैंने इसे बाइनरी छवि को संसाधित करने के लिए उपयोग किया। मैंने पिक्सेल प्रति बिट संग्रहीत किया, इसलिए मैं एक कैश लाइन में 8 * 32 पिक्सल फिट कर सकता था। यह वास्तव में प्रदर्शन

फार्म जावा बढ़ाया, आप JNI उपयोग कर सकते हैं (यह मुश्किल नहीं है) और सी में अपने महत्वपूर्ण कोड लागू स्मृति