std deque на удивление медленный

Question

Я просто узнал, что стандартный std-deque действительно медленный, если сравнивать с моей «самодельной» версией стека, которые используют предварительно выделенный массив.
Это код моего стека:

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

.
я запускаю этот простой тест для дека:

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

.
Использование зЬй стек с вектором в качестве контейнера (как 'Майкл Köhne' предложил)

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,19099
стек 6,1834
стек 6,19315
стек 6,19841

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

Результаты в секундах, и я был запущен код на 3570k Intel i5 (по часам по умолчанию). Я использовал компилятор VS2010 со всеми имеющимися оптимизациями. Я знаю, что у моего FastStack есть много ограничений, но есть много ситуаций, где он может быть использован, и когда он может дать хороший импульс! (Я использовал его в одном проекте, где я получаю 2x ускорение по сравнению с std :: queue).
Итак, теперь мой вопрос:
Есть ли в C++ другие «ингибиторы», которые все используют, но никто не знает о них?
EDIT: Я не хочу быть оскорбительным, мне просто интересно, если вы знаете некоторые неизвестные «ускорения», подобные этому.

Answer 1

Если вы знаете максимальное количество элементов, которые будут находиться в стеке в любой момент времени, вы должны использовать std::vector, на котором вы резервируете пропускную способность. Даже если вы не знаете емкость, для стека вы должны использовать std::vector, который будет расти несколько раз (более высокая стоимость, чем предварительно выделенный вектор при росте), но никогда не сжимается, поэтому через некоторое время он перестанет выделять память.

Проблема с производительностью является то, что std::deque будет выделять блоки по мере необходимости, и освободить их, когда они больше не нужны (после некоторой стратегии), так что если вы заполнить и очистить std::deque часто там будут распределения и deallocations непрерывно.

Answer 2

Вы сравниваете яблоки и апельсины. Dequeue DOUBLE-ENDED, который требует, чтобы он был немного иным, чем простой стек, который вы реализовали. Попробуйте запустить свой тест против std::stack<int, std::vector<int> > и посмотрите, как вы это делаете. std :: stack - это контейнерный адаптер, и если вы используете вектор в качестве базового контейнера, он должен быть почти таким же быстрым, как и ваша домашняя реализация.

С одной стороны, реализация std :: stack не позволяет заранее установить размер, поэтому в ситуациях, когда вы знаете, какой максимальный размер должен быть, это будет сначала немного медленнее, поскольку он должен повторно назначать несколько раз. После этого он будет почти таким же.