Java 8: wydajność strumieni i kolekcji

140

Jestem nowy w Javie 8. Nadal nie znam dokładnie API, ale zrobiłem mały nieformalny test porównawczy, aby porównać wydajność nowego API Streams ze starymi, dobrymi kolekcjami.

Badanie polega na filtrowanie listy Integeri dla każdego numeru nawet obliczyć pierwiastek kwadratowy i przechowywanie go w rezultacie Listo Double.

Oto kod:

    public static void main(String[] args) {
        //Calculating square root of even numbers from 1 to N       
        int min = 1;
        int max = 1000000;

        List<Integer> sourceList = new ArrayList<>();
        for (int i = min; i < max; i++) {
            sourceList.add(i);
        }

        List<Double> result = new LinkedList<>();


        //Collections approach
        long t0 = System.nanoTime();
        long elapsed = 0;
        for (Integer i : sourceList) {
            if(i % 2 == 0){
                result.add(Math.sqrt(i));
            }
        }
        elapsed = System.nanoTime() - t0;       
        System.out.printf("Collections: Elapsed time:\t %d ns \t(%f seconds)%n", elapsed, elapsed / Math.pow(10, 9));


        //Stream approach
        Stream<Integer> stream = sourceList.stream();       
        t0 = System.nanoTime();
        result = stream.filter(i -> i%2 == 0).map(i -> Math.sqrt(i)).collect(Collectors.toList());
        elapsed = System.nanoTime() - t0;       
        System.out.printf("Streams: Elapsed time:\t\t %d ns \t(%f seconds)%n", elapsed, elapsed / Math.pow(10, 9));


        //Parallel stream approach
        stream = sourceList.stream().parallel();        
        t0 = System.nanoTime();
        result = stream.filter(i -> i%2 == 0).map(i -> Math.sqrt(i)).collect(Collectors.toList());
        elapsed = System.nanoTime() - t0;       
        System.out.printf("Parallel streams: Elapsed time:\t %d ns \t(%f seconds)%n", elapsed, elapsed / Math.pow(10, 9));      
    }.

A oto wyniki dla maszyny dwurdzeniowej:

    Collections: Elapsed time:        94338247 ns   (0,094338 seconds)
    Streams: Elapsed time:           201112924 ns   (0,201113 seconds)
    Parallel streams: Elapsed time:  357243629 ns   (0,357244 seconds)

W tym konkretnym teście strumienie są około dwa razy wolniejsze niż kolekcje, a równoległość nie pomaga (lub używam go w niewłaściwy sposób?).

Pytania:

  • Czy ten test jest sprawiedliwy? Czy popełniłem jakiś błąd?
  • Czy strumienie są wolniejsze niż zbiory? Czy ktoś zrobił w tej sprawie dobry formalny punkt odniesienia?
  • Do jakiego podejścia powinienem dążyć?

Zaktualizowane wyniki.

Przeprowadziłem test 1k razy po rozgrzewce JVM (1k iteracji), zgodnie z radą @pveentjer:

    Collections: Average time:      206884437,000000 ns     (0,206884 seconds)
    Streams: Average time:           98366725,000000 ns     (0,098367 seconds)
    Parallel streams: Average time: 167703705,000000 ns     (0,167704 seconds)

W tym przypadku strumienie są bardziej wydajne. Zastanawiam się, co można by zaobserwować w aplikacji, w której funkcja filtrująca jest wywoływana tylko raz lub dwa razy w czasie działania.

Panie Smith
źródło
1
czy próbowałeś IntStreamzamiast tego?
Mark Rotteveel
2
Czy możesz właściwie zmierzyć? Jeśli wszystko, co robisz, to jeden bieg, twoje testy porównawcze będą oczywiście wyłączone.
skiwi
2
@MisterSmith Czy możemy wyjaśnić, jak rozgrzałeś JVM, również za pomocą testów 1K?
skiwi
1
A dla tych, którzy są zainteresowani pisaniem poprawnych mikroznaków, oto pytanie: stackoverflow.com/questions/504103/ ...
Pan Smith
2
@assylias Używanie toListpowinno działać równolegle, nawet jeśli jest zbierane do listy, która nie jest bezpieczna dla wątków, ponieważ różne wątki będą gromadzić się na listach pośrednich ograniczonych wątkami przed scaleniem.
Stuart Marks

