1
votes

Pourquoi ce lambda C ++ récursif local est-il si terriblement lent?

Pour comprendre, j'utilise un lamda local avec un appel récursif (tail recursive). Exécuter ceci (par exemple sur http://cpp.sh/ ou https://coliru.stacked-crooked.com/ ) cela montre toujours que l'appel lamda est beaucoup plus lent que les autres solutions.

Et ma question est pourquoi cela?

lamda(5)        result 6711489344688881664 took 0.076737 ms
inner class(6)  result 6711489344688881664 took 0.000140 ms

Résultats:

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

//tail recursive lamda
long long int Factorial5(long long int n)
{ 
  std::function<long long int(long long int,long long int)> aux
     = [&aux](long long int n, long long int acc)
  { 
    return n < 1 ? acc : aux(n - 1, acc * n);
  };
  return aux(n,1);
}

//tail recursive inline class
long long int Factorial6(long long int n)
{ 
  class aux {
    public: inline static long long int tail(long long int n, long long int acc)
    { 
      return n < 1 ? acc : tail(n - 1, acc * n);
    }
  };
  return aux::tail(n,1);
}


int main()
{
    int v = 55;
    {
        auto t1 = std::chrono::high_resolution_clock::now();
        auto result = Factorial5(v);
        auto t2 = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << std::fixed << "lamda(5)\tresult " << result
                  << " took " << ms.count() << " ms\n";
    }
    {
        auto t1 = std::chrono::high_resolution_clock::now();
        auto result = Factorial6(v);
        auto t2 = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << std::fixed << "inner class(6)\tresult " << result
                  << " took " << ms.count() << " ms\n";
    }
}

performance c++ lambda

5 commentaires

std :: function utilise l'effacement de type donc il est coûteux d'utiliser un ne pas en ligne aussi bien que les foncteurs le font

Il y a un certain nombre de problèmes avec votre approche de profilage ici. Pour commencer, vous utilisez une entrée constante au moment de la compilation (que le compilateur peut potentiellement plier de façon constante, réduisant le coût à zéro), et vous ne mesurez qu'un petit intervalle de temps une seule fois. Ce n'est en aucun cas une comparaison juste (et non indicative de performances réelles dans les deux cas).

@YSC Vous ne pouvez pas faire ça. Pour créer des lambdas récursifs comme celui-ci, vous auriez besoin d'un combinateur Y.

Oh, et 55! déborde un long long int plusieurs fois .

@MaxLanghof Vous avez raison ^^

3 Réponses :

7
votes

Un lambda n'est pas une std :: function . Chaque lambda a son propre type unique. Cela ressemble à peu près à ceci:

auto aux = [](auto aux, long long int n, long long int acc) -> long long int
{ 
  return n < 1 ? acc : aux(aux, n - 1, acc * n);
};

return aux(aux, n, 1);

Donc en principe, un lambda est vraiment rapide, aussi rapide que n'importe quelle fonction ou fonction membre non virtuelle.

La lenteur vient de std :: function , qui est un wrapper d'effacement de type autour d'un lambda. Il transforme un appel de fonction en appel virtuel et alloue potentiellement dynamiquement le lambda. Ceci est coûteux et empêche l'inlining.

Pour créer un lambda récursif, vous devez utiliser des lambdas génériques C ++ 14 et envoyer le lambda à lui-même:

struct /* unnamed */ {
    auto operator()(long long int n, long long int acc) const
    { 
        return n < 1 ? acc : aux(n - 1, acc * n);
    }
} aux{};

0 commentaires

0
votes

Pour ce que ça vaut, le résultat sur mon système était:

lamda(5)        result 6711489344688881664 took 0.003501 ms
inner class(6)  result 6711489344688881664 took 0.002312 ms

Ce qui est beaucoup moins drastique, bien que toujours mesurable différence.

La raison de la différence est que la fonction ne fonctionne pratiquement pas, mais il y a très, très nombreux appels de fonction. En tant que tel, toute surcharge d'appel de fonction domine le résultat. std :: function a une surcharge, et cela apparaît dans la mesure.

Notez que le programme d'exemple déborde long long , donc les résultats n'ont pas de sens car le comportement est totalement indéfini. Le résultat correct devrait être d'environ 6,689503e + 198. En théorie, l'UB invalide également les résultats de la mesure d'exécution, mais pas nécessairement en pratique.

0 commentaires

0
votes

Le lambda est un objet d'un type sans nom, qui appelle operator () d'un objet différent (le std :: function ), qui appelle le lambda,. ..

Autrement dit, il existe une récurrence mutuelle et des indirections à travers les objets, ce qui rend cette optimisation très difficile.
Votre code est plus ou moins équivalent à ceci (j'ai raccourci le type en int):

struct Aux;

struct Fun
{
    const Aux& aux;
    Fun(const Aux& aux) : aux(aux) {}
    int work(int n, int acc) const;
};

struct Aux
{
    const Fun& fun;
    Aux(const Fun& fun) : fun(fun) {}
    int actual_work(int n, int acc) const
    {
        return n < 1 ? acc : fun.work(n-1, acc*n);
    }
};

int Fun::work(int n, int acc) const
{
    return aux.actual_work(n, acc);
}

int factorial5(int n)
{
    Fun fun = Aux(fun);
    return fun.work(n, 1);
}

Ce qui rend plus clair qu'il y a un beaucoup de choses invisibles se passent.

0 commentaires