Functors

From Eigen
Revision as of 12:48, 25 September 2009 by Bjacob (Talk | contribs)

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, and pass an object of class "functor" instead. If the function needed to take argument, 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 T, typename U> struct ei_is_same_type { enum { ret = 0 }; };
template<typename T> struct ei_is_same_type<T,T> { enum { ret = 1 }; };
 
template<typename type>
std::string name_of_type()
{
  if(ei_is_same_type<type,int>::ret)
    return "int";
  else if(ei_is_same_type<type,float>::ret)
    return "float";
  else if(ei_is_same_type<type,double>::ret)
    return "double";
  else return "other";
}
 
template<typename functor_type> void call_and_print_return_value(const functor_type& functor_object)
{
  std::cout << functor_object.f() << std::endl;
}
 
struct sum_of_ints_functor
{
  sum_of_ints_functor(int a, int b) : m_a(a), m_b(b)
  {
    std::cout << "let's compute the sum of the two ints " << a << " and " << b << std::endl;
  }
 
  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 << "let's compute the product of the two numbers (type: " << name_of_type<scalar>() << ") " << a << " and " << b << std::endl;
  }
 
  scalar f() const { return m_a * m_b; }
 
  private:
  scalar m_a, m_b;
};
 
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));    
}

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:

$ 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 T, typename U> struct ei_is_same_type { enum { ret = 0 }; };
template<typename T> struct ei_is_same_type<T,T> { enum { ret = 1 }; };
 
template<typename type>
std::string name_of_type()
{
  if(ei_is_same_type<type,int>::ret)
    return "int";
  else if(ei_is_same_type<type,float>::ret)
    return "float";
  else if(ei_is_same_type<type,double>::ret)
    return "double";
  else return "other";
}
 
template<typename scalar> class functor
{
  public:
    virtual scalar f() const = 0;
};
 
template<typename scalar> void call_and_print_return_value(const functor<scalar>& functor_object)
{
  std::cout << functor_object.f() << std::endl;
}
 
struct sum_of_ints_functor : public functor<int>
{
  sum_of_ints_functor(int a, int b) : m_a(a), m_b(b)
  {
    std::cout << "let's compute the sum of the two ints " << a << " and " << b << std::endl;
  }
 
  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 << "let's compute the product of the two numbers (type: " << name_of_type<scalar>() << ") " << a << " and " << b << std::endl;
  }
 
  scalar f() const { return m_a * m_b; }
 
  private:
  scalar m_a, m_b;
};
 
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));    
}

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        2009-09-25 07:31:21.000000000 -0400
+++ virtual.cpp 2009-09-25 07:31:27.000000000 -0400
@@ -17,12 +17,18 @@
   else return "other";
 }
 
-template<typename functor_type> void call_and_print_return_value(const functor_type& functor_object)
+template<typename scalar> class functor
+{
+  public:
+    virtual scalar f() const = 0;
+};
+
+template<typename scalar> void call_and_print_return_value(const functor<scalar>& functor_object)
 {
   std::cout << functor_object.f() << std::endl;
 }
 
-struct sum_of_ints_functor
+struct sum_of_ints_functor : public functor<int>
 {
   sum_of_ints_functor(int a, int b) : m_a(a), m_b(b)
   {
@@ -36,7 +42,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)
   {

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.

That said, it is important to say that the functors.cpp approach may still be preferable over virtual.cpp 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.

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 T, typename U> struct ei_is_same_type { enum { ret = 0 }; };
template<typename T> struct ei_is_same_type<T,T> { enum { ret = 1 }; };
 
template<typename type>
std::string name_of_type()
{
  if(ei_is_same_type<type,int>::ret)
    return "int";
  else if(ei_is_same_type<type,float>::ret)
    return "float";
  else if(ei_is_same_type<type,double>::ret)
    return "double";
  else return "other";
}
 
/*** 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 << "let's compute the sum of the two ints " << a << " and " << b << std::endl;
  }
 
  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 << "let's compute the product of the two numbers (type: " << name_of_type<scalar>() << ") " << a << " and " << b << std::endl;
  }
 
  scalar f() const { return m_a * m_b; }
 
  private:
  scalar m_a, m_b;
};
 
/*** the unified function *****/
 
template<typename functor_type> void call_and_print_return_value(const functor_type& functor_object)
{
  std::cout << functor_object.f() << std::endl;
}
 
int main()
{
  // by default, the function is instantiated separately for each functor type
  // the compiler should then not be disturbed by the virtual base, and do all the compile time optimizations.
  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));
}

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.