Odpowiedzi:

192
  1. Przestań używać LinkedListdo niczego poza ciężkim usuwaniem ze środka listy za pomocą iteratora.

  2. Przestań pisać ręcznie kod do testów porównawczych, użyj JMH .

Właściwe wzorce:

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(StreamVsVanilla.N)
public class StreamVsVanilla {
    public static final int N = 10000;

    static List<Integer> sourceList = new ArrayList<>();
    static {
        for (int i = 0; i < N; i++) {
            sourceList.add(i);
        }
    }

    @Benchmark
    public List<Double> vanilla() {
        List<Double> result = new ArrayList<>(sourceList.size() / 2 + 1);
        for (Integer i : sourceList) {
            if (i % 2 == 0){
                result.add(Math.sqrt(i));
            }
        }
        return result;
    }

    @Benchmark
    public List<Double> stream() {
        return sourceList.stream()
                .filter(i -> i % 2 == 0)
                .map(Math::sqrt)
                .collect(Collectors.toCollection(
                    () -> new ArrayList<>(sourceList.size() / 2 + 1)));
    }
}

Wynik:

Benchmark                   Mode   Samples         Mean   Mean error    Units
StreamVsVanilla.stream      avgt        10       17.588        0.230    ns/op
StreamVsVanilla.vanilla     avgt        10       10.796        0.063    ns/op

Tak jak się spodziewałem, implementacja strumienia jest dość wolniejsza. JIT jest w stanie wbudować wszystkie elementy lambda, ale nie tworzy tak idealnie zwięzłego kodu, jak wersja waniliowa.

Generalnie strumienie Java 8 nie są magiczne. Nie mogli przyspieszyć już dobrze zaimplementowanych rzeczy (prawdopodobnie z prostymi iteracjami lub instrukcjami for-each w Javie 5 zamienionymi na Iterable.forEach()i Collection.removeIf()wywołania). W strumieniach chodzi bardziej o wygodę i bezpieczeństwo kodowania. Wygoda - tu działa kompromis szybkości.

Leventov
źródło
2
Dzięki za poświęcenie czasu na wycenę. Nie sądzę, aby zmiana LinkedList na ArrayList cokolwiek zmieniła, ponieważ oba testy powinny dodać do tego, nie powinno to mieć wpływu na czasy. W każdym razie, czy mógłbyś wyjaśnić wyniki? Trudno powiedzieć, co tu mierzysz (jednostki mówią ns / op, ale co jest uważane za op?).
Mister Smith,
52
Twoje wnioski dotyczące wydajności są przesadzone. Istnieje wiele przypadków, w których kod strumienia jest szybszy niż kod iteracyjny, głównie dlatego, że koszty dostępu na element są tańsze w przypadku strumieni niż w przypadku zwykłych iteratorów. W wielu przypadkach wersja strumieniowa zawiera coś, co jest odpowiednikiem wersji napisanej ręcznie. Oczywiście diabeł tkwi w szczegółach; każdy fragment kodu może zachowywać się inaczej.
Brian Goetz
26
@BrianGoetz, czy możesz określić przypadki użycia, kiedy strumienie są szybsze?
Alexandr,
1
W ostatniej wersji FMH: użyj @Benchmarkzamiast@GenerateMicroBenchmark
pdem
3
@BrianGoetz, Czy możesz określić przypadki użycia, kiedy strumienie są szybsze?
kiltek
17

1) Korzystając z testu porównawczego, widzisz czas krótszy niż 1 sekunda. Oznacza to, że efekty uboczne mogą mieć silny wpływ na Twoje wyniki. Więc 10 razy zwiększyłem twoje zadanie

    int max = 10_000_000;

i przeprowadź test porównawczy. Moje wyniki:

