std :: fonction vs modèle

Grâce à C ++ 11, nous avons reçu la std::functionfamille des wrappers de foncteurs. Malheureusement, je n'entends que de mauvaises choses à propos de ces nouveaux ajouts. Le plus populaire est qu'ils sont horriblement lents. Je l'ai testé et ils sont vraiment nuls par rapport aux modèles.

#include <iostream>
#include <functional>
#include <string>
#include <chrono>

template <typename F>
float calc1(F f) { return -1.0f * f(3.3f) + 666.0f; }

float calc2(std::function<float(float)> f) { return -1.0f * f(3.3f) + 666.0f; }

int main() {
    using namespace std::chrono;

    const auto tp1 = system_clock::now();
    for (int i = 0; i < 1e8; ++i) {
        calc1([](float arg){ return arg * 0.5f; });
    }
    const auto tp2 = high_resolution_clock::now();

    const auto d = duration_cast<milliseconds>(tp2 - tp1);  
    std::cout << d.count() << std::endl;
    return 0;
}

111 ms contre 1241 ms. Je suppose que c'est parce que les modèles peuvent être bien intégrés, tandis que functions couvrent les internes via des appels virtuels.

Évidemment, les modèles ont leurs problèmes tels que je les vois:

• ils doivent être fournis sous forme d'en-têtes, ce que vous ne voudrez peut-être pas faire lors de la publication de votre bibliothèque sous forme de code fermé,
• ils peuvent allonger le temps de compilation à moins qu'une extern templatepolitique semblable à celle-ci ne soit introduite,
• il n'y a pas (du moins connu de moi) de manière propre de représenter les exigences (concepts, qui que ce soit?) d'un modèle, à l'exception d'un commentaire décrivant le type de foncteur attendu.

Puis-je donc supposer que functions peut être utilisé comme standard de facto pour passer des foncteurs, et dans des endroits où des modèles de haute performance sont attendus, devraient être utilisés?

Éditer:

Mon compilateur est le Visual Studio 2012 sans CTP.

En général, si vous êtes confronté à une situation de conception qui vous laisse le choix, utilisez des modèles . J'ai insisté sur le mot design car je pense que ce sur quoi vous devez vous concentrer est la distinction entre les cas d'utilisation std::functionet les modèles, qui sont assez différents.

En général, le choix des modèles n'est qu'une instance d'un principe plus large: essayez de spécifier autant de contraintes que possible au moment de la compilation . La justification est simple: si vous pouvez détecter une erreur, ou une incompatibilité de type, avant même que votre programme ne soit généré, vous ne livrerez pas de programme bogué à votre client.

De plus, comme vous l'avez correctement souligné, les appels aux fonctions de modèle sont résolus de manière statique (c'est-à-dire au moment de la compilation), de sorte que le compilateur dispose de toutes les informations nécessaires pour optimiser et éventuellement intégrer le code (ce qui ne serait pas possible si l'appel était effectué via un vtable).

Oui, il est vrai que la prise en charge des modèles n'est pas parfaite, et C ++ 11 manque toujours de prise en charge des concepts; cependant, je ne vois pas comment std::functionvous sauverait à cet égard. std::functionn'est pas une alternative aux modèles, mais plutôt un outil pour les situations de conception où les modèles ne peuvent pas être utilisés.

Un tel cas d'utilisation se produit lorsque vous devez résoudre un appel au moment de l'exécution en invoquant un objet appelable qui adhère à une signature spécifique, mais dont le type concret est inconnu au moment de la compilation. C'est généralement le cas lorsque vous avez une collection de rappels de types potentiellement différents , mais que vous devez appeler de manière uniforme ; le type et le nombre de rappels enregistrés sont déterminés au moment de l'exécution en fonction de l'état de votre programme et de la logique de l'application. Certains de ces rappels pourraient être des foncteurs, certains pourraient être des fonctions simples, d'autres pourraient être le résultat de la liaison d'autres fonctions à certains arguments.

std::functionet std::bindoffrent également un idiome naturel pour permettre la programmation fonctionnelle en C ++, où les fonctions sont traitées comme des objets et sont naturellement curées et combinées pour générer d'autres fonctions. Bien que ce type de combinaison puisse également être réalisé avec des modèles, une situation de conception similaire est normalement associée à des cas d'utilisation qui nécessitent de déterminer le type des objets appelables combinés au moment de l'exécution.

Enfin, il existe d'autres situations où std::functionc'est inévitable, par exemple si vous voulez écrire des lambdas récursives ; cependant, ces restrictions sont davantage dictées par des limitations technologiques que par des distinctions conceptuelles, je crois.

Pour résumer, concentrez-vous sur la conception et essayez de comprendre quels sont les cas d'utilisation conceptuels de ces deux constructions. Si vous les comparez comme vous l'avez fait, vous les forcez dans une arène à laquelle ils n'appartiennent probablement pas.

Andy Prowl a bien couvert les problèmes de conception. C'est, bien sûr, très important, mais je pense que la question initiale concerne davantage les problèmes de performance liés à std::function.

Tout d'abord, une petite remarque sur la technique de mesure: les 11ms obtenus pour calc1n'ont aucun sens. En effet, en regardant l'assembly généré (ou en déboguant le code de l'assembly), on peut voir que l'optimiseur de VS2012 est suffisamment intelligent pour se rendre compte que le résultat de l'appel calc1est indépendant de l'itération et déplace l'appel hors de la boucle:

