How is std::function implemented?

According to the sources I have found, a lambda expression is essentially implemented by the compiler creating a class with overloaded function call operator and the referenced variables as members. This suggests that the size of lambda expressions varies, and given enough references variables that size can be arbitrarily large.

An std::function should have a fixed size, but it must be able to wrap any kind of callables, including any lambdas of the same kind. How is it implemented? If std::function internally uses a pointer to its target, then what happens, when the std::function instance is copied or moved? Are there any heap allocations involved?

Answers


The implementation of std::function can differ from one implementation to another, but the core idea is that it uses type-erasure. While there are multiple ways of doing it, you can imagine a trivial (not optimal) solution could be like this (simplified for the specific case of std::function<int (double)> for the sake of simplicity):

struct callable_base {
   virtual int operator()(double d) = 0;
   virtual ~callable_base() {}
};
template <typename F>
struct callable : callable_base {
   F functor;
   callable(F functor) : functor(functor) {}
   virtual int operator()(double d) { return functor(d); }
};
class function_int_double {
   std::unique_ptr<callable_base> c;
public:
   template <typename F>
   function(F f) {
      c.reset(new callable<F>(f));
   }
   int operator()(double d) { return c(d); }
// ...
};

In this simple approach the function object would store just a unique_ptr to a base type. For each different functor used with the function, a new type derived from the base is created and an object of that type instantiated dynamically. The std::function object is always of the same size and will allocate space as needed for the different functors in the heap.

In real life there are different optimizations that provide performance advantages but would complicate the answer. The type could use small object optimizations, the dynamic dispatch can be replaced by a free-function pointer that takes the functor as argument to avoid one level of indirection... but the idea is basically the same.


Regarding the issue of how copies of the std::function behave, a quick test indicates that copies of the internal callable object are done, rather than sharing the state.

// g++4.8
int main() {
   int value = 5;
   typedef std::function<void()> fun;
   fun f1 = [=]() mutable { std::cout << value++ << '\n' };
   fun f2 = f1;
   f1();                    // prints 5
   fun f3 = f1;
   f2();                    // prints 5
   f3();                    // prints 6 (copy after first increment)
}

The test indicates that f2 gets a copy of the callable entity, rather than a reference. If the callable entity was shared by the different std::function<> objects, the output of the program would have been 5, 6, 7.


For certain types of arguments ("if f's target is a callable object passed via reference_wrapper or a function pointer"), std::function's constructor disallows any exceptions, so using dynamic memory is out of the question. For this case, all the data must be stored directly inside the std::function object.

In the general case, (including the lambda case), using dynamic memory (via either the standard allocator, or an allocator passed to the std::function constructor) is allowed as the implementation sees fit. The standard recommends implementations do not use dynamic memory if it can be avoided, but as you rightly say, if the function object (not the std::function object, but the object being wrapped inside it) is large enough, there is no way to prevent it, since std::function has a fixed size.

This permission to throw exceptions is granted to both the normal constructor and the copy constructor, which fairly explicitly allows dynamic memory allocations during copying too. For moves, there is no reason why dynamic memory would be necessary. The standard does not seem to explicitly prohibit it, and probably cannot if the move might call the move constructor of the wrapped object's type, but you should be able to assume that if both the implementation and your objects are sensible, moving won't cause any allocations.


