std::deque の実装 其の弐
いくつかのコンパイラで std::deque の push_back() のパフォーマンス特性を実測してみました。規格上、std::deque の push_back() は定数時間内に終わらなければならないことになっています。が、予想通り、「稀に多大な時間がかかり且つ既存の要素数が多ければ多いほど多くの時間がかかる」という実測結果が得られました。
前回の調査結果でも予想通りの実装方法だったわけですが、これでは厳密にはいずれのコンパイラに付属している STL はどれも規格を満たしていないことになります。
これって私が見落としているだけで、実は規格に「稀に極端な時間がかかってもいいよ」的なことがどこかに記述されてるんでしょうか？ あるいはまだ規格に std::deque の実装方法としてこれこれと言ったものを想定している等の記述があればそこから「まぁ、このアルゴリズムなら稀に時間がかかるのは仕方ないよね」と行間を読めるものなのですが。
それとも、実は実装が面倒なだけで規格の要求を満たす実装方法があるんだけど、どこのコンパイラ(STL)ベンダーも面倒くさがって簡易な実装で逃げてるだけ？
以下に、今回、測定に利用したコードとその結果を残しておきます。
測定に利用したコード
#include <deque> #include <stdexcept> #include <string> #include <stdio.h> #include <stdlib.h> #if defined(__GNUC__) # include <sys/time.h> # include <stdint.h> #else # include <windows.h> #endif #if !defined(__GNUC__) class win32_error :public std::runtime_error { DWORD code; public: win32_error(DWORD X_code = GetLastError()) :std::runtime_error(win32_error::make_error_message(X_code)), code(X_code) { } static const std::string make_error_message(DWORD X_code = GetLastError()); DWORD get_error_code() const { return code; } const char * get_error_message() const { return what(); } }; const std::string win32_error::make_error_message(DWORD X_code) { LPVOID lpMsgBuf; FormatMessageA ( FORMAT_MESSAGE_ALLOCATE_BUFFER | FORMAT_MESSAGE_FROM_SYSTEM, NULL, X_code, MAKELANGID(LANG_NEUTRAL,SUBLANG_DEFAULT), (LPSTR)&lpMsgBuf, 0, NULL ); const std::string result = (const char *)lpMsgBuf; LocalFree(lpMsgBuf); return result; } #endif class performance_time { public: #if defined(__GNUC__) typedef int64_t value_type; #else typedef __int64 value_type; #endif typedef performance_time this_type; value_type value; performance_time(value_type a_value) :value(a_value) { } performance_time(const this_type & a) :value(a.value) { } static performance_time get_current_tick() { value_type result; #if defined(__GNUC__) struct timeval tv; gettimeofday(&tv, NULL); result = tv.tv_sec; result *= 1000000; result += tv.tv_usec; #else if (!QueryPerformanceCounter(reinterpret_cast<LARGE_INTEGER *>(&result))) { throw win32_error(GetLastError()); } #endif return result; } static value_type get_tick_resolution() { #if defined(__GNUC__) return 1000000; #else value_type result; if (!QueryPerformanceFrequency(reinterpret_cast<LARGE_INTEGER *>(&result))) { throw win32_error(GetLastError()); } return result; #endif } value_type get_sec() const { return value /get_tick_resolution(); } value_type get_usec() const { const value_type scale = 1000000; return performance_time(value *scale).get_sec() -get_sec() *scale; } this_type operator = (const this_type & a) { value = a.value; return *this; } this_type operator += (const this_type & a) { value += a.value; return *this; } this_type operator -= (const this_type & a) { value -= a.value; return *this; } this_type operator + (const this_type & a) const { return value + a.value; } this_type operator - (const this_type & a) const { return value - a.value; } }; inline bool operator == (const performance_time & a, const performance_time & b) { return a.value == b.value; } inline bool operator != (const performance_time & a, const performance_time & b) { return a.value != b.value; } inline bool operator < (const performance_time & a, const performance_time & b) { return a.value < b.value; } inline bool operator <= (const performance_time & a, const performance_time & b) { return a.value <= b.value; } inline bool operator > (const performance_time & a, const performance_time & b) { return a.value > b.value; } inline bool operator >= (const performance_time & a, const performance_time & b) { return a.value >= b.value; } int main(int argc, char *args[]) { argc, args; try { std::deque<int> int_deque; performance_time max_tick = 0; performance_time total_tick = 0; const int try_size = 1024 *1024; for(int i = 0; i < try_size; ++i) { performance_time begin = performance_time::get_current_tick(); int_deque.push_back(i); performance_time end = performance_time::get_current_tick(); performance_time current_tick = end -begin; if (max_tick < current_tick) { max_tick = current_tick; printf ( "%7d:%2d.%06d\n", i, static_cast<int>(max_tick.get_sec()), static_cast<int>(max_tick.get_usec()) ); } total_tick += current_tick; } printf ( " total:%2d.%06d\n", static_cast<int>(total_tick.get_sec()), static_cast<int>(total_tick.get_usec()) ); performance_time average_tick = total_tick.value /try_size; printf ( "average:%2d.%06d\n", static_cast<int>(average_tick.get_sec()), static_cast<int>(average_tick.get_usec()) ); } catch(const std::exception & a) { fputs(a.what(), stderr); } catch(...) { fputs("予期せぬエラーが発生しました。", stderr); } return EXIT_SUCCESS; }
Borland C++ 5.6.4 での結果
| 既存の要素数 | 時間(秒) |
|---|---|
| 0 | 0.000002 |
| 1 | 0.000002 |
| 4 | 0.000003 |
| 11 | 0.000003 |
| 25 | 0.000003 |
| 186 | 0.000006 |
| 378 | 0.000006 |
| 425 | 0.000008 |
| 852 | 0.000014 |
| 920 | 0.000248 |
| 27305 | 0.000342 |
| 39703 | 0.000605 |
| 109225 | 0.000723 |
| 218452 | 0.001533 |
| 303583 | 0.004909 |
| 873812 | 0.005564 |
| total | 1.825859 |
| average | 0.000001 |
Microsoft C++ 8 での結果
| 既存の要素数 | 時間(秒) |
|---|---|
| 0 | 0.000007 |
| 44 | 0.000137 |
| 9178 | 0.000691 |
| 32214 | 0.000726 |
| 144712 | 0.000739 |
| 315576 | 0.001084 |
| 473364 | 0.001556 |
| 710048 | 0.002382 |
| total | 1.855766 |
| average | 0.000001 |
Metroweks C/C++ Compiler 3.0.1 での結果
| 既存の要素数 | 時間(秒) |
|---|---|
| 0 | 0.000042 |
| 94 | 0.002739 |
| 114367 | 0.006732 |
| 575119 | 0.021710 |
| total | 1.898673 |
| average | 0.000001 |
g++ 3.4.4 での結果
cygwin上での調査結果の為、タイマーの精度が思わしくなく正常に測定できていませんが、他と同様のパフォーマンス特性が見受けられます。
| 既存の要素数 | 時間(秒) |
|---|---|
| 3885 | 0.015000 |
| 12762 | 0.016000 |
| total | 0.654000 |
| average | 0.000000 |
追記
コメント欄でもご指摘頂いてますが、規格上、このパフォーマンス特性でよいようです。
cf. http://ml.tietew.jp/cppll/cppll/thread_articles/13428
