Under the covers of C++ lambdas - Part 1: The static invoker

Oct 06, 2020

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):

int main()
{
  auto multiply = [](const int val1) noexcept {
    return [val1](const int val2) noexcept { return val1 * val2; };
  };

  auto multiplyBy3 = multiply(3);
  int  res         = multiplyBy3(18);

  // same compilation
  // int res = multiply(3)(18);

  printf("Result: %i\n", res);

  return 0;
}

The transformation with C++ Insights gives the following result:

int main()
{
  class __lambda_5_19
  {
  public:
    inline /*constexpr */ __lambda_6_12
    operator()(const int val1) const noexcept
    {
      A Body of the call operator
      class __lambda_6_12
      {
      public:
        inline /*constexpr */ int operator()(const int val2) const noexcept
        {
          return val1 * val2;
        }

      private:
        const int val1;

      public:
        __lambda_6_12(const int _val1)
        : val1{_val1}
        {}

      } __lambda_6_12{val1};

      return __lambda_6_12;
    }

    using retType_5_19 = __lambda_6_12*;
    inline /*constexpr */ operator retType_5_19() const noexcept
    {
      return __invoke;
    };

  private:
    static inline __lambda_6_12 __invoke(const int val1) noexcept
    {
      B Body of __invoke
      class __lambda_6_12
      {
      public:
        inline /*constexpr */ int operator()(const int val2) const noexcept
        {
          return val1 * val2;
        }

      private:
        const int val1;

      public:
        __lambda_6_12(const int _val1)
        : val1{_val1}
        {}

      } __lambda_6_12{val1};

      return __lambda_6_12;
    }

  public:
     *constexpr */ __lambda_5_19() = default;
  };

  __lambda_5_19 multiply    = __lambda_5_19{};
  __lambda_6_12 multiplyBy3 = multiply.operator()(3);
  int res                   = multiplyBy3.operator()(18);
  printf("Result: %i\n", res);
  return 0;
}

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):

//Note:We don't want to simply forward the call to operator()
//since forwarding is not entirely transparent, and could
//introduce visible side‐effects. To produce the
//desired semantics we copy the parameter‐clause
//and body exactly
template<class A, class B>
static auto __invoke(A a, B b)
{
    return a + b;
}

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:

struct Closure {
   template<class T> auto operator()(T t) const { /* ... */ }
   template<class T> static auto lambda_call_operator_invoker(T a) {
      // forwards execution to operator()(a) and therefore has
      // the same return type deduced
      /* ... */
   }
   template<class T> using fptr_t =
      decltype(lambda_call_operator_invoker(declval<T>())) (*)(T);
   template<class T> operator fptr_t<T>() const
     { return &lambda_call_operator_invoker; }
};

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:

int main()
{
  auto lamb = [](int x) { return ++x; };

  int (*fp)(int) = lamb;
  return fp(4);
}

We can implement __invoke and inside a function object like this:

int main()
{
  class __lambda_3_15
  {
  public:
    inline int operator()(int x) const { return ++x; }

    using retType_3_15 = int (*)(int);
    inline operator retType_3_15() const noexcept { return __invoke; }

  private:
    static inline int __invoke(int x)
    {
      __lambda_3_15
        helper{};  A Create an object of our lambdas type

      return helper(
        x);  B Invoke the call operator for that object
    }
  };

  __lambda_3_15 lamb = __lambda_3_15{};
  int (*fp)(int)     = lamb;
  return fp(4);  C Call __invoke
}

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:

// Map the static invoker for the lambda back to the call operator.
// Conveniently, we don't have to slice out the 'this' argument (as is
// being done for the non-static case), since a static member function
// doesn't have an implicit argument passed in.

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 Patreon or, of course, with code contributions.

Acknowledgments

I’m grateful to Andrew King for reviewing a draft of this post.

Andreas

« Under the covers of C++ lambdas - Part 2: Captures, captures, captures

CppCon B2B Talk C++ Templates - Videos are out »

Blog