Interesting observation (predicate with std::sort)
Victor Bazarov
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
Stephen Howe
>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.
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.
Stephen Howe
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....
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".
--
James Kanze
James Kanze
> On Tue, 02 Feb 2010 12:58:12 -0500, Victor Bazarov
> <v.Abaza...@comAcast.net> 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