This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Proposal: Improving <algorithm> performance with containers of containers
- From: Chris Jefferson <caj at cs dot york dot ac dot uk>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Sat, 26 Feb 2005 13:59:15 +0000
- Subject: Proposal: Improving <algorithm> performance with containers of containers
Hello.
I should point out in advance that I've said most of the things in this
e-mail before, but I thought I'd put them in one place "offically", in
case anyone wanted to make any final comments :)
The problem i intend to tackle is that of the fact that many of the
mutating algorithms, such as sort, perform unnessasary copies of large
objects when sorting a (for example) vector<vector<int> >. There are 3
main methods of tackling this. I present them in order of speed, fastest
first:
1) Introduce a system whereby objects are "memmove"d around. This is the
fastest. However it has the disadvantages that a) it is quite fragile
and b) It would require a safe way of declaring stack space big enough
to hold a T for some type T, moving it into this space (obvously without
previously constructing a T there) and then it being usable. This
appears difficult if not impossible to perform in a safe manner.
2) For each algorithm implent two versions, the normal version and a
swapping version. This is the least complex, but involves a doubling of
the number of algorithms.
3) Implement "move symantics". This can be, for the needs of the
standard library, entirely in templates. It is not quite as fast as a
specialised swapping implementation, but it is close. The move symaniics
I would implement would be "non-destructive", that is if we perform
a=move(b), at the end b is in a valid but unknown state (in actual fact
b will almost always still have it's old value, or have the value a had).
4) Implement a swapping version of the library, remove the non-swapping
implementations of functions. This appears to have been suggested more
than once. At high optimisation levels this is almost as fast on basic
types as the non-swapping implementation, but performance is halved for
any user class which does not have an optimised swap.
I intend to implement 3, template-based move symantics, in such a way
that if these are ever added to the compiler or standard, it should be
easy to update to the "offical ones". This will involve adding moving
constructors to all the standard containers. The main performance
penalty will come from the introduction of a function called (probably)
__moveable, which for non-swapable types will be implemented much like:
template<class T>
T& __moveable(T& t)
{ return t; }
So should be entirely optimised away at any level which does inlining,
but probably not for O(1).
I'd like to try to get this into 4.1 / so_7, and already have quite a
bit of the implementation of all 4 of these, so hopefully that should be
possible.
Chris