Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Interesting observation (predicate with std::sort)

Reply
Thread Tools

Interesting observation (predicate with std::sort)

 
 
Victor Bazarov
Guest
Posts: n/a
 
      02-02-2010
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
 
Reply With Quote
 
 
 
 
red floyd
Guest
Posts: n/a
 
      02-02-2010
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....
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      02-02-2010
On Feb 2, 5:58 pm, Victor Bazarov <(E-Mail Removed)> 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
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      02-02-2010
On Feb 2, 7:06 pm, Stephen Howe <sjhoweATdialDOTpipexDOTcom> wrote:
> On Tue, 02 Feb 2010 12:58:12 -0500, Victor Bazarov
> <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Interesting observation Maybe Computer Support 21 07-24-2006 06:29 PM
An Interesting Observation Sameer Java 2 01-09-2006 10:05 PM
just an observation Adam Bailey Firefox 2 11-16-2003 07:28 AM
.NET Books - Observation dotnetjournal MCSD 0 11-13-2003 12:16 PM
New Observation Ezeh Ikechukwu MCSE 4 09-19-2003 10:30 PM



Advertisments