recursive lambda implemention in c++11

Question

I interested to recursive lambda implementation, and found this code for Fibonacci calculation:

 std::function<int(int)> lfib = [&lfib](int n) {return n < 2 ? 1 : lfib(n-1) + lfib(n-2);};

And I have a question: std::function is a polymorphic function, so lfib creates/and saves the lambda in heap memory, not on the stack. And therefore may lose optimization possibilities of the program. Correct or not?

To a program with O(2^N) algorithmic complexity, the mechanics of the function call don't matter. — Cubbi
– Cubbi, Commented Jul 24, 2013 at 12:52
I wasn't ask about implementation fibbonachi, I was asked about std::function may loss optimization the program. — Khurshid Normuradov
– Khurshid Normuradov, Commented Jul 24, 2013 at 12:54
In practice, yes. But why would you ever do this? You only get an additional layer of abstraction and that's just not necessary. There's hardly ever the need for recursive lambda (which this actually isn't. this is just a lambda that calls a std::function). — stefan
– stefan, Commented Jul 24, 2013 at 15:25
I will convert this json d library to C++: github.com/D-Programming-Language/phobos/blob/master/std/json.d — Khurshid Normuradov
– Khurshid Normuradov, Commented Jul 25, 2013 at 5:26

Ben Voigt · Accepted Answer · 2013-07-24 12:53:40Z

5

The type-erasure data which is the state of std::function will persist as long as the std::function or its copies live, probably via heap allocation.

The same is not true of the closure, which contains captured variables. That's part of the state of the lambda object, and probably contains the address of a data structure on the stack, which will disappear when the current function returns and the variable lfib goes out of scope.

Remember that you've captured lfib by reference. Therefore any changes to lfib for the remainder of the function have to be visible to the lambda (including but not limited to the initialization). The only way the compiler can manage that in a general way is by storing the address of the local lfib. In your particular case, if lfib is not assigned again, it might be possible for the compiler to store the value immediately post-initialization instead of a reference. But it's not guaranteed, and not even particularly likely.

answered Jul 24, 2013 at 12:53

Ben Voigt

286k45 gold badges444 silver badges764 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Xeo Over a year ago

Such a small lambda will likely end up in the Small Buffer Optimization and not cause any heap-alloc.

Ben Voigt Over a year ago

@Xeo: Quite possibly. I'm not an expert in std::function implementations. What's of interest here is the lifetime.

user784668 Over a year ago

@Xeo: not in libstdc++, where lambdas, for some reason, are never stored directly in std::function itself, because they're not considered "location-invariant". See std::_Function_base::_Base_manager::__stored_locally.

Khurshid Normuradov Over a year ago

I'm not sure, but stored locally allowed only for pointer to function or pointer to member functions. For all other states don't stored locally.

Collectives™ on Stack Overflow

recursive lambda implemention in c++11

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related