Collections: Elapsed time:   8592999350 ns  (8.592999 seconds)
Streams: Elapsed time:       2068208058 ns  (2.068208 seconds)
Parallel streams: Elapsed time:  7186967071 ns  (7.186967 seconds)

bez edit ( int max = 1_000_000) wyniki były

Collections: Elapsed time:   113373057 ns   (0.113373 seconds)
Streams: Elapsed time:       135570440 ns   (0.135570 seconds)
Parallel streams: Elapsed time:  104091980 ns   (0.104092 seconds)

To jak Twoje wyniki: strumień jest wolniejszy niż zbieranie. Wniosek: zainicjowanie strumienia / przesłanie wartości zajęło dużo czasu.

2) Po zwiększeniu strumień zadań stał się szybszy (to OK), ale strumień równoległy pozostał zbyt wolny. Co jest nie tak? Uwaga: masz collect(Collectors.toList())w sobie dowództwo. Zbieranie do pojedynczej kolekcji zasadniczo wprowadza wąskie gardło wydajności i obciążenie w przypadku równoczesnego wykonywania. Możliwe jest oszacowanie względnego kosztu narzutów poprzez wymianę

collecting to collection -> counting the element count

W przypadku strumieni można to zrobić za pomocą collect(Collectors.counting()). Otrzymałem wyniki:

Collections: Elapsed time:   41856183 ns    (0.041856 seconds)
Streams: Elapsed time:       546590322 ns   (0.546590 seconds)
Parallel streams: Elapsed time:  1540051478 ns  (1.540051 seconds)

To duże zadanie! ( int max = 10000000) Wniosek: zbieranie przedmiotów do kolekcji zajęło większość czasu. Najwolniejsze jest dodawanie do listy. BTW, simple ArrayListjest używany do Collectors.toList().

Sergey Fedorov
źródło
Musisz zaznaczyć mikrobenchmark ten test, co oznacza, że ​​najpierw należy go wielokrotnie rozgrzewać, a następnie wykonywać wiele tmesów i uśredniać.
skiwi
@skiwi pewnie masz rację, zwłaszcza że są duże odchylenia w pomiarach. Zrobiłem tylko podstawowe badanie i nie udaję, że wyniki są dokładne.
Sergey Fedorov
JIT w trybie serwera uruchamia się po 10 tys. Uruchomień. Skompilowanie kodu i jego zamiana zajmuje trochę czasu.
pveentjer
O tym zdaniu: „ masz collect(Collectors.toList())w sobie polecenie, tj. Może zaistnieć sytuacja, gdy będziesz musiał adresować jedną kolekcję wieloma wątkami. ” Jestem prawie pewien, że toListzbiera się równolegle do kilku różnych instancji list. Dopiero jako ostatni krok w kolekcji elementy są przenoszone na jedną listę, a następnie zwracane. Więc nie powinno być narzutu synchronizacji. Dlatego zbieracze mają zarówno funkcję dostawcy, jak i sumatora. (Oczywiście może to być powolne z innych powodów).
Lii,
@Lii Tak samo myślę o collectimplementacji. Ale ostatecznie kilka list powinno zostać połączonych w jedną i wygląda na to, że scalanie jest najtrudniejszą operacją w podanym przykładzie.
Sergey Fedorov
4
    public static void main(String[] args) {
    //Calculating square root of even numbers from 1 to N       
    int min = 1;
    int max = 10000000;

    List<Integer> sourceList = new ArrayList<>();
    for (int i = min; i < max; i++) {
        sourceList.add(i);
    }

    List<Double> result = new LinkedList<>();


    //Collections approach
    long t0 = System.nanoTime();
    long elapsed = 0;
    for (Integer i : sourceList) {
        if(i % 2 == 0){
            result.add( doSomeCalculate(i));
        }
    }
    elapsed = System.nanoTime() - t0;       
    System.out.printf("Collections: Elapsed time:\t %d ns \t(%f seconds)%n", elapsed, elapsed / Math.pow(10, 9));


    //Stream approach
    Stream<Integer> stream = sourceList.stream();       
    t0 = System.nanoTime();
    result = stream.filter(i -> i%2 == 0).map(i -> doSomeCalculate(i))
            .collect(Collectors.toList());
    elapsed = System.nanoTime() - t0;       
    System.out.printf("Streams: Elapsed time:\t\t %d ns \t(%f seconds)%n", elapsed, elapsed / Math.pow(10, 9));


    //Parallel stream approach
    stream = sourceList.stream().parallel();        
    t0 = System.nanoTime();
    result = stream.filter(i -> i%2 == 0).map(i ->  doSomeCalculate(i))
            .collect(Collectors.toList());
    elapsed = System.nanoTime() - t0;       
    System.out.printf("Parallel streams: Elapsed time:\t %d ns \t(%f seconds)%n", elapsed, elapsed / Math.pow(10, 9));      
}

