Sollte ich nach Möglichkeit immer einen parallelen Stream verwenden?

514

Mit Java 8 und Lambdas ist es einfach, Sammlungen als Streams zu durchlaufen und einen parallelen Stream genauso einfach zu verwenden. Zwei Beispiele aus den Dokumenten , das zweite mit 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()));

Wäre es immer vorteilhaft, die Parallele zu verwenden, solange mir die Bestellung egal ist? Man würde denken, es ist schneller, die Arbeit auf mehr Kerne aufzuteilen.

Gibt es noch andere Überlegungen? Wann sollte ein paralleler Stream verwendet werden und wann sollte der nicht parallele Stream verwendet werden?

(Diese Frage wird gestellt, um eine Diskussion darüber auszulösen, wie und wann parallele Streams verwendet werden sollen, nicht weil ich es für eine gute Idee halte, sie immer zu verwenden.)

Matsemann
quelle

Antworten:

735

Ein paralleler Stream hat einen viel höheren Overhead als ein sequentieller. Das Koordinieren der Threads nimmt viel Zeit in Anspruch. Ich würde standardmäßig sequentielle Streams verwenden und nur parallele berücksichtigen, wenn

  • Ich muss eine große Menge von Artikeln verarbeiten (oder die Verarbeitung jedes Artikels nimmt Zeit in Anspruch und ist parallelisierbar).

  • Ich habe in erster Linie ein Leistungsproblem

  • Ich führe den Prozess noch nicht in einer Multithread-Umgebung aus (Beispiel: Wenn in einem Webcontainer bereits viele Anforderungen parallel verarbeitet werden müssen, kann das Hinzufügen einer zusätzlichen Parallelitätsebene in jeder Anforderung eher negative als positive Auswirkungen haben )

In Ihrem Beispiel wird die Leistung ohnehin durch den synchronisierten Zugriff auf gesteuert System.out.println(), und eine parallele Ausführung dieses Prozesses hat keine oder sogar negative Auswirkungen.

Denken Sie außerdem daran, dass parallele Streams nicht alle Synchronisationsprobleme auf magische Weise lösen. Wenn eine gemeinsam genutzte Ressource von den im Prozess verwendeten Prädikaten und Funktionen verwendet wird, müssen Sie sicherstellen, dass alles threadsicher ist. Insbesondere Nebenwirkungen sind Dinge, über die Sie sich wirklich Sorgen machen müssen, wenn Sie parallel arbeiten.

Auf jeden Fall messen, nicht raten! Nur eine Messung zeigt Ihnen, ob sich die Parallelität lohnt oder nicht.

JB Nizet
quelle
18
Gute Antwort. Ich würde hinzufügen, dass, wenn Sie eine große Menge von Elementen verarbeiten müssen, dies nur die Probleme bei der Thread-Koordination erhöht. Nur wenn die Verarbeitung der einzelnen Elemente Zeit in Anspruch nimmt und parallelisierbar ist, kann die Parallelisierung hilfreich sein.
Warren Dew
16
@ WarrenDew Ich bin anderer Meinung. Das Fork / Join-System teilt die N Elemente einfach in beispielsweise 4 Teile auf und verarbeitet diese 4 Teile nacheinander. Die 4 Ergebnisse werden dann reduziert. Wenn massiv wirklich massiv ist, kann die Parallelisierung selbst für eine schnelle Verarbeitung von Einheiten effektiv sein. Aber wie immer muss man messen.
JB Nizet
Ich habe eine Sammlung von Objekten, die implementiert werden und Runnabledie ich aufrufe start(), um sie als Threadszu verwenden. Ist es in Ordnung, dies in die Verwendung von Java 8-Streams in einer .forEach()Parallelisierung zu ändern ? Dann könnte ich den Thread-Code aus der Klasse entfernen. Aber gibt es irgendwelche Nachteile?
ycomp
1
@JBNizet Wenn 4 Teile nacheinander ausgeführt werden, gibt es keinen Unterschied, ob es sich um Prozessparallelen handelt oder ob Sie nacheinander wissen? Bitte klären Sie
Harshana
3
@ Harshana bedeutet natürlich, dass die Elemente jedes der 4 Teile nacheinander verarbeitet werden. Die Teile selbst können jedoch gleichzeitig bearbeitet werden. Mit anderen Worten, wenn Sie mehrere CPU-Kerne zur Verfügung haben, kann jeder Teil unabhängig von den anderen Teilen auf einem eigenen Kern ausgeführt werden, während seine eigenen Elemente nacheinander verarbeitet werden. (HINWEIS: Ich weiß nicht, ob parallele Java-Streams so funktionieren, ich versuche nur zu klären, was JBNizet bedeutet.)
Morgen,
258

