A question on std::swap and it's performance

[ma740988]

Consider:

# include <vector>
# include <iostream>
# include <cstdlib>
# include <ctime>

bool
ispow2i ( double n )
{
double r = ( n <= 0 ) ? 0.5 : std::log ( n ) / std::log ( 2. ) ;
if ( fmod ( r, 1 ) > 0.5 )
return ( -r + static_cast<long>( r + 1 ) ) < 0.00000000001;
else
return ( r - static_cast<long>( r ) ) < 0.00000000001;
}
typedef std::vector < int > INT_VEC;
int main()
{
INT_VEC iv;
for ( size_t idx ( 1024 ); idx < 0x100000 + 1; ++idx )
{
if ( ispow2i ( idx ) )
iv.push_back ( idx ) ;
}


int const num_iterations ( 50 );

for ( INT_VEC::size_type jdx ( 0 ); jdx < iv.size(); ++jdx )
{
int const NumSamples = iv [ jdx ];
INT_VEC iv2 ( NumSamples, jdx );
INT_VEC iv3;

for ( int idx ( 0 ) ; idx < num_iterations; ++idx )
{
// start time
iv3.swap ( iv2 ) ;
iv2.swap ( iv3 ) ;
// elapsed time
}
}

return ( EXIT_SUCCESS ) ;
}

The code was actually executed on a power pc - as a result the timer
class is specific to that of a power pc. That aside, profiling
surrounded the lines marked "start time" and "elapsed time" . In
essense, I stored the time in a vector then computed the elapsed time
for each iteration. Details aside, if memory serves std::swap executes
in linear time. What's troubling is the fact that the elapsed time was
on average .55 microseconds +/- .02 for all for NumSamples. I would
expect a linear behavior. i.e a gradual increase as NumSamples
increased. Is there something amiss in my logic ?

Thanks in advance .

 

[Noah Roberts]

Consider:

# include <vector>

INT_VEC iv2 ( NumSamples, jdx );
INT_VEC iv3;

// start time
iv3.swap ( iv2 ) ;
iv2.swap ( iv3 ) ;

The code was actually executed on a power pc - as a result the timer
class is specific to that of a power pc. That aside, profiling
surrounded the lines marked "start time" and "elapsed time" . In
essense, I stored the time in a vector then computed the elapsed time
for each iteration. Details aside, if memory serves std::swap executes
in linear time. What's troubling is the fact that the elapsed time was
on average .55 microseconds +/- .02 for all for NumSamples. I would
expect a linear behavior. i.e a gradual increase as NumSamples
increased. Is there something amiss in my logic ?

You are not using std::swap() you are using std::vector::swap. There
is a significant difference.

 

[Alf P. Steinbach]

* Noah Roberts -> ma740988, about algorithmic complexity:

You are not using std::swap() you are using std::vector::swap. There
is a significant difference.

Uh, no, except possibly for notation and clarity.

Consider this overload of std::swap, from the MSVC 7.1 standard library
implementation:

template<class _Ty, class _Alloc> inline
void swap(vector<_Ty, _Alloc>& _Left, vector<_Ty, _Alloc>& _Right)
{ // swap _Left and _Right vectors
_Left.swap(_Right);
}

