C ++ 11 for_each and lambdas optimization

Question

I am testing the following code:

#include <iostream> #include <vector> #include <algorithm> #include <ctime> int main(int argc, char* argv[]) { std::vector<int> v(10000000); clock_t then = clock(); if(argc <= 1) std::for_each(v.begin(), v.end(), [](int& it){ it = 10098; }); else for(auto it = v.begin(); it != v.end(); ++it) *it = 98775; std::cout << clock() - then << "\n"; return 0; } 

I compile it with g ++ 4.6 without any optimization flags and this is what I get:

 [ javadyan@myhost experiments]$ ./a.out 260000 [ javadyan@myhost experiments]$ ./a.out aaa 330000 [ javadyan@myhost experiments]$ 

Using optimization -O1 gives the following (not surprising) results:

 [ javadyan@myhost experiments]$ ./a.out 20000 [ javadyan@myhost experiments]$ ./a.out aaa 20000 

I use Linux 3.0 on a 2 GHz dual-core laptop, if that matters.

I am wondering how in a program compiled without any optimizations, calling for_each with a lambda function could consume less hours than a simple loop? Shouldn't there even be a slight overhead from calling an anonymous function? Is there any documentation on how this code looks like

  std::for_each(v.begin(), v.end(), [](int& it){ it = 10098; }); 

is g ++ handled? What is the behavior of other popular compilers in this case?

UPDATE

I did not think that it in the second expression compares with v.end() at each iteration. However, a fixed for loop consumes less hours than for_each. However, I'm still wondering how the compiler optimizes for_each when the -O1 flag is used.

Answer 1

At first glance, I can say at least that these expressions are not equivalent. Try instead:

  for(auto it = v.begin(), end = v.end(); it != end; ++it) *it = 98775; 

In addition, since the exact type of lambda is passed to for_each , there are pretty good chances that the compiler will disable it, as a result of which the code will not differ from the for loop. Please note that there are no virtual calls in anonymous functions. The compiler will do something like this:

 class __lambda_function_123 { public: void operator()(int& it) const{ it = 10098; } }; std::for_each(v.begin(), v.end(), __lambda_function_123()); 

which, in addition to inlining, will lead to the same code as the for loop (with the modification enabled).

Answer 2

Interestingly, even after optimizing "end = v.end (), I! = End your for_each case and lambda are still faster in debug mode in Visual Studio 2010.

One optimization that makes it faster in VS2010 is that the meta-template engine can detect the use of a vector iterator and switch to using raw integer pointers for start / end, which eliminates many debug check checks for both operator ++, operator * and operator! =.