Object Swapping, Part 2: Algorithms Can Often Swap Instead of Copy
Last week I introduced swapping, and mentioned that is it often faster than assignment — a fact that often allows algorithms that swap to be dramatically faster than they would be if they used assignment. Here's why.
C++ requires all objects of a given class to have the same size, and for the size to be known during compilation. This requirement makes it possible for the compiler to lay out each function's stack memory during compilation, thereby making it much easier to generate efficient machine code.
Of course, this requirement conflicts with the desire for variable-sized data structures such as strings and vectors. The C++ library deals with this conflict by implementing each such data structure as a fixed-size part, which resides in each object, and a variable-size part, which the library allocates and frees dynamically. A string or vector therefore consists typically of a small amount of information that includes a pointer to dynamic memory containing the actual data.
Copying such a data structure requires allocating new dynamic memory and copying the data from the original into it. Destroying such a data structure requires freeing that dynamic memory. Both allocating and freeing dynamic memory are relatively slow operations. Moreover, copying the contents of the dynamic memory will also be slow if there is a lot to copy.
As a result of this implementation strategy, it is expensive to copy or destroy a string, vector, or similar data structure. Swapping two such data structures, on the other hand, is usually much simpler: It suffices to swap the contents of the objects themselves, and the dynamic memory can be left alone. As a result, swapping two such data structures is often much faster than copying or destroying them. If the contents are large, the speed difference can be a factor of 100 or more.
Now let's think about a vector of strings, which we'll name
vs. Here is a code fragment to remove element number
vs. We will assume that
n is unsigned:
assert (n < vs.size()); for (size_t i = n+1; i != vs.size(); ++i) vs[i-1] = vs[i]; vs.resize(vs.size()–1);
assert does not need to check that
n >= 0 because
n is unsigned; so of course it is always
for loop copies
vs[n], then copies
vs[n+1], and so on. After it has finished, we no longer need the last element of
vs, so we shrink
vs by one, discarding the last element.
This code is capable of wasting a great deal of time. Copying
vs[n] creates a copy of
vs[n+1], after which the original
vs[n+1] is overwritten by a copy of
vs[n+2] , and so on. So all but one of the elements following
vs[n] will be copied and the copies then overwritten.
Now consider this rewrite:
assert (n < vs.size()); for (size_t i = n+1; i != vs.size(); ++i) vs[i].swap(vs[i-1]); // changed vs.resize(vs.size()–1);
In this version, instead of copying each element after
vs[n] into its predecessor, we swap the elements. When the loop completes, the original value of
vs[n] will have been swapped all the way into the last element of
vs, so it is this original value that the call to
vs.resize will destroy. Moreover, the loop will accomplish this feat without ever making a copy of any element of
This example suggests a general principle:
For types that are faster to swap than to copy, a sequence of assignments of the form a = b; b = c; … will be faster if rewritten as swap(a, b); swap(b, c); and so on.
If it is necessary to preserve the last value in the sequence, the last assignment can be left alone. So, for example,
a = b; b = c; c = d; d = e;
swap(a, b); swap(b, c); swap(c, d); d = e;
and only the value of
e is copied.
Of course, this swapping strategy is similar to the strategy for using the move operation that is part of C++11. Next week we will look at the curious relationship between swapping and moving.