Functor vs template parameters

Question

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

For instance, a functor-style sort interface is typically 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 could do something more like this, and require that _Pred contained a 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 might dynamically create a temporary functor object on the heap, whereas I believe that the second case is fully evaluated at compile time. I understand that (say) gcc and/or msvc are good at optimising, but can this be done to the same degree in the first case??

Also, I'm not trying to rewrite the STL sort routines or anything like that, just an example for a more general functor question...

Answer 1

Normal use of sort won't put anything on the heap, for the simple reason that nobody calls malloc or new. If your predicate causes a call to malloc or new, either in its constructor or in the comparison, then you only have yourself to blame...

It's plausible that some stack will be used for the parameter of type _Pred (you must not call a template parameter _Pred in your code, because _Pred is a reserved symbol. It can be called that in the implementation of std::sort). But there won't be any associated work to do, beyond what's necessary for any data members that the predicate object might have. If the predicate has no data members then the optimizer will have a field day, and if it does have data members then a static member function wouldn't support what the user wants to do.

As long as operator() in the predicate is non-virtual, the compiler can inline it into the instantiation of sort if it can see the definition and if it feels that's best. Of course there are no guarantees what's faster, but there's no reason to suppose that a call to a static member function is any faster or slower than a call to a non-virtual non-static member function, nor that it's any easier or harder to inline.

Answer 2

In theory, the first case might dynamically create a temporary functor object on the heap, whereas 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 worrying about whether Pred::Pred() will allocate storage? If so, you may as well also worry about whether the static function is going to allocate storage on the heap for some reason.

Regardless, most predicate functor objects that work with this sort of idiom have very simple constructors, since their only purpose is to call an overloaded operator (), so the compiler will likely optimize out the object construction and produce a simple function call.

Answer 3

In the first case, you could create a

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 would allow you to

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 this has been compile-checked. But you get the idea.

In the second case, because you're calling a static method, you do not have free reign to customize the comparator like this.

I wouldn't worry about efficiency. If you're not accessing anything non-static, a good C++ compiler will elide the extra object creation/destruction and possibly even inline the comparator.

Answer 4

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

That is assuming that I'm understanding your code right - real code would be more clear. I assume code 1 does something like if (less_than.compare(a, b)), and code 2 does if (_Pred::less_than(a, b)).

EDIT: I should mention that example 1 would pass the object by value, so you'll incur whatever cost that may involve (like a copy constructor).

Answer 5

If I were you, I'd stop worrying about whether or not you'll buy a micro-nano-second by doing it one way vs. the other...and worry more about not using names that are reserved!

You've got a long way to go before worrying about crap like this. By the time you get there...hopefully you've learned that it's pointless worrying about crap like this.

Though, in order to make this an "answer": Neither, your program is ill-formed.