c++ - logo - ¿Cómo se implementa std:: function?

hbase

Question

De acuerdo con las fuentes que he encontrado, una expresión lambda es implementada esencialmente por el compilador creando una clase con un operador de llamada de función sobrecargado y las variables referenciadas como miembros. Esto sugiere que el tamaño de las expresiones lambda varía, y dadas las suficientes referencias de variables, ese tamaño puede ser arbitrariamente grande .

Una std::function debe tener un tamaño fijo , pero debe ser capaz de envolver cualquier tipo de callables, incluidas las lambdas del mismo tipo. ¿Cómo se implementa? Si std::function internamente utiliza un puntero a su objetivo, ¿qué ocurre cuando se copia o mueve la instancia de std::function ? ¿Hay alguna asignación de montón involucrada?

Answer 1

La implementación de std::function puede diferir de una implementación a otra, pero la idea principal es que usa borrado de tipo. Si bien existen múltiples formas de hacerlo, puede imaginarse que una solución trivial (no óptima) podría ser así (simplificada para el caso específico de std::function<int (double)> por simplicidad):

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); }
// ...
};

En este enfoque simple, el objeto de function almacenaría solo un unique_ptr a un tipo base. Para cada functor diferente utilizado con la function , se crea un nuevo tipo derivado de la base y un objeto de ese tipo instanciado dinámicamente. El objeto std::function siempre tiene el mismo tamaño y asignará espacio según sea necesario para los diferentes funtores en el montón.

En la vida real existen diferentes optimizaciones que proporcionan ventajas de rendimiento pero complicarían la respuesta. El tipo podría usar pequeñas optimizaciones de objetos, el despacho dinámico puede ser reemplazado por un puntero de función libre que toma al funtor como argumento para evitar un nivel de indirección ... pero la idea es básicamente la misma.

Con respecto al problema de cómo se comportan las copias de la std::function , una prueba rápida indica que se realizan copias del objeto interno que se puede llamar, en lugar de compartir el estado.

// 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)
}

La prueba indica que f2 obtiene una copia de la entidad invocable, en lugar de una referencia. Si la entidad invocable fue compartida por los diferentes objetos std::function<> , el resultado del programa habría sido 5, 6, 7.

Answer 2

La respuesta de @David Rodríguez - dribeas es buena para demostrar el borrado de tipos pero no lo suficientemente buena, ya que el borrado de tipos también incluye cómo se copian los tipos (en esa respuesta, el objeto de función no será copiable). Esos comportamientos también se almacenan en el objeto de function , además de los datos del functor.

El truco, utilizado en la implementación de STL de Ubuntu 14.04 gcc 4.8, es escribir una función genérica, especializarla con cada tipo de functor posible y convertirla en un tipo de puntero de función universal. Por lo tanto, la información del tipo se borra .

He improvisado una versión simplificada de eso. Espero que ayude

#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;
}

También hay algunas optimizaciones en la versión de STL

• el construct_f y el destroy_f se mezclan en un puntero de función (con un parámetro adicional que indica qué hacer) como para guardar algunos bytes
• los punteros sin formato se utilizan para almacenar el objeto del functor, junto con un puntero de función en una union , de modo que cuando un objeto de function se construye a partir de un puntero de función, se almacene directamente en la union lugar de almacenar el espacio

Tal vez la implementación de STL no sea la mejor solución ya que he oído hablar de una implementación más rápida . Sin embargo, creo que el mecanismo subyacente es el mismo.

Answer 3

Para ciertos tipos de argumentos ("si el objetivo de f es un objeto invocable pasado a través de reference_wrapper o un puntero de función"), el constructor de std::function no permite ninguna excepción, por lo que no se puede usar memoria dinámica. Para este caso, todos los datos deben almacenarse directamente dentro del objeto std::function .

En el caso general, (incluido el caso lambda), el uso de memoria dinámica (a través del asignador estándar, o un asignador pasado al constructor std::function ) está permitido a medida que la implementación lo considere oportuno. El estándar recomienda implementaciones que no usan memoria dinámica si se puede evitar, pero como dices correctamente, si el objeto de función (no el objeto std::function , pero el objeto que se está envolviendo dentro) es lo suficientemente grande, no hay forma de hacerlo para evitarlo, ya que std::function tiene un tamaño fijo.

Este permiso para lanzar excepciones se otorga tanto al constructor normal como al constructor de copia, lo que de manera bastante explícita también permite la asignación de memoria dinámica durante la copia. Para movimientos, no hay ninguna razón por la cual la memoria dinámica sería necesaria. El estándar no parece prohibirlo explícitamente, y probablemente no puede si el movimiento puede llamar al constructor de movimiento del tipo de objeto envuelto, pero usted debe poder asumir que si tanto la implementación como sus objetos son sensibles, el movimiento no causará cualquier asignación.

Answer 4

Una std::function sobrecarga el operator() convirtiéndolo en un objeto funtor, el trabajo de lambda de la misma manera. Básicamente crea una estructura con variables miembro a las que se puede acceder dentro de la función operator() . Entonces, el concepto básico a tener en cuenta es que un lambda es un objeto (llamado functor u objeto de función) no una función. El estándar dice que no se debe usar memoria dinámica si se puede evitar.