List of Functors

I'm looking to optimize a portion of my code that is extremely time sensitive (will be running at least 1000x/s). It involves sequentially calling a series of functions to modify a given value. To avoid the overhead of function pointers, I would like to use functors allowing the compiler to inline. What I'm trying to do looks like the following:

Code:

---

typedef std::unary_function<DataType&, void> Func;

ClassA InstanceOfA;
ClassB InstanceOfB;

class FuncA : public  Func{
    public:
          void operator()(DataType& d){
              InstanceOfA.MemberFunc(d);
          }
};

class FuncB : public  Func{
    public:
          void operator()(DataType& d){
              InstanceOfB.MemberFunc(d);
          }
};

...

std::list<Func> listOfFuncs;

...

DataType val;
std::list<Func>::iterator it = listOfFuncs.begin();
(*it)(val)

---

I can't seem to get it to work though. I must admit I've never used the unary_function STL base type. Am I using it improperly?

It looks like you forgot the return type when overloading operator(), you did not pass d to call MemberFunc() but instead wrote something that looks vaguely like a function parameter declaration, and you forgot about the terminating semi-colons for your class definitions.

This is just pseudo-code. I just forgot to put them in. Let me try to correct it to make it a bit more C++-ish. I should probably also note that the error I'm getting involves the functor not taking 1 argument.

I'm trying to avoid using virtual functions here for similar overhead reasons. Perhaps there's a different construct that I'm not seeing?

Well, then I suggest that you post the smallest and simplest program that demonstrates the error, and also post the error message. After all, how do you know that your "pseudo-code" is not perfectly correct, whereas what you actually tried is wrong?

The above pseudo-code is now accurate (and was accurate as of your last post).

Error: "error C2064: term does not evaluate to a function taking 1 arguments"

Also, even if I were to construct my own base class, which I have since done, the fact is that a virtual function is still needed to allow for the correct function to be called.

In essence, what I need to do is create an array of functions that can be inlined when called. Function pointers prevent this (cannot inline because we're using the address of the function which isn't known at compile-time), and virtual functions also prevent this (vtable is established at run-time). Since this is going to be in a library, I cannot just directly insert the function calls where they should be called. Hence, the need for a list of functions on which I am going to iterate.

You can't inline something like that, unfortunately, since you can't have a collection (eg: linked list) of different types without them sharing some sort of virtual interface. Otherwise, you could have used the 'curiously recurring template idiom', which would allow you to inline everything, but again, that won't work for a collection.

EDIT: and just to be clear, I was referring to a linked list of pointers or references (the latter aren't compatible with stl containers, of course) to a common base class.

laserlight's question is still valid. Your "pseudocode" example is essentially paraphrasing what you think the problem is, but you are not providing information that mere mortals can use to interpret what your design is or what code you are supplying to your compiler to make it complain.

Try providing a small but complete compileable code example which exhibits your problem. In other words, don't paraphrase with "pseudocode". The process of producing that code example may give you insight into the problem without help. If not, you will be able to pose your question in a manner that doesn't require others to infer information you have not provided.

This function runs only 1000 times per second and you're worried about virtual call overhead?

Start worrying when you're closer to 1 million times per second.

Actually, I just realized how you can do this with the CRT idiom, but it would require specifying all of the functors at once. It's rather involved, so I'll wait to see if that requirement could even be met by your code.

Sebastiani,

Specifying all of the functors at once won't be an issue. While the functors themselves use variables that change during run-time, the actual functors being used are known at compile-time and can be specified as one large collection.

Alright, well give me a few minutes then and I'll put together an example.

Since it's all known at compile-time, there is Boost.Fusion. Below's my first encounter with it :)

Code:

---


#include <iostream>
#include <boost/fusion/container/vector.hpp>
#include <boost/fusion/algorithm/iteration/for_each.hpp>

//some random structs with random methods
struct A
{
    void foo(int& n) const  { ++n; }
};

struct B
{
    void bar(int& n) const { n *= 2; }
    void foobar(int& n) const { n += 17; }
};

//functors to call each of the member functions
struct Foo
{
    const A& a;
    Foo(const A& a): a(a) {}
    void operator() (int& i) const { a.foo(i); }
};

struct Bar
{
    const B& b;
    Bar(const B& b): b(b) {}
    void operator() (int& i) const { b.bar(i); }
};

struct FooBar
{
    const B& b;
    FooBar(const B& b): b(b) {}
    void operator() (int& i) const { b.foobar(i); }
};

//what the name says
struct ApplyFunctionToArray
{
    int* arr;
    unsigned size;
    ApplyFunctionToArray(int* arr, unsigned size): arr(arr), size(size) {}
    template <class Func>
    void operator() (const Func& f) const
    {
        for (unsigned i = 0; i != size; ++i) {
            f(arr[i]);
        }
    }
};

int main()
{
    A a;
    B b;
    boost::fusion::vector<Foo, Bar, FooBar> funcs((Foo(a)), Bar(b), FooBar(b));
    const unsigned size = 4;
    int arr[size] = { 1, 2, 3, 4 };
    for_each(funcs, ApplyFunctionToArray(arr, size));
    for (unsigned i = 0; i != size; ++i) {
        std::cout << arr[i] << '\n';
    }
}