Die Stream-API wurde entwickelt, um das Schreiben von Berechnungen auf eine Weise zu vereinfachen, die von der Art und Weise, wie sie ausgeführt werden, abstrahiert ist, und um das Umschalten zwischen sequentiell und parallel zu vereinfachen.

Nur weil es einfach ist, heißt das nicht, dass es immer eine gute Idee ist, und in der Tat ist es eine schlechte Idee, einfach .parallel()überall vorbeizuschauen, nur weil man es kann.

Beachten Sie zunächst, dass Parallelität keine anderen Vorteile bietet als die Möglichkeit einer schnelleren Ausführung, wenn mehr Kerne verfügbar sind. Eine parallele Ausführung erfordert immer mehr Arbeit als eine sequentielle, da neben der Lösung des Problems auch das Versenden und Koordinieren von Unteraufgaben durchgeführt werden muss. Die Hoffnung ist, dass Sie schneller zur Antwort gelangen, indem Sie die Arbeit auf mehrere Prozessoren aufteilen. Ob dies tatsächlich geschieht, hängt von vielen Faktoren ab, einschließlich der Größe Ihres Datensatzes, der Anzahl der Berechnungen, die Sie für jedes Element ausführen, der Art der Berechnung (insbesondere interagiert die Verarbeitung eines Elements mit der Verarbeitung anderer Elemente?). , die Anzahl der verfügbaren Prozessoren und die Anzahl der anderen Aufgaben, die um diese Prozessoren konkurrieren.

Beachten Sie außerdem, dass Parallelität häufig auch Nichtdeterminismus in der Berechnung aufdeckt, der häufig durch sequentielle Implementierungen verborgen wird. Manchmal spielt dies keine Rolle oder kann durch Einschränkung der beteiligten Vorgänge gemildert werden (dh Reduktionsoperatoren müssen zustandslos und assoziativ sein.)

In der Realität beschleunigt Parallelität manchmal Ihre Berechnung, manchmal nicht und manchmal sogar. Es ist am besten, zuerst mit sequentieller Ausführung zu entwickeln und dann wo Parallelität anzuwenden

(A) Sie wissen, dass eine Leistungssteigerung tatsächlich Vorteile bringt und

(B) dass es tatsächlich eine erhöhte Leistung liefert.

(A) ist ein geschäftliches Problem, kein technisches. Wenn Sie ein Leistungsexperte sind, können Sie normalerweise den Code betrachten und (B) bestimmen, aber der kluge Weg ist zu messen. (Und stören Sie sich nicht einmal, bis Sie von (A) überzeugt sind. Wenn der Code schnell genug ist, sollten Sie Ihre Gehirnzyklen besser an anderer Stelle anwenden.)

Das einfachste Leistungsmodell für Parallelität ist das "NQ" -Modell, wobei N die Anzahl der Elemente und Q die Berechnung pro Element ist. Im Allgemeinen muss der Produkt-NQ einen bestimmten Schwellenwert überschreiten, bevor Sie einen Leistungsvorteil erzielen. Bei einem Problem mit niedrigem Q wie "Addiere Zahlen von 1 bis N" wird im Allgemeinen eine Gewinnschwelle zwischen N = 1000 und N = 10000 angezeigt. Bei Problemen mit höherem Q sehen Sie Breakevens bei niedrigeren Schwellenwerten.

Aber die Realität ist ziemlich kompliziert. Identifizieren Sie also erst, wenn die sequentielle Verarbeitung Sie tatsächlich etwas kostet, und messen Sie dann, ob Parallelität hilfreich ist, bis Sie Erfahrung gesammelt haben.

