02-01-09 - Swap and Templates Part 2

So I'm back into the nightmare of std::swap and template overloading. I've been working on my cb::hash_table a bit, which I built on cb::vector so I'm seeing a lot of stuff with vector. One issue is when the vector changes capacity, you have to copy all the data over and delete the old ones. The normal way to implement vector is to do this with a bunch of uninitialized copy constructor calls, then call the destructor on all the old data. But that copy can be very expensive, and worse if your objects are large in memory it means you can temporarily double your memory use.

So I had the idea to use swap. When the vector capacity changes, first go ahead and default construct everything in the new space so it's valid. Then ::swap the new to the old, and then destruct the old vector. This is of course actually not ideal, what you really want is a single call that would "swap_construct" and object so that you don't have to default construct anything. But anyhoo, for many types of data it's easy to make a very cheap default constructor and a very fast swap.

Apparently this idea is old, and in fact newer versions of the Dinkum STL do this, they call it Swaptimization which you can find on that page if you search for swap. BTW it's also obvious that sometimes swapping is worse, eg. for vector< int > - but it's never much worse. If you wanted maximimum speed on silly cases like that, you could use a type-traits template to choose whether the class prefers swapping or copying. Actually in my old versions of my own vector I had a lot of type-traits to select the most efficient operation, but I've ripped that all out now. I find it too fragile and just also not important. (note that most STL implementations now use type traits for acceleration; I think this is really loathsome, because it's not exposed in a standard way, so you can't get to it for your own types - it makes them fact on basic types and their own types, and slow on your types, which blows - the whole idea of generic programming is that you can adapt it to work on your types, but the standards people have recently started giving special treatment to things in the STL, for example the STL gets different name lookup rules now (wtf)). (for type traits in the STL see for example stuff like "_IsOKToMemCpy" and "has_trivial_destructor" in STLport.)

Anyhoo, the problem now is that you need to make sure the right swap() is called. Ruh roh. You can't really correct overload std::swap in the std namespace ; see for example : STL defects #225-227 or PDF post about swap problems by Alan Griffiths . or C++ Standards - The "swap" Problem

So, what might you do instead? One option is to define your own swap() in your own namespace, and rely on the Koenig lookup to find your swap (cuz your objects are in your namespace). That doesn't work, partly because the STL calls std::swap explicitly. I'm not sure why they do that instead of just calling swap(). Apparently new MSVC uses ADL_Swap or some funny mumbo jumbo to try to fix this.

In any case, I have a hacky solution that I'm using for now.

I go into the STL headers to the definition of std::swap. It should look something like this :

   template < class _Tp >
   inline void swap(_Tp& __a, _Tp& __b) {
     _Tp __tmp = __a;
     __a = __b;
     __b = __tmp;
   }   

I change that to :

   template < class _Tp >
   inline void swap(_Tp& __a, _Tp& __b) {
     MySwap(a,b);
   }   

Now in my own code I have MySwap :

template < typename Type >
struct swap_functor
{
   void operator () (Type &a,Type &b)
   {
      Type c = a; a = b; b = c;
   }
};

template< typename Type > inline void MySwap(Type &a,Type &b)
{
   swap_functor< Type >()(a,b);
}

Which redirects MySwap to a functor, and the default implementation is the usual swap.

The reason to go to a functor is that you can take advantage of partial specialization due to the stronger support for class templates as opposed to function templates. Thus you can easily partial-specialize to all types of vectors (for example) :

template < class t_entry > 
struct swap_functor< cb::vector< t_entry > >
{
   void operator () ( cb::vector< t_entry > & _Left, cb::vector< t_entry > & _Right)
   {
      _Left.swap(_Right);
   }
};

The reason we do the redirects like this is that when you call anything in std::algorithms, they will call std::swap. First of all they will call the STL-provided overrides for std::swap for various STL types (like std::vector and std::string). Then they will call to the default, which calls MySwap. MySwap will go to the specializations that I wanted for my types. Finally it will fall back to the default swap.

This is the only way I know of to get specialization for both my types and the STL types. Note that to get the specializations on the std types, you have to call std::swap() - it's the "outermost" swap, and you always need to call to the leaves.

Now, for example, if I wanted to also get somebody else's library integrated, call it "somelib" that implements "somelib::swap" , I would do all the above, but the cb::swap_functor default implementation would be changed to call somelib::swap. Again everyone should call std::swap to get all the specializations.

Obviously this is not ideal because it involves digging into other people's libraries.

BTW using Swap in vectors is obviously semantically much better, even if it isn't an optimization. If you consider default constructed objects to be "nulls" and objects that have been set up and pushed into a vector to be "initialized", then the standard copy way of growing a vector temporarily makes a bunch of new "initialized" objects. The swap way just moves them and doesn't temporary change the number. A common case is stuffing something like a shared_ptr ref-counted pointer into a vector - the swap way keeps the ref counts all invariant, while the copy way temporarily bumps the refs up then back down again.

BTW one thing I noticed while testing this is that std::sort doesn't seem to use swap (!?). I always thought it did. Other algorithms, like std::reverse and std::random_permutation do call std::swap. sort seems to invoke the copy constructor and assignment a lot. The RAD version rr::sort does work entirely through swap, which means it should beat std::sort very trivially in bad cases, like vector< vector< int > >

ADDENDUM : thanks to the commenters; I think what I like best is to make my swap_functor default to doing a *byte* swap. Then any object which wants to be swapped and can't stand to be byte swapped (very rare) would override swap_functor. Doing it that way means almost nobody ever has to override swap_functor, it just uses the default (byte swap) almost always.

BTW the cool way to byte swap is something like this :

#pragma pack(push)
#pragma pack(1)
template < int n_count >
  struct Bytes { char bytes[n_count]; };
#pragma pack(pop)

template < typename t_type >
void ByteCopy(t_type * pTo,const t_type & from)
{
   typedef Bytes< sizeof(t_type) > t_bytes;

   *(reinterpret_cast< t_bytes * >(pTo)) = reinterpret_cast< const t_bytes & >(from);
}

template < typename t_type >
void ByteSwap(t_type & a,t_type & b)
{
   typedef Bytes< sizeof(t_type) > t_bytes;

   t_bytes c; // don't use t_type cuz we don't want a constructor or destructor
   ByteCopy(&c,reinterpret_cast< const t_bytes & >(a));
   ByteCopy(&a,b);
   ByteCopy(&b,reinterpret_cast< const t_type & >(c));
}

The nice thing about this is for small types the compiler does the right thing and just generates mov instructions. For large types you would want to call a memswap function, but you would never do this on large types so punt.