Under the covers of C++ lambdas - Part 1: The static invoker
This post is the start of a three-part series about lambdas. The focus is on how they are modeled internally. We will compare lambdas with function objects to see whether we as programmers can achieve the same result with a function object, or if the compiler's lambdas are more powerful. We will use C++ Insights, and we will also check the implementation of C++ Insights. Some things are not as easy as you might think.
This post is all about under the covers and not about how and where to apply them. For those of you who like to know how they work and where to use them, I recommend Bartłomiej Filipek's book C++ Lambda Story:
Lambdas are interesting for us
One data point I have about how important lambdas are is the number of requests and issues I received so far for C++ Insights. This theme continues in my training classes. Another source is C++ Weekly from Jason Turner, where he (currently) has 30 C++ Weekly episodes dealing with lambdas C++ Lambdas.
In the last few weeks, several independent lambda topics came up. In the comments for Jason's C++ Weekly - Ep 238 - const mutable Lambdas? Andrew King raised a question about a different example (tweet):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
The transformation with C++ Insights gives the following result:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
|
The issue raised was about __invoke
, where you can see a duplication B of the call operator's body A. As C++ Insights is Clang based, the result most likely is produced that way by Clang. As the developer behind C++ Insights, I can tell you it isn't. I made (make) it up.
Lambdas in C++ Insights
Let's first look at what we are talking about. Here we look at a capture-less lambda. A capture-less lambda is assignable to a function pointer. For this case, there is the invoke
function, which is a static
method in the closure type of a lambda. In our case __lambda_5_19
. This invoke
function is returned by a conversion operator, which returns a function pointer to __invoke
. This method kicks in when we assign a lambda to a function pointer. All that machinery is something we could do ourselves and that since C++98. As __invoke
does the same thing as the call operator, it has the same body. This is at least how it is shown above. The comment from Andrew was that this seems to be a duplication.
When I implemented support for this in C++ Insights, I looked at an early version of N3559 (Proposal for Generic (Polymorphic) Lambda Expressions):
1 2 3 4 5 6 7 8 9 10 |
|
This is more or less what C++ Insights currently shows. But during adoption, the wording slightly changed in N3649. The lambda, as provided by Andrew, is a capture-less non-generic lambda. N4861 [expr.prim.lambda.closure] p7 says:
The value returned by this conversion function is the address of a function F that, when invoked, has the same effect as invoking the closure type’s function call operator on a default-constructed instance of the closure type.
Well, from that part, the transformation shown by C++ Insights is indeed correct. Things get a bit more interesting if we are looking at capture-less generic lambdas. For them, we have N4861 [expr.prim.lambda.closure] p9 where we have a code example:
1 2 3 4 5 6 7 8 9 10 11 12 |
|
The interesting part here is the comment forwards execution to operator()(a) ... . This time, the Standard does not talk explicitly about a function F
. On the other hand, p9 doesn't say anything about not having such a function. The example is about how a conversion function should behave. We are in implementation-freedom-land.
Performance
With all that knowledge, how can we implement the invoke
-function for a capture-less non-generic lambda? Say we like to write the function object's __invoke
for this code:
1 2 3 4 5 6 7 |
|
We can implement __invoke
and inside a function object like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
To be able to call a non-static member function from a static one, we need an object. We can create one inside __invoke
A. For that object, we can invoke the call-operator and pass the variable x
B. This would work. With this implementation of __invoke
, x
is copied twice. First, in C, when we use the function pointer and then in B, we invoke the call-operator inside __invoke
. Imagine x
being some expensive type, like an std::string
which contains the text from all the Lord of the Rings books. You would probably notice the additional copy. Move doesn't help all the time. Even an std::string
contains not just pointers. Making x
and rvalue-reference in __invoke
isn't an option either. The signature must match that of the function pointer. As C++ programmers, we can't do better with function objects. Can lambda's do better?
What Clang does
Let's look at the implementation of a compiler. I can tell you so far that __invoke
's body in the C++ Insights transformation is taken from the call-operator. I just copy it because Clang doesn't provide a body for __invoke
in the AST. The reason why the body of __invoke
is empty can be found here clang/lib/AST/ExprConstant.cpp:
1 2 3 4 |
|
Clang does, in fact, replace a call to __invoke
with a call to operator()(...)
of the closure type. Do you remember how I started this post, comparing function objects and lambdas? We often say that lambdas and function objects are the same. We can create or emulate lambdas with function objects. That is true to some degree. In this case, the compiler can do things we as developers can't. We cannot place a call to a non-static member function without an object from a static-member function. The compiler can! And Clang takes that opportunity to save as code duplications (I assume all other compilers do it the same way).
Lambdas: 1, Function objects: 0
What's next
In the next part of the lambda series, I will go into details about lambda captures and how a lambda is modeled. We will continue to compare lambdas to function objects and see which, in the end, scores better.
Support the project
Have fun with C++ Insights. You can support the project by becoming a GitHub Sponsor or, of course, with code contributions.
Acknowledgments
I’m grateful to Andrew King for reviewing a draft of this post.
Andreas