Interesting observation (predicate with std::sort)

V

Victor Bazarov

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
 
R

red floyd

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....
 
J

James Kanze

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".
 
J

James Kanze

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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top