---

But first, have you actually profiled the application and determined it is slow where you think it is? Or are you just trying to optimize upfront? Next, are you sure you need to call this code that many times? Then, are you sure you are not missing obvious optimizations (e.g why does std::list seem to be your container of choice)? Next, how big do you expect the speed gain to be and are you sure that your approach helps you achieve it in the first place?

Okay, well here's a very basic example (believe it or not!). It should be bug-free, but you might need to do some testing, to be sure.

Code:

---

#include <memory>

/*
        Placeholder
*/
struct DataType
{        };

/*
        This is what all classes derive from.
        A function named 'process' must be defined, and can be inline.
        Also known as 'The Curiously Recurring Template Idiom'.
*/
template < typename Derived >
struct function_base
{
        inline Derived& derived( void )
        {
                return *static_cast< Derived* >( this );
        }

        inline Derived const& derived( void ) const
        {
                return *static_cast< Derived const* >( this );
        }
       
        inline void operator ( )( DataType& data )
        {
                derived( ).process( data );
        }       
};

/*
        This class provides the 'chaining' mechanism. Used internally only.
*/
template < typename Lhs, typename Rhs >
struct function_base_list : function_base< function_base_list< Lhs, Rhs > >
{
        function_base_list( function_base< Lhs > const& lhs, function_base< Rhs > const& rhs )
        : lhs( lhs.derived( ) ), rhs( rhs.derived( ) )
        {        }

        inline void operator ( )( DataType& data )
        {
                lhs( data );
                rhs( data );
        }       
       
        Lhs
                lhs;
        Rhs
                rhs;
};

/*
        The 'chaining' generator.
*/
template < typename Lhs, typename Rhs >
function_base_list< Lhs, Rhs > operator + ( function_base< Lhs > const& lhs, function_base< Rhs > const& rhs )
{
        return function_base_list< Lhs, Rhs >( lhs, rhs );
}

/*
        This class basically just simplifies things so that you:
        1) don't have to write out a complex template declarations.
        2) can assign a value to a function_base_list in the future, rather than immediately.
        Since it's also derived from function_base_list, you can chain it to other lists, as well.
        Ideally, it should use a smart pointer, but since this is just a simple example,
        I just went with an std::auto_ptr. The one nice thing about using that, though,
        is that it allows you to concatenate a greedy_function_base_holder to itself
        without creating a recursive situation.
*/
struct greedy_function_base_holder : function_base< greedy_function_base_holder >
{
        struct base_dispatcher : function_base< base_dispatcher >
        {
                virtual void operator ( )( DataType& )
                {        }
        };
       
        template < typename Derived >
        struct derived_dispatcher : base_dispatcher
        {
                derived_dispatcher( function_base< Derived > const& self )
                : self( self.derived( ) )
                {        }
       
                virtual void operator ( )( DataType& data )
                {
                        self( data );
                }
               
                Derived
                        self;
        };

        greedy_function_base_holder( void )
        {
                *this = base_dispatcher( );
        }
       
        greedy_function_base_holder( greedy_function_base_holder const& rhs )
        {
                *this = rhs;
        }

        template < typename Derived >
        greedy_function_base_holder( function_base< Derived > const& rhs )
        {
                *this = rhs;
        }
       
        greedy_function_base_holder& operator = ( greedy_function_base_holder const& rhs )
        {
                greedy_function_base_holder&
                        sap = const_cast< greedy_function_base_holder& >( rhs );
                ptr = sap.ptr;
                sap = base_dispatcher( );
                return *this;
        }

        template < typename Derived >
        greedy_function_base_holder& operator += ( function_base< Derived > const& rhs )
        {
                return *this = *this + rhs;
        }
       
        template < typename Derived >
        greedy_function_base_holder& operator = ( function_base< Derived > const& rhs )
        {
                ptr = std::auto_ptr< base_dispatcher >( new derived_dispatcher< Derived >( rhs ) );
                return *this;
        }
       
        inline void operator ( )( DataType& data )
        {
                ( *ptr.get( ) )( data );
        }       
       
        std::auto_ptr< base_dispatcher >
                ptr;
};

// Example:

#include <iostream>

using namespace
        std;

struct test : function_base< test >
{
        test( int value = 0 )
        : value( value )
        {        }
       
/*
        Parameter unused for test
*/       
        inline void process( DataType& )
        {
                cout << value << endl;
        }       

        int
                value;
};

int main( void )
{
        DataType
                unused;
        greedy_function_base_holder
                gfbh1 = test( 1 ) + test( 2 ) + test( 3 ),
                gfbh2 = gfbh1 + test( 4 ) + test( 5 ) + test( 6 );
        gfbh2 += test( 7 ) + test( 8 ) + test( 9 );       
        gfbh2( unused );       
        return 0;
}

---

EDIT: Oh and maybe I should make this clear: the greedy_function_base_holder is called 'greedy' because it will 'take' the underlying data from any greedy_function_base_holder's chained to it. So for instance, 'gfbh1' in the example above loses it's data after it is chained to 'gfbh2'. Like I said, a smart pointer would be a better approach for that class (just be careful with cyclic references!).

Thanks Sebastiani and anon. I'll have to take a closer look at your responses tonight when I get a chance.