Functor pattern in C++: CRTP VS Inheritance

Some examples to compare the performances of several implementations of the Functor pattern:

Inheritance (the canonical way),
Curiously Recurring Template Pattern (CRTP).

Abstract

There is several way of implementing the functors in C++. This set of code demonstrate two of them: an inheritance pattern and the CRTP.

With this very rough test, the CRTP implementation seems to be the fastest. On my machine, CRTP is approximately 1.3 times faster than Inheritance.

Introduction

Functor's definition

The Functor pattern seems to have many possible definitions. Here, I will consider the simpler one: a class type functor. This is basically an object that is callable: a function object.

/* For example, this simple class uses the functor pattern to attach a state to
a function. */
struct A:
{
    int _state;
    A ( int state ) : _state(state) {}
    int operator() ( int arg ) const {
        return _state + arg;
    }
};

Composition of function objects

I really like this functor which is a good compromise between composition and inheritance on one side, and object-oriented and functional programming on the other side.

I use it to assemble algorithms as a set of functions applied to a state. This is a pattern heavily used within the ParadisEO framework, for instance.

The targeted use case needs several function objects (called operators) to build an algorithm (which is itself an operator), but here I will do the tests with a single operator that embed an operator itself.

/* An example of the general form of an operator and its usage */
struct Algo
{
    OperatorInit _opi;
    OperatorIter _opt;
    Algo( OperatorInit & opi, OperatorIter opt ) : _opi(opi), _opt(opt) {}
    int operator() ( int & state ) {
        _opi(state);
        for( int i=-1; i<9; ++i ) {
            _opt(state);
        }
        return i;
    }
};

int main(  )
{
    // Operators instanciation
    OperatorInit init;
    // They may take arguments
    OperatorIter iter(1);
    Algo algo( init, iter );
    int state = 0;
    std::cout << algo( state ) << std::endl;
}

Interfaces

Of course, to permits the user of a framework to add new operators, we can use interfaces as a way to force him to avoid mistakes.

/* With an inheritance pattern, we can use abstract classes as interfaces */
struct Operator:
{
    virtual void operator() ( int & arg ) = 0;
};

struct OperatorInit : public Operator
{
    virtual void operator() ( int & arg ) { arg = 0; }
};

Generic programming

As operators are used deep inside the call tree, they may need different interfaces at each level, and not always the one defined by the framework. For example, if there is interaction between user-defined operators somewhere within a framework-defined one (remember operators are composed with operators).

/* Thus, we need templates, most probably for the manipulated state */
template< class T>
struct OperatorIter
{
    // for example because this particular operator needs an access to "length" */
    int operator() ( T & state ) { state++; return state.length(); }
};

Putting it all together

For the comparison, I will use here a simple example that will increment a counter with the help of two functors. One is a generic Assign function that is supposed to call an Increment function that alter the given state and push it in a container. The other is the function that actually do the job.

For simplicity, only the first one will use an interface called Functor.

Keep in mind that this is just a simplified example that implements a hierarchy of operators, it is not supposed to be elegant.

/* A simplified view of the logical articulation of the classes */
template<class T>
struc Increment
{
    template<class OutIt>
    T operator() ( T & arg, OutIt out )
    {
        // do something with the `arg` and push it to `out`
    }
    /* ... */
};

template<class T>
struct Functor
{
    Increment op;
    // the interface
    template<class OutIt>
    int operator() ( int & arg, OutIt out ) /* ... */
};

template<class T>
struct Assign : public Functor<T>
{
    // Assemble operator[s]
    Assign( Increment & op ) : Functor(op) {}
    // This kind of interface
    int operator() ( int & arg, OutIt out )
    {
        return this->op(arg,out);
    }
    /* ... */
};

Note about the implented versions

The implementations are located in the following files:

Inheritance version: inheritance_functor.cpp
CRTP version: crtp_functor_ttp.cpp

Notes about the code are written as comments in those files.

Inheritance code

This version use overloading of the Assign::operator() function, over an abstract base class that provide the interface.

In the Increment functor, the output iterator template is defined over the call function, which permits to ease the declaration of the functor. But in the Assign class, as we want to overload a virtual function, it is not possible to define such a template, it should be defined over the class itself.

This is a limitation of this pattern, because I would have wanted to let the compiler infer the output iterator type at call and thus avoid the need to specify it at the instanciation.

    // we cannot do that:
    Assign<Increment> f(op);

    // we must explictly declare the output iterator type at instanciation
    Assign<Increment,std::back_insert_iterator<std::vector<int> > > f(op);

    // or use a helper that does not have a virtual function
    auto f = mafe_Functor<Assign>(op,out);

Curiously Recurring Template Pattern

Has there is no virtual functions involved in the CRTP, it is possible to declare the output iterator template over the callable function, and the compiler can infer its type.

The use of the CRTP makes hard to design more than one level of "inheritance" for the operator classes, and the template declarations are a pain.

Performance test

The performance test is done with two nested loops, the outer one instanciating the functors and the inner one calling it several times. Both are iterating 10 000 times.

To compile and run the performance tests, use the ./test.sh script.

$ ./test.sh
inheritance_functor

real	0m0.350s
user	0m0.344s
sys	0m0.004s

crtp_functor_ttp

real	0m0.272s
user	0m0.268s
sys	0m0.000s

nojhan/crtp_functor_ttp