Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does a lambda have a size of 1 byte?

I am working with the memory of some lambdas in C++, but I am a bit puzzled by their size.

Here is my test code:

#include <iostream> #include <string>  int main() {   auto f = [](){ return 17; };   std::cout << f() << std::endl;   std::cout << &f << std::endl;   std::cout << sizeof(f) << std::endl; } 

The ouptut is:

17 0x7d90ba8f626f 1 

This suggests that the size of my lambda is 1.

  • How is this possible?

  • Shouldn't the lambda be, at minimum, a pointer to its implementation?

like image 716
sdgfsdh Avatar asked May 27 '16 11:05

sdgfsdh


People also ask

What is special about lambda?

With AWS Lambda, there are no new languages, tools, or frameworks to learn. You can use any third- party library, even native ones. You can also package any code (frameworks, SDKs, libraries, and more) as a Lambda Layer, and manage and share them easily across multiple functions.

How do you explain lambda?

A lambda function is a small anonymous function. A lambda function can take any number of arguments, but can only have one expression.

Why is lambda called lambda?

But what is a Lambda expression? The term “Lambda” comes from mathematics, where it's called lambda calculus. In programming, a Lambda expression (or function) is just an anonymous function, i.e., a function with no name. In fact, some Lambda expressions don't even have a function body.

Why lambda function is fast?

Being anonymous, lambda functions can be easily passed without being assigned to a variable. Lambda functions are inline functions and thus execute comparatively faster. Many times lambda functions make code much more readable by avoiding the logical jumps caused by function calls.


2 Answers

The lambda in question actually has no state.

Examine:

struct lambda {   auto operator()() const { return 17; } }; 

And if we had lambda f;, it is an empty class. Not only is the above lambda functionally similar to your lambda, it is (basically) how your lambda is implemented! (It also needs an implicit cast to function pointer operator, and the name lambda is going to be replaced with some compiler-generated pseudo-guid)

In C++, objects are not pointers. They are actual things. They only use up the space required to store the data in them. A pointer to an object can be larger than an object.

While you might think of that lambda as a pointer to a function, it isn't. You cannot reassign the auto f = [](){ return 17; }; to a different function or lambda!

 auto f = [](){ return 17; };  f = [](){ return -42; }; 

the above is illegal. There is no room in f to store which function is going to be called -- that information is stored in the type of f, not in the value of f!

If you did this:

int(*f)() = [](){ return 17; }; 

or this:

std::function<int()> f = [](){ return 17; }; 

you are no longer storing the lambda directly. In both of these cases, f = [](){ return -42; } is legal -- so in these cases, we are storing which function we are invoking in the value of f. And sizeof(f) is no longer 1, but rather sizeof(int(*)()) or larger (basically, be pointer sized or larger, as you expect. std::function has a min size implied by the standard (they have to be able to store "inside themselves" callables up to a certain size) which is at least as large as a function pointer in practice).

In the int(*f)() case, you are storing a function pointer to a function that behaves as-if you called that lambda. This only works for stateless lambdas (ones with an empty [] capture list).

In the std::function<int()> f case, you are creating a type-erasure class std::function<int()> instance that (in this case) uses placement new to store a copy of the size-1 lambda in an internal buffer (and, if a larger lambda was passed in (with more state), would use heap allocation).

As a guess, something like these is probably what you think is going on. That a lambda is an object whose type is described by its signature. In C++, it was decided to make lambdas zero cost abstractions over the manual function object implementation. This lets you pass a lambda into a std algorithm (or similar) and have its contents be fully visible to the compiler when it instantiates the algorithm template. If a lambda had a type like std::function<void(int)>, its contents would not be fully visible, and a hand-crafted function object might be faster.

The goal of C++ standardization is high level programming with zero overhead over hand-crafted C code.

Now that you understand that your f is in fact stateless, there should be another question in your head: the lambda has no state. Why does it not size have 0?


There is the short answer.

All objects in C++ must have a minimium size of 1 under the standard, and two objects of the same type cannot have the same address. These are connected, because an array of type T will have the elements placed sizeof(T) apart.

Now, as it has no state, sometimes it can take up no space. This cannot happen when it is "alone", but in some contexts it can happen. std::tuple and similar library code exploits this fact. Here is how it works:

As a lambda is equivalent to a class with operator() overloaded, stateless lambdas (with a [] capture list) are all empty classes. They have sizeof of 1. In fact, if you inherit from them (which is allowed!), they will take up no space so long as it doesn't cause a same-type address collision. (This is known as the empty base optimization).

template<class T> struct toy:T {   toy(toy const&)=default;   toy(toy &&)=default;   toy(T const&t):T(t) {}   toy(T &&t):T(std::move(t)) {}   int state = 0; };  template<class Lambda> toy<Lambda> make_toy( Lambda const& l ) { return {l}; } 

the sizeof(make_toy( []{std::cout << "hello world!\n"; } )) is sizeof(int) (well, the above is illegal because you cannot create a lambda in a non-evaluated context: you have to create a named auto toy = make_toy(blah); then do sizeof(blah), but that is just noise). sizeof([]{std::cout << "hello world!\n"; }) is still 1 (similar qualifications).

If we create another toy type:

template<class T> struct toy2:T {   toy2(toy2 const&)=default;   toy2(T const&t):T(t), t2(t) {}   T t2; }; template<class Lambda> toy2<Lambda> make_toy2( Lambda const& l ) { return {l}; } 

this has two copies of the lambda. As they cannot share the same address, sizeof(toy2(some_lambda)) is 2!

like image 107
Yakk - Adam Nevraumont Avatar answered Oct 22 '22 01:10

Yakk - Adam Nevraumont


A lambda is not a function pointer.

A lambda is an instance of a class. Your code is approximately equivalent to:

class f_lambda { public:    auto operator() { return 17; } };  f_lambda f; std::cout << f() << std::endl; std::cout << &f << std::endl; std::cout << sizeof(f) << std::endl; 

The internal class that represents a lambda has no class members, hence its sizeof() is 1 (it cannot be 0, for reasons adequately stated elsewhere).

If your lambda were to capture some variables, they'll be equivalent to class members, and your sizeof() will indicate accordingly.

like image 33
Sam Varshavchik Avatar answered Oct 21 '22 23:10

Sam Varshavchik