Logique d’infrastructure Java fork / join

Cela est apparu comme un “effet secondaire” à une réponse à une autre question aujourd’hui. C’est plus une question de curiosité qu’un problème réel.

Java SE 7 offre ce que Oracle appelle “le framework fork / join”. C’est probablement un moyen supérieur de planifier le travail pour plusieurs processeurs. Bien que je comprenne comment cela est censé fonctionner, je n’arrive pas à comprendre en quoi cela est supérieur et ce que l’on prétend du vol de travail.

Peut-être que quelqu’un d’autre comprend mieux pourquoi cette approche serait souhaitable (autrement que parce qu’elle a un nom sophistiqué).

Les primitives sous-jacentes de fork / join sont ForkJoinTask s, qui sont Future s, et l’idée est d’effectuer le travail immédiatement (sic), le libellé étant trompeur car “immédiatement” implique que cela se produise de manière synchrone dans le fil principal, en réalité se produit dans un Future ) en dessous d’un certain seuil ou divise le travail en deux tâches de manière récursive jusqu’à ce que le seuil soit atteint.

Un avenir est un concept d’encapsulation d’une tâche qui s’exécute de manière asynchrone dans un object de manière opaque et non spécifiée. Vous disposez d’une fonction qui vous permet de vérifier si un résultat est disponible et vous obtenez une fonction qui vous permet (d’attendre et) de récupérer un résultat.
Ssortingctement parlant, vous ne savez même pas si un futur s’exécute de manière asynchrone, il pourrait s’exécuter dans get() . En théorie, l’implémentation pourrait également générer un thread pour chaque futur ou utiliser un pool de threads.
En pratique, Java implémente les futurs en tant que tâches dans une queue de tâches, avec un pool de threads attachés (il en va de même pour tout le framework fork / join).

La documentation fork / join donne cet exemple concret d’utilisation:

 protected void compute() { if (mLength < sThreshold) { computeDirectly(); return; } int split = mLength / 2; invokeAll(new ForkBlur(mSource, mStart, split, mDestination), new ForkBlur(mSource, mStart + split, mLength - split, mDestination)); }

Ceci soumet des tâches à la queue de tâches du pool de threads sous-jacent d’une manière identique à la façon dont Mergesort les traverserait (grâce à la récursion).
Disons par exemple que nous avons un tableau de 32 “éléments” à traiter et que nous avons un seuil de 4, et que nous le divisons de manière égale, cela produirait 8 tâches de 4 “éléments” chacune, et ressemblerait à ceci:

 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 . 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15|16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 . . . 00 01 02 03 04 05 06 07|08 09 10 11 12 13 14 15|16 17 18 19 20 21 22 23|24 25 26 27 28 29 30 31 . . . . . . . 00 01 02 03|04 05 06 07|08 09 10 11|12 13 14 15|16 17 18 19|20 21 22 23|24 25 26 27|28 29 30 31 ------------------------------------------------------------------------------------------------ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

Sur un processeur monocœur, cela soumettra / exécutera (de manière très compliquée) les groupes de tâches 1-2-3-4-5-6-7-8 dans l’ordre.
Sur un processeur dual-core, cela soumettra / exécutera (1,3) – (2,4) – (5,7) – (6,8) ^[1] .
Sur un processeur quad-core, cela soumettra / exécutera (1,3,5,7) – (2,4,6,8).

En comparaison, une implémentation naïve sans toute la magie supérieure ne ferait que soumettre les tâches 1-2-3-4-5-6-7-8 à la queue des tâches immédiatement. Toujours.

Sur un processeur monocœur, cela soumettrait / exécuterait 1-2-3-4-5-6-7-8.
Sur un processeur dual-core, cela soumettrait / exécuterait (1,2) – (3,4) – (5,6) – (7,8).
Sur un processeur quad-core, cela soumettrait / exécuterait (1,2,3,4) – (5,6,7,8).

Des questions:

