C++11 containers: move semantic vs pointers
Motivation
C++11 has introduced the move semantic which can also be used in containers instead of "old-school" pointers. The specific containers owning objects has been proposed earlier by third-party libraries like Boost (for example, ptr_map or ptr_vector).
The goal of the test is to compare the speed of manipulations on the objects having move semantics stored in the standard vector container with the same container storing the pointers only.
Scenario
We'll test
- a sequential access
- a random read-write access
- some algorithms like list reverse
The objects are stored in
- statically sized vectors
- dynamically sized vectors (objects are pushed back)
Both containers are allocated in the heap. The count of objects in the container should be sufficiently huge to see the difference. By default it is 10 million but may be changed.
Program
Here is the simple console program compiled with Microsoft (R) C/C++ Optimizing Compiler Version 19.15.26730 for 64-bits Windows target (release configuration by default is used that means /O2 and /GL optimization options are on).
#include <iostream>
#include <string>
#include <memory>
#include <vector>
#include <random>
#include <ctime>
#include <chrono>
#include <cassert>
using namespace std;
using namespace std::chrono;
class TestData
{
public:
TestData()
: int_value(0), str_value("")
{ }
TestData(int intval, string strval)
: int_value(intval), str_value(strval)
{ }
TestData(TestData&& src)
: int_value(std::move(src.int_value)),
str_value(std::move(src.str_value))
{ }
TestData& operator = (TestData&& src)
{
int_value = std::move(src.int_value);
str_value = std::move(src.str_value);
return *this;
}
int int_value;
string str_value;
};
using TestDataVec = vector<TestData>;
using TestDataPtrVec = vector<TestData*>;
class Timer
{
public:
Timer() {}
void Start(string timer_title)
{
title = timer_title;
t1 = system_clock::now();
}
void Stop()
{
t2 = system_clock::now();
}
void StopAndPrint(string timer_title)
{
Stop();
auto ms1 = duration_cast<std::chrono::microseconds>(t2 - t1);
cout << timer_title << endl;
cout << "\tDuration, mcs: " << ms1.count() << endl;
}
void StopAndPrint()
{
StopAndPrint(title);
}
private:
system_clock::time_point t1 = system_clock::now();
system_clock::time_point t2;
string title;
};
// Globals: tested objects
const int MaxObjectCount = 10000000;
unique_ptr<int[]> random_access(new int[MaxObjectCount]);
TestDataVec* v1 = nullptr;
TestDataPtrVec* v2 = nullptr;
void TestFillAllocated()
{
Timer t1;
t1.Start("Allocating TestDataVec");
v1 = new TestDataVec(MaxObjectCount);
t1.StopAndPrint();
t1.Start("Allocating TestDataPtrVec");
v2 = new TestDataPtrVec(MaxObjectCount);
t1.StopAndPrint();
t1.Start("Fill with TestData");
for (int i = 0; i < MaxObjectCount; i++)
{
TestData data(i, "Mov " + std::to_string(i));
(*v1)[i] = std::move(data);
}
t1.StopAndPrint();
t1.Start("Fill with TestData*");
for (int i = 0; i < MaxObjectCount; i++)
{
TestData* data = new TestData(i, "Ptr " + std::to_string(i));
(*v2)[i] = data;
}
t1.StopAndPrint();
}
void TestFillPushBack()
{
Timer t1;
t1.Start("Allocating TestDataVec");
v1 = new TestDataVec();
t1.StopAndPrint();
t1.Start("Allocating TestDataPtrVec");
v2 = new TestDataPtrVec();
t1.StopAndPrint();
t1.Start("Fill with TestData");
for (int i = 0; i < MaxObjectCount; i++)
{
TestData data(i, "Mov " + std::to_string(i));
v1->push_back(std::move(data));
}
t1.StopAndPrint();
t1.Start("Fill with TestData*");
for (int i = 0; i < MaxObjectCount; i++)
{
TestData* data = new TestData(i, "Ptr " + std::to_string(i));
v2->push_back(data);
}
t1.StopAndPrint();
}
void TestAccess()
{
Timer t1;
t1.Start("Sequential access TestData");
for (int i = 0; i < MaxObjectCount; i++)
{
(*v1)[i].int_value++;
assert((*v1)[i].int_value == i + 1);
}
t1.StopAndPrint();
t1.Start("Sequential access TestData*");
for (int i = 0; i < MaxObjectCount; i++)
{
(*v2)[i]->int_value++;
assert((*v2)[i]->int_value == i + 1);
}
t1.StopAndPrint();
t1.Start("Random access TestData");
for (int i = 0; i < MaxObjectCount; i++)
{
int index = random_access[i];
int old_value = (*v1)[index].int_value;
(*v1)[index].int_value++;
assert((*v1)[index].int_value == old_value + 1);
}
t1.StopAndPrint();
t1.Start("Random access TestData*");
for (int i = 0; i < MaxObjectCount; i++)
{
int index = random_access[i];
int old_value = (*v2)[index]->int_value;
(*v2)[index]->int_value++;
assert((*v2)[index]->int_value == old_value + 1);
}
t1.StopAndPrint();
}
void TestReverseList()
{
Timer t1;
t1.Start("Reverse list TestData");
std::reverse(v1->begin(), v1->end());
t1.StopAndPrint();
t1.Start("Reverse list TestData*");
std::reverse(v2->begin(), v2->end());
t1.StopAndPrint();
}
void TestDelete()
{
Timer t1;
t1.Start("Deleting TestData");
delete v1;
t1.StopAndPrint();
t1.Start("Deleting TestData*");
for (TestDataPtrVec::iterator it = v2->begin(); it != v2->end(); it++)
delete *it;
delete v2;
t1.StopAndPrint();
}
int main()
{
// Random access order
random_device rnd_device;
default_random_engine rnd_engine(rnd_device());
uniform_int_distribution<int> uniform_dist(0, MaxObjectCount - 1);
for (size_t i = 0; i < MaxObjectCount; i++)
random_access[i] = uniform_dist(rnd_engine);
// Benchmarks
cout << "Test preallocated vector data" << endl;
TestFillAllocated();
TestAccess();
TestReverseList();
TestDelete();
cout << endl << "Test dynamically added vector data" << endl;
TestFillPushBack();
TestAccess();
TestReverseList();
TestDelete();
}
Results
Preallocated vector data
Allocating TestDataVec
Duration, mcs: 234000
Allocating TestDataPtrVec
Duration, mcs: 15600
Fill with TestData
Duration, mcs: 358800
Fill with TestData*
Duration, mcs: 982800
Sequential access TestData
Duration, mcs: 31200
Sequential access TestData*
Duration, mcs: 46800
Random access TestData
Duration, mcs: 156000
Random access TestData*
Duration, mcs: 1950000
Reverse list TestData
Duration, mcs: 62400
Reverse list TestData*
Duration, mcs: 0
Deleting TestData
Duration, mcs: 46800
Deleting TestData*
Duration, mcs: 265200
Dynamically added data
Allocating TestDataVec
Duration, mcs: 0
Allocating TestDataPtrVec
Duration, mcs: 0
Fill with TestData
Duration, mcs: 982800
Fill with TestData*
Duration, mcs: 904800
Sequential access TestData
Duration, mcs: 31200
Sequential access TestData*
Duration, mcs: 46800
Random access TestData
Duration, mcs: 156000
Random access TestData*
Duration, mcs: 2012400
Reverse list TestData
Duration, mcs: 62400
Reverse list TestData*
Duration, mcs: 15600
Deleting TestData
Duration, mcs: 62400
Deleting TestData*
Duration, mcs: 249600
Conclusions
One can see that sequential and random access to objects having move semantic is more efficient that the manipulations with pointers except the initial allocation (in statically sized container scenario).
However, a reverse list algorithm test shows that the pointers are still faster than object moving. I seem that all algorithms reallocating items in containers will be faster with pointers.
Other "overhead" is "The rule of 5" conformity: you need to implement the move semantic for all user defined classes, to test and to maintain it after. Whether the drawbacks of additional code will exceed the performance profits, is the decision to make.
blog comments powered by Disqus