Various template approaches to avoid pointer to function penalty

[StephQ]

This is from a thread that I posted on another forum some days ago.
I didn't get any response, so I'm proposing it in this ng in hope of
better luck :)

The standard explanation is that pointer to functions are hard to
inline for the compiler, and so you won't be able to avoid function
call overhead.
This is an important aspect when you are calling a function very
frequently for evaluation reason: think of the problem of performing
numerical integration of function double f(double x).
Another example is the qsort algorithm with different comparison
functions.
The various approaches that I found are:

1) If you are working with 1 function only:

A) Function object approach:
Suppose myfunc is a class with overloaded operator(), then we consider

template<class Fo>
double integrate(Fo f, int n) {
.....
sum += f(i/n);
.....
};
(I know you can use const Fo& f for better performances....)

and call the integration routine with:
integrate(myfunc(),10);

First question: what is myfunc() ? An object of type myfunc? Why?
I would have used:

myfunc f;
integrate(f, 10);

The object has to be created (as an obj of type myfunc is passed to
the function).
If I understand correctly integrate(f, 10) = integrate<myfunc>(f, 10)
as the argument is deduced....

B) Pointer to function as template parameter approach:
Suppose myfunc is a function (take and returns double), then

template<double fp(double)>
double integrate(int n) {
.....
sum += fp(i/n);
.....
};

integrate<myfunc>(10);

I understand the function obj approach is more general: here I just
have the function, previously I had a object (that can embed data and
functions).
Question: In this situation myfunc is not passed to integrate (more
precisely no pointer to this function is passed...). It's like when we
use template parameters for classes. I expect a "substitution" of fp
with the passed myfunc as the code is generated (like for template
classes).
Does this means that we have to distinguish between template arguments
objects that gets passed to the function and template arguments that
are "substituted" word by word like in classes? (see below D)

2) Now to the case where I'm passing more functions (like a function
and the first derivative, they belongs to the same "object").

C) Class as template parameter approach:
Suppose myclass is a class with member functions f1 f2 (as usual take
and return)

template<class fclass>
double integrate(int n) {
.....
sum += fclass::f1(i/n) + fclass::f2(i/n);
.....
};

integrate<myclass>(10);

Here again is it working like situation B?
In B I had a template parameter of type pointer to function, while
here I have a template type parameter.
Maybe the point is that, even if no object here is created I'm able to
use static data inside the class, and define functions f1, f2 that
depends on this data? (while previously I had no class, just the
pointer to function so this possibility was precluded...)

D) A more general apporach:
Suppose myclass is a class with member funcions f1 f2 (as usual double
double)

template<class fclass, double (flcass::*fun1)(double),
double(fclass::*fun2)(double)>
double integrate(int n, const fclass& fc) {
.....
sum += (fc.*fun1)(i/n) + (fc.*fun2)(i/n);
.....
};

myclass mc;
integrate<myclass, &myclass::f1, &myclass::f2>(10, mc);

I understand this approach is more general: not only I choose the
class, but also I can choose the functions of the class that I'm using
in integrate.
Also I create the obj class, so I can have different objects of the
same class with different data member values (while previously only
static data could be used).
I understand his use of pointers to member functions.
So do we need to consider:
fc.*fun1
because I'm considering the particular obj mc of type myclass (and so,
even if the function of every obj of type myclass are the same, they
may depend on different data inside this obj) ?

Do you have any general comment on these approaches?
Thank you in advance for any help!
Best Regards
StephQ

[Alf P. Steinbach]

* StephQ:

>
Do you have any general comment on these approaches?

Measure before you try to optimize.

--
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?

[Michael DOUBEZ]

StephQ a écrit :

This is from a thread that I posted on another forum some days ago.
I didn't get any response, so I'm proposing it in this ng in hope of
better luck :)

The standard explanation is that pointer to functions are hard to
inline for the compiler, and so you won't be able to avoid function
call overhead.
This is an important aspect when you are calling a function very
frequently for evaluation reason: think of the problem of performing
numerical integration of function double f(double x).
Another example is the qsort algorithm with different comparison
functions.
The various approaches that I found are:

1) If you are working with 1 function only:

A) Function object approach:
Suppose myfunc is a class with overloaded operator(), then we consider

template<class Fo>
double integrate(Fo f, int n) {
....
sum += f(i/n);
....
};
(I know you can use const Fo& f for better performances....)

and call the integration routine with:
integrate(myfunc(),10);

First question: what is myfunc() ? An object of type myfunc? Why?
I would have used:

myfunc f;
integrate(f, 10);

Named object used to prevent optimization. Perhaps this is a legacy.
Personnaly, I prefer integrate(myfunc(),10); because then I remember the
object is passed by value.

>
The object has to be created (as an obj of type myfunc is passed to
the function).
If I understand correctly integrate(f, 10) = integrate<myfunc>(f, 10)
as the argument is deduced....

