सी ++ एसटीएल: ऐरे बनाम वेक्टर: कच्चे तत्व का प्रदर्शन प्रदर्शन

Question

मैं एक दुभाषिया का निर्माण कर रहा हूं और क्योंकि मैं इस बार कच्ची गति का लक्ष्य रख रहा हूं, इस घड़ी (कच्चे) मामले में हर घड़ी चक्र मेरे लिए मायने रखता है।

क्या आपके पास कोई अनुभव या जानकारी है जो दोनों तेज़ हैं: वेक्टर या ऐरे? सभी महत्वपूर्ण बात यह है कि मैं एक तत्व (ऑपोड प्राप्त करने) तक पहुंच सकता हूं, मुझे डालने, आवंटन, सॉर्टिंग इत्यादि की परवाह नहीं है।

मैं अब खिड़की से बाहर निकलने जा रहा हूं और कहूंगा:

• एरे तत्वों तक पहुंचने के मामले में वेक्टरों की तुलना में कम से कम तेज हैं।

यह मेरे लिए वास्तव में तार्किक लगता है। वैक्टरों के साथ आपके पास उन सभी सुरक्षा और नियंत्रण ओवरहेड हैं जो सरणी के लिए मौजूद नहीं हैं।

(क्यों) क्या मैं गलत हूं?

नहीं, मैं प्रदर्शन अंतर को नजरअंदाज नहीं कर सकते हैं - भले ही वह तो छोटा है - मैं पहले से ही अनुकूलित और वी एम के हर दूसरे भाग जो opcodes :)

Answer 1

एक std::vector का एक विशिष्ट कार्यान्वयन में

तत्व उपयोग समय उपलब्ध एक साधारण सरणी में तत्व उपयोग समय के रूप में ही एक सूचक वस्तु (यानी एक रन-टाइम सूचक मूल्य)

std::vector<int> v; 
int *pa; 
... 
v[i]; 
pa[i]; 
// Both have the same access time 

माध्यम से होता है हालांकि, सरणी ऑब्जेक्ट के रूप में उपलब्ध एक सरणी के तत्व के लिए एक्सेस समय उपरोक्त दोनों एक्सेसों से बेहतर है (संकलन-समय सूचक मूल्य के माध्यम से पहुंच के बराबर)

int a[100]; 
... 
a[i]; 
// Faster than both of the above 

उदाहरण के लिए, उपलब्ध एक int सरणी के लिए एक विशिष्ट पढ़ने के लिए पहुंच एक रन-टाइम सूचक मूल्य के माध्यम से 86 मंच पर संकलित कोड में इस प्रकार

// pa[i] 
mov ecx, pa // read pointer value from memory 
mov eax, i 
mov <result>, dword ptr [ecx + eax * 4] 

वेक्टर तत्व तक पहुंच सुंदर लग रही हो जाएगा दिखेगा वैसा ही है।

एक ठेठ एक स्थानीय int सरणी के लिए एक सरणी वस्तु के रूप में दिखाई देगा के रूप में उपलब्ध पहुँच

// a[i] 
mov eax, i 
mov <result>, dword ptr [esp + <offset constant> + eax * 4] 

एक ठेठ एक सरणी वस्तु के रूप में

// a[i] 
mov eax, i 
mov <result>, dword ptr [<absolute address constant> + eax * 4] 

इस प्रकार दिखेगा के रूप में उपलब्ध एक वैश्विक int सरणी के लिए उपयोग इस प्रकार है

पहले भिन्नता में उस अतिरिक्त mov निर्देश से भिन्नता में अंतर उत्पन्न होता है, जिसे अतिरिक्त मेमोरी एक्सेस करना होता है।

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

तो "सर थोड़ा तेज होने" के बारे में बयान संकीर्ण मामले में सही है जब सरणी सीधे ऑब्जेक्ट के माध्यम से पहुंच योग्य है, पॉइंटर ऑब्जेक्ट के माध्यम से नहीं। लेकिन उस अंतर का व्यावहारिक मूल्य वस्तुतः कुछ भी नहीं है।

Answer 2

