std deque es sorprendentemente lento

Question

Acabo de enterarme que el estándar std deque es realmente lento cuando se compara con mi versión "casera" de la pila que usa una matriz preasignada.
Este es el código de mi pila:

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

.
corro este simple punto de referencia para 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()); 

.
utilizan la pila de std con vector como recipiente (como 'Michael Kohne' sugerido)

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

.
Y lo mismo para mi 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()); 

.
Los resultados después de 4 pistas son como sigue:
deque 15.529
deque 15,3756
deque 15.429
deque 15,4778

pila 6,19099
pila 6,1834
pila 6,19315
pila 6,19841

FastStack 3.01085
FastStack 2,9934
FastStack 3,02536
FastStack 3,00937

Los resultados se expresan en segundos y estaba ejecutando el código en 3570k i5 de Intel (en el reloj por defecto). Usé el compilador VS2010 con todas las optimizaciones que están disponibles. Sé que mi FastStack tiene muchas limitaciones, pero hay muchas situaciones en las que se puede usar y ¡cuando puede dar un buen impulso! (Lo usé en un proyecto donde obtengo una aceleración de 2x en comparación con std :: queue).
Así que ahora mi pregunta es:
¿Hay algún otro "inhibidor" en C++ que todos usen pero nadie sepa sobre ellos?
EDITAR: No quiero ser ofensivo, solo tengo curiosidad si conoces algunas "aceleraciones" desconocidas como esta.

Answer 1

Si conoce la cantidad máxima de elementos que estarán en la pila en un momento dado, debe usar un std::vector en el que reserve la capacidad por adelantado. Incluso si no conoce la capacidad, para una pila debe usar std::vector que crecerá varias veces (mayor costo que un vector preasignado al crecer) pero nunca se encogerá, por lo que después de un tiempo dejará de asignar memoria.

El problema con el rendimiento es que std::deque atribuirá bloques, según sea necesario, y desasignar ellos cuando ya no son necesarios (siguiendo alguna estrategia), por lo que si usted llena y despejar el std::deque A menudo habrá asignaciones y cancelaciones de asignación de forma continua.

Answer 2

Estás viendo manzanas y naranjas. La dequeue tiene DOBLE SENTIDO, lo que requiere que sea bastante diferente internamente que la simple pila que has implementado. Intente ejecutar su punto de referencia contra un std::stack<int, std::vector<int> > en su lugar y vea cómo lo hace. std :: stack es un adaptador de contenedor, y si usa un vector como contenedor subyacente, debería ser casi tan rápido como la implementación local.

El único inconveniente es que la implementación de std :: stack no tiene una forma de preestablecer el tamaño, por lo que en situaciones donde SEPA cuál debe ser el tamaño máximo, será una un poco más lento inicialmente, ya que tiene que reasignarse varias veces. Después de eso, será más o menos lo mismo.