最近、いくつかのパフォーマンス ベンチマークを実行しようとしていてstd::stack<int, std::vector<int>>、スタックの単純な実装 (事前に割り当てられたメモリを使用) と比較しました。今、私はいくつかの奇妙な行動を経験しています。
最初に質問したいのは、スタック ベンチマーク コードの次の行です。
// std::vector<int> magicVector(10);
この行のコメントを外すと、パフォーマンスが約 17% 向上します (ベンチマーク時間が 6.5 秒から 5.4 秒に短縮されます)。ただし、この行は他のメンバーを変更していないため、プログラムの残りの部分に影響を与えることはありません。それに、intのベクトルかdoubleのベクトルかは関係ありません...
2 番目に聞きたいことは、スタックの実装とstd::stack. std::stack私のスタックと同じくらい速いはずだと 言われましたが、結果は私の「FastStack」が2倍速いことを示しています。
結果(コメントなしのパフォーマンス向上行):
stack 5.38979
stack 5.34406
stack 5.32404
stack 5.30519
FastStack 2.59635
FastStack 2.59204
FastStack 2.59713
FastStack 2.64814
これらの結果は、/O2、/Ot、/Ob2 およびその他の既定の最適化を使用した VS2010 からのリリース ビルドから得られたものです。私の CPU は Intel i5 3570k で、デフォルトのクロック (1 スレッドで 3.6 GHz) です。
誰でも簡単にテストできるように、すべてのコードを 1 つのファイルにまとめました。
#define _SECURE_SCL 0
#include <iostream>
#include <vector>
#include <stack>
#include <Windows.h>
using namespace std;
//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
// Purpose: High Resolution Timer
//---------------------------------------------------------------------------------
class HRTimer
{
public:
HRTimer();
double GetFrequency(void);
void Start(void) ;
double Stop(void);
double GetTime();
private:
LARGE_INTEGER start;
LARGE_INTEGER stop;
double frequency;
};
HRTimer::HRTimer()
{
frequency = this->GetFrequency();
}
double HRTimer::GetFrequency(void)
{
LARGE_INTEGER proc_freq;
if (!::QueryPerformanceFrequency(&proc_freq))
return -1;
return proc_freq.QuadPart;
}
void HRTimer::Start(void)
{
DWORD_PTR oldmask = ::SetThreadAffinityMask(::GetCurrentThread(), 0);
::QueryPerformanceCounter(&start);
::SetThreadAffinityMask(::GetCurrentThread(), oldmask);
}
double HRTimer::Stop(void)
{
DWORD_PTR oldmask = ::SetThreadAffinityMask(::GetCurrentThread(), 0);
::QueryPerformanceCounter(&stop);
::SetThreadAffinityMask(::GetCurrentThread(), oldmask);
return ((stop.QuadPart - start.QuadPart) / frequency);
}
double HRTimer::GetTime()
{
LARGE_INTEGER time;
::QueryPerformanceCounter(&time);
return time.QuadPart / frequency;
}
//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
// Purpose: Should be faster than std::stack
//---------------------------------------------------------------------------------
template <class T>
class FastStack
{
public:
T* st;
int allocationSize;
int lastIndex;
public:
FastStack(int stackSize);
~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( 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];
}
//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
// Purpose: Benchmark of std::stack and FastStack
//---------------------------------------------------------------------------------
int main(int argc, char *argv[])
{
#if 1
for (int it = 0; it < 4; it++)
{
std::stack<int, std::vector<int>> bStack;
int x;
for (int i = 0; i < 100; i++) // after this two loops, bStack's capacity will be 141 so there will be no more reallocating
bStack.push(i);
for (int i = 0; i < 100; i++)
bStack.pop();
// std::vector<int> magicVector(10); // when you uncomment this line, performance will magically rise about 18%
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();
cout << "stack " << totalTime << endl;
}
#endif
//------------------------------------------------------------------------------------
#if 1
for (int it = 0; it < 4; it++)
{
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();
cout << "FastStack " << totalTime << endl;
}
#endif
cout << "Done";
cin.get();
return 0;
}
.
編集:私のスタックの本当に悪い実装について誰もが話しているので、私は物事を正しく設定したいと思います。そのスタックを数分で作成し、現在必要な機能をいくつか実装しました。std::stack :) の代わりになることや、すべての場合に使用するために保存することを意図したものではありませんでした。唯一の目標は、最高速度と正しい結果を達成することでした。この誤解については申し訳ありません…私はいくつかの答えを知りたいだけです…</p>