Czy zawsze powinienem używać strumienia równoległego, jeśli to możliwe?

514

W Javie 8 i lambdach łatwo jest iterować kolekcje jako strumienie, a równie łatwo korzystać z równoległego strumienia. Dwa przykłady z dokumentów , drugi z wykorzystaniem 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()));

Tak długo, jak długo nie dbam o zamówienie, czy zawsze byłoby korzystne korzystanie z równoległości? Można by pomyśleć, że szybciej dzieli się pracę na więcej rdzeni.

Czy są inne względy? Kiedy należy stosować strumień równoległy, a kiedy nie-równoległy?

(To pytanie ma na celu zainicjowanie dyskusji na temat tego, jak i kiedy używać strumieni równoległych, nie dlatego, że myślę, że zawsze korzystanie z nich jest dobrym pomysłem).

Matsemann
źródło

Odpowiedzi:

735

Strumień równoległy ma znacznie większy narzut w porównaniu do strumienia sekwencyjnego. Koordynacja wątków zajmuje dużo czasu. Domyślnie używałbym strumieni sekwencyjnych i rozważałbym te równoległe, jeśli

  • Mam do przetworzenia ogromną liczbę elementów (lub przetwarzanie każdego elementu wymaga czasu i jest możliwe do równoległego przetwarzania)

  • Przede wszystkim mam problem z wydajnością

  • Nie uruchomiłem jeszcze tego procesu w środowisku wielowątkowym (na przykład: w kontenerze internetowym, jeśli mam już wiele żądań do równoległego przetwarzania, dodanie dodatkowej warstwy równoległości w każdym żądaniu może mieć bardziej negatywne niż pozytywne skutki )

W twoim przykładzie wydajność i tak będzie zależała od zsynchronizowanego dostępu do System.out.println(), a uczynienie tego procesu równoległym nie przyniesie żadnego efektu, a nawet negatywnego.

Ponadto pamiętaj, że równoległe strumienie nie rozwiązują magicznie wszystkich problemów z synchronizacją. Jeśli predykaty i funkcje używane w tym procesie korzystają z zasobu współdzielonego, musisz upewnić się, że wszystko jest bezpieczne dla wątków. W szczególności efekty uboczne to rzeczy, o które naprawdę musisz się martwić, jeśli pójdziesz równolegle.

W każdym razie mierz, nie zgaduj! Tylko pomiar pokaże, czy równoległość jest tego warta, czy nie.

JB Nizet
źródło
18
Dobra odpowiedź. Dodałbym, że jeśli masz ogromną liczbę przedmiotów do przetworzenia, to tylko zwiększa problemy z koordynacją wątków; paralelizacja może być użyteczna tylko wtedy, gdy przetwarzanie każdego elementu wymaga czasu i jest możliwe do zrównoleglenia.
Warren Dew
16
@WarrenDew Nie zgadzam się. System Fork / Join po prostu podzieli N elementów na, na przykład, 4 części i przetworzy te 4 części kolejno. 4 wyniki zostaną wówczas zmniejszone. Jeśli masywność jest naprawdę ogromna, nawet w przypadku szybkiego przetwarzania jednostkowego, równoległość może być skuteczna. Ale jak zawsze musisz zmierzyć.
JB Nizet,
Mam kolekcję obiektów, które implementuję, Runnablektóre wywołuję, start()aby ich użyć, ponieważ czy mogę Threadsto zmienić na używanie strumieni Java 8 w trybie .forEach()równoległym? Wtedy będę mógł usunąć kod wątku z klasy. Ale czy są jakieś wady?
ycomp
1
@JBNizet Jeśli 4 części pocieszają się sekwencyjnie, to nie ma różnicy, że są równoległe do procesu lub sekwencyjnie wiesz? Proszę o wyjaśnienie
Harshana
3
@Harshana on oczywiście oznacza, że ​​elementy każdej z 4 części będą przetwarzane sekwencyjnie. Jednak same części mogą być przetwarzane jednocześnie. Innymi słowy, jeśli masz dostępnych kilka rdzeni procesora, każda część może działać na swoim własnym rdzeniu niezależnie od innych części, jednocześnie przetwarzając własne elementy sekwencyjnie. (UWAGA: Nie wiem, jeśli tak działają równoległe strumienie Java, po prostu próbuję wyjaśnić, co miał na myśli JBNizet.)
jutro,
258

