473,320 Members | 2,147 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

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



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 .

Oct 11 '06 #1
9 6143

ma740988 wrote:
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.

Oct 11 '06 #2
* 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 _Allocinline
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.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Oct 11 '06 #3
Alf P. Steinbach wrote:
* Noah Roberts -ma740988, about algorithmic complexity:
>>
You are not using std::swap() you are using std::vector::swap. There
is a significant difference.

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.
Oct 12 '06 #4
* red floyd:
Alf P. Steinbach wrote:
>* Noah Roberts -ma740988, about algorithmic complexity:
>>>
You are not using std::swap() you are using std::vector::swap. There
is a significant difference.


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.ascand
perhaps also <url: http://www.gotw.ca/publications/mill17.htm>.

Cheers,

- Alf

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Oct 12 '06 #5

ma740988 wrote:
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.

Oct 12 '06 #6
ma740988 wrote:
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

Oct 12 '06 #7

Mi*************@tomtom.com wrote:
ma740988 wrote:
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.
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?

Oct 12 '06 #8
Earl Purple wrote:
>
Mi*************@tomtom.com wrote:
>ma740988 wrote:
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.

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

Oct 12 '06 #9

ma740988 wrote:
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

Oct 13 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Davis King | last post by:
Can I assume that std::swap will not throw when it is used to swap std::string objects? In the standard it says that the swap() std::string member function runs in constant time. I didn't see...
5
by: Steve Hill | last post by:
Hi, suppose I have a vector allocated on the heap. Can I use a temporary (stack based vector) and swap to clear it, or is this unsafe. e.g. vector<int> *v; vector<int> tmp; v->swap(tmp); // is...
17
by: beliavsky | last post by:
Many of my C++ programs have the line using namespace std; but the "Accelerated C++" book of Koenig and Moo has many examples where the library names are included one at a time, for example ...
2
by: ma740988 | last post by:
So I'm reading the C++ coding standards(Shutter & Andrei), more specifically item 56. There's a statement: "Prefer to provide a nonmember swap function in the same namespace as your type when...
8
by: Jason Heyes | last post by:
Does the STL have a function like this one? template <typename T> void remove(std::vector<T> &v, std::vector<T>::size_type index) { std::swap(v, v.back()); v.resize(index); } Unlike...
1
by: Sung Jin Hwang | last post by:
Hi. Is there a good way to extend std::swap to user type classes? Overloading can be a solution but when user type is not a class but class template, we need partial specialization and function...
4
by: Niels Dekker (no reply address) | last post by:
When calling swap as follows (as recommanded in Effective C++, 3rd Edition, by Scott Meyers), what swap is chosen to be called? using std::swap; swap(a, b); Suppose there is a global ::swap...
1
by: ma740988 | last post by:
Consider the source snippet. # include <iostream> struct foo_struct { int odx ; int pdx ; foo_struct () : odx ( 0 ) , pdx ( 0 )
11
by: Dennis Jones | last post by:
Hi all, 1) Let's say you have two char 's of the same size. How would you write a no-fail swap method for them? For example: class Test { char s; void swap( Test &rhs ) {
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.