std::vector Performance Analysis
Introduction
The std::vector template is frequently used in all kinds of C++ programs.
However, many programmers don't know that the containers performance is low
and that it is unsuitable for processing of large datasets.
Documentation: cppreference.com
Protocol class
To investigate the runtime behavior of std::vector we use a chatty protocol class
which tells us all about its life as an C++ object.
class Chatterbox
{
int i;
public:
Chatterbox ()
{ cout << "+ Chatterbox" << endl; i = 0; }
Chatterbox (int init)
{ cout << "+ Chatterbox " << init << endl; i = init; }
Chatterbox (const Chatterbox & cp)
{ cout << "+ Chatterbox cp " << cp. i << endl; i = cp. i; }
~Chatterbox ()
{ cout << "- Chatterbox " << i << endl; }
Chatterbox & operator = (const Chatterbox & asgn)
{ cout << ". Chatterbox = " << asgn. i << endl; i = asgn. i; return * this; }
};
|
Sample data
At the beginning of our little test program some sample objects are declared.
cout << "Construct samples" << endl;
Chatterbox cb1 (1);
Chatterbox cb2 (2);
Chatterbox cb3 (3);
Chatterbox cb4 (4);
Chatterbox cb5 (5);
|
Output:
Construct samples
+ Chatterbox 1
+ Chatterbox 2
+ Chatterbox 3
+ Chatterbox 4
+ Chatterbox 5
|
Test vector
The test vector is declared at the beginning of a nested block.
At the end of the block scope we can observe the vectors destructor.
{
vector <Chatterbox> cbvec;
|
Insert and append
If the size of the internal memory block changes the block is not reallocated.
Instead, a new block is allocated and all existing elements are copied by using their copy constructor.
Afterwards, the old objects are destructed and the old memory block is released.
This behavior does not depend on the position of insertion.
cout << "--------------" << endl;
cout << "Append cb 3" << endl;
cbvec. push_back (cb3);
cout << "--------------" << endl;
cout << "Insert cb 2" << endl;
cbvec. insert (cbvec. begin (), cb2);
cout << "--------------" << endl;
cout << "Append cb 4" << endl;
cbvec. push_back (cb4);
cout << "--------------" << endl;
cout << "Insert cb 1" << endl;
cbvec. insert (cbvec. begin (), cb1);
cout << "--------------" << endl;
cout << "Append cb 5" << endl;
cbvec. push_back (cb5);
|
Output:
--------------
Append cb 3
+ Chatterbox cp 3
--------------
Insert cb 2
+ Chatterbox cp 2
+ Chatterbox cp 3
- Chatterbox 3
--------------
Append cb 4
+ Chatterbox cp 4
+ Chatterbox cp 2
+ Chatterbox cp 3
- Chatterbox 2
- Chatterbox 3
--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
--------------
Append cb 5
+ Chatterbox cp 5
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
|
Delete elements
If a vector element is deleted all following elements are copied by using their assignment operator.
The number of operations depends on the position of deletion.
In most cases the extra memory is not released automatically.
To release this memory the method shrink_to_fit must be called.
cout << "--------------" << endl;
cout << "Remove first" << endl;
cbvec. erase (cbvec. begin ());
cout << "--------------" << endl;
cout << "Remove last" << endl;
cbvec. pop_back ();
|
Output:
--------------
Remove first
. Chatterbox = 2
. Chatterbox = 3
. Chatterbox = 4
. Chatterbox = 5
- Chatterbox 5
--------------
Remove last
- Chatterbox 5
|
Insert and append in free space
If the internal memory block has some free space
(e.g. because of the deletion of elements)
insert and append operations are very similar to delete operations
(copy following elements by using their assignment operator).
cout << "--------------" << endl;
cout << "Insert cb 1" << endl;
cbvec. insert (cbvec. begin (), cb1);
cout << "--------------" << endl;
cout << "Append cb 5" << endl;
cbvec. push_back (cb5);
|
Output:
--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox cp 4
. Chatterbox = 3
. Chatterbox = 2
. Chatterbox = 1
- Chatterbox 1
--------------
Append cb 5
+ Chatterbox cp 5
|
Adjust internal block size
If we adjust the internal block size the behavior is like described above.
The block is not reallocated. Instead, a new block is allocated and all
existing elements are copied by using their copy constructor.
cout << "--------------" << endl;
cout << "Reserve" << endl;
cbvec. reserve (10);
cout << "--------------" << endl;
cout << "Shrink" << endl;
cbvec. shrink_to_fit ();
|
Output:
--------------
Reserve
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
+ Chatterbox cp 5
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
- Chatterbox 5
--------------
Shrink
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
+ Chatterbox cp 5
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
- Chatterbox 5
|
Destructor
At the end of the nested block scope the destructors of the
test vector and of all vector elements are called.
cout << "--------------" << endl;
cout << "Destruct vector" << endl;
}
|
Output:
--------------
Destruct vector
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
- Chatterbox 5
|
Delete sample data
At the end of our little test program the destructors of the sample data are called.
cout << "--------------" << endl;
cout << "Destruct samples" << endl;
return 0;
|
Output:
--------------
Destruct samples
- Chatterbox 5
- Chatterbox 4
- Chatterbox 3
- Chatterbox 2
- Chatterbox 1
|
Compiler differences
The output of the test program was generated using the MSVC compiler 2022.
If we run the program using a different compiler or a different compiler version
the contents of the test vector will always be the same.
However, the internal intermediate steps may be very different.
Below we see the output of the first-time insertion of object 1 using the g++ compiler 11.2.0.
Output:
--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox cp 4
. Chatterbox = 3
. Chatterbox = 2
. Chatterbox = 1
- Chatterbox 1
|
C++11 move semantics
Our chatty protocol class can be extended by the C++11 move semantics.
Now the compiler calls in some, but not in all, cases the move constructor (instead
of the copy constructor) and the move assignment operator (instead of the assignment operator).
Please note that the number and order of the internal intermediate steps remain the same.
class Chatterbox
{
int i;
public:
Chatterbox ()
{ cout << "+ Chatterbox" << endl; i = 0; }
Chatterbox (int init)
{ cout << "+ Chatterbox " << init << endl; i = init; }
Chatterbox (const Chatterbox & cp)
{ cout << "+ Chatterbox cp " << cp. i << endl; i = cp. i; }
Chatterbox (Chatterbox && mv)
{ cout << "+ Chatterbox mv " << mv. i << endl; i = mv. i; }
~Chatterbox ()
{ cout << "- Chatterbox " << i << endl; }
Chatterbox & operator = (const Chatterbox & asgn)
{ cout << ". Chatterbox = " << asgn. i << endl; i = asgn. i; return * this; }
Chatterbox & operator = (Chatterbox && mv)
{ cout << ". Chatterbox mv = " << mv. i << endl; i = mv. i; return * this; }
};
|
Sample output, first-time insertion of object 1 and 5:
--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox mv 2
+ Chatterbox mv 3
+ Chatterbox mv 4
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
--------------
Append cb 5
+ Chatterbox cp 5
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
|
C++11 move semantics with noexcept
If we tag the move constructor and the move assignment operator with the noexcept
keyword the std::vector calls these methods more frequently.
Please consider the following points:
- This is undocumented behavior which may or may not work.
- The number of the internal intermediate steps remains the same.
- In some cases the move constructor and the move assignment operator may throw exceptions.
class Chatterbox
{
int i;
public:
Chatterbox ()
{ cout << "+ Chatterbox" << endl; i = 0; }
Chatterbox (int init)
{ cout << "+ Chatterbox " << init << endl; i = init; }
Chatterbox (const Chatterbox & cp)
{ cout << "+ Chatterbox cp " << cp. i << endl; i = cp. i; }
Chatterbox (Chatterbox && mv) noexcept
{ cout << "+ Chatterbox mv " << mv. i << endl; i = mv. i; }
~Chatterbox ()
{ cout << "- Chatterbox " << i << endl; }
Chatterbox & operator = (const Chatterbox & asgn)
{ cout << ". Chatterbox = " << asgn. i << endl; i = asgn. i; return * this; }
Chatterbox & operator = (Chatterbox && mv) noexcept
{ cout << ". Chatterbox mv = " << mv. i << endl; i = mv. i; return * this; }
};
|
Sample output, first-time insertion of object 1 and 5:
--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox mv 2
+ Chatterbox mv 3
+ Chatterbox mv 4
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
--------------
Append cb 5
+ Chatterbox cp 5
+ Chatterbox mv 1
+ Chatterbox mv 2
+ Chatterbox mv 3
+ Chatterbox mv 4
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
|
Background info
Documentation: cppreference.com
The C++ language standard ISO/IEC 14882, version C++20, describes the class properties
"trivially copyable" (6.8, 11.2.1) and "standard-layout" (11.2.5).
Older language standards additionally describe the class property POD (Plain Old Data, 14882:2017 6.9.9).
Since C++20 this property is deprecated.
According to C++20 6.8 "trivially copyable" objects may be copied and moved
in memory by using memcpy and memmove.
The standard document does not provide information about objects which are not "trivially copyable".
The C++ language standard also describes the API and the semantics of container templates
like std::vector. The specific implementation is the job of the compiler engineer.
A std::vector must be able to process any C++ objects, not only "trivially copyable" objects.
That's why the implementations don't use realloc, memcpy and memmove.
See also: C++ Object relocation, Published Proposal
"It is intended that most standard library types be trivially relocatable types."
Possible optimizations
In practice, almost all C++ objects can be relocated by memcpy
and memmove without any side effects.
Note: We talk about relocating complete objects ("most derived object", C++20 6.7.2.2, 6.7.2.6),
not about "potentially-overlapping subobjects" (C++20 6.7.2.7).
A container like std::vector always contains complete objects.
Note also: We talk about moving elements inside of a dynamic array container
(relocating objects to a different position in memory),
not about duplicating objects using memcpy.
There are, among others, the following possibilities to improve the performance of dynamic array containers:
- If an object is inserted or deleted, the following objects can be moved by
memmove.
- If the size of the internal memory block has to be changed, the block is simply reallocated.
- An optimized memory management reduces the number of reallocations and the memory fragmentation.
Source code
Here are the source codes of the three test programs without and with move semantics:
01_vector1.cpp
01_vector2.cpp
01_vector3.cpp