Interfejs API Stream został zaprojektowany tak, aby ułatwić pisanie obliczeń w sposób oderwany od sposobu ich wykonywania, ułatwiając przełączanie między sekwencyjnym a równoległym.

Jednak tylko dlatego, że jest łatwy, nie oznacza, że ​​zawsze jest to dobry pomysł, a tak naprawdę, to zły pomysł, aby po prostu rzucić się .parallel()w to miejsce tylko dlatego, że możesz.

Po pierwsze, zauważ, że równoległość nie oferuje żadnych innych korzyści poza możliwością szybszego wykonania, gdy dostępnych jest więcej rdzeni. Wykonanie równoległe zawsze będzie wymagało więcej pracy niż wykonanie sekwencyjne, ponieważ oprócz rozwiązania problemu musi również wykonywać wysyłanie i koordynację pod-zadań. Mamy nadzieję, że szybciej uzyskasz odpowiedź, dzieląc pracę na wiele procesorów; to, czy tak się faktycznie dzieje, zależy od wielu rzeczy, w tym od wielkości zbioru danych, ilości obliczeń wykonywanych dla każdego elementu, charakteru obliczeń (w szczególności, czy przetwarzanie jednego elementu współdziała z przetwarzaniem innych?) , liczbę dostępnych procesorów i liczbę innych zadań konkurujących o te procesory.

Ponadto zauważ, że równoległość często ujawnia również niedeterminizm w obliczeniach, który często jest ukryty przez sekwencyjne implementacje; czasami nie ma to znaczenia lub można je złagodzić ograniczając związane z tym operacje (tj. operatory redukcji muszą być bezpaństwowcami i asocjatywne).

W rzeczywistości czasami paralelizm przyspieszy obliczenia, czasem nie, a czasem nawet spowolni. Najlepiej jest najpierw opracować przy użyciu wykonywania sekwencyjnego, a następnie zastosować równoległość gdzie

(A) wiesz, że tak naprawdę korzyści płyną ze zwiększonej wydajności i

(B) że faktycznie zapewni zwiększoną wydajność.

(A) to problem biznesowy, a nie techniczny. Jeśli jesteś ekspertem od wydajności, zwykle będziesz w stanie spojrzeć na kod i ustalić (B), ale inteligentną ścieżką jest pomiar. (I nawet nie zawracaj sobie głowy, dopóki nie przekonasz się o (A); jeśli kod jest wystarczająco szybki, lepiej zastosować cykle mózgowe w innym miejscu).

Najprostszym modelem wydajności dla równoległości jest model „NQ”, w którym N oznacza liczbę elementów, a Q jest obliczeniem na element. Ogólnie rzecz biorąc, potrzebujesz NQ produktu, aby przekroczyć pewien próg, zanim zaczniesz uzyskiwać korzyści z wydajności. W przypadku problemu o niskiej wartości Q, takiego jak „zsumowanie liczb od 1 do N”, generalnie widać wartość progową między N = 1000 a N = 10000. W przypadku problemów z wyższym Q zobaczysz progi rentowności przy niższych progach.

Ale rzeczywistość jest dość skomplikowana. Tak więc, dopóki nie osiągniesz stanu eksperymentalnego, najpierw określ, kiedy sekwencyjne przetwarzanie faktycznie cię kosztuje, a następnie zmierz, czy równoległość pomoże.