for (int i = 0; i < 1e8; ++i) {
}
calc1([](float arg){ return arg * 0.5f; });

De plus, il se rend compte que l'appel calc1n'a aucun effet visible et supprime complètement l'appel. Par conséquent, 111 ms est le temps nécessaire à la boucle vide pour s'exécuter. (Je suis surpris que l'optimiseur ait gardé la boucle.) Alors, soyez prudent avec les mesures de temps en boucles. Ce n'est pas aussi simple que cela puisse paraître.

Comme cela a été souligné, l'optimiseur a plus de difficultés à comprendre std::functionet ne déplace pas l'appel hors de la boucle. Donc, 1241 ms est une mesure juste pour calc2.

Notez que, std::functionest capable de stocker différents types d'objets appelables. Par conséquent, il doit effectuer une certaine magie d'effacement de type pour le stockage. Généralement, cela implique une allocation de mémoire dynamique (par défaut via un appel à new). Il est bien connu qu'il s'agit d'une opération assez coûteuse.

Le standard (20.8.11.2.1 / 5) encore les implémentations pour éviter l'allocation dynamique de mémoire pour les petits objets, ce que fait heureusement VS2012 (en particulier pour le code d'origine).

Pour avoir une idée de combien il peut être plus lent lorsque l'allocation de mémoire est impliquée, j'ai changé l'expression lambda pour capturer trois floats. Cela rend l'objet appelable trop grand pour appliquer l'optimisation des petits objets:

float a, b, c; // never mind the values
// ...
calc2([a,b,c](float arg){ return arg * 0.5f; });

Pour cette version, le temps est d'environ 16000ms (contre 1241ms pour le code d'origine).

Enfin, notez que la durée de vie du lambda englobe celle du std::function. Dans ce cas, plutôt que de stocker une copie du lambda, std::functionpourrait stocker une "référence" à celui-ci. Par «référence», j'entends un std::reference_wrapperqui est facilement construit par des fonctions std::refet std::cref. Plus précisément, en utilisant:

auto func = [a,b,c](float arg){ return arg * 0.5f; };
calc2(std::cref(func));

le temps diminue à environ 1860 ms.

J'ai écrit à ce sujet il y a quelque temps:

http://www.drdobbs.com/cpp/efficient-use-of-lambda-expressions-and/232500059

Comme je l'ai dit dans l'article, les arguments ne s'appliquent pas tout à fait à VS2010 en raison de sa faible prise en charge de C ++ 11. Au moment de la rédaction de cet article, seule une version bêta de VS2012 était disponible mais sa prise en charge de C ++ 11 était déjà suffisante à cet égard.

Avec Clang, il n'y a pas de différence de performance entre les deux

En utilisant clang (3.2, tronc 166872) (-O2 sous Linux), les binaires des deux cas sont en fait identiques .

-Je reviendrai retentir à la fin du message. Mais d'abord, gcc 4.7.2:

