Functor vs parameter options

Question

Is there any performance advantage when using template parameters with static member functions instead of functor-style predicates?

For example, a functor-style sorting interface usually looks something like this:

template <typename _Type, typename _Pred> void sort ( RandomAccessIterator first, RandomAccessIterator last , _Pred less_than ) { // actual sorting code here, calling less_than()... } 

You can do something more like this and require _Pred contain the static member function _Pred::less_than :

 template <typename _Type, typename _Pred> void sort ( RandomAccessIterator first, RandomAccessIterator last ) { // actual sorting code here, calling _Pred::less_than()... } 

In theory, the first case can dynamically create a temporary functor object on the heap, while I believe that the second case is fully evaluated at compile time. I understand that (say) gcc and / or msvc are good at optimizing, but can this be done to the same extent in the first case?

Also, I am not trying to rewrite STL sorting procedures or something like that, just an example for a more general question about a functor ...

Answer 1

The usual use of sort will not put anything in the heap for the simple reason that no one calls malloc or new . If your predicate calls malloc or new , either in its constructor or in comparison, then you only blame yourself ...

It is likely that some stack will be used for a parameter of type _Pred (you should not call the template parameter _Pred in your code, because _Pred is a reserved character. It can be called that in the implementation of std::sort ). But there will be no related work other than what is needed for any data members that may have predicate objects. If the predicate does not have data elements, then the optimizer will have a field day, and if it has data members, then the static member function will not support what the user wants to do.

As long as operator() in the predicate is not virtual, the compiler can embed it in the sort instance if it can see the definition and if it feels better. Of course, there is no guarantee that it is faster, but there is no reason to believe that a call to a static member function is faster or slower than a call to a non-virtual non-static member function, and also that it is simpler or more complex than a row one.

Answer 2

Theoretically, the first case can dynamically create a temporary functor object on the heap, while I believe that the second case is fully evaluated at compile time.

The first case will create a temporary functor object on the stack. Are you worried about whether Pred::Pred() allocate memory? If so, you may also worry about whether the static function will collect storage on the heap for some reason.

Regardless of the fact that most of the predicate-precursor objects that work with this type of idiom have very simple constructors, since their only purpose is to call an overloaded operator () , so the compiler will most likely optimize the object's construction and make a simple function call.

Answer 3

In the first case, you can create

 template<class T> struct CompareByIntProperties { CompareByIntProperties(vector<T::*int> props) : props_(props) {} bool less_than(const T& a, const T& b) const { for (vector<T::*int>::const_iterator it = props_.begin(); it != props_.end(); ++it) { if (a.(**it) < b.(**it)) return true; if (a.(**it) > b.(**it)) return false; } return false; } vector<T::*int> props_; }; 

which will allow you

 vector<Foo::*int> properties; if (compare_foo) properties.push_back(&Foo::foo); if (compare_bar) properties.push_back(&Foo::bar); if (compare_qux) properties.push_back(&Foo::qux); sort(container.begin(), container.end(), CompareByIntProperties<Foo>(properties)); 

Please forgive any syntax errors, none of them have been verified by compilation. But you have an idea.

In the second case, since you are invoking a static method, you do not have free ownership to configure the comparator in this way.

I would not worry about efficiency. If you do not get access to anything non-static, good C ++ compiler can speed up the creation / destruction of additional objects and, possibly, even embed a comparator.

Answer 4

If _Pred::less_than not virtual, both solutions are identical, since the compiler knows exactly what the function is, and can be built in if necessary.

This assumes that I understand your code correctly - the real code will be more understandable. I assume that code 1 does something like if (less_than.compare(a, b)) , and code 2 if (_Pred::less_than(a, b)) .

EDIT: I should mention that Example 1 passed an object by value, so you incur any cost that might be required (e.g. copy constructor).

Answer 5

If I were you, I would not have to worry about whether you would buy a micron-second by doing it in one way against another ... and worry more about not using reserved names!

You have a long way to go before worrying about this shit. By the time you get there ... I hope you find out that it makes no sense to worry about this shit.

Although, to make this the "answer": neither your program is poorly formed.