Wie ist die std :: Funktion implementiert?

98

Gemäß den Quellen, die ich gefunden habe, wird ein Lambda-Ausdruck im Wesentlichen vom Compiler implementiert, der eine Klasse mit überladenem Funktionsaufrufoperator und den referenzierten Variablen als Mitglieder erstellt. Dies deutet darauf hin, dass die Größe der Lambda-Ausdrücke variiert und bei ausreichenden Referenzvariablen die Größe beliebig groß sein kann .

Ein std::functionsollte eine feste Größe haben , aber es muss in der Lage sein, alle Arten von Callables zu verpacken, einschließlich aller Lambdas der gleichen Art. Wie ist es implementiert? Wenn std::functionintern ein Zeiger auf sein Ziel verwendet wird, was passiert dann, wenn die std::functionInstanz kopiert oder verschoben wird? Gibt es Heap-Zuweisungen?

Miklós Homolya
quelle
2
Ich habe mir vor einiger Zeit die Implementierung von gcc / stdlib angesehen std::function. Es ist im Wesentlichen eine Handle-Klasse für ein polymorphes Objekt. Eine abgeleitete Klasse der internen Basisklasse wird erstellt, um die auf dem Heap zugewiesenen Parameter zu speichern. Anschließend wird der Zeiger darauf als Unterobjekt von gespeichert std::function. Ich glaube, es verwendet Referenzzählung std::shared_ptr, um das Kopieren und Verschieben zu handhaben.
Andrew Tomazos
4
Beachten Sie, dass Implementierungen möglicherweise Magie verwenden, dh sich auf Compiler-Erweiterungen stützen, die für Sie nicht verfügbar sind. Dies ist in der Tat für einige Typmerkmale erforderlich. Insbesondere Trampoline sind eine bekannte Technik, die in Standard-C ++ nicht verfügbar ist.
MSalters

Antworten:

78

Die Implementierung von std::functionkann von Implementierung zu Implementierung unterschiedlich sein, aber die Kernidee ist, dass Typlöschung verwendet wird. Obwohl es mehrere Möglichkeiten gibt, können Sie sich vorstellen, dass eine triviale (nicht optimale) Lösung wie folgt aussehen könnte ( std::function<int (double)>der Einfachheit halber für den speziellen Fall vereinfacht):

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

Bei diesem einfachen Ansatz würde das functionObjekt nur unique_ptreinen Basistyp speichern . Für jeden anderen Funktor, der mit dem verwendet wird function, wird ein neuer Typ erstellt, der von der Basis abgeleitet ist, und ein Objekt dieses Typs wird dynamisch instanziiert. Dasstd::function Objekt hat immer die gleiche Größe und weist den verschiedenen Funktoren im Heap nach Bedarf Speicherplatz zu.

Im wirklichen Leben gibt es verschiedene Optimierungen, die Leistungsvorteile bieten, aber die Antwort erschweren würden. Der Typ könnte kleine Objektoptimierungen verwenden. Der dynamische Versand kann durch einen Zeiger mit freien Funktionen ersetzt werden, der den Funktor als Argument verwendet, um eine Indirektionsebene zu vermeiden. Die Idee ist jedoch im Grunde dieselbe.


In Bezug auf die Frage, wie sich Kopien des std::functionVerhaltens verhalten, zeigt ein schneller Test an, dass Kopien des internen aufrufbaren Objekts erstellt werden, anstatt den Status zu teilen.

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

Der Test zeigt an, dass f2eine Kopie der aufrufbaren Entität anstelle einer Referenz abgerufen wird. Wenn die aufrufbare Entität von den verschiedenen std::function<>Objekten gemeinsam genutzt worden wäre, wäre die Ausgabe des Programms 5, 6, 7 gewesen.

