C++ Move Semantics Using std::move to reduce complexity from O(n²) to O(n)
Example
C++11 introduced core language and standard library support for moving an object. The idea is that when an object o is a temporary and one wants a logical copy, then its safe to just pilfer o's resources, such as a dynamically allocated buffer, leaving o logically empty but still destructible and copyable.
The core language support is mainly
-
the rvalue reference type builder
&&, e.g.,std::string&&is an rvalue reference to astd::string, indicating that that referred to object is a temporary whose resources can just be pilfered (i.e. moved) -
special support for a move constructor
T( T&& ), which is supposed to efficiently move resources from the specified other object, instead of actually copying those resources, and -
special support for a move assignment operator
auto operator=(T&&) -> T&, which also is supposed to move from the source.
The standard library support is mainly the std::move function template from the <utility> header. This function produces an rvalue reference to the specified object, indicating that it can be moved from, just as if it were a temporary.
For a container actual copying is typically of O(n) complexity, where n is the number of items in the container, while moving is O(1), constant time. And for an algorithm that logically copies that container n times, this can reduce the complexity from the usually impractical O(n²) to just linear O(n).
In his article “Containers That Never Change” in Dr. Dobbs Journal in September 19 2013, Andrew Koenig presented an interesting example of algorithmic inefficiency when using a style of programming where variables are immutable after initialization. With this style loops are generally expressed using recursion. And for some algorithms such as generating a Collatz sequence, the recursion requires logically copying a container:
// Based on an example by Andrew Koenig in his Dr. Dobbs Journal article
// “Containers That Never Change” September 19, 2013, available at
// <url: http://www.drdobbs.com/cpp/containters-that-never-change/240161543>
// Includes here, e.g. <vector>
namespace my {
template< class Item >
using Vector_ = /* E.g. std::vector<Item> */;
auto concat( Vector_<int> const& v, int const x )
-> Vector_<int>
{
auto result{ v };
result.push_back( x );
return result;
}
auto collatz_aux( int const n, Vector_<int> const& result )
-> Vector_<int>
{
if( n == 1 )
{
return result;
}
auto const new_result = concat( result, n );
if( n % 2 == 0 )
{
return collatz_aux( n/2, new_result );
}
else
{
return collatz_aux( 3*n + 1, new_result );
}
}
auto collatz( int const n )
-> Vector_<int>
{
assert( n != 0 );
return collatz_aux( n, Vector_<int>() );
}
} // namespace my
#include <iostream>
using namespace std;
auto main() -> int
{
for( int const x : my::collatz( 42 ) )
{
cout << x << ' ';
}
cout << '\n';
}
Output:
42 21 64 32 16 8 4 2
The number of item copy operations due to copying of the vectors is here roughly O(n²), since it's the sum 1 + 2 + 3 + ... n.
In concrete numbers, with g++ and Visual C++ compilers the above invocation of collatz(42) resulted in a Collatz sequence of 8 items and 36 item copy operations (8*7/2 = 28, plus some) in vector copy constructor calls.
All of these item copy operations can be removed by simply moving vectors whose values are not needed anymore. To do this it's necessary to remove const and reference for the vector type arguments, passing the vectors by value. The function returns are already automatically optimized. For the calls where vectors are passed, and not used again further on in the function, just apply std::move to move those buffers rather than actually copying them:
using std::move;
auto concat( Vector_<int> v, int const x )
-> Vector_<int>
{
v.push_back( x );
// warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
// See https://stackoverflow.com/documentation/c%2b%2b/2489/copy-elision
// return move( v );
return v;
}
auto collatz_aux( int const n, Vector_<int> result )
-> Vector_<int>
{
if( n == 1 )
{
return result;
}
auto new_result = concat( move( result ), n );
struct result; // Make absolutely sure no use of `result` after this.
if( n % 2 == 0 )
{
return collatz_aux( n/2, move( new_result ) );
}
else
{
return collatz_aux( 3*n + 1, move( new_result ) );
}
}
auto collatz( int const n )
-> Vector_<int>
{
assert( n != 0 );
return collatz_aux( n, Vector_<int>() );
}
Here, with g++ and Visual C++ compilers, the number of item copy operations due to vector copy constructor invocations, was exactly 0.
The algorithm is necessarily still O(n) in the length of the Collatz sequence produced, but this is a quite dramatic improvement: O(n²) → O(n).
With some language support one could perhaps use moving and still express and enforce the immutability of a variable between its initialization and final move, after which any use of that variable should be an error. Alas, as of C++14 C++ does not support that. For loop-free code the no use after move can be enforced via a re-declaration of the relevant name as an incomplete struct, as with struct result; above, but this is ugly and not likely to be understood by other programmers; also the diagnostics can be quite misleading.
Summing up, the C++ language and library support for moving allows drastic improvements in algorithm complexity, but due the support's incompleteness, at the cost of forsaking the code correctness guarantees and code clarity that const can provide.
For completeness, the instrumented vector class used to measure the number of item copy operations due to copy constructor invocations:
template< class Item >
class Copy_tracking_vector
{
private:
static auto n_copy_ops()
-> int&
{
static int value;
return value;
}
vector<Item> items_;
public:
static auto n() -> int { return n_copy_ops(); }
void push_back( Item const& o ) { items_.push_back( o ); }
auto begin() const { return items_.begin(); }
auto end() const { return items_.end(); }
Copy_tracking_vector(){}
Copy_tracking_vector( Copy_tracking_vector const& other )
: items_( other.items_ )
{ n_copy_ops() += items_.size(); }
Copy_tracking_vector( Copy_tracking_vector&& other )
: items_( move( other.items_ ) )
{}
};
