私はいくつかの文字列プール アロケーターのパフォーマンスをテストしていました。ここで示した、サブ割り当てを呼び出しVirtualAllocて分割するものと、標準 C++ を使用した同様の実装 (Win32 API を直接呼び出さない) とnew[].
VirtualAllocC++ よりもオーバーヘッドが少ないはずだと思っていたので、バージョンが高速になることを期待していましたnew[]。しかし、私が観察した結果は逆です: を使用するnew[]と、下位レベルの を使用するよりもコードが高速になるようですVirtualAlloc。
テストを数回実行しました (コードは VS2010 SP1 でコンパイルされています)。出力は次のようになります。
String pool using VirtualAlloc: 1280.07 ms String pool using new[]: 799.193 ms
どうしてこれなの？new[]よりも速いように見えるのはなぜVirtualAllocですか?
テスト ソース コードは次のとおりです。
////////////////////////////////////////////////////////////////////////////
// Testing VirtualAlloc vs. new[].
////////////////////////////////////////////////////////////////////////////
#include <string.h>
#include <wchar.h>
#include <algorithm>
#include <exception>
#include <iostream>
#include <new>
#include <ostream>
#include <stdexcept>
#include <string>
#include <vector>
#include <windows.h>
using namespace std;
//--------------------------------------------------------------------------
// String pool allocator using VirtualAlloc, based on this:
// http://blogs.msdn.com/oldnewthing/archive/2005/05/19/420038.aspx
//--------------------------------------------------------------------------
class StringPoolUsingVirtualAlloc
{
public:
StringPoolUsingVirtualAlloc()
: m_pchNext(nullptr),
m_pchLimit(nullptr),
m_phdrCur(nullptr)
{
SYSTEM_INFO si;
GetSystemInfo(&si);
m_dwGranularity = static_cast<DWORD>(
RoundUp( sizeof(HEADER) + MIN_CBCHUNK, si.dwAllocationGranularity
));
}
~StringPoolUsingVirtualAlloc()
{
HEADER* phdr = m_phdrCur;
while (phdr)
{
HEADER * phdrPrev = phdr->m_phdrPrev;
VirtualFree(phdr, 0, MEM_RELEASE);
phdr = phdrPrev;
}
}
wchar_t* DuplicateString(const wstring& source)
{
return AllocString(source.c_str(), source.c_str() + source.length());
}
private:
union HEADER
{
struct
{
HEADER* m_phdrPrev;
SIZE_T m_cb;
};
wchar_t alignment;
};
enum
{
MIN_CBCHUNK = 32000,
MAX_CHARALLOC = 1024*1024
};
wchar_t* m_pchNext;
wchar_t* m_pchLimit;
HEADER* m_phdrCur;
DWORD m_dwGranularity;
static SIZE_T RoundUp(SIZE_T cb, SIZE_T units)
{
return ((cb + units - 1) / units) * units;
}
wchar_t* AllocString(const wchar_t* pchBegin, const wchar_t* pchEnd)
{
SIZE_T cchTotal = pchEnd - pchBegin + 1;
if (cchTotal > MAX_CHARALLOC)
throw length_error("String too big.");
wchar_t* psz = m_pchNext;
if (m_pchNext + cchTotal <= m_pchLimit)
{
m_pchNext += cchTotal;
lstrcpynW(psz, pchBegin, static_cast<int>(cchTotal));
return psz;
}
SIZE_T cbAlloc = RoundUp(cchTotal * sizeof(wchar_t) + sizeof(HEADER), m_dwGranularity);
BYTE* pbNext = reinterpret_cast<BYTE*>(
VirtualAlloc(nullptr, cbAlloc, MEM_COMMIT, PAGE_READWRITE));
if (pbNext == nullptr)
throw bad_alloc();
m_pchLimit = reinterpret_cast<wchar_t*>(pbNext + cbAlloc);
HEADER* phdrCur = reinterpret_cast<HEADER*>(pbNext);
phdrCur->m_phdrPrev = m_phdrCur;
phdrCur->m_cb = cbAlloc;
m_phdrCur = phdrCur;
m_pchNext = reinterpret_cast<wchar_t*>(phdrCur + 1);
return AllocString(pchBegin, pchEnd);
}
StringPoolUsingVirtualAlloc(const StringPoolUsingVirtualAlloc &);
StringPoolUsingVirtualAlloc & operator=(const StringPoolUsingVirtualAlloc &);
};
//--------------------------------------------------------------------------
// String pool allocator that uses standard C++ (no Win32 stuff) and new[].
//--------------------------------------------------------------------------
class StringPoolUsingNew
{
public:
StringPoolUsingNew()
: m_pchNext(NULL),
m_pchLimit(NULL),
m_currChunk(NULL)
{
}
~StringPoolUsingNew()
{
for (auto it = m_chunks.begin(); it != m_chunks.end(); ++it)
delete *it;
}
wchar_t* DuplicateString(const wstring& source)
{
return AllocString(source.c_str(), source.c_str() + source.length());
}
private:
class Chunk
{
public:
explicit Chunk(size_t maxCharCount)
{
m_data = new wchar_t[maxCharCount];
m_maxCharCount = maxCharCount;
}
~Chunk()
{
delete [] m_data;
}
wchar_t* Begin() { return m_data; }
const wchar_t* Begin() const { return m_data; }
size_t Length() const { return m_maxCharCount; }
private:
Chunk(const Chunk&);
Chunk& operator=(const Chunk&);
wchar_t * m_data;
size_t m_maxCharCount;
};
static const size_t kMinChunkCharCount = 16000;
static const size_t kMaxCharAlloc = 1024*1024;
wchar_t* m_pchNext;
wchar_t* m_pchLimit;
Chunk* m_currChunk;
vector<Chunk*> m_chunks;
wchar_t* AllocString(const wchar_t* pchBegin, const wchar_t* pchEnd)
{
const size_t cchTotal = pchEnd - pchBegin + 1;
if (cchTotal > kMaxCharAlloc)
throw length_error("String too big.");
wchar_t* dest = m_pchNext;
if (m_pchNext + cchTotal <= m_pchLimit)
{
m_pchNext += cchTotal;
const size_t copyCount = cchTotal - 1;
if (copyCount != 0)
wmemcpy(dest, pchBegin, copyCount);
dest[copyCount] = L'\0';
return dest;
}
const size_t newChunkSize = max(cchTotal, kMinChunkCharCount);
Chunk* newChunk = new Chunk(newChunkSize);
m_chunks.push_back(newChunk);
m_pchNext = newChunk->Begin();
m_pchLimit = newChunk->Begin() + newChunk->Length();
m_currChunk = newChunk;
return AllocString(pchBegin, pchEnd);
}
StringPoolUsingNew(const StringPoolUsingNew&);
StringPoolUsingNew& operator=(const StringPoolUsingNew&);
};
//------------------------------------------------------------------------
// Perf Measurement
//------------------------------------------------------------------------
long long Counter()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
return li.QuadPart;
}
long long Frequency()
{
LARGE_INTEGER li;
QueryPerformanceFrequency(&li);
return li.QuadPart;
}
void PrintTime(long long start, long long finish, const char * s)
{
cout << s << ": " << (finish - start) * 1000.0 / Frequency() << " ms" << endl;
}
//--------------------------------------------------------------------------
// Test
//--------------------------------------------------------------------------
int main()
{
static const int kExitOk = 0;
static const int kExitError = 1;
try
{
long long start = 0;
long long finish = 0;
const auto shuffled = []() -> vector<wstring>
{
const wstring lorem[] = {
L"Lorem ipsum dolor sit amet, consectetuer adipiscing elit.",
L"Maecenas porttitor congue massa. Fusce posuere, magna sed",
L"pulvinar ultricies, purus lectus malesuada libero,",
L"sit amet commodo magna eros quis urna.",
L"Nunc viverra imperdiet enim. Fusce est. Vivamus a tellus.",
L"Pellentesque habitant morbi tristique senectus et netus et",
L"malesuada fames ac turpis egestas. Proin pharetra nonummy pede.",
L"Mauris et orci."
};
vector<wstring> v;
for (long long i = 0; i < 400*1000; ++i)
{
for (auto it = begin(lorem); it != end(lorem); ++it)
{
v.push_back((*it) + L" (#" + to_wstring(i) + L")");
}
}
random_shuffle(v.begin(), v.end());
return v;
}();
start = Counter();
{
StringPoolUsingVirtualAlloc pool;
vector<const wchar_t*> v;
for (auto it = shuffled.begin(); it != shuffled.end(); ++it)
{
v.push_back( pool.DuplicateString(*it) );
}
}
finish = Counter();
PrintTime(start, finish, "String pool using VirtualAlloc");
start = Counter();
{
StringPoolUsingNew pool;
vector<const wchar_t*> v;
for (auto it = shuffled.begin(); it != shuffled.end(); ++it)
{
v.push_back( pool.DuplicateString(*it) );
}
}
finish = Counter();
PrintTime(start, finish, "String pool using new[]");
return kExitOk;
}
catch (const exception& e)
{
cerr << "*** ERROR: " << e.what() << endl;
return kExitError;
}
}
////////////////////////////////////////////////////////////////////////////