C++11 std::function plus lent que les appels virtuels ?

Question

Je suis en train de créer un mécanisme qui permet aux utilisateurs de former des fonctions complexes arbitraires à partir de blocs de construction de base en utilisant l'outil de gestion de l'information de l'entreprise. motif décoratif . Cela fonctionne bien du point de vue fonctionnel, mais je n'aime pas le fait que cela implique beaucoup d'appels virtuels, en particulier lorsque la profondeur d'imbrication devient importante. Cela m'inquiète car la fonction complexe peut être appelée souvent (>100 000 fois).

Pour éviter ce problème, j'ai essayé de transformer le schéma du décorateur en une std::function une fois qu'il était terminé (cfr. to_function() dans le SSCCE). Tous les appels de fonctions internes sont câblés lors de la construction de la std::function . Je me suis dit que cette méthode serait plus rapide à évaluer que le schéma original du décorateur, car aucune recherche virtuelle ne doit être effectuée dans le fichier std::function version.

Hélas, les bancs d'essai prouvent que j'avais tort : le schéma du décorateur est en fait plus rapide que le schéma de l'utilisateur. std::function J'ai construit à partir de ça. Je me demande maintenant pourquoi. Peut-être que ma configuration de test est défectueuse puisque je n'utilise que deux fonctions de base triviales, ce qui signifie que les recherches dans les vtable peuvent être mises en cache ?

Le code que j'ai utilisé est inclus ci-dessous, malheureusement il est assez long.

---

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

---

Point de repère

Utilisation de pipe :

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

Utilisation de fun :

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

Answer 1

Vous avez std::function s liant des lambdas qui appellent std::function qui lient des lamdbas qui appellent std::function s que ...

Regardez votre to_function . Il crée un lambda qui appelle deux std::function et renvoie ce lambda lié à un autre std::function . Le compilateur ne résoudra pas cualquier de ces derniers de manière statique.

Au bout du compte, on se retrouve avec autant d'appels indirects que dans la solution de la fonction virtuelle, et ce, même si l'on se débarrasse de la borne processfun et l'appeler directement dans le lambda. Sinon, vous en avez deux fois plus.

Si vous voulez gagner en rapidité, vous devrez créer l'ensemble du pipeline de manière à ce qu'il puisse être résolu de manière statique, ce qui signifie beaucoup plus de modèles avant de pouvoir finalement effacer le type en un unique std::function .

Answer 2

Comme l'indique la réponse de Sebastian Redl, votre "alternative" aux fonctions virtuelles ajoute plusieurs couches d'indirection par le biais de fonctions liées dynamiquement (soit virtuelles, soit par le biais de pointeurs de fonction, en fonction de l'environnement de l'utilisateur). std::function ) et ensuite, il appelle toujours l'implémentation virtuelle Pipeline::process(double) de toute façon !

Cette modification le rend sensiblement plus rapide, en supprimant une couche de std::function et empêchant l'appel à Derived::process être virtuel :

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

Il y a encore plus de travail à faire ici que dans la version de la fonction virtuelle.

Answer 3

std::function est notoirement lent ; l'effacement des types et l'allocation qui en résulte jouent également un rôle, avec gcc les invocations sont mal alignées/optimisées. Pour cette raison, il existe une pléthore de "délégués" C++ avec lesquels les gens tentent de résoudre ce problème. J'en ai porté un à Code Review :

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

Mais vous pouvez en trouver beaucoup d'autres avec Google, ou écrire le vôtre.

Answer 4

L'implémentation libstdc++ de std::function fonctionne à peu près comme suit :

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

Donc, bien que std::function ne connaît pas le type exact de l'objet Functor, il distribue les opérations importantes par le biais d'un pointeur de fonction functor_manager qui est une fonction statique d'une instance de modèle qui connaît le type de l'objet Functor. Functor type.

Chaque std::function allouera sur le tas sa propre copie de l'objet functor (à moins qu'il ne soit pas plus grand qu'un pointeur, tel qu'un pointeur de fonction, auquel cas il maintient simplement le pointeur comme un sous-objet).

Ce qu'il faut retenir, c'est que la copie de std::function est coûteux si l'objet foncteur sous-jacent a un constructeur de copie coûteux et/ou prend beaucoup d'espace (par exemple pour contenir les paramètres liés).