Au lieu de simplement entasser des éléments consécutifs sThreshold dans une tâche et de soumettre une tâche après l’autre dans la queue des tâches du pool de threads, une hiérarchie de récurrence en forme d’arborescence est générée. Cela implique la construction, la référence et la destruction de N + objects log2 (N) pour N sous-tâches qui, en réalité, ne font rien. Pourquoi est-ce supérieur?
Aucune localité de référence n’est conservée. Ni les caches de processeur ni la mémoire virtuelle ne sont traités de la sorte. Pourquoi est-ce supérieur?
Sauf sur un système à un seul processeur, il est garanti que les tâches ne seront pas planifiées dans un ordre proche de leur ordre d’origine. Ce n’est peut-être pas un problème si cela n’a pas vraiment d’importance, mais cela rend par exemple une clôture ou une barrière quasiment irréalisable. La seule façon d’avoir quelque chose comme une clôture est d’attendre que l’object racine soit terminé et de ne soumettre que de nouvelles tâches par la suite. Cela équivaut à un décrochage complet du pipeline (ce qui est exactement ce que vous ne voulez pas arriver).
La documentation Oracle affirme que cette approche implémente le vol de travail et est donc préférable à un pool de threads . Je ne vois pas cela arriver. Tout ce que je peux voir, c’est une manière très compliquée de soumettre des tâches à un pool de threads normal. Comment cela est-il supposé mettre en œuvre magiquement le vol de travail?

^[1] Ne compliquons pas les choses et supposons que les threads de travail ne se distancent pas, les tâches prennent toutes le même temps. Sinon, l’exécution pourrait bien entendu se dérouler dans un ordre différent, bien que la soumission soit la même.

Lorsque vous utilisez un ExecutorService vous décidez du nombre de threads dans le pool de threads. Il n’y a aucune distinction entre les tâches que vous planifiez et les sous- tâches créées par ces tâches .
ForkJoinPool classe ForkJoinPool , à la place, gère les threads en fonction de 1) les processeurs disponibles et 2) de la demande de tâches.
Dans ce cas, les sous-tâches créées par les tâches actives sont planifiées par des méthodes différentes de celles des tâches externes.
Nous avons généralement un seul groupe de jointures pour une application entière (contrairement à ExecutorService où il est généralement possible d’en avoir plus d’un dans une application non sortingviale) et il n’est pas nécessaire d’ shutdown .
Je n’ai pas passé en revue les internes pour vous donner une explication plus simple, mais si vous voyez ici, il y a une présentation et un repère indiquant les mesures montrant le parallélisme promis.

Mettre à jour:
Cette infrastructure résout certains types de problèmes ( ExecutorService fonctionne mieux pour les tâches combinant une activité à la fois CPU et E / S).
L’idée de base consiste à utiliser une approche récursive / division / conquête afin de garder les processeurs constamment occupés. L’idée est de créer de nouvelles tâches (forking) et de suspendre la tâche en cours jusqu’à ce que les nouvelles tâches soient terminées (rejoindre), mais sans créer de nouveaux threads et sans disposer d’une queue de travail partagée.
Le framework Fork-join est donc implémenté à l’aide de work-stlying en créant un nombre limité de threads de travail (autant que de cœurs). Chaque thread de travail maintient une queue privée à double tâche.
Lors de la frappe, le travailleur pousse une nouvelle tâche en tête de sa deque. Lorsque vous attendez ou que vous êtes inactif, le travailleur relève une tâche de la tête de son deque et l’exécute au lieu de dormir.
Si la deque du travailleur est vide, vole un élément de la queue du deque d’un autre ouvrier choisi au hasard.
Je recommanderais de lire le parallélisme des données en Java et de faire vous-même des tests pour vous convaincre. La théorie n’est bonne que jusqu’à un certain point. Après cela, faites vos mesures pour voir s’il ya un avantage de performance significatif ou non

Permettez-moi de commencer par un article [oui, je l’ai écrit] qui critique le cadre. Une calamité Java à la fourche

Maintenant à vos questions:

Ce n’est pas. Le framework veut traiter un DAG. C’est la structure de conception.
Ce n’est pas. Comme le mentionne l’article, les applications Java ne connaissent rien aux caches, à la mémoire, etc., de sorte que les hypothèses sont erronées.
Oui. C’est exactement ce qui se passe. Les stalles sont si courantes que le framework doit créer des “threads de continuation” pour continuer à avancer. L’article fait référence à une question ici où plus de 700 threads de continuation étaient nécessaires.
Je conviens certainement que le code est complexe. Scatter-collecte fonctionne beaucoup mieux que le vol de travail pour les applications. En ce qui concerne la documentation, quelle documentation? Il n’y a pas de détails d’Oracle. C’est tout un effort pour utiliser le cadre.

Il y a des alternatives.