C++ 11 std :: funkcja wolniejsza niż połączenia wirtualne?

Question

Tworzę mechanizm, który umożliwia użytkownikom tworzenie dowolnych złożonych funkcji z podstawowych bloków konstrukcyjnych przy użyciu decorator pattern. Działa to dobrze, ale nie podoba mi się to, że wiąże się z wieloma wirtualnymi połączeniami, szczególnie gdy głębokość zagnieżdżania staje się duża. Martwi mnie to, ponieważ funkcja złożona może często wywoływać (> 100 000 razy).

Aby uniknąć tego problemu, próbowałem zmienić schemat dekoratora na std::function po jego zakończeniu (patrz: to_function() w SSCCE). Wszystkie wewnętrzne wywołania funkcji są łączone podczas budowy urządzenia std::function. Pomyślałem, że będzie to szybsze do oceny niż oryginalny schemat dekoratora, ponieważ nie trzeba wykonywać żadnych wirtualnych wyszukiwań w wersji std::function.

Niestety, testy porównawcze potwierdzają, że się mylę: schemat dekoratorów jest w rzeczywistości szybszy od tego, który zbudowałem na nim. Więc teraz zastanawiam się, dlaczego. Może moja konfiguracja testu jest wadliwa, ponieważ używam tylko dwóch podstawowych funkcji podstawowych, co oznacza, że ​​vtable może być buforowane?

Kod, którego użyłem, znajduje się poniżej, niestety jest dość długi.

---

SSCCE

// sscce.cpp 
#include <iostream> 
#include <vector> 
#include <memory> 
#include <functional> 
#include <random> 

/** 
* Base class for Pipeline scheme (implemented via decorators) 
*/ 
class Pipeline { 
protected: 
    std::unique_ptr<Pipeline> wrappee; 
    Pipeline(std::unique_ptr<Pipeline> wrap) 
    :wrappee(std::move(wrap)){} 
    Pipeline():wrappee(nullptr){} 

public: 
    typedef std::function<double(double)> FnSig; 
    double operator()(double input) const{ 
     if(wrappee.get()) input=wrappee->operator()(input); 
     return process(input); 
    } 

    virtual double process(double input) const=0; 
    virtual ~Pipeline(){} 

    // Returns a std::function which contains the entire Pipeline stack. 
    virtual FnSig to_function() const=0; 
}; 

/** 
* CRTP for to_function(). 
*/ 
template <class Derived> 
class Pipeline_CRTP : public Pipeline{ 
protected: 
    Pipeline_CRTP(const Pipeline_CRTP<Derived> &o):Pipeline(o){} 
    Pipeline_CRTP(std::unique_ptr<Pipeline> wrappee) 
    :Pipeline(std::move(wrappee)){} 
    Pipeline_CRTP():Pipeline(){}; 
public: 
    typedef typename Pipeline::FnSig FnSig; 

    FnSig to_function() const override{ 
     if(Pipeline::wrappee.get()!=nullptr){ 

      FnSig wrapfun = Pipeline::wrappee->to_function(); 
      FnSig processfun = std::bind(&Derived::process, 
       static_cast<const Derived*>(this), 
       std::placeholders::_1); 
      FnSig fun = [=](double input){ 
       return processfun(wrapfun(input)); 
      }; 
      return std::move(fun); 

     }else{ 

      FnSig processfun = std::bind(&Derived::process, 
       static_cast<const Derived*>(this), 
       std::placeholders::_1); 
      FnSig fun = [=](double input){ 
       return processfun(input); 
      }; 
      return std::move(fun); 
     } 

    } 

    virtual ~Pipeline_CRTP(){} 
}; 

/** 
* First concrete derived class: simple scaling. 
*/ 
class Scale: public Pipeline_CRTP<Scale>{ 
private: 
    double scale_; 
public: 
    Scale(std::unique_ptr<Pipeline> wrap, double scale) // todo move 
:Pipeline_CRTP<Scale>(std::move(wrap)),scale_(scale){} 
    Scale(double scale):Pipeline_CRTP<Scale>(),scale_(scale){} 

    double process(double input) const override{ 
     return input*scale_; 
    } 
}; 

/** 
* Second concrete derived class: offset. 
*/ 
class Offset: public Pipeline_CRTP<Offset>{ 
private: 
    double offset_; 
public: 
    Offset(std::unique_ptr<Pipeline> wrap, double offset) // todo move 
:Pipeline_CRTP<Offset>(std::move(wrap)),offset_(offset){} 
    Offset(double offset):Pipeline_CRTP<Offset>(),offset_(offset){} 

    double process(double input) const override{ 
     return input+offset_; 
    } 
}; 

int main(){ 

    // used to make a random function/arguments 
    // to prevent gcc from being overly clever 
    std::default_random_engine generator; 
    auto randint = std::bind(std::uniform_int_distribution<int>(0,1),std::ref(generator)); 
    auto randdouble = std::bind(std::normal_distribution<double>(0.0,1.0),std::ref(generator)); 

    // make a complex Pipeline 
    std::unique_ptr<Pipeline> pipe(new Scale(randdouble())); 
    for(unsigned i=0;i<100;++i){ 
     if(randint()) pipe=std::move(std::unique_ptr<Pipeline>(new Scale(std::move(pipe),randdouble()))); 
     else pipe=std::move(std::unique_ptr<Pipeline>(new Offset(std::move(pipe),randdouble()))); 
    } 

    // make a std::function from pipe 
    Pipeline::FnSig fun(pipe->to_function()); 

    double bla=0.0; 
    for(unsigned i=0; i<100000; ++i){ 
#ifdef USE_FUNCTION 
     // takes 110 ms on average 
     bla+=fun(bla); 
#else 
     // takes 60 ms on average 
     bla+=pipe->operator()(bla); 
#endif 
    } 
    std::cout << bla << std::endl; 
} 

