Composition de fonctions

Vous trouverez d'autres textes sur la composition de fonctions sur ce site (en particulier Composition-fonctions-00.html, Composition-fonctions-01.html et Composition-fonctions-02.html). Ces textes sont pertinents avec C++ 03 mais le sont moins avec C++ 11. Le présent document est plus à jour que ces prédécesseurs; veuillez en tenir compte en lisant chacun d'eux.

J'ai ajouté un bonbon C++ 14 vers la fin de ce document; vous apprécierez peut-être la chose...

Lors de l'exécution d'une répétitive appliquant plusieurs opérations à chaque valeur d'une même séquence, on sous-estime souvent le coût inhérent à la répétitive elle-même. Le coût du test de poursuite (la condition testée à chaque itération) est d'abord celui du test à valider (p. ex. : vérifier si un compteur excède ou non un certain seuil; tester un prédicat), puis – et surtout! – celui du pipeline d'instructions du processeur qui risque alors de pâtir si les suppositions sur la base desquelles il a préparé les prochaines instructions à exécuter ne s'avèrent pas.

En effet, un processeur contemporain découpe les instructions à exécuter un micro-opérations qu'il exécute dans un pipeline. Ceci lui permet, une fois le pipeline plein (et tant qu'il reste plein!), d'exécuter une opération par tic d'horloge (ou presque!) même si certaines opérations, prises individuellement, nécessiteraient plus de temps pour se compléter.

Un branchement (if, while, switch, etc.) entraîne un risque, soit le risque d'avoir préparé le mauvais chemin dans le pipeline. Si tel est le cas, alors le pipeline doit être vidé, puis rempli avec les instructions qui doivent effectivement être exécutées. Le coût pour remplir le pipeline est proportionnel à la taille du pipeline; conséquemment, un processeur « plus performant » (capable de préparer plus de cycles d'instructions à l'avance) pourra perdre « plus de temps » (plus de tics d'horloge) s'il a prévu le mauvais chemin lors d'un branchement.

Conséquemment, s'il est possible de réduire les branchements dans un programme, il est aussi possible d'en améliorer la vitesse d'exécution... Du moins, en théorie. Voyons voir.

Exécution séquentielle en plusieurs blocs

Pour les besoins du test, nous utiliserons en mode Release une fonction réalisant trois opérations sur tous les éléments d'une même séquence de valeurs (un vector<double>). Ces trois opérations ont pour principal but de demander au processeur un peu de temps de calcul. L'affichage (bidon) en fin d'exécution du test a pour objectif d'empêcher le compilateur d'éliminer l'ensemble des calculs, qu'il jugerait sans doute inutiles dû au constat qu'ils n'ont en pratique aucun effet.

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <numeric>
#include <random>
using namespace std;
using namespace std::chrono;

double racine(double x) { return sqrt(x); }
double negation(double x) { return -x; }
double maganage(double x) { return x + 100.5; }

