Futures « maison »

Les futures sont une métaphore de programmation par promesse, métaphore que l'on retrouve dans plusieurs langages de programmation (dont C++ 11). L'idée est de transformer une fonction synchrone (au sens faible du terme) en une fonction dont le résultat sera calculé de manière asynchrone et sera éventuellement rendu disponible au point d'appel – une promesse d'un éventuel résultat.

Bien qu'il existe des futures « standards », les implémenter soi-même est un exercice amusant et instructif. Le code résultant est à la fois élégant et efficace.

J'ai écrit ce qui suit avant d'avoir accès à une implémentation opérationnelle de la partie multiprogrammation du standard C++ 11 – j'y ai maintenant accès et c'est absolument adorable.

Les futures proposées dans le présent article sont en fait une mixture des std::future et des std::async de ce standard; si vous utilisez ce qui suit, mieux vaut le savoir. En pratique, privilégiez bien sûr les outils standards, qui sont de qualité industrielle.

Fichier Principal.cpp

À titre d'exemple, voici un programme de test utilisant les futures « maison » que nous développerons ici.

Nous utiliserons deux fonctions de test, soit sequentiel() et parallele().

Chacune prendra en paramètre deux opérations unaires, f et g, de même qu'un paramètre arg à leur passer, puis effectuera f(arg)+g(arg). L'une exécutera donc f(arg) et g(arg) en séquence, alors que l'autre, grâce aux futures, les fera en parallèle.

 
#include "future.h"
#include <iostream>
#include <chrono>
// ... using ...
template <class F, class G, class A>
   auto sequentiel(F f, G g, A arg) -> decltype(f(arg) + g(arg))
      { return f(arg) + g(arg); }
template <class F, class G, class A>
   auto parallele(F f, G g, A arg) -> decltype(f(arg) + g(arg))
   {
      auto f_ = future(f, arg);
      auto g_ = future(g, arg);
      //using std::cout;
      //using std::flush;
      //while (!f_)
      //   cout << '.' << flush;
      //while (!g_)
      //   cout << '.' << flush;
      return f_() + g_();
   }

Remarquez la notation des futures utilisées ici :

Le programme de test compare les temps d'exécution de sequentiel(f,g,0) et de parallele(f,g,0) pour un même couple de fonctions f() et g().

Les temps d'exécution sont mesurés au CLOCKS_PER_SEC près, ce qui donne un résultat à la milliseconde près sous Microsoft Windows. Vous constaterez toutefois un peu plus bas que la différence entre les deux calculs est suffisamment significative pour que cette démonstration soit convaincante.

Si vous avez une compilateur suffisamment à jour, préférez les outils de <chrono> pour évaluer le passage du temps.

 
int f(int);
int g(int);
int main()
{
   {
      auto avant = system_clock::now();
      auto resultat = sequentiel(f, g, 0);
      auto apres = system_clock::now();
      cout << "sequentielle: f() + g() == " << resultat << ", temps "
           << duration_cast<milliseconds>(apres-avant).count()
           << " ms." << endl;
   }
   {
      auto avant = system_clock::now();
      auto resultat = parallele(f, g, 0);
      auto apres = system_clock::now();
      cout << "parallele: f() + g() == " << resultat << ", temps "
           << duration_cast<milliseconds>(apres-avant).count()
           << " ms." << endl;
   }
}

Pour les fins de la discussion, les fonctions f() et g() seront archi simples, mais chacune prendra environ une minute pour s'exécuter (et se suspendra pendant ce temps). Vous comprendrez sans peine que de meilleurs tests pourraient être conçus, les fonctions réalisant de véritables calculs, mais bon, c'est un exemple.

 
int f(int)
{
   this_thread::sleep(seconds(1));
   return 2;
}
int g(int)
{
   this_thread::sleep(seconds(1));
   return 3;
}