---

benchmark

Stosując pipe:

g++ -std=gnu++11 sscce.cpp -march=native -O3 
sudo nice -3 /usr/bin/time ./a.out 
-> 60 ms 

Stosując fun:

g++ -DUSE_FUNCTION -std=gnu++11 sscce.cpp -march=native -O3 
sudo nice -3 /usr/bin/time ./a.out 
-> 110 ms 

Answer 1

Jako odpowiedź Sebastiana Redl mówi, twój „alternatywa” do funkcji wirtualnych dodaje kilka warstw zadnie przez dynamicznie związanymi funkcji (albo wirtualne, lub za pośrednictwem wskaźników funkcji, w zależności od implementacji std::function), a następnie nadal wywołuje wirtualną Pipeline::process(double) funkcji tak czy inaczej!

Ta zmiana sprawia, że ​​znacznie szybciej, usuwając jedną warstwę std::function zadnie i zapobiegania wezwanie do Derived::process bycie wirtualnym:

FnSig to_function() const override { 
    FnSig fun; 
    auto derived_this = static_cast<const Derived*>(this); 
    if (Pipeline::wrappee) { 
     FnSig wrapfun = Pipeline::wrappee->to_function(); 
     fun = [=](double input){ 
      return derived_this->Derived::process(wrapfun(input)); 
     }; 
    } else { 
     fun = [=](double input){ 
      return derived_this->Derived::process(input); 
     }; 
    } 
    return fun; 
} 

Jest jeszcze praca wykonywana tutaj niż w wersji funkcji wirtualnej chociaż.

Answer 2

Masz std::function s wiążących lambdy które wywołują std::function s, które wiążą lamdbas które wywołują std::function jakoby ...

spojrzeć na swoje to_function. Tworzy lambdę, która wywołuje dwa std::function s, i zwraca tę lambdę do innego std::function. Kompilator nie będzie statycznie przetwarzał żadnego żadnego z tych.

W efekcie kończymy z tak samo wieloma połączeniami pośrednimi, jak rozwiązanie funkcji wirtualnej, a to oznacza, że ​​pozbędziemy się związanego processfun i bezpośrednio wywołajmy go w lambda. W przeciwnym razie masz dwa razy więcej.

Jeśli chcesz przyspieszyć, będziesz musiał stworzyć cały potok w sposób, który może być statycznie rozdzielony, a to oznacza dużo więcej szablonów, zanim w końcu możesz wymazać typ w pojedynczy std::function.

Answer 3

std::function jest notorycznie powolny; Usunięcie tekstu i wynikowa alokacja odgrywają w tym również rolę, również z gcc, wywołania są źle zinterpretowane/zoptymalizowane. Z tego powodu istnieje mnóstwo "delegatów" w C++, z którymi ludzie próbują rozwiązać ten problem. I przeniesione do kodu jeden test:

https://codereview.stackexchange.com/questions/14730/impossibly-fast-delegate-in-c11

Ale można znaleźć mnóstwo innych z Google, lub napisać własne.

EDIT:

Te dni, spojrzeć here do szybkiego delegata.

Answer 4

libstdC++ implementacja std :: funkcja działa z grubsza następująco:

template<typename Signature> 
struct Function 
{ 
    Ptr functor; 
    Ptr functor_manager; 

    template<class Functor> 
    Function(const Functor& f) 
    { 
     functor_manager = &FunctorManager<Functor>::manage; 
     functor = new Functor(f); 
    } 

    Function(const Function& that) 
    { 
     functor = functor_manager(CLONE, that->functor); 
    } 

    R operator()(args) // Signature 
    { 
     return functor_manager(INVOKE, functor, args); 
    } 

    ~Function() 
    { 
     functor_manager(DESTROY, functor); 
    } 
} 

template<class Functor> 
struct FunctorManager 
{ 
    static manage(int operation, Functor& f) 
    { 
     switch (operation) 
     { 
     case CLONE: call Functor copy constructor; 
     case INVOKE: call Functor::operator(); 
     case DESTROY: call Functor destructor; 
     } 
    } 
} 

Więc chociaż std::function nie zna dokładny typ obiektu funktora, to wywoła ważne operacje poprzez functor_manager funkcji wskaźnika, który jest statyczna funkcja instancji szablonu, która wie o typie Functor.

Każda instancja std::function przydzieli na stercie swoją własną kopię obiektu funktora (o ile nie jest on większy niż wskaźnik, taki jak wskaźnik funkcji, w takim przypadku po prostu utrzymuje wskaźnik jako obiekt podrzędny).

Ważne jest, że kopiowanie std::function jest kosztowne, jeśli bazowy obiekt funktora ma kosztowny konstruktor kopii i/lub zajmuje dużo miejsca (na przykład do przechowywania powiązanych parametrów).