#include < afxtempl.h >
#include < stdlib.h > 

int compare(const void* a1, const void* a2) { return *(UINT*)(a1)- *(UINT*)(a2); }
void CSortDlg::OnButton1() 
{
	// TODO: この位置にコントロール通知ハンドラ用のコードを追加してください
	CUIntArray a;
	a.Add(7);
	a.Add(1);
	a.Add(4);
	UINT* p = a.GetData();
	qsort((LPVOID)p, a.GetSize(), sizeof(int), compare);
}

prep /OM /SF function /FT name
profile name
prep /M name
plist /ST name >summary

2013-02-18
実行時間を調べる処理 (1) 方法を見てみるAdd Star
プログラム, コード |  実行時間を調べる処理 (1) 方法を見てみるを含むブックマーク   実行時間を調べる処理 (1) 方法を見てみるのブックマークコメント

QueryPerformanceCounterを実時間計測には使えないを書いて以来、このページを見るたびに思うところがありまして、使い方と言うことでまた言及してみることにしました。

今回はWindowsやLinuxで実行時間計測に使う方法を通じて、それぞれどういう性質を持っているのか？を考えてみたいと思います。

基本的に科学技術計算で使うことを前提に利点および欠点を考察しています。


実行時間計測の基本は「基準時間を取得」=>「処理」=>「終了時間を取得」=>「差分をとる」

ストップウォッチの手順とほぼ同じです。

微妙に違うのはストップウォッチで時間をクリアすると0になるのに対してプログラム内では「基準時間をとる」=>これを0地点とする、の流れになります。

以降コード内で出てくるf()は、時間取得の対象となる処理関数を指す物とします。


Windows,Linux(,MacOS)すべてで使えるclock()を使う

標準ライブラリ関数であるclock()を使った時間計測です。

これに関してだけはWindowsだけではなくLinuxでも使用可能です。

//clock()版
int main(void)
{
	clock_t t1,t2,td,tb;

	tb = CLOCKS_PER_SEC;
	t1 = clock();
	f();
	t2 = clock();
	td = t2 - t1;
	printf("f() took %d count [%4.2f sec].\n",td,(double)td / (double)tb);
	getchar();
	return 0;
}
利点
Windows、Linuxどちらでも使用できるため汎用性が高い
欠点
タイマーの分解能は実装系によって違うため不明
Windows(VC++)ではCLOCKS_PER_SECが1000(clock()の最小単位はms)に対してLinux(gcc)では1000000(clock()の最小単位はμs)になる
Linux特有の問題として、特に32bit処理系ではclock()が約71.6分周期になるので、間隔が長くなる場合は正しくない値を返すこともある
基本的にWindowsでclock()を使うと内部実装はGetTickCount()を使った物になることが多いようです。


Windowsの基本となる時間取得のGetTickCount()を使う

//GetTickCount()版
int main(void)
{
	DWORD t1,t2,td,tb;

	tb = 1000;
	t1 = GetTickCount();
	f();
	t2 = GetTickCount();
	td = t2 - t1;
	printf("f() took %d count [%4.2f sec].\n",td,(double)td / (double)tb);
	getchar();
	return 0;
}
利点
初期化も何もせずに使用可能
Windowsプログラムであれば常に使用可能
欠点
タイマーの分解能が悪いことが多い(そもそもGetTickCountの分解能はシステムタイマの影響を受ける、となっているため保証されていない)
Windowsで時間テストを簡易的に行うにはよく出てくるルーチンですね。


ゲームなどで時間計測を行うtimeGetTime()を使う

#pragma comment(lib,"winmm.lib")

//timeGetTime()版
int main(void)
{
	DWORD t1,t2,td,tb; TIMECAPS tc;

	timeGetDevCaps(&tc,sizeof(tc));
	timeBeginPeriod(tc.wPeriodMin);

	tb = 1000;
	t1 = timeGetTime();
	f();
	t2 = timeGetTime();
	td = t2 - t1;
	printf("f() took %d count [%4.2f sec].\n",td,(double)td / (double)tb);
	getchar();

	timeEndPeriod(tc.wPeriodMin);
	return 0;
}
利点
timeBeginPeriodとtimeEndPeriodを併用することで分解能をシステムに強制することが出来る。そのため精度が高い。
欠点
分解能を設定するための手順が必要になり、コード量が増える
分解能をシステムに強制した場合、システム負荷が上がり、演算に影響を及ぼす可能性がある
timeGetTime系は分解能を上げることが出来るため、ゲームで正確な時間測定が必要なときによく使われます。

が、科学技術などで時間測定をするパターンではあまり見ることはないと思います。


問題となっているQueryPerformance系では？

//QueryPerformanceCounter()版
int main(void)
{
	LARGE_INTEGER t1,t2,td,tb;

	QueryPerformanceFrequency(&tb);
	QueryPerformanceCounter(&t1);
	f();
	QueryPerformanceCounter(&t2);
	td.QuadPart = t2.QuadPart - t1.QuadPart;
	printf("f() took %lld count [%4.2f sec].\n",td.QuadPart,(double)td.QuadPart / (double)tb.QuadPart);
	getchar();
	return 0;
}
利点
タイマ値が常に64bit値なのでほぼラウンドすることはない
Windows側でも「高分解能」と言っているので、分解能そのものは上記3つの方法よりほぼ確実に上回る
欠点
WinVista以前のOSでの使用時にはタイマがCPUクロックとなってしまうことがあり、そのときには間隔時間値は信用できない(カウントの差分値の比較は有効)
QueryPerformance系のタイマが「ない」ことがある(よほど古いPC(Win95時代とか)でもない限りはほぼあると思って良いが)
普通に科学技術計算なら使っても大丈夫ですか。