Brian Goetz
źródło
18
W tym poście podano dalsze szczegóły dotyczące modelu NQ: gee.cs.oswego.edu/dl/html/StreamParallelGuidance.html
Pino
4
@specializt: przełączania strumienia z sekwencyjnym równoległych nie zmienić algorytm (w większości przypadków). Wspomniany tutaj determinizm dotyczy właściwości, na których mogą polegać Twoi (arbitralni) operatorzy (implementacja Stream nie może tego wiedzieć), ale oczywiście nie powinien na nim polegać. Tak próbowała powiedzieć ta część tej odpowiedzi. Jeśli zależy ci na regułach, możesz osiągnąć deterministyczny wynik, tak jak mówisz (w przeciwnym razie równoległe strumienie byłyby zupełnie bezużyteczne), ale istnieje również możliwość celowo dozwolonego niedeterminizmu, na przykład przy użyciu findAnyzamiast findFirst...
Holger
4
„Po pierwsze, zauważ, że równoległość nie oferuje żadnych innych korzyści niż możliwość szybszego wykonania, gdy dostępnych jest więcej rdzeni” - lub jeśli stosujesz akcję, która obejmuje IO (np myListOfURLs.stream().map((url) -> downloadPage(url))....).
Jules
6
@Pacerier To ładna teoria, ale niestety naiwna (na początek zapoznaj się z 30-letnią historią prób zbudowania kompilatorów z automatyczną równoległością). Ponieważ nie jest praktyczne odgadnięcie wystarczającej ilości czasu, aby nie drażnić użytkownika, gdy nieuchronnie popełniamy błąd, odpowiedzialne było po prostu pozwolić użytkownikowi powiedzieć, co chce. W większości sytuacji domyślna (sekwencyjna) jest właściwa i bardziej przewidywalna.
Brian Goetz
2
@Jules: Nigdy nie używaj równoległych strumieni dla IO. Są przeznaczone wyłącznie do operacji intensywnie wykorzystujących procesor. Używają równoległych strumieni ForkJoinPool.commonPool()i nie chcesz, aby blokowały Cię zadania.
R2C2
68

Patrzyłem jedną z prezentacji z Brian Goetz (Język Java Architect & specyfikacji dla ołowiu Lambda Expressions) . Wyjaśnia szczegółowo następujące 4 punkty, które należy rozważyć przed przystąpieniem do równoległości:

Koszty dzielenia / rozkładu
- Czasami dzielenie jest droższe niż wykonywanie pracy!
Koszty wysyłki / zarządzania
zadaniami - mogą wykonać dużo pracy w czasie potrzebnym na przekazanie pracy innemu wątkowi.
Koszty kombinacji wyników
- czasami kombinacja obejmuje kopiowanie dużej ilości danych. Na przykład dodawanie liczb jest tanie, a scalanie zestawów drogie.
Lokalizacja
- Słoń w pokoju. To ważna kwestia, której każdy może przegapić. Powinieneś rozważyć pominięcie pamięci podręcznej, jeśli procesor czeka na dane z powodu braków pamięci podręcznej, nic nie zyskasz przez równoległość. Dlatego źródła oparte na macierzach najlepiej zrównoleglają się najlepiej, gdy kolejne indeksy (w pobliżu bieżącego indeksu) są buforowane i istnieje mniejsze prawdopodobieństwo, że procesor odczuje brak pamięci podręcznej.

Wspomina także o stosunkowo prostej formule, aby określić szansę na równoległe przyspieszenie.

Model NQ :

N x Q > 10000

gdzie
N = liczba elementów danych
Q = ilość pracy na element

Ram Patra
źródło
13

JB uderzył w gwóźdź. Jedyne, co mogę dodać, to to, że Java 8 nie wykonuje czystego przetwarzania równoległego, robi parakwencjalne . Tak, napisałem ten artykuł i robię F / J od trzydziestu lat, więc rozumiem ten problem.

