Why C++ lambda is slower than ordinary function when called multiple times?

Question

I just have tried to compare performance of lambda expressions in C++11, so I did the test -- compute sum of elements in a vector of double values. Here is the implementation:

#include <vector>
#include <algorithm>
#include <iostream>
#include <ctime>

#define LOG(x) { std::cout << #x << " = " << (x) << "\n"; }
#define TIME(t) { std::cout << ((double)(clock() - (t)) / CLOCKS_PER_SEC) << " s\n"; }

double sum(const std::vector<double>& v)
{
    double s = 0.0;
    for (auto i = v.cbegin(); i != v.cend(); ++i)
        s += *i;
    return s;
}

int main()
{
    const size_t MAX = 1; // number of tests
    const size_t SIZE = 100000000; // length of the vector

    std::vector<double> v(SIZE, 1.0);
    double out;

    clock_t clk;

    std::cout << "iterator\n";

    clk = clock();
    out = 0.0;
    for (size_t i = 0; i < MAX; ++i)
        out += sum(v);
    TIME(clk)
    LOG(out)

    std::cout << "\nlambda\n";

    clk = clock();
    out = 0.0;
    for (size_t i = 0; i < MAX; ++i)
        std::for_each(v.cbegin(), v.cend(), [&](double d) { out += d; });
    TIME(clk)
    LOG(out)

    return 0;
}

Here is the result of this program (compiled in VS2010 SP1, in Release mode):

iterator
0.32 s
out = 1e+008

lambda
0.326 s
out = 1e+008

As one may see, there is practically no difference in performance. However, if I give 10 as the value of MAX (it means summation will be performed 10 times instead of one), results differ:

iterator
0.287 s
out = 1e+009

lambda
2.84 s
out = 1e+009

Test for lambda expression took approximately 10 times more time. Why? I thought it may be caused by the fact, that on every iteration new lambda is created, but whet I tried this:

out = 0.0;
auto f = [&](double d) { out += d; };
for (size_t i = 0; i < MAX; ++i)
    std::for_each(v.cbegin(), v.cend(), f);

the results hadn't changed. Could someone explain that behaviour to me?

This is very intriguing! Could you try using lambda in a hand-written loop instead of `foreach`? — Sergey Kalinichenko, Dec 23 '11 at 02:54
g++ 4.6.2 on linux gives exactly identical run times (0.13 - 0.12 s on my computer) — Cubbi, Dec 23 '11 at 03:12
No more mistery, check my edit. My mistake, but still I find it pretty interesting. :) — Archie, Dec 23 '11 at 03:12
You should add your edit as an answer and accept it for future reference by others. — anthonyvd, Dec 23 '11 at 03:18

score 65 · Accepted Answer · edited Mar 31 '23 at 12:10

65

It turned out that this is not an issue with lambda expressions, just that the compiler optimized-out the outer loop in the first case by caching the result of the sum() function.

After changing the first case to this form:

out = 0.0;
for (size_t i = 0; i < MAX; ++i)
{
    out += sum(v);
    v[i] = 1.0; // this adds O(1) time and prevents caching
}

in both cases the timings are approximately equal, with the lambda as a favourite.

edited Mar 31 '23 at 12:10

Gregor Hartl Watters

518
1
3
17

answered Dec 23 '11 at 03:21

Archie

6,391
4
36
44

14

And the moral of the story -- always test and benchmark with *real* code, never with *toy* code. – David Schwartz Dec 28 '11 at 01:14
3

@Archie Did you also add the v[i] = 1.0 to the lambda as well? – sprite Dec 30 '13 at 05:35

Why C++ lambda is slower than ordinary function when called multiple times?

1 Answers1

Linked