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

Discussion in 'C++' started by ma740988, Oct 11, 2006.

  1. ma740988

    ma740988 Guest

    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 .
    ma740988, Oct 11, 2006
    #1
    1. Advertising

  2. ma740988

    Noah Roberts Guest

    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.
    Noah Roberts, Oct 12, 2006
    #2
    1. Advertising

  3. * 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.

    --
    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?
    Alf P. Steinbach, Oct 12, 2006
    #3
  4. ma740988

    red floyd Guest

    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.
    red floyd, Oct 12, 2006
    #4
  5. * 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.asc> and
    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?
    Alf P. Steinbach, Oct 12, 2006
    #5
  6. ma740988

    Earl Purple Guest

    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.
    Earl Purple, Oct 12, 2006
    #6
  7. ma740988

    Guest

    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, 2006
    #7
  8. ma740988

    Earl Purple Guest

    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?
    Earl Purple, Oct 12, 2006
    #8
  9. ma740988

    Kai-Uwe Bux Guest

    Earl Purple wrote:

    >
    > 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
    Kai-Uwe Bux, Oct 12, 2006
    #9
  10. ma740988

    Greg Guest

    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
    Greg, Oct 13, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Davis King

    std::swap and exceptions

    Davis King, Jul 20, 2003, in forum: C++
    Replies:
    2
    Views:
    353
    Davis King
    Jul 20, 2003
  2. Marcin Kalicinski

    Custom swap in std namespace

    Marcin Kalicinski, Dec 5, 2005, in forum: C++
    Replies:
    2
    Views:
    323
    red floyd
    Dec 5, 2005
  3. Jason Heyes
    Replies:
    8
    Views:
    703
    Andrew Koenig
    Jan 15, 2006
  4. Niels Dekker (no reply address)

    What swap is called when using std::swap?

    Niels Dekker (no reply address), Jul 19, 2006, in forum: C++
    Replies:
    4
    Views:
    970
    Niels Dekker (no reply address)
    Jul 20, 2006
  5. ma740988

    composite types and std::swap

    ma740988, Mar 24, 2007, in forum: C++
    Replies:
    1
    Views:
    254
    Alf P. Steinbach
    Mar 24, 2007
Loading...

Share This Page