Dans la continuité de mes deux précédents articles, je voudrais aborder ici les bonnes approches de division en tâches dans le cadre du framework fork / join. Cela me permettra aussi de répondre ici à des questions envoyées par quelques précieux lecteurs (car oui, ce blog est lu par plusieurs personnes !). Le framework fork / join a pour objet de traiter de très grandes quantités de données, dans de très nombreuses tâches, tout en conservant le principe qu’une tâche doit effectuer un « petit » traitement. L’une des difficultés est de garantir que la quantité d’opérations réalisées par une tâche donnée reste limitée, et, surtout, n’augmente pas avec la taille globale du traitement.

Par exemple, dans un calcul matriciel, on ne veut pas que le temps de traitement d’une tâche dépende de la taille de la matrice à traiter.

Deux stratégies de division récursive

Le paradigme sur lequel s’appuie le framework fork / join est « diviser pour mieux régner ». La documentation nous explique qu’il faut diviser une tâche à effectuer, tant que celle-ci dépasse, en volume de calculs, un certain seuil, que l’on se fixe. Supposons que ce seuil soit un nombre d’opérations à effectuer, qui peuvent être des multiplications, ou des divisions, ou autre chose encore. Si la tâche que je reçois comporte plus d’opérations que ce seuil, alors je la divise, sinon je l’effectue.

Deux façons naturelles de diviser cette tâche s’offrent immédiatement :

• diviser la tâche en deux sous-tâches de mêmes tailles ;
• diviser la tâche en une première sous-tâche de la bonne taille (connaissant le seuil, on doit pouvoir y arriver !), et une autre sous-tâche avec le reste des opérations.

Dans le premier cas, on ne sait pas a priori si les deux sous-tâches devront être à nouveau divisées. On a donc le choix : soit on forke les deux, soit on exécute la première, et on forke la deuxième.

Le premier choix n’est pas très efficace, puisque la tâche dans laquelle on est n’aura exécuté qu’une division par 2 et un test. Le coût de gestion de cette tâche risque de devenir prohibitif par rapport à ce qu’elle a effectué, c’est-à-dire approximativement rien.

Dans le second cas, la première tâche peut être exécutée immédiatement : elle a la bonne taille par construction. La seconde tâche peut être forkée. Chaque tâche a le même volume : un test et l’exécution du bon nombre d’opérations, sauf pour la dernière tâche, qui va, en général, comporter trop peu d’opérations.

Le nombre d’opérations par tâche est également mieux réparti dans la deuxième stratégie que dans la première. Si N est le nombre d’opérations de mon seuil, dans la première stratégie, chaque tâche effectuera un nombre d’opérations compris entre N/2 et N. Dans la seconde, ce nombre sera constant et égal à N, sauf pour la dernière tâche, où il sera compris entre 0 et N.

Diviser sans récursivité

Pourquoi ne pas générer toutes les tâches en une fois dans une boucle, en les forkant toutes d’un coup ?

La réponse est un peu subtile, et tient à la façon dont le framework fork / join est construit.

Chaque thread de notre pool est associé à une file d’attente, dans laquelle il va aller chercher ses tâches à exécuter. Il place chaque tâche qu’il forke dans sa propre file d’attente.

Si une file d’attente s’assèche, alors le thread concerné va aller prendre une tâche dans la file d’un de ses petits camarades. C’est la technique classique de task stealing. Il vaut mieux éviter de recourir à cette possibilité, pour des raisons de performances. D’ailleurs la classe ForkJoinTask, classe de base de RecursiveTask et RecursiveAction (entre autres), expose une méthode getSurplusTaskCount() qui permet de tester si une de ces files d’attente comporte trop de tâches par rapport aux autres. Si c’est le cas, alors ce thread va très probablement se faire voler des tâches. Cette information peut aussi être utilisée pour décider de forker ou non.

Générer un très grand nombre de petites tâches, qui elles-mêmes ne forkent pas, nous met dans la pire des situations. Le thread qui traite la première tâche voit sa file d’attente se remplir de toutes les tâches du traitement. Les autres threads devront donc toutes les voler une par une pour pouvoir les exécuter.

Cette dernière stratégie est donc à éviter. Il vaut mieux forker des tâches divisibles, ce qui répartira les tâches élémentaires plus rapidement dès le début du traitement.

Remarques sur la Javadoc

La Javadoc de la classe RecursiveAction donne plusieurs exemples de patterns d’utilisation du fork / join.

Le premier exemple porte sur le tri en place d’un tableau, une opération qui ne retourne rien. Dans la mesure où cette opération ne retourne rien, il est effectivement pertinent d’utiliser RecursiveAction plutôt que RecursiveTask. Cela dit, l’exemple de la Javadoc est en fait incomplet, puisqu’il y manque la fonction de tri en elle-même (on peut utiliser Arrays.sort(array, low, high)), et surtout la fonction de fusion de deux tableaux triés. Cette fonction de fusion n’est pas si simple à écrire, surtout si l’on ne veut pas créer de tableaux intermédiaires (ce problème est tellement classique, qu’il a été baptisé Merge Sort). Comme remarqué lors de mon dernier article, la relecture du tableau trié peut poser des problèmes de synchronisation.

Le deuxième exemple est un parcours de tableau, qui incrémente chaque case. Cela pourrait être d’ailleurs toute autre opération sur les cases. La stratégie de division est la dichotomie, qui n’est pas la bonne, et l’exemple passe également sous silence le problème de synchronisation de la lecture.