B) Pointer to function as template parameter approach:
Suppose myfunc is a function (take and returns double), then

template<double fp(double)>
double integrate(int n) {
....
sum += fp(i/n);
....
};

integrate<myfunc>(10);

I understand the function obj approach is more general: here I just
have the function, previously I had a object (that can embed data and
functions).

And in particular object can take a parameter. This approach needs a new
function for each metaparameter.
By example, if I want to compute different sum of powered:
- object case:
struct powfun{
const int p;
powfun(int powval):p(powval){}
double operator(double x){return pow(x,p);
//...
};
And then
integrate(powfun(2),10);
integrate(powfun(3),10);
....
- function case
double pow2(double x){return pow(x,2);}
double pow3(double x){return pow(x,3);}
.....

Question: In this situation myfunc is not passed to integrate (more
precisely no pointer to this function is passed...). It's like when we
use template parameters for classes. I expect a "substitution" of fp
with the passed myfunc as the code is generated (like for template
classes).
Does this means that we have to distinguish between template arguments
objects that gets passed to the function and template arguments that
are "substituted" word by word like in classes? (see below D)

No but class can also carry traits which is not the case with function.
This is useful for object function composition.

>
2) Now to the case where I'm passing more functions (like a function
and the first derivative, they belongs to the same "object").

C) Class as template parameter approach:
Suppose myclass is a class with member functions f1 f2 (as usual take
and return)

template<class fclass>
double integrate(int n) {
....
sum += fclass::f1(i/n) + fclass::f2(i/n);
....
};

integrate<myclass>(10);

Here again is it working like situation B?
In B I had a template parameter of type pointer to function, while
here I have a template type parameter.
Maybe the point is that, even if no object here is created I'm able to
use static data inside the class, and define functions f1, f2 that
depends on this data? (while previously I had no class, just the
pointer to function so this possibility was precluded...)

You still cannot have metaparameters in a practical way.

>
D) A more general apporach:
Suppose myclass is a class with member funcions f1 f2 (as usual double
double)

template<class fclass, double (flcass::*fun1)(double),
double(fclass::*fun2)(double)>
double integrate(int n, const fclass& fc) {
....
sum += (fc.*fun1)(i/n) + (fc.*fun2)(i/n);
....
};

The only reason you would want to pass a reference of fclass would be to
be able to use a derived class but the standard specifies function
object can be copied and then you have slicing.
Let say you pass it by value.

>
myclass mc;
integrate<myclass, &myclass::f1, &myclass::f2>(10, mc);

I understand this approach is more general: not only I choose the
class, but also I can choose the functions of the class that I'm using
in integrate.

This approach doesn't add anything. If you need to compose a class
operation, the better is to do it in a function that can be called.
And if you think about implmenting all functions in a single class and
then be able to chose the member function to use, that is a design I
would avoid (I would even refactor a code to avoid it).

Also I create the obj class, so I can have different objects of the
same class with different data member values (while previously only
static data could be used).
I understand his use of pointers to member functions.
So do we need to consider:
fc.*fun1
because I'm considering the particular obj mc of type myclass (and so,
even if the function of every obj of type myclass are the same, they
may depend on different data inside this obj) ?

[StephQ]

Measure before you try to optimize.

Yes, profiling the code is always a good practice.
This was just a thread to check if my understanding of the subject was
at least acceptable :P

StephQ

>
--
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?

[StephQ]

and call the integration routine with:

integrate(myfunc(),10);

First question: what is myfunc() ? An object of type myfunc? Why?
I would have used:

myfunc f;
integrate(f, 10);

Named object used to prevent optimization. Perhaps this is a legacy.
Personnaly, I prefer integrate(myfunc(),10); because then I remember the
object is passed by value.

So myfunc() just calls the default constructor and the created obj is
passed to integrate.
I don' t understand why you say that from the syntax you remember that
the object is passed by value.
I could have defined the template function integrate this way too to
use pass by reference:

template<class Fo>
double integrate(const Fo& f, int n) { //instead of (Fo f, int n)
....
sum += f(i/n);
....
};

integrate(myfunc(),10);

...class can also carry traits which is not the case with function.
This is useful for object function composition.

For object function composition you mean when, for example, you call
the sort algorithm and use different comparison criteria right?

D) A more general apporach:
Suppose myclass is a class with member funcions f1 f2 (as usual double
double)

template<class fclass, double (flcass::*fun1)(double),
double(fclass::*fun2)(double)>
double integrate(int n, const fclass& fc) {
....
sum += (fc.*fun1)(i/n) + (fc.*fun2)(i/n);
....
};

The only reason you would want to pass a reference of fclass would be to
be able to use a derived class but the standard specifies function
object can be copied and then you have slicing.
Let say you pass it by value.

I use pass by reference because I want to avoid copying the object, as
the copy operation could be time expensive if the object is big.
Is there good reasons to use pass by value instead? (I don't have
conversion problems....)
How would you have defined integrate in this situation?

