std deque è sorprendentemente lento

Question

Ho appena scoperto che la deiezione standard di std è molto lenta quando si confronta con la mia versione di stack "fatta in casa" che utilizza una matrice pre-allocata.
Questo è il codice del mio stack:

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]; 
} 

.
ho eseguito questo semplice punto di riferimento per coda doppia:

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()); 

.
utilizza lo Stack std con vettore come contenitore (come 'Michael Kohne' suggerito)

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()); 

.
E lo stesso per la mia 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()); 

.
I risultati dopo 4 piste sono i seguenti:
deque 15,529
deque 15,3756
deque 15,429
deque 15,4778

pila 6,19,099 mila
pila 6,1834
pila 6,19,315 mila
pila 6,19841

FastStack 3.01085
FastStack 2,9934
FastStack 3,02,536 mila
FastStack 3,00937

I risultati sono in pochi secondi e stavo correndo il codice su Intel i5 3570k (il clock di default). Ho usato il compilatore VS2010 con tutte le ottimizzazioni disponibili. So che il mio FastStack ha un sacco di limitazioni, ma ci sono molte situazioni, dove può essere usato e quando può dare una bella spinta! (L'ho usato in un progetto in cui ottengo 2x speed up rispetto a std :: queue).
Quindi la mia domanda è:
Esistono altri "inibitori" in C++ che tutti usano ma nessuno li conosce?
EDIT: Non voglio essere offensivo, sono solo curioso di conoscere alcuni "speedup" sconosciuti come questo.

Answer 1

Se si conosce la quantità massima di elementi che saranno nella pila in un dato momento, è necessario utilizzare uno std::vector in cui si riserva la capacità in anticipo. Anche se non si conosce la capacità, per uno stack si dovrebbe usare un std::vector che crescerà alcune volte (costo superiore a un vettore preallocato in fase di crescita) ma non si ridurrà mai, quindi dopo un po 'di tempo smetterà di allocare memoria.

Il problema con le prestazioni è che std::deque sarà allocare blocchi come necessario, e li deallocare quando non sono più necessari (dopo un po 'di strategia), quindi se si riempire e cancellare le std::deque spesso non ci sarà allocazioni e deallocazioni continuamente.

Answer 2

Stai confrontando mele e arance. Il dequeue è DOUBLE-ENDED, il che richiede che sia un po 'diverso internamente rispetto allo stack semplice che hai implementato. Prova invece a eseguire il tuo benchmark con uno std::stack<int, std::vector<int> > e guarda come lo fai. std :: stack è un adattatore per container e se si utilizza un vettore come contenitore sottostante, dovrebbe essere veloce quasi quanto l'implementazione nazionale.

Il lato negativo è che l'implementazione std :: stack non ha un modo per preimpostare la dimensione, quindi in situazioni in cui SAPETE quale deve essere la dimensione massima, sarà un inizialmente un po 'più lento in quanto deve essere riassegnato più volte. Dopo quello, sarà praticamente lo stesso.