Le résultat de son exécution sur mon petit ordinateur portatif va comme suit (à une milliseconde près, d'une exécution à l'autre, dû à l'imprécision des outils de mesure dont je me sers dans le programme ci-dessus) :

sequentielle: f() + g() == 5, temps 2000 ms.
parallele: f() + g() == 5, temps 1000 ms.
Appuyez sur une touche pour continuer...

Du simple au double, donc, pour une écriture aussi simple dans le code client, c'est à ne pas à négliger. Voici comment il est possible d'y arriver.

Les enjeux

Examinons brièvement les enjeux conceptuels et techniques dans la mise en place d'une stratégie telle que celle proposée ci-dessus pour le code client.

La fonction génératrice future() doit accepter n'importe quelle opération unaire (fonction, foncteur, λ) et n'importe quel paramètre susceptible de lui être passé.

Pour une paire f,a de paramètres respectivement de type F et A, future(f,a) doit retourner un objet ayant au minimum une méthode operator bool() const (pour être testable comme un booléen) et une méthode nullaire operator() retournant un decltype(f(a)).

L'objet retourné par future(f,a) doit « encapsuler » un thread déjà démarré et réalisant le calcul f(a) en arrière-plan. Cet objet doit aussi être en contact avec le thread de manière à ce qu'il soit possible, à travers lui, de tester de manière non-bloquante la complétion de ce thread et d'en récupérer le résultat.

Évidemment, il est hors de question de laisser fuir des ressources à travers cette mécanique.

 
//
// même exemple, simplifié
//
template <class F, class G, class A>
   auto parallele(F f, G g, A arg) -> decltype(f(arg) + g(arg))
   {
      auto f_ = future(f, arg);
      auto g_ = future(g, arg);
      return f_() + g_();
   }

Pour simplifier le portrait, je limiterai la démonstration à des futures sur des opérations unaires et dont le type est non-void. Ce n'est pas à strictement parler nécessaire : il est possible d'accomoder le type void en mettant en place une spécialisation déterminant un mécanisme différent de gestion de f(a) pour une future(f,a) donnée, et supporter des fonctions d'arité est simple mais fastidieux.

Déduire la signature d'une opération unaire – fichier unary_function_traits.h

Pour qu'une future(f,a) retourne ce que f(a) retournerait, il faudra (a) entreposer f, (b) entreposer a, et (c) faire en sorte que l'opérateur () de l'objet retourné par future(f,a) soit du type decltype(f(a)).

Plusieurs techniques distinctes permettent d'y arriver; ici, j'utiliserai entre autres des traits. Plusieurs approches sont possibles (certaines sont détaillées ailleurs sur ce site), mais j'y suis allé ici avec ce que je nommerais une « approche moderne ».

Par « approche moderne », j'entends une approche où chaque trait décrit une et une seule chose (contrairement à des types comme numeric_limits, par exemple).

Ainsi, là où j'aurais pu écrire le type unary_function_traits<T> exposant à la fois les types internes et public result_type et argument_type, par exemple, j'y suis allé avec deux types distincts, soit argument_of<T>::type et result_of<T>::type décrivant respectivement, pour une opération unaire T, le type du paramètre passé à cette opération et le type de ce qu'elle retourne.

Ces deux traits sont applicables à la fois à des fonctions globales et à des foncteurs correctement documentés. Je ne peux promettre qu'ils soient applicables à des λ.

 
#ifndef UNARY_FUNCTION_TRAITS_H
#define UNARY_FUNCTION_TRAITS_H
template <class F>
   struct argument_of
   {
      using type = typename F::argument_type;
   };
template <class R, class A>
   struct argument_of<R (*)(A)>
   {
      using type = A;
   };
template <class F>
   struct result_of
   {
      using type = typename F::result_type;
   };
template <class R, class A>
   struct result_of<R (*)(A)>
   {
      using type = R;
   };
#endif

Entreposer une valeur quelconque – fichier peu_importe.h

Le problème d'entreposer la valeur retournée par f(a) dans future(f,a) est un problème qui peut être complexe. Dans le cas du code qui suit, j'utiliserai un peu_importe, décrit dans cet article et auquel je vous invite à vous référer. Je ne répéterai pas le code de l'article, celui utilisé ici étant identique en tout point.

Le problème avec un type comme peu_importe n'est pas tant d'entreposer un objet de n'importe quel type dans un même contenant mais bien de le récupérer à la fois efficacement et de manière sécuritaire par la suite. Nous le verrons plus bas, il sera possible pour nous d'y arriver de manière très efficace.

Les futures elles-mêmes

Il ne nous reste qu'à examiner comment fonctionne la fonction génératrice future() elle-même et comment s'expriment les divers types impliqués dans la mécanique que ces types décrivent.

Vous remarquerez dans cete démarche un soin particulier porté à la question de la portabilité du code client. En effet, future.h sera pleinement portable à toutes les plateformes, l'idiome pImpl étant appliqué pour reléguer à future.cpp tous les détails spécifiques à une plateforme donnée. Ceci demande un effort supplémentaire au moment du design de la classe, mais rapporte très rapidement en termes de simplicité d'entretien du code.

J'ai aussi porté une attention spéciale à la réduction de la quantité de code générique à produire pour un type donné, factorisant la partie réutilisable générale dans des types distincts. Ceci réduit la consommation de ressources (quantité de code à générer ou à dupliquer) dans un programme donné utilisant des futures.

Fichier future.h

Commençons, comme il se doit, par l'interface de nos futures.

J'ai choisi d'utiliser des exceptions pour décrire les cas d'erreurs possibles dans la mécanique des futures.

Considérant notre souhait de faire en sorte que cette mécanique soit fluide et ressemble, à l'usage, à celle d'un appel de fonction nullaire synchrone (sens faible), traiter les éventuels cas problèmes comme des situations exceptionnelles semble la chose raisonnable à faire.

 
#ifndef FUTURE_H
#define FUTURE_H
#include "peu_importe.h"
#include "unary_function_traits.h"
#include <memory>
class NotStarted {};
class CouldNotStart {};

Le code commun à toutes les futures, peu importe la fonction unaire représentée, a été placé dans la classe base_future. Cette classe servira de parent (privé, car non-polymorphique) pour les véritables implémentations de futures.

On trouvera dans cette classe :

  • une représentation d'une unité de travail (type work_unit). C'est dans les enfants de cette classe abstraite que seront implémentés les véritables appels à f(a) pour une future(f,a) donnée. La méthode execute() d'un work_unit sera appelée dans un thread distinct de celui du code client, et le résultat de l'exécution sera déposé dans result_;
  • une représentation d'une unité d'exécution (d'un thread), décrite par la classe future_rep;
  • une sémantique de mouvement pour la construction (je n'ai pas implémenté l'affectation de mouvement, mais c'est de la simple négligence de ma part);
  • un service start() qui démarrera le thread associé à la future;
  • un service ready() non bloquant qui sera vrai seulement si le traitement associé à la future est terminé; et
  • un service wait() bloquant qui suspendra l'exécution du thread appelant jusqu'à la complétion du thread dans lequel la future réalise son travail.

On aurait pu ajouter un service wait() prenant en paramètre un délai maximal d'attente et retournant un booléen, mais j'ai décidé d'y aller pour la simplicité ici. 

class base_future
{
public:
   struct work_unit
   {
      peu_importe result_;
      virtual void execute() = 0;
      virtual ~work_unit() = default;
   };
protected:
   class future_rep;
   std::unique_ptr<future_rep> rep_;
   std::unique_ptr<work_unit> wu_;
   base_future(work_unit*);
   base_future(base_future&&);
   ~base_future() noexcept;
   void start();
public:
   bool ready() const;
   void wait() const;
};

Les détails typés d'une future sont placés dans les divers enfants privés de base_future que j'ai nommés future_impl<F>, donc qui sont générés en fonction des divers types F d'opérations unaires impliquées.

Dans chaque future_impl<F>, on trouve une classe actual_work interne, dérivant de work_unit et générée elle aussi en fonction du type F.

Une instance d'actual_work<F> implémente une méthode execute() réalisant l'appel à f(a) et capturant le résultat dans un peu_importe.

Le reste du code est presque évident : l'opérateur () bloque jusqu'à complétion et récupère le résultat du calcul (profitant de sa connaissance du type retourné par f(a) pour convertir le peu_importe de manière optimale), l'opérateur de conversion en booléen délègue son travail à la méthode ready() du parent base_future, et les constructeurs font leur travail de manière banale.

 
template <class F>
   class future_impl
      : private base_future
   {
   public:
      using result_type = typename result_of<F>::type;
      using argument_type = typename argument_of<F>::type;
   private:
      class actual_work
         : public work_unit
      {
         F fct_;
         argument_type arg_;
      public:
         actual_work(F fct, argument_type arg)
            : fct_{fct}, arg_{arg}
         {
         }
         void execute()
            { result_ = fct_(arg_); }
      };
   public:
      using base_future::start;
      future_impl(F fct, argument_type arg)
         : base_future{new actual_work(fct, arg)}
      {
      }
      future_impl(future_impl &&autre)
         : base_future{std::move(autre)}
      {
      }
      result_type operator()()
      {
         wait();
         return peu_importe_cast_risque<result_type>(wu_->result_);
      }
      operator bool() const
         { return ready(); }
   };

La mécanique de démarrage automatique de l'exécution asynchrone d'une future est sans doute la partie la plus subtile (bien que succincte) du design.

En effet, une future se veut incopiable mais déplaçable (dû à l'utilisation du type unique_ptr pour entreposer les objets représentant ses ressources). Il faut donc que les manipulations qui s'y appliquent gèrent avec soin sa sémantique de mouvement.

La fonction globale start() prend une référence transférable fct, sollicite son service start() pour la démarrer et retourne une référence transférable sur fct.

Le compilateur détecte automatiquement que fct est jetable lors du return et appelle son constructeur de mouvement.

 
template <class F>
   future_impl<F> start(future_impl<F> fct)
   {
      fct.start();
      return fct;
   }

Enfin, la fonction génératrice future<F,A>(f,a) crée une future_impl<F> capable d'exécuter f(a) de manière asynchrone, puis la passe (par mouvement) à start() qui la démarrera puis la retournera démarrée.

Notez que future() retourne une copie de l'objet anonyme résultant, ce qui permet à la sémantique de mouvement de s'appliquer pleinement. Notez aussi l'application du Perfect Forwarding aux paramètres f et a, qui estune pratique typique de fonctions génératrices comme celle-ci.

 
template <class F, class A>
   future_impl<F> future(F f, A arg)
   {
      return start(
         future_impl<F>(
            std::forward<F>(f), std::forward<A>(arg)
         )
      );
   }
#endif

Fichier future.cpp

Il nous reste à examiner l'implémentation d'une future et de la mécanique qui la sous-tend.

Tout d'abord, un thread doit réaliser le travail attendu, soit exécuter une unité de travail (un work_unit).

Dans le but de garder la mécanique de gestion de la durée d'exécution d'un thread distincte de celle de l'unité de travail à réaliser, je passe une paire faite d'une unité de travail et d'un booléen (représentant la complétion ou non de l'exécution, donc initialement faux) au thread.

Le thread exécute l'unité de travail et, que celle-ci se complète normalement ou lève une exception, affecte true au booléen.

Notez l'utilisation d'un unique_ptr local au thread pour gérer la durée de vie de la paire reçue en paramètre. Notez aussi que la gestion d'exceptions lors de l'exécution d'une unité de travail est... rudimentaire (c'est peu dire).

 
#include "future.h"
#include <utility>
#include <memory>
#include <Windows.h>
using namespace std;
unsigned long __stdcall work(void *p)
{
   using param_type = pair<base_future::work_unit*, bool*>;
   auto param = unique_ptr<param_type>(static_cast<param_type*>(p));
   try
   {
      param->first->execute();
      *(param->second) = true;
   }
   catch(...)
   {
      *(param->second) = true;
      return -1;
   }
   return 0;
};

La classe future_rep isole le code associé à la gestion du thread exécutant le code de la future.

Ici, le code sous-jacent utilise des threads Win32, représentés par des HANDLE. La logique des méthodes ready(), wait() et start(), de même que celle du destructeur de future_rep, en sont clairement le reflet; sur une autre plateforme, des versions équivalentes mais adaptées aux réalités locales seraient nécessaires.

 
class base_future::future_rep
{
   HANDLE h;
   mutable bool done_;
public:
   future_rep()
      : h{INVALID_HANDLE_VALUE}, done_{}
   {
   }
   bool ready() const
   {
      if (!h) throw NotStarted{};
      return done_;
   }
   void wait() const
   {
      if (!h) throw NotStarted{};
      WaitForSingleObject(h, INFINITE);
      done_ = true;
   }
   void start(unique_ptr<base_future::work_unit> &p)
   {
      auto param = new pair<base_future::work_unit*, bool*>(p.get(), &done_);
      h = CreateThread(0, 0, work, param, 0, 0);
      if (!h)
      {
         delete param;
         throw CouldNotStart{};
      }
   }
   ~future_rep() noexcept
   {
      if (h)
      {
         wait();
         CloseHandle(h);
      }
   }
};

Les méthodes restantes sont évidentes, constituées selon les cas d'opérations usitées ou de délégations vers des fonctions implémentées dans les classes de représentations sous-jacentes.

Portez attention au constructeur paramétrique de base_future et à l'initialisation en deux temps de wu_ et de rep_. Dans ce cas bien précis, il est important de procéder ainsi du fait que wu est présumé alloué dynamiquement au préalable, et « flottant » à ce stade sans que quelque objet que ce soit n'en soit responsable. Si rep_ était initialisé en préconstruction et si le new servant à l'initialiser échouait, il y aurait un risque que wu soit perdu, entraînant une fuite de ressources.

 
base_future::base_future(base_future::work_unit *wu)
   : wu_(wu)
{
   rep_ = unique_ptr<future_rep>(new future_rep);
}
base_future::base_future(base_future &&autre)
   : rep_(std::move(autre.rep_)), wu_(std::move(autre.wu_))
{
   autre.rep_ = {};
   autre.wu_ = {};
}
base_future::~base_future() noexcept
   { wait(); }
void base_future::start()
{
   if (rep_) rep_->start(wu_);
}
bool base_future::ready() const
   { return rep_->ready(); }
void base_future::wait() const
   { if (rep_) rep_->wait(); }

Voilà!

Valid XHTML 1.0 Transitional

CSS Valide !