static double doSomeCalculate(int input) {
    for(int i=0; i<100000; i++){
        Math.sqrt(i+input);
    }
    return Math.sqrt(input);
}

Trochę zmieniam kod, uruchomiłem na moim Mac Book Pro z 8 rdzeniami, uzyskałem rozsądny wynik:

Kolekcje: czas, który upłynął: 1522036826 ns (1,522037 sekund)

Strumienie: czas, który upłynął: 4315833719 ns (4,315834 sekund)

Strumienie równoległe: czas, który upłynął: 261152901 ns (0,261153 sekundy)

Mellon
źródło
Myślę, że twój test jest uczciwy, potrzebujesz tylko maszyny z większą liczbą rdzeni procesora.
Mellon
3

Do tego, co próbujesz zrobić, i tak nie użyłbym zwykłych interfejsów API Java. Jest mnóstwo boksu / unboxingu, więc jest ogromny narzut wydajności.

Osobiście uważam, że wiele zaprojektowanych API to bzdury, ponieważ tworzą dużo zaśmiecania obiektów.

Spróbuj użyć prymitywnych tablic double / int i spróbuj zrobić to w jednym wątku i zobacz, jaka jest wydajność.

PS: Możesz rzucić okiem na JMH, aby zająć się wykonaniem testu porównawczego. Rozwiązuje niektóre typowe pułapki, takie jak rozgrzewanie JVM.

pveentjer
źródło
LinkedLists są jeszcze gorsze niż ArrayLists, ponieważ musisz utworzyć wszystkie obiekty węzłów. Operator modów również jest powolny. Uważam, że około 10/15 cykli + opróżnia potok instrukcji. Jeśli chcesz zrobić bardzo szybkie dzielenie przez 2, po prostu przesuń liczbę o 1 bit w prawo. To są podstawowe sztuczki, ale jestem pewien, że istnieją zaawansowane triki w trybie, które przyspieszają działanie, ale prawdopodobnie są one bardziej specyficzne dla problemu.
pveentjer
Jestem świadomy boksu. To tylko nieformalny punkt odniesienia. Chodzi o to, aby mieć taką samą ilość pudełek / rozpakowywania zarówno w testach kolekcji, jak i strumieni.
Pan Smith
Najpierw upewnię się, że nie jest to błąd pomiaru. Spróbuj uruchomić test kilka razy, zanim zrobisz prawdziwy test porównawczy. Wtedy przynajmniej rozgrzewka JVM jest na uboczu, a kod jest poprawnie JITTED. Bez tego prawdopodobnie wyciągniesz błędne wnioski.
pveentjer
Ok, opublikuję nowe wyniki zgodnie z twoją radą. Przyjrzałem się JMH, ale wymaga Mavena i konfiguracja zajmuje trochę czasu. W każdym razie dzięki.
Pan Smith
Myślę, że najlepiej jest unikać myślenia o testach porównawczych w kategoriach „Za to, co próbujesz zrobić”. tj. zazwyczaj tego typu ćwiczenia są na tyle uproszczone, że można je zademonstrować, ale na tyle złożone, że wyglądają, jakby można je było uprościć.
ryvantage