David Rodríguez - Dribeas
quelle
@ Cole "Cole9" Johnson vermutet, dass er es selbst geschrieben hat
Aaronon
8
@Cole "Cole9" Johnson: Dies ist eine übermäßige Vereinfachung des realen Codes. Ich habe ihn nur in den Browser eingegeben, sodass er möglicherweise Tippfehler enthält und / oder aus verschiedenen Gründen nicht kompiliert werden kann. Der Code in der Antwort dient nur dazu, darzustellen, wie die Typlöschung implementiert wird / implementiert werden kann. Dies ist eindeutig kein Produktionsqualitätscode.
David Rodríguez - Dribeas
2
@MooingDuck: Ich glaube, Lambdas sind kopierbar (5.1.2 / 19), aber das ist nicht die Frage, sondern ob die Semantik von std::function korrekt wäre, wenn das interne Objekt kopiert würde, und ich denke nicht, dass dies der Fall ist (Denken Sie an ein Lambda, das einen Wert erfasst und veränderbar ist und in a gespeichert ist std::function. Wenn der Funktionsstatus kopiert wurde, kann die Anzahl der Kopien std::functionin einem Standardalgorithmus zu unterschiedlichen Ergebnissen führen, was unerwünscht ist.
David Rodríguez - dribeas
1
@ MiklósHomolya: Ich habe mit g ++ 4.8 getestet und die Implementierung kopiert den internen Status. Wenn die aufrufbare Entität groß genug ist, um eine dynamische Zuordnung zu erfordern, std::functionlöst die Kopie der Entität eine Zuordnung aus.
David Rodríguez - Dribeas
4
@ DavidRodríguez-dribeas gemeinsam genutzter Status wäre unerwünscht, da die Optimierung für kleine Objekte bedeuten würde, dass Sie bei einem vom Compiler und der Compilerversion festgelegten Größenschwellenwert vom gemeinsam genutzten Status in den nicht gemeinsam genutzten Status wechseln würden (da die Optimierung für kleine Objekte den gemeinsam genutzten Status blockieren würde). Das scheint problematisch.
Yakk - Adam Nevraumont
22

Die Antwort von @David Rodríguez - dribeas ist gut, um die Typlöschung zu demonstrieren, aber nicht gut genug, da die Typlöschung auch beinhaltet, wie Typen kopiert werden (in dieser Antwort ist das Funktionsobjekt nicht kopierkonstruierbar). Diese Verhaltensweisen werden auch in der gespeichertfunction neben den Funktordaten Objekt gespeichert.

Der Trick, der in der STL-Implementierung von Ubuntu 14.04 gcc 4.8 verwendet wird, besteht darin, eine generische Funktion zu schreiben, sie auf jeden möglichen Funktionstyp zu spezialisieren und sie in einen universellen Funktionszeigertyp umzuwandeln. Daher werden die Typinformationen gelöscht .

Ich habe eine vereinfachte Version davon zusammengeschustert. Hoffe es wird helfen

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

Es gibt auch einige Optimierungen in der STL-Version

  • das construct_funddestroy_f werden in einen Funktionszeiger gemischt (mit einem zusätzlichen Parameter, der angibt, was zu tun ist), um einige Bytes zu sparen
  • Rohzeiger werden verwendet, um das Funktorobjekt zusammen mit einem Funktionszeiger in a zu speichern union , sodass ein functionObjekt , wenn es aus einem Funktionszeiger erstellt wird, direkt im unionHeap-Bereich und nicht im Heap-Bereich gespeichert wird

Vielleicht ist die STL-Implementierung nicht die beste Lösung, da ich von einer schnelleren Implementierung gehört habe . Ich glaube jedoch, dass der zugrunde liegende Mechanismus der gleiche ist.

Neuront
quelle
20

Für bestimmte Arten von Argumenten ("wenn das Ziel von f ein überrufbares Objekt reference_wrapperoder ein Funktionszeiger ist") lässt std::functionder Konstruktor keine Ausnahmen zu, sodass die Verwendung des dynamischen Speichers nicht in Frage kommt. In diesem Fall müssen alle Daten direkt im gespeichert werdenstd::function Objekt .

Im allgemeinen Fall (einschließlich des Lambda-Falls) ist die Verwendung des dynamischen Speichers (entweder über den Standard-Allokator oder einen an den std::functionKonstruktor übergebenen Allokator) nach eigenem Ermessen zulässig. Der Standard empfiehlt, dass Implementierungen keinen dynamischen Speicher verwenden, wenn dies vermieden werden kann. Wie Sie jedoch zu Recht sagen std::function, gibt es keine Möglichkeit, dies zu verhindern , wenn das Funktionsobjekt (nicht das Objekt, sondern das darin eingeschlossene Objekt) groß genug ist. da std::functionhat eine feste größe.

Diese Berechtigung zum Auslösen von Ausnahmen wird sowohl dem normalen Konstruktor als auch dem Kopierkonstruktor erteilt, wodurch dynamische Speicherzuweisungen auch während des Kopierens ziemlich explizit möglich sind. Für Bewegungen gibt es keinen Grund, warum ein dynamischer Speicher erforderlich wäre. Der Standard scheint dies nicht explizit zu verbieten und kann es wahrscheinlich nicht, wenn die Verschiebung den Verschiebungskonstruktor des Typs des umschlossenen Objekts aufruft. Sie sollten jedoch davon ausgehen können, dass das Verschieben keine Ursache hat, wenn sowohl die Implementierung als auch Ihre Objekte sinnvoll sind etwaige Zuweisungen.


quelle
-6

Ein std::functionÜberladen operator()macht es zu einem Funktorobjekt, Lambdas Arbeit auf die gleiche Weise. Grundsätzlich wird eine Struktur mit Mitgliedsvariablen erstellt, auf die innerhalb der operator()Funktion zugegriffen werden kann. Das Grundkonzept ist also, dass ein Lambda ein Objekt (Funktor oder Funktionsobjekt genannt) ist, keine Funktion. Der Standard sagt, keinen dynamischen Speicher zu verwenden, wenn dies vermieden werden kann.

Aaronman
quelle
1
Wie können möglicherweise beliebig große Lambdas in eine feste Größe passen std::function? Das ist hier die Schlüsselfrage.
Miklós Homolya
2
@aaronman: Ich garantiere, dass jedes std::functionObjekt die gleiche Größe hat und nicht die Größe der enthaltenen Lambdas.
Mooing Duck
5
@aaronman auf die gleiche Weise, wie jedes std::vector<T...> Objekt eine feste Größe (Copiletime) hat, unabhängig von der tatsächlichen Allokatorinstanz / Anzahl der Elemente.
sehe
3
@aaronman: Nun, vielleicht sollten Sie eine Stackoverflow-Frage finden, die beantwortet, wie die std :: -Funktion so implementiert wird, dass sie beliebig große Lambdas enthalten kann: P
Mooing Duck
1
@aaronman: Wenn die aufrufbare Entität festgelegt ist, in der Konstruktion, Zuweisung ... std::function<void ()> f;keine Notwendigkeit, dort zuzuweisen, std::function<void ()> f = [&]() { /* captures tons of variables */ };höchstwahrscheinlich zuweisen. std::function<void()> f = &free_function;wahrscheinlich auch nicht zuweisen ...
David Rodríguez - Dribeas