>

myclass mc;
integrate<myclass, &myclass::f1, &myclass::f2>(10, mc);

I understand this approach is more general: not only I choose the
class, but also I can choose the functions of the class that I'm using
in integrate.

This approach doesn't add anything. If you need to compose a class
operation, the better is to do it in a function that can be called.
And if you think about implmenting all functions in a single class and
then be able to chose the member function to use, that is a design I
would avoid (I would even refactor a code to avoid it).

I don't understand what you mean here.
Suppose we write an algorithm for finding the maximum of a function
that uses the function and the first derivative of the function.
We can define a class containing the function parameters as private
data, and the function and the first derivative of the function as
public member functions of the class.
We can then call the alg for any of these classes.
We let the user select the name of f and f' in the classes because
probably these names have particular meanings depending on the
"object" that these classes represents.
Is there a better way to accomplish this task?

Thank you for your reply.
StephQ

[Michael DOUBEZ]

StephQ a écrit :

>>and call the integration routine with:
integrate(myfunc(),10);
First question: what is myfunc() ? An object of type myfunc? Why?
I would have used:
myfunc f;
integrate(f, 10);

Named object used to prevent optimization. Perhaps this is a legacy.
Personnaly, I prefer integrate(myfunc(),10); because then I remember the
object is passed by value.

So myfunc() just calls the default constructor and the created obj is
passed to integrate.
I don' t understand why you say that from the syntax you remember that
the object is passed by value.
I could have defined the template function integrate this way too to
use pass by reference:

template<class Fo>
double integrate(const Fo& f, int n) { //instead of (Fo f, int n)
....
sum += f(i/n);
....
};

integrate(myfunc(),10);

It is STL deformation I presume.

>

>...class can also carry traits which is not the case with function.
This is useful for object function composition.

For object function composition you mean when, for example, you call
the sort algorithm and use different comparison criteria right?

I mean composing binary function object with not2(), compose2(), plus(), ...

>

>>D) A more general apporach:
Suppose myclass is a class with member funcions f1 f2 (as usual double
double)
template<class fclass, double (flcass::*fun1)(double),
double(fclass::*fun2)(double)>
double integrate(int n, const fclass& fc) {
....
sum += (fc.*fun1)(i/n) + (fc.*fun2)(i/n);
....
};

The only reason you would want to pass a reference of fclass would be to
be able to use a derived class but the standard specifies function
object can be copied and then you have slicing.
Let say you pass it by value.

I use pass by reference because I want to avoid copying the object, as
the copy operation could be time expensive if the object is big.
Is there good reasons to use pass by value instead? (I don't have
conversion problems....)
How would you have defined integrate in this situation?

Yes, here it is possible. Again STL polution.

But then, I would have used accumulate() template with a functor parameter.

template<typename T>
struct add_mean : public binary_function<T,T,T>
{
const size_t n;
add_mean(size_t number):n(number){}
T operator() (const T& sum, const T& x) const{return sum+x/n;}
};

accumulate (v.begin(),v.end(),0.0,add_mean<double>(v.size())) ;

>

>>

>>myclass mc;
integrate<myclass, &myclass::f1, &myclass::f2>(10, mc);
I understand this approach is more general: not only I choose the
class, but also I can choose the functions of the class that I'm using
in integrate.

This approach doesn't add anything. If you need to compose a class
operation, the better is to do it in a function that can be called.
And if you think about implmenting all functions in a single class and
then be able to chose the member function to use, that is a design I
would avoid (I would even refactor a code to avoid it).

I don't understand what you mean here.
Suppose we write an algorithm for finding the maximum of a function
that uses the function and the first derivative of the function.
We can define a class containing the function parameters as private
data, and the function and the first derivative of the function as
public member functions of the class.
We can then call the alg for any of these classes.
We let the user select the name of f and f' in the classes because
probably these names have particular meanings depending on the
"object" that these classes represents.
Is there a better way to accomplish this task?

It is a way to it but not in the case you mentioned in the OP where the
accumulating function was:

sum += (fc.*fun1)(i/n) + (fc.*fun2)(i/n);

in this case, it is likely to be more efficient (I would have to test to
be sure) and more maintainable to define a functor that return double
operator(double sum, double i){return sum+fc.fun1(i/n)+fc.fun2(i/n)}.

However, I find it strange to define a template taking adapation to the
member function to call; it is not a clear design in THIS case.
I would rather require an adaptor
template<typename ARG, typename RET>
struct derivable_function
{
//traits
RET function(const ARG& x);
RET derivative(const ARG& x);
};

An then, for each case:
struct myclass_derivation: public derivable_function<double,double>
{
const myclass& fun;
myfunc(const myclass& obj):fun(obj){}
double function(const double& x){return fun.f1(x);}
double derivative(const double& x){return fun.f2(x);}
}

Michael