This is not a partial specialization of a function template (which for
some unfathomable reason isn't allowed[1]), it's an overload, and its
existence is specified or at least implied by the general library
container requirements listed in §23.1/5.

The only catch is that swap only /should/ have constant time complexity
for a standard container, but whether it actually has is up to the
implementor.

In practice, though, a C++ implementation where swap didn't have
constant time complexity for standard containers, would be one not used.

Cheers,

- Alf


Notes:

[1] An article in DDJ, whose author may well be the author of the code
snippet above, stated that this is a partial specialization; it's not.

 

[red floyd]

* Noah Roberts -> ma740988, about algorithmic complexity:

No, Alf, if you look at the OP's code, he's calling the member function
swap.

Now, this may wind up calling a specialization of std::swap for vectors,
but that's an implementation specific detail.

 

[Alf P. Steinbach]

* red floyd:

No, Alf, if you look at the OP's code, he's calling the member function
swap.

Now, this may wind up calling a specialization of std::swap for vectors,
but that's an implementation specific detail.

Not sure what you mean. The above seems self-contradicting or perhaps
just backwards -- it's std::swap that does the calling! And the quoting
(nothing I wrote is quoted in your quote of me) is also difficult to
understand; perhaps what you meant to quote was swallowed by the text
editor daemon, always lurking under the keyboard?

Anyway, the overload of std::swap for std::vector arguments that I
mentioned is specified by §23.2.4/2, so it's hardly implementation
specific; at least not for a conforming implementation.

Regarding such overloads being overloads and not partial
specializations, if that's an issue?, see §14/2 as well as
<url: http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2001/n1295.asc> and
perhaps also <url: http://www.gotw.ca/publications/mill17.htm>.

Cheers,

- Alf

 

[Earl Purple]

bool
ispow2i ( double n )
{
double r = ( n <= 0 ) ? 0.5 : std::log ( n ) / std::log ( 2. ) ;
if ( fmod ( r, 1 ) > 0.5 )
return ( -r + static_cast<long>( r + 1 ) ) < 0.00000000001;
else
return ( r - static_cast<long>( r ) ) < 0.00000000001;
}

Given that you pass this integers it is a very inefficient way of
checking for a power of 2. A feature that is true for all powers of 2
(and not for other numbers) is that if you "and" it with N-1 then it
yields 0. This happens also for 0 itself (which we will assume is not a
power of 2) so we can exclude that case. Thus:

inline bool ispow2i( unsigned int n )
{
return (n != 0) && (( n & (n-1) ) == 0);
}

Note you can have this overload in addition to your above function.

 

[Michiel.Salters]

typedef std::vector < int > INT_VEC;
INT_VEC iv2 ( NumSamples, jdx );
INT_VEC iv3;
iv3.swap ( iv2 ) ;

That's not std::swap(T,T).

To get std::swap, write std::swap(iv2, iv3);

Member swap's performance often is the same, though.

HTH,
Michiel Salters

 

[Earl Purple]

That's not std::swap(T,T).

To get std::swap, write std::swap(iv2, iv3);

Member swap's performance often is the same, though.

std::swap won't call member-swap unless you overload it to. For vector
it may already be overloaded.

Let's see if we can come up with has_member_swap. Can it be done? For a
type T it would be of type void ( *T::func )( T & ) but just because
there is a function with such a signature doesn't mean it is definitely
a swap function.

I know one can overload functions to take a function pointer or ... but
can that be done just to compare the size of the return function or
could we actually use this?

 

[Kai-Uwe Bux]

std::swap won't call member-swap unless you overload it to. For vector
it may already be overloaded.

Not *may* but *is* -- see 23.2.4.4 in the standard:

template <class T, class Allocator>
void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
1 Effects:
x.swap(y);

Let's see if we can come up with has_member_swap. Can it be done? For a
type T it would be of type void ( *T::func )( T & ) but just because
there is a function with such a signature doesn't mean it is definitely
a swap function.

I know one can overload functions to take a function pointer or ... but
can that be done just to compare the size of the return function or
could we actually use this?

template < typename T >
class has_swap {
/*
stolen from Rani Sharoni, who attributes this to
Richard Smith and also Artem Livshits
*/

typedef char (&no) [1];
typedef char (&yes) [2];

template < typename S, void ( S::* ) ( S & ) >
struct dummy {};

template < typename S >
static
yes check ( dummy< S, &S::swap > * );

template < typename S >
static
no check ( ... );

public:

static bool const value = sizeof( check<T>(0) ) == sizeof( yes );

}; // has_swap

You can also use this to make a swap function that calls member swap if
available:


template < typename T >
struct swap_traits {
static const bool has_swap_method = has_swap<T>::value;
};

template < typename T,
bool has_swap_method = swap_traits<T>::has_swap_method >
struct Alg_Swap;

template < typename T >
struct Alg_Swap<T,false> {

static
void swap ( T & a, T & b ) {
std::swap( a, b );
}

}; // Alg_Swap<T>

template < typename T >
struct Alg_Swap<T,true> {

static
void swap ( T & a, T & b ) {
a.swap(b);
}

}; // Alg_Swap<T>

template < typename T >
void swap ( T & a, T & b ) {
Alg_Swap<T>::swap(a,b);
}


Best

Kai-Uwe Bux

 

[Greg]

The code was actually executed on a power pc - as a result the timer
class is specific to that of a power pc. That aside, profiling
surrounded the lines marked "start time" and "elapsed time" . In
essense, I stored the time in a vector then computed the elapsed time
for each iteration. Details aside, if memory serves std::swap executes
in linear time. What's troubling is the fact that the elapsed time was
on average .55 microseconds +/- .02 for all for NumSamples. I would
expect a linear behavior. i.e a gradual increase as NumSamples
increased. Is there something amiss in my logic ?

Since swapping two vectors likely does little more than swap two
pointers (to the allocated storage for the vector's elements), it would
make more sense that any measurable relationship between the size of
the vectors and the time it takes to swap them, would be the much more
disturbing discovery.

Greg