Il y a déjà beaucoup de perspicacité en cours, mais je tiens à souligner que le résultat des calculs de calc1 et calc2 ne sont pas les mêmes, en raison de la doublure etc. Comparez par exemple la somme de tous les résultats:

float result=0;
for (int i = 0; i < 1e8; ++i) {
  result+=calc2([](float arg){ return arg * 0.5f; });
}

avec calc2 qui devient

1.71799e+10, time spent 0.14 sec

tandis qu'avec calc1 il devient

6.6435e+10, time spent 5.772 sec

c'est un facteur de ~ 40 dans la différence de vitesse et un facteur de ~ 4 dans les valeurs. Le premier est une bien plus grande différence que ce qu'OP a publié (en utilisant Visual Studio). En fait, imprimer la valeur à la fin est également une bonne idée pour empêcher le compilateur de supprimer du code sans résultat visible (règle as-if). Cassio Neri l'a déjà dit dans sa réponse. Notez à quel point les résultats sont différents - Il faut être prudent lors de la comparaison des facteurs de vitesse des codes qui effectuent des calculs différents.

De plus, pour être honnête, comparer différentes manières de calculer f (3.3) de manière répétée n'est peut-être pas si intéressant. Si l'entrée est constante, elle ne doit pas être en boucle. (Il est facile pour l'optimiseur de le remarquer)

Si j'ajoute un argument de valeur fourni par l'utilisateur à calc1 et 2, le facteur de vitesse entre calc1 et calc2 revient à un facteur de 5, à partir de 40! Avec Visual Studio, la différence est proche d'un facteur de 2, et avec clang il n'y a pas de différence (voir ci-dessous).

De plus, comme les multiplications sont rapides, parler des facteurs de ralentissement n'est souvent pas si intéressant. Une question plus intéressante est la suivante: quelle est la taille de vos fonctions et ces appels constituent-ils le goulot d'étranglement dans un programme réel?

Bruit:

Clang (j'ai utilisé 3.2) a en fait produit des binaires identiques lorsque je bascule entre calc1 et calc2 pour l'exemple de code (affiché ci-dessous). Avec l'exemple d'origine publié dans la question, les deux sont également identiques mais ne prennent pas du tout de temps (les boucles sont simplement complètement supprimées comme décrit ci-dessus). Avec mon exemple modifié, avec -O2:

Nombre de secondes à exécuter (au meilleur de 3):

clang:        calc1:           1.4 seconds
clang:        calc2:           1.4 seconds (identical binary)

gcc 4.7.2:    calc1:           1.1 seconds
gcc 4.7.2:    calc2:           6.0 seconds

VS2012 CTPNov calc1:           0.8 seconds 
VS2012 CTPNov calc2:           2.0 seconds 

VS2015 (14.0.23.107) calc1:    1.1 seconds 
VS2015 (14.0.23.107) calc2:    1.5 seconds 

MinGW (4.7.2) calc1:           0.9 seconds
MinGW (4.7.2) calc2:          20.5 seconds 

Les résultats calculés de tous les binaires sont les mêmes et tous les tests ont été exécutés sur la même machine. Il serait intéressant que quelqu'un avec des connaissances plus profondes ou VS puisse commenter les optimisations qui ont pu être effectuées.

Mon code de test modifié:

#include <functional>
#include <chrono>
#include <iostream>

template <typename F>
float calc1(F f, float x) { 
  return 1.0f + 0.002*x+f(x*1.223) ; 
}

float calc2(std::function<float(float)> f,float x) { 
  return 1.0f + 0.002*x+f(x*1.223) ; 
}

int main() {
    using namespace std::chrono;

    const auto tp1 = high_resolution_clock::now();

    float result=0;
    for (int i = 0; i < 1e8; ++i) {
      result=calc1([](float arg){ 
          return arg * 0.5f; 
        },result);
    }
    const auto tp2 = high_resolution_clock::now();

    const auto d = duration_cast<milliseconds>(tp2 - tp1);  
    std::cout << d.count() << std::endl;
    std::cout << result<< std::endl;
    return 0;
}

Mettre à jour:

Ajouté vs2015. J'ai également remarqué qu'il y a des conversions double-> float dans calc1, calc2. Les supprimer ne change pas la conclusion pour Visual Studio (les deux sont beaucoup plus rapides mais le ratio est à peu près le même).

Différent n'est pas pareil.

C'est plus lent car il fait des choses qu'un modèle ne peut pas faire. En particulier, il vous permet d'appeler n'importe quelle fonction qui peut être appelée avec les types d'arguments donnés et dont le type de retour est convertible en type de retour donné à partir du même code .

void eval(const std::function<int(int)>& f) {
    std::cout << f(3);
}

int f1(int i) {
    return i;
}

float f2(double d) {
    return d;
}

int main() {
    std::function<int(int)> fun(f1);
    eval(fun);
    fun = f2;
    eval(fun);
    return 0;
}

Notez que le même objet fonction,, funest passé aux deux appels à eval. Il détient deux fonctions différentes .

Si vous n'avez pas besoin de faire cela, vous ne devriez pas utiliser std::function.

Vous avez déjà de bonnes réponses ici, donc je ne vais pas les contredire, bref comparer std :: function à des modèles, c'est comme comparer des fonctions virtuelles à des fonctions. Vous ne devriez jamais "préférer" les fonctions virtuelles aux fonctions, mais plutôt utiliser des fonctions virtuelles quand cela correspond au problème, en déplaçant les décisions du moment de la compilation au moment de l'exécution. L'idée est qu'au lieu d'avoir à résoudre le problème en utilisant une solution sur mesure (comme une table de saut), vous utilisez quelque chose qui donne au compilateur une meilleure chance d'optimiser pour vous. Cela aide également d'autres programmeurs, si vous utilisez une solution standard.

Cette réponse a pour but de contribuer, à l'ensemble des réponses existantes, à ce que je crois être une référence plus significative pour le coût d'exécution des appels std :: function.

Le mécanisme std :: function doit être reconnu pour ce qu'il fournit: toute entité appelable peut être convertie en une fonction std :: de signature appropriée. Supposons que vous ayez une bibliothèque qui ajuste une surface à une fonction définie par z = f (x, y), vous pouvez l'écrire pour accepter a std::function<double(double,double)>, et l'utilisateur de la bibliothèque peut facilement convertir n'importe quelle entité appelable en cela; que ce soit une fonction ordinaire, une méthode d'une instance de classe, ou un lambda, ou tout ce qui est pris en charge par std :: bind.

Contrairement aux approches de modèle, cela fonctionne sans avoir à recompiler la fonction de bibliothèque pour différents cas; en conséquence, peu de code compilé supplémentaire est nécessaire pour chaque cas supplémentaire. Cela a toujours été possible, mais cela nécessitait des mécanismes maladroits, et l'utilisateur de la bibliothèque aurait probablement besoin de construire un adaptateur autour de sa fonction pour la faire fonctionner. std :: function construit automatiquement l'adaptateur nécessaire pour obtenir une interface d'appel d' exécution commune pour tous les cas, ce qui est une fonctionnalité nouvelle et très puissante.

À mon avis, c'est le cas d'utilisation le plus important de std :: function en ce qui concerne les performances: je suis intéressé par le coût d'appeler une fonction std :: function plusieurs fois après qu'elle a été construite une fois, et elle doit être une situation où le compilateur est incapable d'optimiser l'appel en connaissant la fonction réellement appelée (c'est-à-dire que vous devez cacher l'implémentation dans un autre fichier source pour obtenir un benchmark approprié).

J'ai fait le test ci-dessous, similaire aux OP; mais les principaux changements sont:

1. Chaque cas boucle 1 milliard de fois, mais les objets std :: function ne sont construits qu'une seule fois. J'ai trouvé en regardant le code de sortie que 'operator new' est appelé lors de la construction d'appels std :: function réels (peut-être pas lorsqu'ils sont optimisés).
2. Le test est divisé en deux fichiers pour éviter une optimisation indésirable
3. Mes cas sont: (a) la fonction est en ligne (b) la fonction est passée par un pointeur de fonction ordinaire (c) la fonction est une fonction compatible enveloppée comme std :: function (d) function est une fonction incompatible rendue compatible avec un std :: bind, enveloppé comme std :: function

Les résultats que j'obtiens sont:

• cas (a) (en ligne) 1,3 nsec

• tous les autres cas: 3,3 nsec.

Le cas (d) a tendance à être légèrement plus lent, mais la différence (environ 0,05 nsec) est absorbée dans le bruit.

La conclusion est que la fonction std :: est comparable (au moment de l'appel) à l'utilisation d'un pointeur de fonction, même lorsqu'il y a une simple adaptation 'bind' à la fonction réelle. Le inline est 2 ns plus rapide que les autres, mais c'est un compromis attendu puisque le inline est le seul cas qui soit «câblé» au moment de l'exécution.

Lorsque j'exécute le code de johan-lundberg sur la même machine, je vois environ 39 nsec par boucle, mais il y en a beaucoup plus dans la boucle, y compris le constructeur et le destructeur réels de la fonction std ::, qui est probablement assez élevé car il s'agit d'un nouveau et supprimer.

-O2 gcc 4.8.1, vers la cible x86_64 (core i5).

Notez que le code est divisé en deux fichiers, pour empêcher le compilateur d'étendre les fonctions là où elles sont appelées (sauf dans le cas où il est prévu).

----- premier fichier source --------------

#include <functional>


// simple funct
float func_half( float x ) { return x * 0.5; }

// func we can bind
float mul_by( float x, float scale ) { return x * scale; }

//
// func to call another func a zillion times.
//
float test_stdfunc( std::function<float(float)> const & func, int nloops ) {
    float x = 1.0;
    float y = 0.0;
    for(int i =0; i < nloops; i++ ){
        y += x;
        x = func(x);
    }
    return y;
}

// same thing with a function pointer
float test_funcptr( float (*func)(float), int nloops ) {
    float x = 1.0;
    float y = 0.0;
    for(int i =0; i < nloops; i++ ){
        y += x;
        x = func(x);
    }
    return y;
}

// same thing with inline function
float test_inline(  int nloops ) {
    float x = 1.0;
    float y = 0.0;
    for(int i =0; i < nloops; i++ ){
        y += x;
        x = func_half(x);
    }
    return y;
}

----- deuxième fichier source -------------

#include <iostream>
#include <functional>
#include <chrono>

extern float func_half( float x );
extern float mul_by( float x, float scale );
extern float test_inline(  int nloops );
extern float test_stdfunc( std::function<float(float)> const & func, int nloops );
extern float test_funcptr( float (*func)(float), int nloops );

int main() {
    using namespace std::chrono;


    for(int icase = 0; icase < 4; icase ++ ){
        const auto tp1 = system_clock::now();

        float result;
        switch( icase ){
         case 0:
            result = test_inline( 1e9);
            break;
         case 1:
            result = test_funcptr( func_half, 1e9);
            break;
         case 2:
            result = test_stdfunc( func_half, 1e9);
            break;
         case 3:
            result = test_stdfunc( std::bind( mul_by, std::placeholders::_1, 0.5), 1e9);
            break;
        }
        const auto tp2 = high_resolution_clock::now();

        const auto d = duration_cast<milliseconds>(tp2 - tp1);  
        std::cout << d.count() << std::endl;
        std::cout << result<< std::endl;
    }
    return 0;
}

Pour ceux qui sont intéressés, voici l'adaptateur que le compilateur a construit pour que 'mul_by' ressemble à un float (float) - il est 'appelé' lorsque la fonction créée en tant que bind (mul_by, _1,0.5) est appelée:

movq    (%rdi), %rax                ; get the std::func data
movsd   8(%rax), %xmm1              ; get the bound value (0.5)
movq    (%rax), %rdx                ; get the function to call (mul_by)
cvtpd2ps    %xmm1, %xmm1        ; convert 0.5 to 0.5f
jmp *%rdx                       ; jump to the func

(donc ça aurait pu être un peu plus rapide si j'avais écrit 0.5f dans la liaison ...) Notez que le paramètre 'x' arrive dans% xmm0 et y reste juste.

Voici le code dans la zone où la fonction est construite, avant d'appeler test_stdfunc - exécutez via c ++ filt:

movl    $16, %edi
movq    $0, 32(%rsp)
call    operator new(unsigned long)      ; get 16 bytes for std::function
movsd   .LC0(%rip), %xmm1                ; get 0.5
leaq    16(%rsp), %rdi                   ; (1st parm to test_stdfunc) 
movq    mul_by(float, float), (%rax)     ; store &mul_by  in std::function
movl    $1000000000, %esi                ; (2nd parm to test_stdfunc)
movsd   %xmm1, 8(%rax)                   ; store 0.5 in std::function
movq    %rax, 16(%rsp)                   ; save ptr to allocated mem

   ;; the next two ops store pointers to generated code related to the std::function.
   ;; the first one points to the adaptor I showed above.

movq    std::_Function_handler<float (float), std::_Bind<float (*(std::_Placeholder<1>, double))(float, float)> >::_M_invoke(std::_Any_data const&, float), 40(%rsp)
movq    std::_Function_base::_Base_manager<std::_Bind<float (*(std::_Placeholder<1>, double))(float, float)> >::_M_manager(std::_Any_data&, std::_Any_data const&, std::_Manager_operation), 32(%rsp)


call    test_stdfunc(std::function<float (float)> const&, int)

J'ai trouvé vos résultats très intéressants et j'ai donc creusé un peu pour comprendre ce qui se passe. Tout d'abord, comme beaucoup d'autres l'ont dit, sans avoir les résultats de l'effet de calcul, l'état du programme, le compilateur optimisera simplement cela. Deuxièmement, ayant une constante 3.3 donnée comme armement au rappel, je soupçonne qu'il y aura d'autres optimisations en cours. Dans cet esprit, j'ai un peu changé votre code de référence.

template <typename F>
float calc1(F f, float i) { return -1.0f * f(i) + 666.0f; }
float calc2(std::function<float(float)> f, float i) { return -1.0f * f(i) + 666.0f; }
int main() {
    const auto tp1 = system_clock::now();
    for (int i = 0; i < 1e8; ++i) {
        t += calc2([&](float arg){ return arg * 0.5f + t; }, i);
    }
    const auto tp2 = high_resolution_clock::now();
}

Compte tenu de cette modification du code, j'ai compilé avec gcc 4.8 -O3 et j'ai obtenu un temps de 330ms pour calc1 et 2702 pour calc2. Donc, utiliser le modèle était 8 fois plus rapide, ce nombre m'a semblé suspect, une vitesse d'une puissance de 8 indique souvent que le compilateur a vectorisé quelque chose. quand j'ai regardé le code généré pour la version des modèles, il était clairement vectoreized

.L34:
cvtsi2ss        %edx, %xmm0
addl    $1, %edx
movaps  %xmm3, %xmm5
mulss   %xmm4, %xmm0
addss   %xmm1, %xmm0
subss   %xmm0, %xmm5
movaps  %xmm5, %xmm0
addss   %xmm1, %xmm0
cvtsi2sd        %edx, %xmm1
ucomisd %xmm1, %xmm2
ja      .L37
movss   %xmm0, 16(%rsp)

Là où la version std :: function ne l'était pas. Cela a du sens pour moi, car avec le modèle, le compilateur sait avec certitude que la fonction ne changera jamais tout au long de la boucle, mais avec la fonction std :: passée, elle pourrait changer et ne peut donc pas être vectorisée.

Cela m'a amené à essayer autre chose pour voir si je pouvais faire en sorte que le compilateur effectue la même optimisation sur la version std :: function. Au lieu de passer une fonction, je crée une fonction std :: function en tant que var globale, et je l'appelle.

float calc3(float i) {  return -1.0f * f2(i) + 666.0f; }
std::function<float(float)> f2 = [](float arg){ return arg * 0.5f; };

int main() {
    const auto tp1 = system_clock::now();
    for (int i = 0; i < 1e8; ++i) {
        t += calc3([&](float arg){ return arg * 0.5f + t; }, i);
    }
    const auto tp2 = high_resolution_clock::now();
}

Avec cette version, nous voyons que le compilateur a maintenant vectorisé le code de la même manière et j'obtiens les mêmes résultats de benchmark.

• modèle: 330ms
• std :: fonction: 2702ms
• global std :: function: 330ms

Donc ma conclusion est que la vitesse brute d'une fonction std :: function par rapport à un foncteur modèle est à peu près la même. Cependant, cela rend le travail de l'optimiseur beaucoup plus difficile.