Interesting observation (predicate with std::sort)

Discussion in 'C++' started by Victor Bazarov, Feb 2, 2010.

  1. Hello,

    You might find this interesting/useful...

    Using a temporary object as a class predicate with 'std::sort' turned
    out to be faster than using a function pointer. Check it out:
    ------------------------------------------------------------------ >8
    #include <iostream>
    #include <ostream>
    #include <time.h>
    #include <algorithm>

    struct S
    {
    int i;
    double d;
    S(int i_ = 0, double d_ = 0) : i(i_), d(d_) {}
    };

    bool compareFunc(S const &s1, S const &s2)
    {
    return s1.i < s2.i || (s1.i == s2.i && s1.d < s2.d);
    }

    struct compareFunctor
    {
    bool operator()(S const &s1, S const &s2) const
    {
    return s1.i < s2.i || (s1.i == s2.i && s1.d < s2.d);
    }
    };

    int main()
    {
    const int MANY = 50000000;
    S *sArr = new S[MANY];

    clock_t c0 = clock();
    std::sort(sArr, sArr + MANY, compareFunc);
    clock_t c1 = clock();
    std::sort(sArr, sArr + MANY, compareFunctor());
    clock_t c2 = clock();

    std::cout << "std::sort with a function as a predicate "
    << c1 - c0 << std::endl;
    std::cout << "std::sort with a functor for a predicate "
    << c2 - c1 << std::endl;

    std::cout << "Once more...";

    clock_t c10 = clock();
    std::sort(sArr, sArr + MANY, compareFunctor());
    clock_t c11 = clock();
    std::sort(sArr, sArr + MANY, compareFunc);
    clock_t c12 = clock();

    std::cout << std::endl;
    std::cout << "std::sort with a function as a predicate "
    << c12 - c11 << std::endl;
    std::cout << "std::sort with a functor for a predicate "
    << c11 - c10 << std::endl;

    delete[] sArr;
    }
    ------------------------------------------------------------------ >8
    Results (on my machine):

    std::sort with a function as a predicate 375
    std::sort with a functor for a predicate 264
    Once more...
    std::sort with a function as a predicate 375
    std::sort with a functor for a predicate 261

    My guess is that the compiler I used (VC9) manages to inline the functor
    code (a member function operator()) better than it can a stand-alone
    function when they are used as the predicate of 'std::sort'.

    I am sure I'm not the first one to find this, I just hadn't run across
    that behaviour until a few days ago.

    Do criticize it, of course.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Feb 2, 2010
    #1
    1. Advertising

  2. Victor Bazarov

    red floyd Guest

    On Feb 2, 11:06 am, Stephen Howe <sjhoweATdialDOTpipexDOTcom> wrote:

    > But I am wondering, what are the benefits to making sure yoru functor is publically derived from unary_function and
    > binary_function? Can the compiler and/or library do additional optimisations because they can infer sometihng on the types?
    > I am not seeing any mileage but I would like to be convinced for/against.
    >


    Internal typedefs, such as first_argument_type, result_type, etc....
    red floyd, Feb 2, 2010
    #2
    1. Advertising

  3. Victor Bazarov

    James Kanze Guest

    On Feb 2, 5:58 pm, Victor Bazarov <> wrote:

    > You might find this interesting/useful...


    > Using a temporary object as a class predicate with 'std::sort'
    > turned out to be faster than using a function pointer.


    > My guess is that the compiler I used (VC9) manages to inline
    > the functor code (a member function operator()) better than it
    > can a stand-alone function when they are used as the predicate
    > of 'std::sort'.


    In general, if you use a pointer to a function, the type the
    compiler instantiates the template over is something like bool
    (*f)( int, int ). You can use a lot of different functions with
    that instantiation, so unless the compiler inlines everything
    (so that the fact that the function pointer is a constant
    propagates down to the lowest level), it has to use a call
    through the pointer. If you use a functional object, the type
    is FunctionalObject; there's only one possible function that can
    be called, and the compiler can inline it even if it doesn't
    inline the sort function itself.

    > I am sure I'm not the first one to find this, I just hadn't
    > run across that behaviour until a few days ago.


    It's a more or less well known fact. For appropriate meanings
    of "well known" and "fact".

    --
    James Kanze
    James Kanze, Feb 2, 2010
    #3
  4. Victor Bazarov

    James Kanze Guest

    On Feb 2, 7:06 pm, Stephen Howe <sjhoweATdialDOTpipexDOTcom> wrote:
    > On Tue, 02 Feb 2010 12:58:12 -0500, Victor Bazarov
    > <> wrote:
    > >I am sure I'm not the first one to find this, I just hadn't
    > >run across that behaviour until a few days ago.


    > Yes I found this out recently. I dont believe the compiler can
    > inline function pointers (what the function decays to) whereas
    > it can inline functors. Just about the entire STL runs on
    > functors so supplying functors is better.


    In theory, a compiler can inline anything it knows about. The
    problem is that the instantiation type doesn't tell the compiler
    which function will be called in the case of a pointer to
    function; it does in the case of a functional object.

    > But I am wondering, what are the benefits to making sure yoru
    > functor is publically derived from unary_function and
    > binary_function? Can the compiler and/or library do additional
    > optimisations because they can infer sometihng on the types?


    > I am not seeing any mileage but I would like to be convinced
    > for/against.


    It allows your functional object to be combined with other types
    defined in <functional>. It has absolutely no effect in
    functions like sort.

    --
    James Kanze
    James Kanze, Feb 2, 2010
    #4
    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. Sameer

    An Interesting Observation

    Sameer, Jan 9, 2006, in forum: Java
    Replies:
    2
    Views:
    343
    Oliver Wong
    Jan 9, 2006
  2. hall
    Replies:
    4
    Views:
    656
  3. Replies:
    1
    Views:
    484
    Marcus Kwok
    Apr 6, 2007
  4. Replies:
    4
    Views:
    472
  5. Ganesh
    Replies:
    3
    Views:
    360
    James Kanze
    Sep 30, 2008
Loading...

Share This Page