ゲームでも今であれば(WinVista以降のOSであれば)あまり問題は出ないと思います。


お遊び・・・rdtscを使ってみた

#pragma comment(lib,"winmm.lib")

typedef DWORD_PTR (WINAPI *LPFNSETTHREADAFFINITYMASK)(HANDLE hThread,DWORD_PTR dwThreadAffinityMask);
typedef BOOL (WINAPI *LPFNGETPROCESSAFFINITYMASK)(HANDLE hProcess,DWORD_PTR *lpProcessAffinityMask,DWORD_PTR *lpSystemAffinityMask);

unsigned __int64 GetClockPerSec(void);

//__rdtsc()版
int main(void)
{
	unsigned __int64 t1,t2,td,tb; 

	tb = GetClockPerSec();
	t1 = __rdtsc();
	f();
	t2 = __rdtsc();
	td = t2 - t1;
	printf("f() took %lld count [%4.2f sec].\n",td,(double)td / (double)tb);
	getchar();
	return 0;
}

unsigned __int64 GetClockPerSec(void)
{
	HANDLE hThisProcess,hThisThread; HMODULE hKernelDLL;
	LPFNSETTHREADAFFINITYMASK fnSetThreadAffinityMask; LPFNGETPROCESSAFFINITYMASK fnGetProcessAffinityMask;
	
	DWORD_PTR dwProcessAffinityMask,dwSystemAffinityMask,dwAffinityMask;
	DWORD dwProcessPriority; int nThreadPriority; unsigned __int64 ts,te,ti; TIMECAPS tc; DWORD t1,t2,tn; int i;

	hKernelDLL = GetModuleHandle(TEXT("kernel32.dll"));
	hThisProcess = GetCurrentProcess(); hThisThread = GetCurrentThread();
	fnSetThreadAffinityMask = NULL; fnGetProcessAffinityMask = NULL;
	dwProcessAffinityMask = 1; dwSystemAffinityMask = 1;

	if(hKernelDLL != NULL){
		fnGetProcessAffinityMask = (LPFNGETPROCESSAFFINITYMASK)GetProcAddress(hKernelDLL,"GetProcessAffinityMask");
		if(fnGetProcessAffinityMask != NULL) fnGetProcessAffinityMask(hThisProcess,&dwProcessAffinityMask,&dwSystemAffinityMask);
		if(dwProcessAffinityMask != 1){
			fnSetThreadAffinityMask = (LPFNSETTHREADAFFINITYMASK)GetProcAddress(hKernelDLL,"SetThreadAffinityMask");
			if(fnSetThreadAffinityMask != NULL){
				for(i = 0,dwAffinityMask = dwProcessAffinityMask;i < (int)(sizeof(dwProcessAffinityMask) * 8);i++){
					if(dwProcessAffinityMask & (DWORD_PTR)(1 << i)){ dwAffinityMask = (DWORD_PTR)(1 << i); break; }
				}
				fnSetThreadAffinityMask(hThisThread,dwAffinityMask);
			}
		}
	}

	dwProcessPriority = GetPriorityClass(hThisProcess); if(dwProcessPriority == 0) dwProcessPriority = NORMAL_PRIORITY_CLASS;
	nThreadPriority = GetThreadPriority(hThisThread); if(nThreadPriority == THREAD_PRIORITY_ERROR_RETURN) nThreadPriority = THREAD_PRIORITY_NORMAL;
	SetPriorityClass(hThisProcess,REALTIME_PRIORITY_CLASS); SetThreadPriority(hThisThread,THREAD_PRIORITY_TIME_CRITICAL);

	timeGetDevCaps(&tc,sizeof(tc));
	timeBeginPeriod(tc.wPeriodMin);

	ts = __rdtsc(); t1 = timeGetTime(); t2 = t1 + 1000;
	if(t2 > t1){ while(tn = timeGetTime(),tn < t2); }
	else{ while(tn = timeGetTime(),tn < t2 || tn >= t1); }
	te = __rdtsc();
	ti = te - ts;
	timeEndPeriod(tc.wPeriodMin);

	SetThreadPriority(hThisThread,nThreadPriority); SetPriorityClass(hThisProcess,dwProcessPriority);
	if(fnSetThreadAffinityMask != NULL) fnSetThreadAffinityMask(hThisThread,dwProcessAffinityMask);

	return ti;
}
利点
もろにCPUクロックを使って比較するので、アルゴリズムの詳細な比較を行うことが出来るかも
カウント値は64bit値なのでラウンドすることはほぼない
欠点
そもそも1秒間のクロック数は今ではほぼ不定なので取得できないと思った方がよい(上記のルーチンも頑張ってはいるがTurboBoost時に間違いが出る)
マルチCPU環境でのrdtscは各コアで微妙に値が異なることがあり、取得するCPUを限定しないと間違った結果を取得することがある
間隔の比較はほぼ正確だが、CPUの種類が変わっただけで値が大きく変動することがあるので、意味がないことも。(特にアルゴリズムの優劣を比較するときに、加算が早い、乗算が早い、と言った特性が出てしまうことも)
欠点の最後の点はどの方法でも出ることですが、クロック数でとるとより明確になってしまうことがあります。

ただ、逆にその性質を使ってアルゴリズムの優劣を考えることも出来るので善し悪しですか。


03/25 追記

Linux版についてはこちらに別の方法を紹介しています。


と言うことで紹介完了

まずは各方法を紹介完了です。それぞれ特性を見ながら比較していきました。

今となってしまえばQueryPerformanceFrequencyを使った取得がまずい、と言うことはあまりなさそうです。

昔よりWinXPの比率が大幅に落ちていますからね。実時間計測には相変わらず要注意ですが。

なお、これらの方法を併用して詳細に調べていく、というのはありです。rdtscとtimeGetTimeとかですね。