views:

84

answers:

4

The key reason this works is that for_each () doesn’t actually assume its third argument to be a function. It simply assumes that its third argument is something that can be called with an appropriate argument. A suitably defined object serves as well as – and often better than – a function. For example, it is easier to inline the application operator of a class than to inline a function passed as a pointer to function. Consequently, function objects often execute faster than do ordinary functions. An object of a class with an application operator (§11.9) is called a functionlike object, a functor, or simply a function object.

[Stroustrup, C++ 3rd edition, 18.4-last paragraph]

  1. I always thought that the operator ( ) call is just like function call at runtime. how does it differ from a normal function call?

  2. Why is it easier to inline the application operator than a normal function?

  3. How are they faster than function call?

+3  A: 

Generally, functors are passed to templated functions - if you're doing so, then it doesn't matter if you pass a "real" function (i.e. a function pointer) or a functor (i.e. a class with an overloaded operator()). Essentially, both have a function call operator and are thus valid template parameters for which the compiler can instantiate the for_each template. That means for_each is either instantiated with the specific type of the functor passed, or with the specific type of function pointer passed. And it's in that specialization that it is possible for functors to outperform function pointers.

After all, if you're passing a function pointer, then the compile-type type of the argument is just that - a function pointer. If for_each itself is not inlined, then this particular for_each instance is compiled to call an opaque function pointer - after all, how could the compiler inline a function pointer? It just knows its type, not which function of that type is actually passed - at least, unless it can use non-local information when optimizing, which is harder to do.

However, if you pass a functor, then the compile-time type of that functor is used to instantiate the for_each template. In doing so, you're probably passing a simple, non-virtual class with only one implementation of the appropriate operator(). So, when the compiler encounters a call to operator() it knows exactly which implementation is meant - the unique implementation for that functor - and now it can inline that.

If your functor uses virtual methods, the potential advantage disappears. And, of course, a functor is a class with which you can do all kinds of other inefficient things. But for the basic case, this is why it's easier for the compiler to optimize & inline a functor call than a function pointer call.

Summary

Function pointers can't be inlined since while compiling for_each the compiler has only the type of the function and not the identity of the function. By contrast, functors can be inlined since even though the compiler only has the type of functor, the type generally suffices to uniquely identify the functor's operator() method.

Eamon Nerbonne
+4  A: 

Consider the two following template instantiations:

std::for_each<class std::vector<int>::const_iterator, class Functor>(...)

and

std::for_each<class std::vector<int>::const_iterator, void(*)(int)>(...)

Because the 1st is customised for each type of function object, and because operator() is often defined inline, then the compiler may, at its discretion, choose to inline the call.

In the 2nd scenario, the compiler will instantiate the template once for all functions of the same signature, therefore, it cannot easily inline the call.

Now, smart compilers may be able to figure out which function to call at compile time, especially in scenarios like this:

std::for_each(v.begin(), v.end(), &foo);

and still inline the function by generating custom instantiations instead of the single generic one mentioned earlier.

André Caron
A: 

I always thought that the operator ( ) call is just like function call at runtime. how does it differ from a normal function call?

My guess is not very much. For evidence of this, look at your compiler's assembly output for each. Assuming the same level of optimization, it's likely to be nearly identical. (With the additional detail that the this pointer will have to get passed.)

Why is it easier to inline the application operator than a normal function?

To quote the blurb you quoted:

For example, it is easier to inline the application operator of a class than to inline a function passed as a pointer to function.

I am not a compiler person, but I read this as: If the function is being called through a function pointer, it's a hard problem for the compiler to guess whether the address stored in that function pointer will ever change at runtime, therefore it's not safe to replace the call instruction with the body of the function; come to think of it, the body of the function itself wouldn't necessarily be known at compile time.

How are they faster than function call?

In many circumstances I'd expect you wouldn't notice any difference. But, given your quotation's argument that the compiler is free to do more inlining, this could produce better code locality and fewer branches. If the code is called frequently this would produce notable speedup.

asveikau
A: 

Its all thoroughly explained here

Anders K.