Dois-je toujours utiliser un flux parallèle lorsque cela est possible?

515

Avec Java 8 et lambdas, il est facile d'itérer les collections en tant que flux et tout aussi facile d'utiliser un flux parallèle. Deux exemples tirés de la documentation , le second utilisant parallelStream:

myShapesCollection.stream()
    .filter(e -> e.getColor() == Color.RED)
    .forEach(e -> System.out.println(e.getName()));

myShapesCollection.parallelStream() // <-- This one uses parallel
    .filter(e -> e.getColor() == Color.RED)
    .forEach(e -> System.out.println(e.getName()));

Tant que je ne me soucie pas de la commande, serait-il toujours avantageux d'utiliser le parallèle? On pourrait penser qu'il est plus rapide de diviser le travail sur plus de cœurs.

Y a-t-il d'autres considérations? Quand utiliser le flux parallèle et quand utiliser le non parallèle?

(Cette question est posée pour déclencher une discussion sur comment et quand utiliser des flux parallèles, pas parce que je pense que toujours les utiliser est une bonne idée.)

Matsemann
la source

Réponses:

736

Un flux parallèle a une surcharge beaucoup plus élevée par rapport à un flux séquentiel. La coordination des fils prend beaucoup de temps. J'utiliserais des flux séquentiels par défaut et ne considérerais que les flux parallèles si

  • J'ai une quantité énorme d'articles à traiter (ou le traitement de chaque article prend du temps et est parallélisable)

  • J'ai un problème de performance en premier lieu

  • Je n'exécute pas déjà le processus dans un environnement multi-thread (par exemple: dans un conteneur Web, si j'ai déjà plusieurs demandes à traiter en parallèle, l'ajout d'une couche supplémentaire de parallélisme à l'intérieur de chaque demande pourrait avoir des effets plus négatifs que positifs. )

Dans votre exemple, les performances seront de toute façon déterminées par l'accès synchronisé à System.out.println(), et rendre ce processus parallèle n'aura aucun effet, ni même un effet négatif.

De plus, n'oubliez pas que les flux parallèles ne résolvent pas comme par magie tous les problèmes de synchronisation. Si une ressource partagée est utilisée par les prédicats et les fonctions utilisés dans le processus, vous devrez vous assurer que tout est thread-safe. En particulier, les effets secondaires sont des choses dont vous devez vraiment vous inquiéter si vous opérez en parallèle.

En tout cas, mesurez, ne devinez pas! Seule une mesure vous dira si le parallélisme en vaut la peine ou non.

JB Nizet
la source
18
Bonne réponse. J'ajouterais que si vous avez une quantité massive d'articles à traiter, cela ne fait qu'augmenter les problèmes de coordination des threads; ce n'est que lorsque le traitement de chaque élément prend du temps et est parallélisable que la parallélisation peut être utile.
Warren Dew
16
@WarrenDew Je ne suis pas d'accord. Le système Fork / Join divisera simplement les N éléments en, par exemple, 4 parties, et traitera ces 4 parties séquentiellement. Les 4 résultats seront alors réduits. Si massif est vraiment massif, même pour un traitement unitaire rapide, la parallélisation peut être efficace. Mais comme toujours, il faut mesurer.
JB Nizet
j'ai une collection d'objets qui implémentent Runnableque j'appelle start()pour les utiliser comme Threads, est-ce correct de changer cela en utilisant des flux java 8 dans un .forEach()parallélisé? Ensuite, je serais en mesure de retirer le code de thread de la classe. Mais y a-t-il des inconvénients?
ycomp
1
@JBNizet Si 4 parties sont traitées séquentiellement, alors il n'y a aucune différence s'il s'agit de processus parallèles ou séquentiellement connus?
Veuillez
3
@Harshana, il signifie évidemment que les éléments de chacune des 4 parties seront traités séquentiellement. Cependant, les pièces elles-mêmes peuvent être traitées simultanément. En d'autres termes, si vous disposez de plusieurs cœurs CPU, chaque partie peut fonctionner sur son propre cœur indépendamment des autres parties, tout en traitant ses propres éléments de manière séquentielle. (REMARQUE: je ne sais pas, si c'est ainsi que fonctionnent les flux Java parallèles, j'essaie simplement de clarifier ce que signifiait JBNizet.)
demain
258

