views:

150

answers:

4

In the wikipedia article about function objects it says such objects have performance advantages when used with for_each because the compiler can "inline" them.

I'm a bit foggy on exactly what this means in this context... or any context I'm embarrassed to say. Thanks for any help!

+2  A: 

Inlining just means replacing every call to that function with the body of that function directly.

It's an optimization for small functions because it reduces the overhead of jumping to a new function and then returning.

John Weldon
+3  A: 

It means that the function's definition (code) may be copied and saving you from a function call (which is considered to be expensive on some systems). Think of macro replacement.

dirkgently
+4  A: 

Inline is the process a compiler can replace a call to a function with the contents of the function itself. It requires the compiler to know the contents of the function when it's being compiled.

The compiler often can't do this if a function pointer is passed.

Charles Beattie
+3  A: 

The last parameter of for_each template is a functor. Functor is something that can be "called" using the () operator (possibly with arguments). By defintion, there are two distinctive kinds of functors:

  1. Ordinary non-member functions are functors.
  2. Objects of class type with overloaded () operator (so called function objects) are also functors.

Now, if you wanted to use an ordinary function as a functor for for_each, it would look something like the following

inline void do_something(int &i) { /* do something */ }

int main() {
  int array[10];
  std::for_each(array, array + 10, &do_something);
}

In this case the for_each template is instantiated with [deduced] arguments <int *, void (*)(int &)>. Note that the actual functor value in this case is the function pointer &do_something passed as the function argument. From the point of view of for_each function this is a run-time value. And since it is a run-time value, the calls to the functor cannot be inlined. (Just like it is in general case impossible to inline any call made through a function pointer).

But if we use a function object instead, the code might look as follows

struct do_something {
  void operator()(int &i) { /* do something */ }
}; 

int main() {
  int array[10];
  std::for_each(array, array + 10, do_something());
}

In this case the for_each template is instantiated with [deduced] arguments <int *, do_something>. The calls to the functor from inside for_each will be directed to do_something::operator(). The target for the call is known and fixed at compile-time. Since the target function is known at compile-time, the call can easily be inlined.

In the latter case we, of course, also have a run-time value passed as an argument to for_each. It is a [possibly "dummy" temporary] instance of do_something class we create when we call for_each. But this run-time value has no effect on the target for the call (unless the operator () is virtual), so it doesn't affect inlining.

AndreyT
But the full definition of `::std::for_each` is available to the compiler. To a smart compiler, it should see that it's being called with a particular argument that happens to be the address of a function that was declared inline. The compiler should be able to inline the function call just as well as if it were a class method.
Omnifarious
AndreyT
For example (forget about templates), when I have function `void foo(int)` in my program and call it several times as `foo(1); foo(2); foo(3);` I generally expect the compiler to generate one function body for `foo` and execute the same body with different arguments: 1, 2, and 3. If I discover that the compiler instead generated 3 different bodies of `foo` with "inlined" constants 1, 2, and 3 respectively, I'll be unpleasantly surprised. For small `foo` that would be OK (if it is inlined after that), but for a larger `foo` this is undesirable. What you describing is essentially the same thing.
AndreyT
@AndreyT: Oh! *slaps forhead* That makes sense. And it's pretty dumb as well, but you're right, it just has to be that way, there's no way around it. I DO know a way around it though. *big grin* A function pointer template argument causing the name of the type to include which function you're going to use. The template's operator () just forwards to the function passed as a template argument.
Omnifarious
@Omnifarious: Yes, exactly! Function pointer as *template* argument would indeed work and would indeed requre no extra effort for inlining. But in case of `std::for_each`, the function pointer itself is *function* argument (not *template* argument). Template argument is function pointer *type*.
AndreyT
@AndreyT - a compiler would be unwise to do inline random foo()s with constant arguments. But `std::for_each` is not a random function. For starters, it typically _is_ quite trivial. Inlining it is quite reasonable. Furthermore, with template tricks it's certainly possible to make it a simple (inlined) forwarder to a partially specialized implementation; an implementation that also inlines when you pass a funciton pointer. And at that point you can leave it to the optimizer again.
MSalters
@MSalters: You are right, but I'd say there's still a qualitative difference between something that is strictly a compile-time value (template parameter) and something that is generally a run-time value (function parameter) that just happens to be known at compile time in some specific context. It is true that a smart compiler can close the gap between the two in many specific cases, but in general case the difference will be there. This is the difference that is normally implied by the articles like the one in the OP.
AndreyT