Functors

From Eigen
Revision as of 19:51, 26 September 2009 by Bjacob (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

In pure C, when one wants to pass a function as parameter to another function, one passes its address. However, in C++ this technique should generally not be used, as one can do much better.

The functors approach with static polymorphism

One can define a class "functor" that contains the wanted function as a method, and pass an object of class "functor" instead. If the function needed to take arguments, they can be passed to the constructor of "functor" and stored in the functor object. The compiler is typically very good at optimizing this away when possible. Here's an example:

functors.cpp:

#include<iostream>
#include<string>
 
/*** print the name of some types... ***/
template<typename type> std::string name_of_type() { return "other"; }
template<> std::string name_of_type<int>() { return "int"; }
template<> std::string name_of_type<float>() { return "float"; }
template<> std::string name_of_type<double>() { return "double"; }
 
struct sum_of_ints_functor
{
  sum_of_ints_functor(int a, int b) : m_a(a), m_b(b)
  {
    std::cout << "Type: int. Computing the sum of the two ints " << a << " and " << b << ".";
  }
 
  int f() const { return m_a + m_b; }
 
  private:
  int m_a, m_b;
};
 
template<typename scalar=int>
struct product_functor
{
  product_functor(scalar a, scalar b) : m_a(a), m_b(b)
  {
    std::cout << "Type: " << name_of_type<scalar>() << ". Computing the product of " << a << " and " << b << ".";
  }
 
  scalar f() const { return m_a * m_b; }
 
  private:
  scalar m_a, m_b;
};
 
template<typename functor_type> void call_and_print_return_value(const functor_type& functor_object)
{
  std::cout << " The result is: " << functor_object.f() << std::endl;
}
 
int main()
{
  call_and_print_return_value(sum_of_ints_functor(3,5));
  call_and_print_return_value(product_functor<float>(0.2f,0.4f));
  call_and_print_return_value(product_functor<>(7,8));    
}

Output:

$ g++ functors.cpp -o functors && ./functors
Type: int. Computing the sum of the two ints 3 and 5. The result is: 8
Type: float. Computing the product of 0.2 and 0.4. The result is: 0.08
Type: int. Computing the product of 7 and 8. The result is: 56

The immediate advantages of this technique, over the C technique of passing function pointers, are that:

  • This allows the functor calls to be inlined, and in that case the compiler will easily optimize the functor object away completely. Thus, this is an optimization when the functor call inlining is important for performance.
  • This allows to pass all sorts of additional information as part of the functor type.

But there is also a drawback: the code for the function call_and_print_return_value has been generated 3 times, instead of 2 (2 is the minimum possible here because we do 2 different types, int and float, so in C they would have to write 2 separate functions too):

$ nm --demangle functors | grep call_and_print
08048b2c W void call_and_print_return_value<product_functor<float> >(product_functor<float> const&)
08048af8 W void call_and_print_return_value<product_functor<int> >(product_functor<int> const&)
08048ac4 W void call_and_print_return_value<sum_of_ints_functor>(sum_of_ints_functor const&)

Here, of course the code needs to be generated separately for int and for float, but one may at least want to factor the code for the two versions with int. This is possible through virtual inheritance of the functors, as explained in the next section:

The virtual functors approach: functors with dynamic polymorphism

It goes like this:

virtual.cpp:

#include<iostream>
#include<string>
 
/*** print the name of some types... ***/
template<typename type> std::string name_of_type() { return "other"; }
template<> std::string name_of_type<int>() { return "int"; }
template<> std::string name_of_type<float>() { return "float"; }
template<> std::string name_of_type<double>() { return "double"; }
 
template<typename scalar> class functor
{
  public:
    virtual scalar f() const = 0;
};
 
struct sum_of_ints_functor : public functor<int>
{
  sum_of_ints_functor(int a, int b) : m_a(a), m_b(b)
  {
    std::cout << "Type: int. Computing the sum of the two ints " << a << " and " << b << ".";
  }
 
  int f() const { return m_a + m_b; }
 
  private:
  int m_a, m_b;
};
 
template<typename scalar=int>
struct product_functor : public functor<scalar>
{
  product_functor(scalar a, scalar b) : m_a(a), m_b(b)
  {
    std::cout << "Type: " << name_of_type<scalar>() << ". Computing the product of " << a << " and " << b << ".";
  }
 
  scalar f() const { return m_a * m_b; }
 
  private:
  scalar m_a, m_b;
};
 
template<typename scalar> void call_and_print_return_value(const functor<scalar>& functor_object)
{
  std::cout << " The result is: " << functor_object.f() << std::endl;
}
 
int main()
{
  call_and_print_return_value(sum_of_ints_functor(3,5));
  call_and_print_return_value(product_functor<float>(0.2f,0.4f));
  call_and_print_return_value(product_functor<>(7,8));    
}

Output:

$ g++ virtual.cpp -o virtual && ./virtual
Type: int. Computing the sum of the two ints 3 and 5. The result is: 8
Type: float. Computing the product of 0.2 and 0.4. The result is: 0.08
Type: int. Computing the product of 7 and 8. The result is: 56

This new version looks very similar to the functors.cpp discussed earlier, actually the diff is very small:

$ diff -u functors.cpp virtual.cpp
--- functors.cpp
+++ virtual.cpp
@@ -7,7 +7,13 @@
 template<> std::string name_of_type<float>() { return "float"; }
 template<> std::string name_of_type<double>() { return "double"; }
 
-struct sum_of_ints_functor
+template<typename scalar> class functor
+{
+  public:
+    virtual scalar f() const = 0;
+};
+
+struct sum_of_ints_functor : public functor<int>
 {
   sum_of_ints_functor(int a, int b) : m_a(a), m_b(b)
   {
@@ -21,7 +27,7 @@
 };
 
 template<typename scalar=int>
-struct product_functor
+struct product_functor : public functor<scalar>
 {
   product_functor(scalar a, scalar b) : m_a(a), m_b(b)
   {
@@ -34,7 +40,7 @@
   scalar m_a, m_b;
 };
 
-template<typename functor_type> void call_and_print_return_value(const functor_type& functor_object)
+template<typename scalar> void call_and_print_return_value(const functor<scalar>& functor_object)
 {
   std::cout << " The result is: " << functor_object.f() << std::endl;
 }

The advantage of this new version is that the code of call_and_print_return_value is now shared for all functors sharing the same base (that is, here, to say that they share the same scalar type). Indeed:

$ nm --demangle virtual | grep call_and_print
08048d0f W void call_and_print_return_value<float>(functor<float> const&)
08048bec W void call_and_print_return_value<int>(functor<int> const&)

So we have only 2 instantiations anymore, instead of 3.

On the other hand, this version also has drawbacks compared to the first one (functors.cpp). Either one may be preferable depending on circumstances. The functors.cpp version means that the polymorphism is resolved at compile time, which allows for compile-time optimizations that aren't possible in the virtual.cpp version. To begin with, functors.cpp allows the functor calls to be inlined, which virtual.cpp doesn't. To make things worse, in virtual.cpp the functor calls are virtual function calls, which are a bit more expensive than normal function calls. This may or may not be a problem, depending on your context.

There's no universal rule, only you can know what's best in your context.

The unified approach: write once, let the user decide between the two

The good thing is that, as a library developer, you can write your library code in such a way that you allow the user to choose for himself which approach is best for his context. Indeed, you can do this:

unified.cpp

#include<iostream>
#include<string>
 
/*** print the name of some types... ***/
template<typename type> std::string name_of_type() { return "other"; }
template<> std::string name_of_type<int>() { return "int"; }
template<> std::string name_of_type<float>() { return "float"; }
template<> std::string name_of_type<double>() { return "double"; }
 
/*** functors inheriting a common virtual base ***/
 
template<typename scalar=int> class functor
{
  public:
    virtual scalar f() const = 0;
};
 
struct sum_of_ints_functor : public functor<int>
{
  sum_of_ints_functor(int a, int b) : m_a(a), m_b(b)
  {
    std::cout << "Type: int. Computing the sum of the two ints " << a << " and " << b << ".";
  }
 
  int f() const { return m_a + m_b; }
 
  private:
  int m_a, m_b;
};
 
template<typename scalar=int>
struct product_functor : public functor<scalar>
{
  product_functor(scalar a, scalar b) : m_a(a), m_b(b)
  {
    std::cout << "Type: " << name_of_type<scalar>() << ". Computing the product of " << a << " and " << b << ". ";
  }
 
  scalar f() const { return m_a * m_b; }
 
  private:
  scalar m_a, m_b;
};
 
template<typename functor_type> void call_and_print_return_value(const functor_type& functor_object)
{
  std::cout << " The result is: " << functor_object.f() << "." << std::endl;
}
 
int main()
{
  // by default, the function is instantiated separately for each functor type
  call_and_print_return_value(sum_of_ints_functor(3,5));
  call_and_print_return_value(product_functor<float>(0.2f,0.4f));
  call_and_print_return_value(product_functor<>(7,8));
 
  // but if we want, we may also tell it "hey, instantiate only with respect to the virtual base type"!
  // then it is instantiated only once per scalar type, so we factor the binary code (good!)
  // and the polymorphism (for a given scalar type) is resolved at runtime
  call_and_print_return_value<functor<> >(sum_of_ints_functor(3,5));
  call_and_print_return_value<functor<float> >(product_functor<float>(0.2f,0.4f));
  call_and_print_return_value<functor<> >(product_functor<>(7,8));
}

Output:

$ g++ unified.cpp -o unified && ./unified
Type: int. Computing the sum of the two ints 3 and 5. The result is: 8.
Type: float. Computing the product of 0.2 and 0.4.  The result is: 0.08.
Type: int. Computing the product of 7 and 8.  The result is: 56.
Type: int. Computing the sum of the two ints 3 and 5. The result is: 8.
Type: float. Computing the product of 0.2 and 0.4.  The result is: 0.08.
Type: int. Computing the product of 7 and 8.  The result is: 56.

Let's now examine the instantiations of call_and_print_return_value:

$ nm --demangle unified | grep call_and_print
08048d89 W void call_and_print_return_value<product_functor<float> >(product_functor<float> const&)
08048e9d W void call_and_print_return_value<product_functor<int> >(product_functor<int> const&)
08048c66 W void call_and_print_return_value<sum_of_ints_functor>(sum_of_ints_functor const&)
08048f0b W void call_and_print_return_value<functor<float> >(functor<float> const&)
08048ed4 W void call_and_print_return_value<functor<int> >(functor<int> const&)

Only 5 instantiations for 6 function calls, because the two virtual calls for int are sharing the same code.

A note about overloading operator()

Some people like to overload operator() in a functor, instead of defining a method f() like we did here. It's just a matter of taste, it really amounts to the same. It's nice syntactic sugar, because you then call your functor exactly with the same syntax as a function:

functor_object();

However, the user himself doesn't call the functor, so that doesn't make his life easier, on the contrary the syntax is a bit more cumbersome for him when he defines the functor class, as he needs to overload operator().

There's also a situation when overloading operator() is not an option: if your functor class doesn't need to carry any member data, you may want to make the method static, so one doesn't even need to construct a functor object. This may further help the compiler to optimize away the abstraction. In that case, operator() isn't an option, because it can't be static.