Brian Goetz
quelle
18
Dieser Beitrag enthält weitere Details zum NQ-Modell: gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html
Pino
4
@specializt: einen Strom aus sequentiellen parallel zum Schalt macht den Algorithmus ändern (in den meisten Fällen). Der hier erwähnte Determinismus bezieht sich auf Eigenschaften, auf die sich Ihre (willkürlichen) Operatoren möglicherweise verlassen (die Stream-Implementierung kann das nicht wissen), sollte sich aber natürlich nicht darauf verlassen. Das versuchte dieser Abschnitt dieser Antwort zu sagen. Wenn Sie sich für die Regeln interessieren, können Sie ein deterministisches Ergebnis erzielen, genau wie Sie sagen (ansonsten waren parallele Streams ziemlich nutzlos), aber es besteht auch die Möglichkeit, absichtlich Nichtdeterminismus zuzulassen, wie wenn Sie findAnyanstelle von findFirst...
Holger
4
"Beachten Sie zunächst, dass Parallelität keine anderen Vorteile bietet als die Möglichkeit einer schnelleren Ausführung, wenn mehr Kerne verfügbar sind" - oder wenn Sie eine Aktion anwenden, die E / A umfasst (z myListOfURLs.stream().map((url) -> downloadPage(url)).... B. ).
Jules
6
@Pacerier Das ist eine schöne Theorie, aber leider naiv (siehe zunächst die 30-jährige Geschichte der Versuche, automatisch parallelisierende Compiler zu erstellen). Da es nicht praktisch ist, die richtige Zeit zu erraten, um den Benutzer nicht zu ärgern, wenn wir es unvermeidlich falsch verstehen, war es die verantwortliche Aufgabe, den Benutzer nur sagen zu lassen, was er will. In den meisten Situationen ist die Standardeinstellung (sequentiell) richtig und vorhersehbarer.
Brian Goetz
2
@Jules: Verwenden Sie niemals parallele Streams für E / A. Sie sind ausschließlich für CPU-intensive Vorgänge gedacht. Parallele Streams werden verwendet ForkJoinPool.commonPool()und Sie möchten nicht, dass blockierende Aufgaben dorthin gehen.
R2C2
68

Ich habe mir eine der Präsentationen von Brian Goetz (Java Language Architect & Spezifikationsleiter für Lambda Expressions) angesehen . Er erklärt ausführlich die folgenden 4 Punkte, die vor der Parallelisierung zu beachten sind:

Aufteilungs- / Zerlegungskosten
- Manchmal ist das Aufteilen teurer als nur die Arbeit zu erledigen!
Kosten für Aufgabenversand / -verwaltung
- Kann in der Zeit, die für die Übergabe der Arbeit an einen anderen Thread erforderlich ist, viel Arbeit leisten.
Ergebniskombinationskosten
- Manchmal umfasst die Kombination das Kopieren vieler Daten. Das Hinzufügen von Zahlen ist beispielsweise billig, während das Zusammenführen von Sätzen teuer ist.
Lokalität
- Der Elefant im Raum. Dies ist ein wichtiger Punkt, den jeder übersehen kann. Sie sollten Cache-Fehler berücksichtigen. Wenn eine CPU aufgrund von Cache-Fehlern auf Daten wartet, würden Sie durch Parallelisierung nichts gewinnen. Aus diesem Grund parallelisieren Array-basierte Quellen am besten, wenn die nächsten Indizes (in der Nähe des aktuellen Index) zwischengespeichert werden und die Wahrscheinlichkeit geringer ist, dass die CPU einen Cache-Fehler erleidet.

Er erwähnt auch eine relativ einfache Formel, um die Wahrscheinlichkeit einer parallelen Beschleunigung zu bestimmen.

NQ-Modell :

N x Q > 10000

Dabei ist
N = Anzahl der Datenelemente.
Q = Arbeitsaufwand pro Element

Ram Patra
quelle
13

JB traf den Nagel auf den Kopf. Das einzige, was ich hinzufügen kann, ist, dass Java 8 keine reine Parallelverarbeitung durchführt, sondern paraquential . Ja, ich habe den Artikel geschrieben und mache seit 30 Jahren F / J, damit ich das Problem verstehe.

