std deque आश्चर्यजनक रूप से धीमा है

Question

मुझे पता है कि मानक स्टड डेक वास्तव में धीमा है जब स्टैक के "घर से बने" संस्करण की तुलना में पूर्व-आवंटित सरणी का उपयोग किया जाता है।

template <class T> 
class FastStack 
{  
public: 
    T* st; 
    int allocationSize; 
    int lastIndex; 

public: 
    FastStack(int stackSize); 
    FastStack(); 
    ~FastStack(); 

    inline void resize(int newSize); 
    inline void push(T x); 
    inline void pop(); 
    inline T getAndRemove(); 
    inline T getLast(); 
    inline void clear(); 
}; 

template <class T> 
FastStack<T>::FastStack() 
{ 
    lastIndex = -1; 
    st = NULL; 
} 

template <class T> 
FastStack<T>::FastStack(int stackSize) 
{ 
    st = NULL; 
    this->allocationSize = stackSize; 
    st = new T[stackSize]; 
    lastIndex = -1; 
} 

template <class T> 
FastStack<T>::~FastStack() 
{ 
    delete [] st; 
} 

template <class T> 
void FastStack<T>::clear() 
{ 
    lastIndex = -1; 
} 

template <class T> 
T FastStack<T>::getLast() 
{ 
    return st[lastIndex]; 
} 

template <class T> 
T FastStack<T>::getAndRemove() 
{ 
    return st[lastIndex--]; 
} 

template <class T> 
void FastStack<T>::pop() 
{ 
    --lastIndex; 
} 

template <class T> 
void FastStack<T>::push(T x) 
{ 
    st[++lastIndex] = x; 
} 

template <class T> 
void FastStack<T>::resize(int newSize) 
{ 
    if (st != NULL) 
     delete [] st; 
    st = new T[newSize]; 
} 

:
यह मेरा ढेर के कोड है।
मैं Deque के लिए इस सरल बेंचमार्क चलाएँ:

std::deque<int> aStack; 
int x; 

HRTimer timer; 
timer.Start(); 

for (int i = 0; i < 2000000000; i++) 
{ 
    aStack.push_back(i); 
    x = aStack.back(); 
    if (i % 100 == 0 && i != 0) 
     for (int j = 0; j < 100; j++) 
      aStack.pop_back(); 
} 

double totalTime = timer.Stop(); 
stringstream ss; 
ss << "std::deque " << totalTime; 
log(ss.str()); 

।
कंटेनर के रूप में वेक्टर के साथ एसटीडी ढेर (के रूप में माइकल Kohne 'का सुझाव दिया)

std::stack<int, std::vector<int>> bStack; 
int x; 

HRTimer timer; 
timer.Start(); 

for (int i = 0; i < 2000000000; i++) 
{ 
    bStack.push(i); 
    x = bStack.top(); 
    if (i % 100 == 0 && i != 0) 
     for (int j = 0; j < 100; j++) 
      bStack.pop(); 
} 

double totalTime = timer.Stop(); 
stringstream ss; 
ss << "std::stack " << totalTime; 
log(ss.str()); 

का उपयोग करना।
और मेरे FastStack के लिए एक ही एक:

FastStack<int> fstack(200); 
int x; 

HRTimer timer; 
timer.Start(); 

for (int i = 0; i < 2000000000; i++) 
{ 
    fstack.push(i); 
    x = fstack.getLast(); 
    if (i % 100 == 0 && i != 0) 
     for (int j = 0; j < 100; j++) 
      fstack.pop(); 
} 

double totalTime = timer.Stop(); 
stringstream ss; 
ss << "FastStack " << totalTime; 
log(ss.str()); 

।
4 रन के बाद परिणाम इस प्रकार हैं:
Deque 15.529
Deque 15.3756
Deque 15.429
Deque 15,4778

ढेर ६.१९०९९
ढेर 6.1834
ढेर ६.१९३१५
ढेर 6,19841

फास्टस्टैक 3.01085
FastStack 2.9934
FastStack ३.०२५३६
FastStack 3,00937

परिणाम सेकंड में कर रहे हैं और मैं इंटेल i5 3570k पर कोड (डिफ़ॉल्ट घड़ी पर) चल रहा था। मैंने वीएस -2010 कंपाइलर का उपयोग उन सभी अनुकूलन के साथ किया जो उपलब्ध हैं। मुझे पता है कि मेरे फास्टस्टैक में बहुत सी सीमाएं हैं लेकिन बहुत सी स्थितियां हैं, जहां इसका उपयोग किया जा सकता है और जब यह अच्छा बढ़ावा दे सकता है! (मैंने इसे एक प्रोजेक्ट में इस्तेमाल किया जहां मुझे std :: queue की तुलना में 2x गति मिलती है)।
तो अब मेरा प्रश्न है:
क्या सी ++ में कोई अन्य "अवरोधक" है जो हर कोई उपयोग करता है लेकिन कोई भी उनके बारे में नहीं जानता?
संपादित करें: मैं आक्रामक नहीं होना चाहता, अगर आप कुछ अज्ञात "speedups" जानते हैं तो मैं उत्सुक हूं।

Answer 1

यदि आप किसी भी समय किसी भी समय स्टैक में मौजूद तत्वों की अधिकतम मात्रा जानते हैं तो आपको std::vector का उपयोग करना चाहिए जिस पर आप क्षमता को पहले से सुरक्षित रखते हैं। यहां तक ​​कि यदि आप क्षमता को नहीं जानते हैं, तो स्टैक के लिए आपको std::vector का उपयोग करना चाहिए जो कुछ बार बढ़ेगा (बढ़ते समय एक प्रीलोकेटेड वेक्टर की तुलना में उच्च लागत) लेकिन कभी भी कम नहीं होता है, इसलिए कुछ समय बाद यह स्मृति आवंटित करना बंद कर देगा।

प्रदर्शन के साथ इस मुद्दे, जब वे अब जरूरत है (कुछ रणनीति का पालन) हैं कि std::deque रूप में की जरूरत ब्लॉक आवंटित करेगा, और उन्हें पुनःआवंटन है, इसलिए यदि आप को भरने और लगातार std::deque आवंटन और deallocations अक्सर नहीं होगा साफ़ करें।

Answer 2

आप सेब और संतरे की तुलना कर रहे हैं। डेक्यू डब्लूबल-एंडेड है, जिसे आपके द्वारा लागू किए गए सरल स्टैक की तुलना में आंतरिक रूप से थोड़ा अलग होना आवश्यक है। इसके बजाय std::stack<int, std::vector<int> > के विरुद्ध अपना बेंचमार्क चलाने का प्रयास करें और देखें कि आप कैसे करते हैं। std :: स्टैक एक कंटेनर एडाप्टर है, और यदि आप अंतर्निहित कंटेनर के रूप में वेक्टर का उपयोग करते हैं, तो यह आपके घर के उगाए जाने वाले कार्यान्वयन के जितना तेज़ होना चाहिए।

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