This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]