L'API Stream a été conçue pour faciliter l'écriture de calculs d'une manière qui soit abstraite de la façon dont ils seraient exécutés, facilitant ainsi le passage du séquentiel au parallèle.

Cependant, ce n'est pas parce que c'est facile, c'est toujours une bonne idée, et en fait, c'est une mauvaise idée de simplement laisser tomber .parallel()partout simplement parce que vous le pouvez.

Tout d'abord, notez que le parallélisme n'offre aucun avantage autre que la possibilité d'une exécution plus rapide lorsque davantage de cœurs sont disponibles. Une exécution parallèle impliquera toujours plus de travail qu'une exécution séquentielle, car en plus de résoudre le problème, elle doit également effectuer la répartition et la coordination des sous-tâches. L'espoir est que vous serez en mesure d'obtenir la réponse plus rapidement en répartissant le travail sur plusieurs processeurs; si cela se produit réellement dépend de beaucoup de choses, y compris la taille de votre ensemble de données, la quantité de calcul que vous faites sur chaque élément, la nature du calcul (en particulier, le traitement d'un élément interagit-il avec le traitement des autres?) , le nombre de processeurs disponibles et le nombre d'autres tâches en concurrence pour ces processeurs.

De plus, notez que le parallélisme expose également souvent le non-déterminisme dans le calcul qui est souvent caché par les implémentations séquentielles; parfois cela n'a pas d'importance ou peut être atténué en contraignant les opérations impliquées (c'est-à-dire que les opérateurs de réduction doivent être sans état et associatifs).

En réalité, parfois le parallélisme accélérera votre calcul, parfois non, et parfois même le ralentira. Il est préférable de développer d'abord en utilisant l'exécution séquentielle, puis d'appliquer le parallélisme là où

(A) vous savez qu'il y a effectivement un avantage à augmenter les performances et

(B) qu'il fournira réellement des performances accrues.

(A) est un problème commercial et non technique. Si vous êtes un expert en performances, vous pourrez généralement consulter le code et déterminer (B), mais le chemin intelligent est de mesurer. (Et, ne vous embêtez pas jusqu'à ce que vous soyez convaincu de (A); si le code est assez rapide, mieux vaut appliquer vos cycles cérébraux ailleurs.)

Le modèle de performance le plus simple pour le parallélisme est le modèle "NQ", où N est le nombre d'éléments et Q est le calcul par élément. En général, vous devez que le produit NQ dépasse un certain seuil avant de commencer à obtenir un avantage en termes de performances. Pour un problème à faible Q comme «additionner des nombres de 1 à N», vous verrez généralement un seuil de rentabilité entre N = 1000 et N = 10000. Avec des problèmes à Q plus élevé, vous verrez des points morts à des seuils inférieurs.

Mais la réalité est assez compliquée. Donc, jusqu'à ce que vous atteigniez l'expertise, identifiez d'abord quand le traitement séquentiel vous coûte réellement quelque chose, puis mesurez si le parallélisme vous aidera.

Brian Goetz
la source
18
Cet article donne plus de détails sur le modèle NQ: gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html
Pino
4
@specializt: la commutation d' un flux séquentiel de parallèle à fait changer l'algorithme (dans la plupart des cas). Le déterminisme mentionné ici concerne les propriétés sur lesquelles vos opérateurs (arbitraires) peuvent compter (l'implémentation Stream ne peut pas le savoir), mais bien sûr , ne devrait pas compter. C'est ce que cette section de cette réponse a essayé de dire. Si vous vous souciez des règles, vous pouvez avoir un résultat déterministe, comme vous le dites, (sinon les flux parallèles étaient tout à fait inutiles), mais il y a aussi la possibilité d'un non-déterminisme intentionnellement autorisé, comme lors de l'utilisation à la findAnyplace de findFirst...
Holger
4
"Tout d'abord, notez que le parallélisme n'offre aucun avantage autre que la possibilité d'une exécution plus rapide lorsque davantage de cœurs sont disponibles" - ou si vous appliquez une action impliquant des E / S (par exemple myListOfURLs.stream().map((url) -> downloadPage(url))...).
Jules
6
@Pacerier C'est une belle théorie, mais malheureusement naïve (voir l'histoire de 30 ans de tentatives de construction de compilateurs à parallélisation automatique pour commencer). Comme il n'est pas pratique de deviner suffisamment de temps pour ne pas ennuyer l'utilisateur lorsque nous nous trompons inévitablement, la chose responsable à faire était simplement de laisser l'utilisateur dire ce qu'il veut. Pour la plupart des situations, la valeur par défaut (séquentielle) est correcte et plus prévisible.
Brian Goetz
2
@Jules: n'utilisez jamais de flux parallèles pour les E / S. Ils sont uniquement destinés aux opérations gourmandes en CPU. Les flux parallèles utilisent ForkJoinPool.commonPool()et vous ne voulez pas que les tâches de blocage y soient effectuées.
R2C2
68

J'ai regardé l'une des présentations de Brian Goetz (Java Language Architect et responsable des spécifications pour Lambda Expressions) . Il explique en détail les 4 points suivants à considérer avant de passer à la parallélisation:

Coûts de fractionnement / décomposition
- Parfois, le fractionnement est plus cher que de simplement faire le travail!
Coûts de répartition / gestion des tâches
- Peut faire beaucoup de travail dans le temps qu'il faut pour remettre le travail à un autre thread.
Coûts de combinaison des résultats
- Parfois, la combinaison implique la copie de nombreuses données. Par exemple, l'ajout de numéros est bon marché tandis que la fusion d'ensembles coûte cher.
Localité
- L'éléphant dans la pièce. C'est un point important que tout le monde peut manquer. Vous devriez considérer les échecs de cache, si un CPU attend des données à cause des échecs de cache, alors vous ne gagneriez rien à la parallélisation. C'est pourquoi les sources basées sur des tableaux se parallélisent le mieux car les prochains index (proches de l'index actuel) sont mis en cache et il y a moins de chances que le CPU subisse un échec de cache.

Il mentionne également une formule relativement simple pour déterminer une chance d'accélération parallèle.

Modèle NQ :

N x Q > 10000

où,
N = nombre d'éléments de données
Q = quantité de travail par élément

Ram Patra
la source
13

JB a frappé le clou sur la tête. La seule chose que je peux ajouter, c'est que Java 8 ne fait pas de traitement parallèle pur, il fait du paraquentiel . Oui, j'ai écrit l'article et je fais du F / J depuis trente ans, donc je comprends le problème.

éduqué
la source
10
Les flux ne sont pas itérables car les flux effectuent une itération interne plutôt qu'externe. C'est de toute façon la raison des streams. Si vous avez des problèmes avec le travail académique, la programmation fonctionnelle pourrait ne pas vous convenir. Programmation fonctionnelle === math === académique. Et non, le J8-FJ n'est pas cassé, c'est juste que la plupart des gens ne lisent pas le manuel f ******. Les documents java disent très clairement qu'il ne s'agit pas d'un cadre d'exécution parallèle. C'est toute la raison de tous les trucs de séparateur. Oui c'est académique, oui ça marche si vous savez vous en servir. Oui, il devrait être plus facile d'utiliser un exécuteur personnalisé
Kr0e
1
Stream a une méthode iterator (), vous pouvez donc les itérer externes si vous le souhaitez. J'ai cru comprendre qu'ils n'implémentent pas Iterable car vous ne pouvez utiliser cet itérateur qu'une seule fois et personne ne peut décider si cela est correct.
Trejkaz
14
pour être honnête: tout votre article se lit comme une diatribe massive et élaborée - et cela nie à peu près sa crédibilité ... je recommanderais de le refaire avec une nuance beaucoup moins agressive sinon peu de gens prendront la peine de le lire entièrement ... im just sayan
specializt
Quelques questions sur votre article ... tout d'abord, pourquoi assimilez-vous apparemment des structures d'arbre équilibrées à des graphiques acycliques dirigés? Oui, les arbres équilibrés sont des DAG, mais il en va de même pour les listes liées et à peu près toutes les structures de données orientées objet autres que les tableaux. De plus, lorsque vous dites que la décomposition récursive ne fonctionne que sur des structures arborescentes équilibrées et n'est donc pas pertinente commercialement, comment justifiez-vous cette affirmation? Il me semble (certes sans vraiment approfondir la question) que cela devrait fonctionner aussi bien sur des infrastructures de données basées sur des baies, par exemple ArrayList/ HashMap.
Jules
1
Ce fil date de 2013, beaucoup de choses ont changé depuis. Cette section est destinée aux commentaires et non aux réponses détaillées.
edharned
3

D'autres réponses ont déjà couvert le profilage pour éviter une optimisation prématurée et des frais généraux dans le traitement parallèle. Cette réponse explique le choix idéal des structures de données pour le streaming parallèle.

En règle générale, les gains de performance du parallélisme sont les meilleurs sur les flux sur ArrayList, HashMap, HashSetet des ConcurrentHashMapcas; tableaux; intgammes; et longplages. Ce que ces structures de données ont en commun, c'est qu'elles peuvent toutes être divisées avec précision et à moindre coût en sous-gammes de toutes les tailles souhaitées, ce qui facilite la répartition du travail entre les threads parallèles. L'abstraction utilisée par la bibliothèque de flux pour effectuer cette tâche est le séparateur, qui est renvoyé par la spliteratorméthode sur Streamet Iterable.

Un autre facteur important que toutes ces structures de données ont en commun est qu'elles fournissent une localité de référence bonne à excellente lorsqu'elles sont traitées séquentiellement: les références d'éléments séquentielles sont stockées ensemble en mémoire. Les objets référencés par ces références peuvent ne pas être proches les uns des autres en mémoire, ce qui réduit la localité de référence. La localité de référence s'avère extrêmement importante pour la parallélisation des opérations en masse: sans elle, les threads passent une grande partie de leur temps inactif, en attendant que les données soient transférées de la mémoire dans le cache du processeur. Les structures de données avec la meilleure localité de référence sont des tableaux primitifs car les données elles-mêmes sont stockées de manière contiguë en mémoire.

Source: article n ° 48 Soyez prudent lorsque vous créez des flux parallèles, efficace Java 3e par Joshua Bloch

ruhong
la source
2

Ne parallélisez jamais un flux infini avec une limite. Voici ce qui se passe:

    public static void main(String[] args) {
        // let's count to 1 in parallel
        System.out.println(
            IntStream.iterate(0, i -> i + 1)
                .parallel()
                .skip(1)
                .findFirst()
                .getAsInt());
    }

Résultat

    Exception in thread "main" java.lang.OutOfMemoryError
        at ...
        at java.base/java.util.stream.IntPipeline.findFirst(IntPipeline.java:528)
        at InfiniteTest.main(InfiniteTest.java:24)
    Caused by: java.lang.OutOfMemoryError: Java heap space
        at java.base/java.util.stream.SpinedBuffer$OfInt.newArray(SpinedBuffer.java:750)
        at ...

Même si vous utilisez .limit(...)

Explication ici: Java 8, l'utilisation de .parallel dans un flux provoque une erreur OOM

De même, n'utilisez pas parallèle si le flux est ordonné et contient beaucoup plus d'éléments que vous souhaitez traiter, par exemple

public static void main(String[] args) {
    // let's count to 1 in parallel
    System.out.println(
            IntStream.range(1, 1000_000_000)
                    .parallel()
                    .skip(100)
                    .findFirst()
                    .getAsInt());
}

Cela peut s'exécuter beaucoup plus longtemps car les threads parallèles peuvent fonctionner sur de nombreuses plages de numéros au lieu de la plage cruciale 0-100, ce qui peut prendre très longtemps.

tkruse
la source