The answer from @David Rodríguez - dribeas is good for demonstrating the type-erasure but not good enough since type-erasure also includes how types are copied (in that answer the function object won't be copy-constructible). Those behaviors are also stored in the function object, besides the functor data.

The trick, used in the STL implementation from Ubuntu 14.04 gcc 4.8, is to write one generic function, specialize it with each possible functor type, and cast them to a universal function pointer type. Therefore the type information is erased.

I've cobbled up a simplified version of that. Hope it'll help

#include <iostream>
#include <memory>

template <typename T>
class function;

template <typename R, typename... Args>
class function<R(Args...)>
{
    // function pointer types for the type-erasure behaviors
    // all these char* parameters are actually casted from some functor type
    typedef R (*invoke_fn_t)(char*, Args&&...);
    typedef void (*construct_fn_t)(char*, char*);
    typedef void (*destroy_fn_t)(char*);

    // type-aware generic functions for invoking
    // the specialization of these functions won't be capable with
    //   the above function pointer types, so we need some cast
    template <typename Functor>
    static R invoke_fn(Functor* fn, Args&&... args)
    {
        return (*fn)(std::forward<Args>(args)...);
    }

    template <typename Functor>
    static void construct_fn(Functor* construct_dst, Functor* construct_src)
    {
        // the functor type must be copy-constructible
        new (construct_dst) Functor(*construct_src);
    }

    template <typename Functor>
    static void destroy_fn(Functor* f)
    {
        f->~Functor();
    }

    // these pointers are storing behaviors
    invoke_fn_t invoke_f;
    construct_fn_t construct_f;
    destroy_fn_t destroy_f;

    // erase the type of any functor and store it into a char*
    // so the storage size should be obtained as well
    std::unique_ptr<char[]> data_ptr;
    size_t data_size;
public:
    function()
        : invoke_f(nullptr)
        , construct_f(nullptr)
        , destroy_f(nullptr)
        , data_ptr(nullptr)
        , data_size(0)
    {}

    // construct from any functor type
    template <typename Functor>
    function(Functor f)
        // specialize functions and erase their type info by casting
        : invoke_f(reinterpret_cast<invoke_fn_t>(invoke_fn<Functor>))
        , construct_f(reinterpret_cast<construct_fn_t>(construct_fn<Functor>))
        , destroy_f(reinterpret_cast<destroy_fn_t>(destroy_fn<Functor>))
        , data_ptr(new char[sizeof(Functor)])
        , data_size(sizeof(Functor))
    {
        // copy the functor to internal storage
        this->construct_f(this->data_ptr.get(), reinterpret_cast<char*>(&f));
    }

    // copy constructor
    function(function const& rhs)
        : invoke_f(rhs.invoke_f)
        , construct_f(rhs.construct_f)
        , destroy_f(rhs.destroy_f)
        , data_size(rhs.data_size)
    {
        if (this->invoke_f) {
            // when the source is not a null function, copy its internal functor
            this->data_ptr.reset(new char[this->data_size]);
            this->construct_f(this->data_ptr.get(), rhs.data_ptr.get());
        }
    }

    ~function()
    {
        if (data_ptr != nullptr) {
            this->destroy_f(this->data_ptr.get());
        }
    }

    // other constructors, from nullptr, from function pointers

    R operator()(Args&&... args)
    {
        return this->invoke_f(this->data_ptr.get(), std::forward<Args>(args)...);
    }
};

// examples
int main()
{
    int i = 0;
    auto fn = [i](std::string const& s) mutable
    {
        std::cout << ++i << ". " << s << std::endl;
    };
    fn("first");                                   // 1. first
    fn("second");                                  // 2. second

    // construct from lambda
    ::function<void(std::string const&)> f(fn);
    f("third");                                    // 3. third

    // copy from another function
    ::function<void(std::string const&)> g(f);
    f("forth - f");                                // 4. forth - f
    g("forth - g");                                // 4. forth - g

    // capture and copy non-trivial types like std::string
    std::string x("xxxx");
    ::function<void()> h([x]() { std::cout << x << std::endl; });
    h();

    ::function<void()> k(h);
    k();
    return 0;
}

There are also some optimizations in the STL version

  • the construct_f and destroy_f are mixed into one function pointer (with an additional parameter that tells what to do) as to save some bytes
  • raw pointers are used to store the functor object, along with a function pointer in a union, so that when a function object is constructed from an function pointer, it will be stored directly in the union rather than heap space

Maybe the STL implementation is not the best solution as I've heard about some faster implementation. However I believe the underlying mechanism is the same.


An std::function overloads the operator() making it a functor object, lambda's work the same way. It basically creates a struct with member variables that can be accessed inside the operator() function. So the basic concept to keep in mind is that a lambda is an object (called a functor or function object) not a function. The standard says not to use dynamic memory if it can be avoided.


Need Your Help

Build an own SMS Gateway

sms gateway

We run a remote system and would like the servers to be able to alert us to their status via SMS. Is it possible to setup our own SMS gateway (or our own GSM network) so we DO NOT have to pay for a...

BitmapSource from file

c# wpf

How can I load a BitmapSource from an image file?