swap_vector
Introduction
Probably the second most used container in the C++ standard library is
std::vector (with std::string being the most used). Like most standard
library containers std::vector has a small memory footprint (e.g. 3 pointers
in STLport) with the bulk of its storage being on the heap (on behalf of
its contained objects). This leads to the observation that it may be significantly
faster to swap elements rather than assign or copy construct them. So a
new std::vector like class template called swap_vector is proposed.
Copy construction
For primitive C/C++ types, copy construction (and assignment) is faster
than swapping. Furthermore there is no primitive C function to swap integers
(or pointers) so the "copy via a temporary variable" method is usually
employed. All the standard C++ containers support a swap(T &) method
which turns out to be useful for meeting exception safety guarantees [Sutter00].
As standard containers are nested within one another, for example vector<vector<string>
>, the cost of copy construction in the outer container increases markedly.
Interestingly, the cost of swapping elements in the outer container stays
the same. The swap() method in standard containers is guaranteed to be
constant time complexity. Other design idioms such as "pimpl" [Sutter00]
lead to objects that will have constant time complexity swap() methods.
Significant performance improvements can be obtained when vector<vector<string>
> (for example) is replaced by swap_vector<vector<string> >. Normally,
when swap is used to replace copy construction, then a default object construction
and a corresponding empty object destruction are required. So swapping
techniques used by swap_vector become attractive when this relation is
met (preferably by a comfortable margin).
time[copy_ctor] > (time[swap] +
time[default_ctor] + time[empty_dtor])
swap_vector
This class template has been implemented by just "borrowing" an existing
implementation of std::vector and keeping its interface. Several new member
functions have been added to allow elements to be passed to a swap_vector
using a swap rather than value semantics (i.e. using a copy constructor),
but strictly speaking these extra methods are not required. None of the
existing member functions borrowed for std::vector change their semantics.
When the new member functions are not being used, the only change is the
way the vector elements are re-arranged when an insert method (e.g. push_back()
) finds the internal storage all used up. Using STLport's implementation
of std::vector as a guide, a larger block (typically twice as big as before)
of contiguous memory is allocated and then the elements of the previous
block are copied across to the new, larger block. swap_vector still creates
the new, larger contiguous block but then uses the default constructor
to initialize the elements of the new block and swaps the original elements
into the new block. This leaves the old block full of default constructed
elements but the old block is destined to be deleted anyway.
If the contained class does not have a swap(T&) method then compilation
while break. However there is no way to check at compile time that a class
that supports swap(T&) has implemented it with the intended semantics.
[Another problem is that swap semantics may be supported by a differently
named member function (e.g. Swap(T &) ). An adapter class could take
care of this.]
swap_vector's extra methods
// swap second argument with element at pos
void swap_at(size_type pos, T &) throw(std::out_of_range);
// swap argument with empty object that was pushed
as part of this method
void swap_push_back(T &);
// swap second argument with empty object inserted
at before pos
typedef swap_vector<T>::iterator iterator;
iterator swap_insert(iterator pos, T &);
// swap the elements in the range [from, to[
with empty objects
// inserted before pos
void swap_insert(iterator pos, ForwardIterator from, ForwardIterator
to);
// first make the swap_vector (this) have the
same number of elements
// as [from, to[ (by adding empty objects at
the end or erasing objects),
// then swap each element in this with those
in [from, to[.
void swap_assign(ForwardIterator from, ForwardIterator to);
The last member function has some interesting possibilities. It allows
a large std::vector to be cheaply swapped into a swap_vector (and possibly
swapped again into a std::deque or a std::list). Swapping into associative
containers is more problematic :-)
Extensions
Some standard algorithms could have "swap" variants. std::reverse, sort
and stable_sort spring to mind. Would a swappable trait be useful?
Exception Safety
Intuitively the types for which swap_vector<T> is efficient, will
have a T::swap(T&) that moves pointers and integers rather than "heavy"
objects. For the case where T is a standard container then T::swap(T&)
gives the "no throw" guarantee. While swap_vector substitutes all copy
constructors with swap() calls when the capacity() is exceeded, there are
still copy constructors when arguments are passed into and out of the container.
[These "interface" copy constructors can be avoided by using the extra
methods outlined above, however standard algorithms will continue to use
the vector-like interface when given iterators to a swap_vector.] Also
swap_vector<T> uses T's default constructor a lot, but it is unlikely
that this will be less exception safe than T's copy constructor.
Implementation
An implementation is available which overlays on top of STLport's version
4.5.3 (current at the time of writing). The patch is non-invasive in the
sense that it does not modify any existing STLport files, it just adds
three new files. It has been tested on Linux (Mandrake 8.1 with a gcc 3.0
compiler), Solaris (5.0 with a Forte 5.3 C++ compiler), HP aCC (3.30) and
Visual Studio 7. A Makefile is included for Linux and Solaris. It is best
to unzip the tarball (or zip archive) in the directory that contains the
STLport-4.5.3 distribution. In the "my_test" directory there is a
test program which exercise swap_vector (and allows std::vector to be dropped
back in for timing comparisons).
The my_test program illustrates that swap_vector can be slower (around
15%) for repeated push_back()s on a vector of small strings. However, as
a contrived example, repeated insertion at the beginning of a vector<vector<string>
> can be over a magnitude faster if the outer vector is changed to a swap_vector.
Note: _STLP_DEBUG is not supported {need to add proper implementations
of stlport/stl/debug/_swap_vector.[hc] for that}. I am not STLport library
expert and this implementation could no doubt be improved by Boris Fomitchev
and his colleagues.
Downloads
Here is a gzipped tarball: swap_vec08.tgz
and this is a zip archive: swap_vec07.zip
. They have the similar contents.
[Sutter00] "Exceptional C++" by Herb Sutter, 2000 ISBN: 0-201-61562-2
Last updated: 7th April 2002
Douglas Gilbert
dgilbert@interlog.com
dougg@torque.net