नंबर के तहत कार्यान्वित कम से कम है हूड, std::vector और सी ++ 0x std::array पहले तत्व के सूचक को n जोड़कर तत्व n पर पॉइंटर ढूंढें।

vector::atarray::at की तुलना में धीमी हो सकती है, जबकि दूसरा एक निरंतर खिलाफ तुलना क्योंकि पूर्व एक चर के खिलाफ तुलना करना होगा। उन वे कार्य हैं जो सीमाओं की जांच प्रदान करते हैं, operator[] नहीं।

आप सी-शैली सरणियों बजाय C++ 0x std::array मतलब है, तो वहाँ कोई at सदस्य है, लेकिन बात बनी हुई है।

संपादित करें: आप एक opcode तालिका है, तो एक वैश्विक सरणी (जैसे के साथ extern या static लिंकेज के रूप में) तेजी से हो सकता है। एक ग्लोबल सरणी के तत्व अलग-अलग चर के रूप में संबोधित किए जा सकते हैं जब वैश्विक चर को ब्रैकेट के अंदर रखा जाता है, और ऑपकोड अक्सर स्थिर होते हैं।

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

Answer 3

आप संतरे से सेब की तुलना कर रहे हैं। Arrays के पास स्थिर आकार होता है और स्वचालित रूप से आवंटित किया जाता है, जबकि वैक्टरों का गतिशील आकार होता है और गतिशील रूप से आवंटित किया जाता है। जो आप उपयोग करते हैं उस पर निर्भर करता है कि आपको क्या चाहिए।

आम तौर पर, सरणी आवंटित करने के लिए "तेज़" होते हैं (उद्धरणों में क्योंकि तुलना अर्थहीन है) क्योंकि गतिशील आवंटन धीमा है। हालांकि, एक तत्व का उपयोग करना वही होना चाहिए। (माना जाता है कि एक सरणी कैश में होने की अधिक संभावना है, हालांकि इससे पहले पहुंच के बाद कोई फर्क नहीं पड़ता।)

इसके अलावा, मुझे नहीं पता कि आप किस "सुरक्षा" के बारे में बात कर रहे हैं, vector है सरणी की तरह अपरिभाषित व्यवहार पाने के कई तरीके। हालांकि उनके पास at() है, यदि आपको पता है कि इंडेक्स मान्य है तो आपको इसका उपयोग करने की आवश्यकता नहीं है।

आखिरकार, प्रोफ़ाइल और उत्पन्न असेंबली को देखें। किसी का अनुमान कुछ भी हल करने वाला नहीं है।

Answer 4

आप गलत पेड़ को भंग कर सकते हैं। कैश मिस निष्पादित निर्देशों की संख्या से कहीं अधिक महत्वपूर्ण हो सकता है।

Answer 5

सभ्य परिणामों के लिए, समर्थन भंडारण के रूप में std::vector का उपयोग करें और अपने मुख्य पाश या जो कुछ भी करने से पहले अपनी पहली तत्व के लिए सूचक ले:

std::vector<T> mem_buf; 
// stuff 
uint8_t *mem=&mem_buf[0]; 
for(;;) { 
    switch(mem[pc]) { 
    // stuff 
    } 
} 

इस अति-उपयोगी कार्यान्वयन सीमा में जाँच प्रदर्शन है कि साथ किसी भी मुद्दे से बचा जाता है operator[], और बाद में कोड में mem_buf[pc] जैसे अभिव्यक्तियों में कदम उठाने पर सिंगल-स्टेपिंग आसान बनाता है।

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

वैश्विक सरणी का उपयोग करने की तुलना में, x86 पर इस प्रकार के प्रेषण के लिए निर्देश अधिक संक्षेप (कहीं भी 32-बिट विस्थापन फ़ील्ड नहीं) होना चाहिए, और अधिक आरआईएससी-जैसे लक्ष्यों के लिए कम निर्देश उत्पन्न होना चाहिए (नहीं टीओसी लुकअप या अजीब 32-बिट स्थिरांक), क्योंकि आमतौर पर उपयोग किए जाने वाले मान स्टैक फ्रेम में हैं।

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