Thread: List of Functors

  1. #1
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138

    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?
    Last edited by golfinguy4; 09-29-2009 at 11:04 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    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?
    Last edited by golfinguy4; 09-29-2009 at 11:06 AM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    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.

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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.
    Last edited by Sebastiani; 09-29-2009 at 12:07 PM.

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  8. #8
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  9. #9
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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.

  10. #10
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    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.

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Alright, well give me a few minutes then and I'll put together an example.

  12. #12
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  13. #13
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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!).
    Last edited by Sebastiani; 09-29-2009 at 01:50 PM.

  14. #14
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    Thanks Sebastiani and anon. I'll have to take a closer look at your responses tonight when I get a chance.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 05:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM