Re: [RFA] Algorithms vs operator* and operator==

[Joe Buck <Joe dot Buck at synopsys dot COM>]

On Sat, Nov 06, 2004 at 09:41:42PM +0000, chris jefferson wrote:
> Connected to this, I've been investigating a number of the algorithms 
> where it can be much more efficent to implement them purely in terms of 
> swap rather than assignments (reverse, sort, and others) for those 
> classes where a swap is MUCH cheaper than an assignment (lists and 
> vectors come to mind). However a swap is twice as expensive as an 
> assignment for scalar classes, and could in theory be 3 times as 
> expensive for a big class which didn't implement a swap (although I'm 
> tempted to ignore these).
> 
> Therefore, similarily I have 3 options..
> 
> 1) Make the int, float, etc. case efficent
> 2) Make the vector, list, etc case efficent
> 3) Use somethiing like _is_scalar (and perhaps others.. is_pod comes to 
> mind)  to try to decide when to make the choice

The needed property is something that might be called "relocatable".

Many classes have the property that they can be relocated by means of
a shallow copy.  This is true of vector, list, string, map, hash_map,
and many user-written classes that store part of their state on the heap.
This property means that swap has a very efficient implementation, but
it goes beyond this.  Consider resizing a vector of strings, or a vector
of vectors.  It turns out that it would suffice to do a bitwise copy
of the old vector storage to the new vector storage, without calling
any constructors or destructors!  This can be hugely more efficient.

If a class has the relocatable property, then two can be swapped by just
swapping their data members, and just copying the data members from one
object to another is an efficient replacement for copy construction
followed by destruction of the source object.

If you can come up with some clean way of marking certain types as
relocatable, and design the library to take advantage of this, you'll
have a huge win.  Exposing the hook to the users is of course an
extension, but the implementation can give the attribute to all the
standard containers and to std::string, so users will just notice that
with g++, std::vector<std::string> is much faster than the competition.