edharned
źródło
10
Strumieni nie można iterować, ponieważ strumienie wykonują iterację wewnętrzną zamiast zewnętrznej. To zresztą cały powód strumieni. Jeśli masz problemy z pracą naukową, programowanie funkcjonalne może nie być dla Ciebie. Programowanie funkcjonalne === matematyka === akademickie. I nie, J8-FJ nie jest zepsuty, po prostu większość ludzi nie czyta podręcznika f ******. Dokumenty java mówią bardzo wyraźnie, że nie jest to równoległe środowisko wykonywania. To jest cały powód tego, co dotyczy spliteratora. Tak, jest akademicki, tak, działa, jeśli wiesz, jak go używać. Tak, powinno być łatwiej używać niestandardowego
modułu wykonującego
1
Stream ma metodę iteratora (), więc możesz iterować je zewnętrznie, jeśli chcesz. Zrozumiałem, że nie implementują iteracji, ponieważ możesz użyć tego iteratora tylko raz i nikt nie może zdecydować, czy to jest w porządku.
Trejkaz
14
szczerze mówiąc: cały artykuł brzmi jak ogromny, wyszukany rant - i to w znacznym stopniu neguje jego wiarygodność ... zaleciłbym powtórzenie go ze znacznie mniej agresywnym tonem, w przeciwnym razie niewiele osób w ogóle będzie się starało go w pełni przeczytać ... im just sayan
specializt
Kilka pytań dotyczących twojego artykułu ... po pierwsze, dlaczego najwyraźniej utożsamiasz zrównoważone struktury drzew z ukierunkowanymi wykresami acyklicznymi? Tak, zrównoważone drzewa DAG, ale podobnie jak listy połączone i prawie każda obiektowa struktura danych inna niż tablice. Ponadto, gdy mówisz, że rekurencyjny rozkład działa tylko na zrównoważonych strukturach drzew i dlatego nie ma znaczenia komercyjnego, jak uzasadniasz to twierdzenie? Wydaje mi się (co prawda bez dogłębnego zbadania problemu), że powinien on równie dobrze działać na strukturach bazujących na macierzach, np . ArrayList/ HashMap.
Jules
1
Wątek pochodzi z 2013 roku, od tego czasu wiele się zmieniło. Ta sekcja dotyczy komentarzy, a nie szczegółowych odpowiedzi.
edharned
3

Inne odpowiedzi obejmowały już profilowanie, aby uniknąć przedwczesnej optymalizacji i kosztów ogólnych w przetwarzaniu równoległym. Ta odpowiedź wyjaśnia idealny wybór struktur danych do równoległego przesyłania strumieniowego.

Z reguły wzrost wydajności od równoległości są najlepsze na strumieniach nad ArrayList, HashMap, HashSet, i ConcurrentHashMapwystąpień; tablice; intzakresy; i longzakresy. Wspólne dla tych struktur danych jest to, że wszystkie można dokładnie i tanio podzielić na podzakresy o dowolnych pożądanych rozmiarach, co ułatwia podział pracy na równoległe wątki. Abstrakcją używaną przez bibliotekę strumieni do wykonania tego zadania jest spliterator, który jest zwracany przez spliteratormetodę na Streami Iterable.

Innym ważnym czynnikiem, który łączy wszystkie te struktury danych jest to, że zapewniają one dobrą do doskonałej lokalizacji odniesienia, gdy są przetwarzane sekwencyjnie: odniesienia do elementów sekwencyjnych są przechowywane razem w pamięci. Obiekty, do których odwołują się te odniesienia, mogą nie znajdować się blisko siebie w pamięci, co zmniejsza lokalizację odniesienia. Lokalizacja odniesienia okazuje się być niezwykle ważna dla równoległych operacji masowych: bez niej wątki spędzają dużo czasu bezczynnie, czekając na przesłanie danych z pamięci do pamięci podręcznej procesora. Struktury danych z najlepszą lokalizacją odniesienia to prymitywne tablice, ponieważ same dane są przechowywane w pamięci w sposób ciągły.

Źródło: Przedmiot nr 48 Zachowaj ostrożność podczas tworzenia równoległych strumieni, skuteczna Java 3e autorstwa Joshua Blocha

ruhong
źródło
2

Nigdy nie równolegle nieskończonego strumienia z ograniczeniem. Oto co się dzieje:

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

Wynik

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

To samo, jeśli używasz .limit(...)

Objaśnienie tutaj: Java 8, użycie .parallel w strumieniu powoduje błąd OOM

Podobnie nie używaj równolegle, jeśli strumień jest uporządkowany i zawiera znacznie więcej elementów niż chcesz przetworzyć, np

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

Może to działać znacznie dłużej, ponieważ wątki równoległe mogą działać na wielu zakresach liczb zamiast kluczowych 0-100, co powoduje, że zajmuje to bardzo dużo czasu.

tkruse
źródło