Composition de fonctions

Vous voudrez peut-être vous familiariser avec ceci avant de lire le présent article : ../AuSecours/Mesurer-le-temps.html

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... Et, pendant qu'on y est, pourquoi pas une composition variadique (voir ceci)?

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

template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

void test_plusieurs_blocs(vector<double> v) {
   auto [r, dt] = test [&v] {
      for (auto & val : v)
         val = racine(val);
      for (auto & val : v)
         val = negation(val);
      for (auto & val : v)
         val = maganage(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Plusieurs blocs, " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

int main() {
   auto N = 50'000'000;
   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; }

template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

void test_plusieurs_blocs(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = racine(val);
      for (auto & val : v)
         val = negation(val);
      for (auto & val : v)
         val = maganage(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Plusieurs blocs, " << re << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = maganage(negation(racine(val)));
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (manuel), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

int main() {
   auto N = 50'000'000;
   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 };
   }

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

... et ce serait pire si l'une ou l'autre des fonctions était une λ. 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 };
   }

template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

void test_plusieurs_blocs(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = racine(val);
      for (auto & val : v)
         val = negation(val);
      for (auto & val : v)
         val = maganage(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Plusieurs blocs, " << re << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = maganage(negation(racine(val)));
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (manuel), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_fonctions(vector<double> v) {
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto [r, dt] = test([&v, fct] {
      for (auto & val : v)
         val = fct(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (fonctions), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

int main() {
   auto N = 50'000'000;
   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 };
   }

template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

void test_plusieurs_blocs(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = racine(val);
      for (auto & val : v)
         val = negation(val);
      for (auto & val : v)
         val = maganage(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Plusieurs blocs, " << re << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = maganage(negation(racine(val)));
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (manuel), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_fonctions(vector<double> v) {
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto [r, dt] = test([&v, fct] {
      for (auto & val : v)
         val = fct(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (fonctions), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_fonctions_transform(vector<double> v) {
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto [r, dt] = test([&v, fct] {
      transform(begin(v), end(v), begin(v), fct);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (fonctions, transform), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

int main() {
   auto N = 50'000'000;
   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 demeure déplaisante. 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 };
   }

template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

void test_plusieurs_blocs(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = racine(val);
      for (auto & val : v)
         val = negation(val);
      for (auto & val : v)
         val = maganage(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Plusieurs blocs, " << re << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = maganage(negation(racine(val)));
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (manuel), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_fonctions(vector<double> v) {
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto [r, dt] = test([&v, fct] {
      for (auto & val : v)
         val = fct(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (fonctions), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_fonctions_transform(vector<double> v) {
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto [r, dt] = test([&v, fct] {
      transform(begin(v), end(v), begin(v), fct);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (fonctions, transform), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_foncteurs(vector<double> v) {
   auto fct = f_g_x(maganage_{}, f_g_x(negation_{}, racine_{}));
   auto [r, dt] = test([&v, fct] {
      for ( auto & val : v)
         val = fct(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (foncteurs), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

int main() {
   auto N = 50'000'000;
   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 };
   }

template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

void test_plusieurs_blocs(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = racine(val);
      for (auto & val : v)
         val = negation(val);
      for (auto & val : v)
         val = maganage(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Plusieurs blocs, " << re << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_manuel(vector<double> v) {
   auto [r, dt] = test([&v] {
      for (auto & val : v)
         val = maganage(negation(racine(val)));
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (manuel), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_fonctions(vector<double> v) {
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto [r, dt] = test([&v, fct] {
      for (auto & val : v)
         val = fct(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (fonctions), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_fonctions_transform(vector<double> v) {
   auto fct = f_g_x(maganage, f_g_x(negation, racine));
   auto [r, dt] = test([&v, fct] {
      transform(begin(v), end(v), begin(v), fct);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (fonctions, transform), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_foncteurs(vector<double> v) {
   auto fct = f_g_x(maganage_{}, f_g_x(negation_{}, racine_{}));
   auto [r, dt] = test([&v, fct] {
      for ( auto & val : v)
         val = fct(val);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (foncteurs), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

void test_un_bloc_foncteurs_transform(vector<double> v) {
   auto fct = f_g_x(maganage_{}, f_g_x(negation_{}, racine_{}));
   auto [r, dt] = test([&v, fct] {
      transform(begin(v), end(v), begin(v), fct);
      return accumulate(begin(v), end(v), double{});
   });
   cout << "Un bloc (foncteurs, transform), " << r << " en " << duration_cast<milliseconds>(dt).count() << " ms." << endl;
}

int main() {
   auto N = 50'000'000;
   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 ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

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

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

   vector<double> v(N);
   iota(begin(v), end(v), 1.0);
   auto [r0, dt0] = test([v]() mutable {
      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); });
      return v.back();
   });
   cout << "vector<double> -- " << N << " elements, trois repetitives, "
        << duration_cast<microseconds>(dt).count() << " us" << endl;

   auto [r1, dt1] = test([v]() mutable {
      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); })
      ));
      return v.back();
   });
   cout << "vector<double> -- " << N << " elements, une repetitive, "
        << duration_cast<microseconds>(dt1).count() << " us" << endl;

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

   auto [r2, dt2] = test([lst]() mutable {
      transform(begin(lst), end(lst), begin(lst), [](double x) { return pow(x, 2); });
      transform(begin(lst), end(lst), begin(lst), [](double x) { return x + 1.0; });
      transform(begin(lst), end(lst), begin(lst), [](double x) { return sqrt(x); });
      return lst.back();
   });

   cout << "list<double>  --  " << N << " elements, trois repetitives, "
        << duration_cast<microseconds>(dt2).count() << " us" << endl;

   auto [r3, dt3] = test([lst]() mutable {
      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); })
      ));
      return lst.back();
   });
   cout << "list<double>  --  " << N << " elements, une repetitive, "
        << duration_cast<microseconds>(dt3).count() << " us" << 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 };
   }
 
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,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,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...

Composition variadique

Et que faire si nous souhaitons composer un nombre variadique de fonctions, sous la forme ? En fait, c'est à peine plus compliqué :

#include <utility>
template <class F, class ... Fs>
   auto compose(F f, Fs ... fs) {
      return [=](auto && x) {
         auto g = compose(fs...);
         return f(g(std::forward<decltype(x)>(x)));
      };
   }
template <class F>
   auto compose(F f) {
      return [=](auto && x) {
          return f(std::forward<decltype(x)>(x));
      };
   }

Valid XHTML 1.0 Transitional

CSS Valide !