edharned
quelle
10
Streams können nicht iteriert werden, da Streams eine interne Iteration anstelle einer externen Iteration durchführen. Das ist sowieso der ganze Grund für Streams. Wenn Sie Probleme mit der akademischen Arbeit haben, ist funktionale Programmierung möglicherweise nichts für Sie. Funktionale Programmierung === Mathematik === akademisch. Und nein, J8-FJ ist nicht kaputt, es ist nur so, dass die meisten Leute das Handbuch nicht lesen. In den Java-Dokumenten wird sehr deutlich, dass es sich nicht um ein Framework für die parallele Ausführung handelt. Das ist der ganze Grund für all das Spliterator-Zeug. Ja, es ist akademisch, ja, es funktioniert, wenn Sie wissen, wie man es benutzt. Ja, es sollte einfacher sein, einen benutzerdefinierten Executor zu verwenden
Kr0e
1
Stream verfügt über eine iterator () -Methode, sodass Sie sie bei Bedarf extern iterieren können. Mein Verständnis war, dass sie Iterable nicht implementieren, da Sie diesen Iterator nur einmal verwenden können und niemand entscheiden kann, ob dies in Ordnung ist.
Trejkaz
14
um ehrlich zu sein: Ihr gesamtes Papier liest sich wie ein massiver, ausgefeilter Scherz - und das negiert so ziemlich seine Glaubwürdigkeit ... Ich würde empfehlen, es mit einem viel weniger aggressiven Unterton zu wiederholen, sonst werden sich nicht viele Leute tatsächlich die Mühe machen, es vollständig zu lesen ... ich bin nur sayan
spezialisiert
Ein paar Fragen zu Ihrem Artikel ... Zunächst einmal, warum setzen Sie anscheinend ausgeglichene Baumstrukturen mit gerichteten azyklischen Graphen gleich? Ja, ausgeglichene Bäume sind DAGs, aber auch verknüpfte Listen und so ziemlich jede objektorientierte Datenstruktur außer Arrays. Wenn Sie sagen, dass rekursive Zerlegung nur bei ausgeglichenen Baumstrukturen funktioniert und daher kommerziell nicht relevant ist, wie rechtfertigen Sie diese Behauptung? Es scheint mir (zugegebenermaßen ohne das Problem wirklich eingehend zu untersuchen), dass es auf Array-basierten Datenstrukturen, z . B. /, genauso gut funktionieren sollte . ArrayListHashMap
Jules
1
Dieser Thread stammt aus dem Jahr 2013, seitdem hat sich viel geändert. Dieser Abschnitt ist für Kommentare nicht detaillierte Antworten.
Edharned
3

Andere Antworten betrafen bereits die Profilerstellung, um vorzeitige Optimierung und Gemeinkosten bei der Parallelverarbeitung zu vermeiden. Diese Antwort erklärt die ideale Auswahl von Datenstrukturen für paralleles Streaming.

In der Regel sind Leistungssteigerungen von der Parallelität besten auf Ströme über ArrayList, HashMap, HashSet, und ConcurrentHashMapInstanzen; Arrays; intBereiche; und longBereiche. Gemeinsam ist diesen Datenstrukturen, dass sie alle genau und kostengünstig in Unterbereiche beliebiger Größe aufgeteilt werden können, was die Aufteilung der Arbeit auf parallele Threads erleichtert. Die Abstraktion, die von der Streams-Bibliothek zur Ausführung dieser Aufgabe verwendet wird, ist der Spliterator, der von der spliteratorMethode on Streamund zurückgegeben wird Iterable.

Ein weiterer wichtiger Faktor, den alle diese Datenstrukturen gemeinsam haben, ist, dass sie bei sequentieller Verarbeitung eine gute bis ausgezeichnete Referenzlokalität bieten: Sequentielle Elementreferenzen werden zusammen im Speicher gespeichert. Die Objekte, auf die sich diese Referenzen beziehen, befinden sich möglicherweise nicht nahe beieinander im Speicher, wodurch die Referenzlokalität verringert wird. Die Referenzlokalität erweist sich als äußerst wichtig für die Parallelisierung von Massenoperationen: Ohne sie verbringen Threads einen Großteil ihrer Zeit im Leerlauf und warten darauf, dass Daten aus dem Speicher in den Cache des Prozessors übertragen werden. Die Datenstrukturen mit der besten Referenzlokalität sind primitive Arrays, da die Daten selbst zusammenhängend im Speicher gespeichert sind.

Quelle: Item # 48 Vorsicht beim parallelen Erstellen von Streams, effektives Java 3e von Joshua Bloch

ruhong
quelle
2

Parallelisieren Sie niemals einen unendlichen Strom mit einem Limit. Folgendes passiert:

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

Ergebnis

    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 ...

Gleiches, wenn Sie verwenden .limit(...)

Erläuterung hier: Java 8, das .parallel in einem Stream verwendet, verursacht einen OOM-Fehler

Verwenden Sie in ähnlicher Weise nicht parallel, wenn der Stream geordnet ist und viel mehr Elemente enthält, als Sie verarbeiten möchten, z

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

Dies kann viel länger dauern, da die parallelen Threads möglicherweise in vielen Nummernbereichen anstelle des entscheidenden 0-100 arbeiten, was sehr lange dauert.

tkruse
quelle