void test_plusieurs_blocs(vector<double> v)
{
   auto avant = system_clock::now();
   for (auto & val : v)
      val = racine(val);
   for (auto & val : v)
      val = negation(val);
   for (auto & val : v)
      val = maganage(val);
   auto res = accumulate(begin(v), end(v), double{});
   auto apres = system_clock::now();
   cout << "Plusieurs blocs, " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

int main()
{
   auto N = 50000000;
   vector<double> v;
   random_device rd;
   mt19937 prng{ rd() };
   uniform_int_distribution<int> distrib;
   v.reserve(N);
   generate_n(back_inserter(v), N, []() { return distrib(prng); });
   test_plusieurs_blocs(v);
}

L'affichage à l'exécution sur mon petit ordinateur personnel est :

Plusieurs blocs, -1.53971e+012 en 478 ms.

Considérant que les fonctions appelées font pour l'essentiel peu de calcul, il est possible de se baser sur ce test pour évaluer le coût de la mécanique des appels de fonctions et le coût de la mécanique derrière la répétitive en tant que telle.

Exécution en un seul bloc (manuellement)

Qu'advient-il si nous combinons manuellement les opérations exécutées initialement dans trois répétitives distinctes pour fondre les trois répétitives en une seule? La composition manuelle de fonctions ressemblerait alors à ceci.

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <numeric>
#include <random>
using namespace std;
using namespace std::chrono;

double racine(double x) { return sqrt(x); }
double negation(double x) { return -x; }
double maganage(double x) { return x + 100.5; }

void test_plusieurs_blocs(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = racine(val);
   for ( auto & val : v)
      val = negation(val);
   for ( auto & val : v)
      val = maganage(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Plusieurs blocs, " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = maganage(negation(racine(val)));
   auto res = accumulate(begin(v), end(v), double{});
   auto apres = system_clock::now();
   cout << "Un bloc (manuel), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

int main()
{
   auto N = 50000000;
   vector<double> v;
   random_device rd;
   mt19937 prng{ rd() };
   uniform_int_distribution<int> distrib;
   v.reserve(N);
   generate_n(back_inserter(v), N, [&]() { return distrib(prng); });
   test_plusieurs_blocs(v);
   test_un_bloc_manuel(v);
}

Y a-t-il un gain? Voyons voir.

Plusieurs blocs, -1.53976e+012 en 463 ms.
Un bloc (manuel), -1.53976e+012 en 317 ms.

Clairement, nous épargnons un peu moins de du temps total d'exécution. Il y a donc lieu de faire un effort ici.

Une classe représentant une composition de fonctions

Cherchons à formaliser la composition de fonctions de manière à en arriver à une solution réutilisable, en particulier dans le contexte de l'utilisation d'algorithmes standards comme std::for_each() ou, dans notre cas, std::transform(). Deux grandes options s'offrent à nous, soit :

// ...
transform(begin(v), end(v), begin(v), [](double x) {
   return maganage(negation(racine(x)));
});
// ...
template <class F, class G>
   class f_g_x_impl
   {
      F f_;
      G g_;
   public:
      f_g_x_impl(F f, G g)
         : f_(f), g_(g)
      {
      }
      template <class A>
         auto operator()(A x) -> decltype(f_(g_(x)))
         {
            return f_(g_(x));
         }
   };
template <class F, class G>
   f_g_x_impl<F, G> f_g_x(F f, G g)
   {
      return f_g_x_impl<F, G>(f,g);
   }

Ici, F et G sont les types des opérations à composer; f_ et g_ sont les opérations elles-mêmes; et A est le type du paramètre x à passer à g_; le type de retour de f_(g_(x)) est déduit par le compilateur grâce à l'opérateur statique decltype. Pour éviter d'obliger le code client à déclarer explicitement les types de F et de G (ce qui peut être laborieux), nous générons un f_g_x_impl<F,G> à l'aide de la fonction génératrice f_g_x(). Des exemples apparaîtront plus bas, mais l'exemple suivant devrait clarifier l'utilité de cette démarche à vos yeux :

Sans fonction génératriceAvec fonction génératrice
int f(int);
double g(int);
// ...
f_g_x_impl<double(*)(int),int(*)(int)> fct(g,f);
int f(int);
double g(int);
// ...
auto fct = f_g_x(g,f);

Je suppose l'argument convaincant.

Exécution composite – composition de fonctions unaires

Examinons l'impact d'utiliser notre mécanisme de composition de fonctions.

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <numeric>
#include <random>
using namespace std;
using namespace std::chrono;

double racine(double x) { return sqrt(x); }
double negation(double x) { return -x; }
double maganage(double x) { return x + 100.5; }

template <class F, class G>
   class f_g_x_impl
   {
      F f_;
      G g_;
   public:
      f_g_x_impl(F f, G g)
         : f_(f), g_(g)
      {
      }
      template <class A>
         auto operator()(A x) -> decltype(f_(g_(x)))
         {
            return f_(g_(x));
         }
   };
template <class F, class G>
   f_g_x_impl<F, G> f_g_x(F f, G g)
   {
      return f_g_x_impl<F, G>(f,g);
   }

void test_plusieurs_blocs(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = racine(val);
   for ( auto & val : v)
      val = negation(val);
   for ( auto & val : v)
      val = maganage(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Plusieurs blocs, " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = maganage(negation(racine(val)));
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (manuel), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_fonctions(vector<double> v)
{
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = fct(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (fonctions), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

int main()
{
   auto N = 50000000;
   vector<double> v;
   random_device rd;
   mt19937 prng{ rd() };
   uniform_int_distribution<int> distrib;
   v.reserve(N);
   generate_n(back_inserter(v), N, [&]() { return distrib(prng); });
   test_plusieurs_blocs(v);
   test_un_bloc_manuel(v);
   test_un_bloc_fonctions(v);
}

Les résultats à l'exécution sont les suivants :

Plusieurs blocs, -1.53971e+012 en 484 ms.
Un bloc (manuel), -1.53971e+012 en 329 ms.
Un bloc (fonctions), -1.53971e+012 en 850 ms.

Manifestement, nous avons perdu au change. Que se passe-t-il ici?

En fait, pour notre classe f_g_x_impl, les fonctions combinées sont en fait des adresses de fonctions. Pour le compilateur, le code est généré en termes de la signature de la fonction, et il y a au moins trois fonctions de signature double(double) dans le programme (les nôtres!), et probablement bien plus que ça en pratique.

Ne sachant pas de quelle fonction exactement on parle à chaque accès aux attributs f_ et g_ d'un f_g_x_impl, le compilateur doit réaliser l'appel entier à la fonction (placer les paramètres sur la pile, réaliser un saut à l'adresse de la fonction, récupérer les paramètres sur la pile, réaliser le traitement, retourner le résultat calculé au point d'appel) car il se trouve incapable de réaliser du inlining (remplacer le code appelant par le code appelé).

C'est le coût des appels de fonctions qui transparaît ici. Ce coût est important car les fonctions ne font que peu de traitement; si le code exécuté par la fonction appelée était en soi coûteux, alors le coût de l'appel lui-même serait négligeable.

Exécution composite – composition de fonctions unaires et std::transform()

La situation s'améliore-t-elle si nous remplaçons la répétitive manuelle par un appel à std::transform()? Voyons voir.

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <numeric>
#include <random>
using namespace std;
using namespace std::chrono;

double racine(double x) { return sqrt(x); }
double negation(double x) { return -x; }
double maganage(double x) { return x + 100.5; }

template <class F, class G>
   class f_g_x_impl
   {
      F f_;
      G g_;
   public:
      f_g_x_impl(F f, G g)
         : f_(f), g_(g)
      {
      }
      template <class A>
         auto operator()(A x) -> decltype(f_(g_(x)))
         {
            return f_(g_(x));
         }
   };
template <class F, class G>
   f_g_x_impl<F, G> f_g_x(F f, G g)
   {
      return f_g_x_impl<F, G>(f,g);
   }

void test_plusieurs_blocs(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = racine(val);
   for ( auto & val : v)
      val = negation(val);
   for ( auto & val : v)
      val = maganage(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Plusieurs blocs, " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = maganage(negation(racine(val)));
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (manuel), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_fonctions(vector<double> v)
{
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = fct(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (fonctions), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_fonctions_transform(vector<double> v)
{
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto avant = system_clock::now();
   transform(begin(v), end(v), begin(v), fct);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (fonctions, transform), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

int main()
{
   auto N = 50000000;
   vector<double> v;
   random_device rd;
   mt19937 prng{ rd() };
   uniform_int_distribution<int> distrib;
   v.reserve(N);
   generate_n(back_inserter(v), N, [&]() { return distrib(prng); });
   test_plusieurs_blocs(v);
   test_un_bloc_manuel(v);
   test_un_bloc_fonctions(v);
   test_un_bloc_fonctions_transform(v);
}

Nous obtenons maintenant à l'exécution ce qui suit.

Plusieurs blocs, -1.53964e+012 en 482 ms.
Un bloc (manuel), -1.53964e+012 en 332 ms.
Un bloc (fonctions), -1.53964e+012 en 838 ms.
Un bloc (fonctions, transform), -1.53964e+012 en 706 ms.

La situation est pire encore, quoique très légèrement. Manifestement, il y a un problème.

Exécution composite – composition de foncteurs unaires

La clé du succès ici est de remplacer les fonctions par des foncteurs. En effet, contrairement aux fonctions, les foncteurs sont des objets, dont le type est clair dès la compilation. Ceci permet au compilateur de réaliser le inlining dans chaque cas... même si le foncteur appelle en pratique les fonctions originales!

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <numeric>
#include <random>
using namespace std;
using namespace std::chrono;

double racine(double x) { return sqrt(x); }
double negation(double x) { return -x; }
double maganage(double x) { return x + 100.5; }

struct racine_
{
   double operator()(double x) const { return racine(x); }
};
struct negation_
{
   double operator()(double x) const { return negation(x); }
};
struct maganage_
{
   double operator()(double x) const { return maganage(x); }
};

template <class F, class G>
   class f_g_x_impl
   {
      F f_;
      G g_;
   public:
      f_g_x_impl(F f, G g)
         : f_(f), g_(g)
      {
      }
      template <class A>
         auto operator()(A x) -> decltype(f_(g_(x)))
         {
            return f_(g_(x));
         }
   };
template <class F, class G>
   f_g_x_impl<F, G> f_g_x(F f, G g)
   {
      return f_g_x_impl<F, G>(f,g);
   }

void test_plusieurs_blocs(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = racine(val);
   for ( auto & val : v)
      val = negation(val);
   for ( auto & val : v)
      val = maganage(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Plusieurs blocs, " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = maganage(negation(racine(val)));
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (manuel), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_fonctions(vector<double> v)
{
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = fct(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (fonctions), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_fonctions_transform(vector<double> v)
{
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto avant = system_clock::now();
   transform(begin(v), end(v), begin(v), fct);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (fonctions, transform), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_foncteurs(vector<double> v)
{
   auto fct = f_g_x(maganage_{}, f_g_x(negation_{}, racine_{}));
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = fct(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (foncteurs), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

int main()
{
   auto N = 50000000;
   vector<double> v;
   random_device rd;
   mt19937 prng{ rd() };
   uniform_int_distribution<int> distrib;
   v.reserve(N);
   generate_n(back_inserter(v), N, [&]() { return distrib(prng); });
   test_plusieurs_blocs(v);
   test_un_bloc_manuel(v);
   test_un_bloc_fonctions(v);
   test_un_bloc_fonctions_transform(v);
   test_un_bloc_foncteurs(v);
}

En pratique, nous obtenons maintenant ce qui suit.

Plusieurs blocs, -1.53979e+012 en 521 ms.
Un bloc (manuel), -1.53979e+012 en 410 ms.
Un bloc (fonctions), -1.53979e+012 en 843 ms.
Un bloc (fonctions, transform), -1.53979e+012 en 686 ms.
Un bloc (foncteurs), -1.53979e+012 en 391 ms.

Une amélioration significative; en fait, notre composition formelle de fonctions est maintenant un peu meilleure que la composition manuelle!

Exécution composite – composition de foncteurs unaires et std::transform()

Est-ce que std::transform() ira maintenant plus rapidement que ne le fait une répétitive manuelle? Faisons le test.

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <numeric>
#include <random>
using namespace std;
using namespace std::chrono;

double racine(double x) { return sqrt(x); }
double negation(double x) { return -x; }
double maganage(double x) { return x + 100.5; }

struct racine_
{
   double operator()(double x) const { return racine(x); }
};
struct negation_
{
   double operator()(double x) const { return negation(x); }
};
struct maganage_
{
   double operator()(double x) const { return maganage(x); }
};

template <class F, class G>
   class f_g_x_impl
   {
      F f_;
      G g_;
   public:
      f_g_x_impl(F f, G g)
         : f_(f), g_(g)
      {
      }
      template <class A>
         auto operator()(A x) -> decltype(f_(g_(x)))
         {
            return f_(g_(x));
         }
   };
template <class F, class G>
   f_g_x_impl<F, G> f_g_x(F f, G g)
   {
      return f_g_x_impl<F, G>(f,g);
   }

void test_plusieurs_blocs(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = racine(val);
   for ( auto & val : v)
      val = negation(val);
   for ( auto & val : v)
      val = maganage(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Plusieurs blocs, " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v)
{
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = maganage(negation(racine(val)));
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (manuel), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_fonctions(vector<double> v)
{
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = fct(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (fonctions), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_fonctions_transform(vector<double> v)
{
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto avant = system_clock::now();
   transform(begin(v), end(v), begin(v), fct);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (fonctions, transform), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_foncteurs(vector<double> v)
{
   auto fct = f_g_x(maganage_{}, f_g_x(negation_{}, racine_{}));
   auto avant = system_clock::now();
   for ( auto & val : v)
      val = fct(val);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (foncteurs), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

void test_un_bloc_foncteurs_transform(vector<double> v)
{
   auto fct = f_g_x(maganage_{}, f_g_x(negation_{}, racine_{}));
   auto avant = system_clock::now();
   transform(begin(v), end(v), begin(v), fct);
   auto res = accumulate(begin(v), end(v), 0.0);
   auto apres = system_clock::now();
   cout << "Un bloc (foncteurs, transform), " << res << " en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
}

int main()
{
   auto N = 50000000;
   vector<double> v;
   random_device rd;
   mt19937 prng{ rd() };
   uniform_int_distribution<int> distrib;
   v.reserve(N);
   generate_n(back_inserter(v), N, [&]() { return distrib(prng); });
   test_plusieurs_blocs(v);
   test_un_bloc_manuel(v);
   test_un_bloc_fonctions(v);
   test_un_bloc_fonctions_transform(v);
   test_un_bloc_foncteurs(v);
   test_un_bloc_foncteurs_transform(v);
}

Le résultat va comme suit.

Plusieurs blocs, -1.53956e+012 en 511 ms.
Un bloc (manuel), -1.53956e+012 en 435 ms.
Un bloc (fonctions), -1.53956e+012 en 865 ms.
Un bloc (fonctions, transform), -1.53956e+012 en 692 ms.
Un bloc (foncteurs), -1.53956e+012 en 388 ms.
Un bloc (foncteurs, transform), -1.53956e+012 en 334 ms.

La combinaison de l'algorithme std::transform() et d'un composé de foncteurs nous donne de meilleurs résultats qu'une séquence de répétitives, incluant les répétitives manuelles. En pratique, la clarté gagnée par le recours à transform() serait considérée comme un gain en soi, et il est probable que la qualité des gains dépende au moins en partie du compilateur et de l'implémentation de STL qui l'accompagne. Privilégiez les algorithmes standards dans la mesure du possible.

Pour un autre exemple, examinez ce qui suit (j'y utilise la version de f_g_x() décrite dans la section Bonbon en terminant – l'impact de C++ 14, plus bas, par souci de concision) :

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <chrono>
#include <cmath>
#include <list>
using namespace std;
using namespace std::chrono;

template <class F, class G>
   auto f_g_x(F f, G g)
   {
      return [f, g](auto x) { return f(g(x)); };
   }

int main()
{
   enum { N = 10'000'000 };
   clog.rdbuf(nullptr);

   {
      vector<double> v(N);
      iota(begin(v), end(v), 1.0);

      auto avant = high_resolution_clock::now();
      transform(begin(v), end(v), begin(v), [](double x) { return pow(x, 2); });
      transform(begin(v), end(v), begin(v), [](double x) { return x + 1.0; });
      transform(begin(v), end(v), begin(v), [](double x) { return sqrt(x); });
      auto apres = high_resolution_clock::now();

      cout << "vector<double> -- " << N << " elements, trois repetitives, "
           << duration_cast<microseconds>(apres - avant).count() << " us" << endl;
      clog << accumulate(begin(v), end(v), 0.0) << endl;
   }

   {
      vector<double> v(N);
      iota(begin(v), end(v), 1.0);

      auto avant = high_resolution_clock::now();
      transform(begin(v), end(v), begin(v), f_g_x(
         [](double x) { return sqrt(x); },
         f_g_x([](double x) { return x + 1.0; }, [](double x) { return pow(x, 2); })
      ));
      auto apres = high_resolution_clock::now();

      cout << "vector<double> -- " << N << " elements, une repetitive, "
           << duration_cast<microseconds>(apres - avant).count() << " us" << endl;
      clog << accumulate(begin(v), end(v), 0.0) << endl;
   }

   {
      list<double> v;
      for (int i = 0; i < N; ++i)
         v.push_back(static_cast<double>(i));

      auto avant = high_resolution_clock::now();
      transform(begin(v), end(v), begin(v), [](double x) { return pow(x, 2); });
      transform(begin(v), end(v), begin(v), [](double x) { return x + 1.0; });
      transform(begin(v), end(v), begin(v), [](double x) { return sqrt(x); });
      auto apres = high_resolution_clock::now();

      cout << "list<double>  --  " << N << " elements, trois repetitives, "
           << duration_cast<microseconds>(apres - avant).count() << " us" << endl;
      clog << accumulate(begin(v), end(v), 0.0) << endl;
   }

   {
      list<double> v;
      for (int i = 0; i < N; ++i)
         v.push_back(static_cast<double>(i));

      auto avant = high_resolution_clock::now();
      transform(begin(v), end(v), begin(v), f_g_x(
            [](double x) { return sqrt(x); },
            f_g_x([](double x) { return x + 1.0; }, [](double x) { return pow(x, 2); }
         )
      ));
      auto apres = high_resolution_clock::now();

      cout << "list<double>  --  " << N << " elements, une repetitive, "
           << duration_cast<microseconds>(apres - avant).count() << " us" << endl;
      clog << accumulate(begin(v), end(v), 0.0) << endl;
   }
}

Si vous testez ce programme (en mode Release, évidemment), vous y constaterez probablement un impact, sur le plan du temps d'exécution, du passage de trois parcours à un seul parcours :

Les valeurs peuvent varier d'un test à l'autre, bien sûr, et sont élevées du fait que les calculs sont peu coûteux lorsque pris individuellement (ce qui fait ressortir le coût du parcours du conteneur). Ce qu'on peut en comprendre est que l'impact de la Cache est amorti par la réduction des parcours, et que le parcours lui-même n'est pas gratuit.

Conclusion

Le poids des tests de la répétitive est visible et mesurable, en particulier lorsque le traitement fait dans la répétitive est bref. Il est possible d'atténuer ce poids en combinant plusieurs opérations par itération, et il est possible de formaliser cette composition de fonctions par un type. Les gains obtenus sont appréciables. Pour en profiter pleinement, cependant, mieux vaut être conscient du coût inhérent à un appel indirect de fonction et privilégier le recours aux foncteurs, qui offrent au compilateur de meilleurs opportunités d'optimisation.

Bonbon en terminant – l'impact de C++ 14

Plusieurs prétendent que C++ 14 n'est qu'une mise à jour pour épargner du travail à celles et ceux qui appuient sur les touches du clavier. C'est un peu vrai... mais pas tout à fait.

En fait, avec la déduction automatique des types des paramètres, la déduction automatique des types de retour des fonctions, les templates variadiques de C++ 11, les λ, la programmation n'est vraiment plus la même... et ce, sans la moindre perte d'efficacité à l'exécution des programmes.

Comparez par vous-mêmes.

Avec C++ 11 Avec C++ 14
template <class F, class G>
   class f_g_x_impl
   {
      F f_;
      G g_;
   public:
      f_g_x_impl(F f, G g)
         : f_(f), g_(g)
      {
      }
      template <class A>
         auto operator()(A x) -> decltype(f_(g_(x)))
         {
            return f_(g_(x));
         }
   };
template <class F, class G>
   f_g_x_impl<F, G> f_g_x(F f, G g)
   {
      return f_g_x_impl<F, G>(f,g);
   }
template <class F, class G>
auto f_g_x(F f, G g)
{
   return [f, g](auto... x) { return f(g(x...)); };
}
template <class F, class G>
   class f_and_g_x_impl
   {
      F f_;
      G g_;
   public:
      f_and_g_x_impl(F f, G g)
         : f_(f), g_(g)
      {
      }
      template <class A>
         auto operator()(A x) -> decltype(f_(x) && g_(x))
         {
            return f_(x) && g_(x);
         }
   };
template <class F, class G>
   f_and_g_x_impl<F, G> f_and_g_x(F f, G g)
   {
      return f_and_g_x_impl<F, G>(f,g);
   }
template <class F, class G>
auto f_and_g(F f, G g)
{
   return [f, g](auto... args) {
      return f(args...) && g(args...);
   };
}
template <class F, class G>
   class f_or_g_x_impl
   {
      F f_;
      G g_;
   public:
      f_or_g_x_impl(F f, G g)
         : f_(f), g_(g)
      {
      }
      template <class A>
         auto operator()(A x) -> decltype(f_(x) || (g_(x))
         {
            return f_(x) || g_(x);
         }
   };
template <class F, class G>
   f_or_g_x_impl<F, G> f_or_g_x(F f, G g)
   {
      return f_or_g_x_impl<F, G>(f,g);
   }
template <class F, class G>
auto f_or_g(F f, G g)
{
   return [f, g](auto... args) {
      return f(args...) || g(args...);
   };
}

Pensez-y...


Valid XHTML 1.0 Transitional

CSS Valide !