Java 8: Leistung von Streams gegen Sammlungen

140

Ich bin neu in Java 8. Ich kenne die API noch nicht genau, aber ich habe einen kleinen informellen Benchmark erstellt, um die Leistung der neuen Streams-API mit den guten alten Sammlungen zu vergleichen.

Der Test besteht darin, eine Liste von zu filtern Integerund für jede gerade Zahl die Quadratwurzel zu berechnen und in einem Ergebnis Listvon zu speichern Double.

Hier ist der Code:

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

Und hier sind die Ergebnisse für eine Dual-Core-Maschine:

    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)

Für diesen speziellen Test sind Streams ungefähr doppelt so langsam wie Sammlungen, und Parallelität hilft nicht (oder verwende ich sie falsch?).

Fragen:

  • Ist dieser Test fair? Habe ich einen Fehler gemacht?
  • Sind Streams langsamer als Sammlungen? Hat jemand einen guten formalen Maßstab dafür gesetzt?
  • Welchen Ansatz sollte ich anstreben?

Aktualisierte Ergebnisse.

Ich habe den Test 1k Mal nach dem Aufwärmen der JVM (1k Iterationen) ausgeführt, wie von @pveentjer empfohlen:

    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)

In diesem Fall sind Streams leistungsfähiger. Ich frage mich, was in einer App zu beobachten wäre, in der die Filterfunktion zur Laufzeit nur ein- oder zweimal aufgerufen wird.

Herr Smith
quelle
1
Hast du es IntStreamstattdessen mit einem versucht ?
Mark Rotteveel
2
Können Sie bitte richtig messen? Wenn Sie nur einen Lauf ausführen, sind Ihre Benchmarks natürlich deaktiviert.
Skiwi
2
@MisterSmith Können wir etwas Transparenz darüber haben, wie Sie Ihre JVM aufgewärmt haben, auch mit 1K-Tests?
Skiwi
1
Und für diejenigen, die daran interessiert sind, korrekte Mikrobenchmarks zu schreiben, ist hier die Frage: stackoverflow.com/questions/504103/…
Mister Smith
2
@assylias Using toListsollte parallel ausgeführt werden, auch wenn es in einer nicht threadsicheren Liste erfasst wird , da die verschiedenen Threads vor dem Zusammenführen in threadbeschränkten Zwischenlisten erfasst werden.
Stuart Marks

Antworten:

192
  1. Stop mit LinkedListfür alles andere als schwer von der Mitte der Liste zu entfernen mit Iterator.

  2. Hören Sie auf, Benchmarking-Code von Hand zu schreiben, und verwenden Sie JMH .

Richtige Benchmarks:

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

Ergebnis:

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

Genau wie ich erwartet hatte, ist die Stream-Implementierung ziemlich langsamer. JIT ist in der Lage, alle Lambda-Inhalte zu integrieren, produziert jedoch keinen so präzisen Code wie die Vanille-Version.

Im Allgemeinen sind Java 8-Streams keine Zauberei. Sie konnten bereits gut implementierte Dinge nicht beschleunigen (wahrscheinlich mit einfachen Iterationen oder Java 5-Anweisungen für jede Anweisung, die durch Iterable.forEach()und Collection.removeIf()Aufrufe ersetzt wurden). Bei Streams geht es mehr um Codierungskomfort und -sicherheit. Komfort - Geschwindigkeitskompromiss funktioniert hier.

leventov
quelle
2
Vielen Dank, dass Sie sich die Zeit genommen haben, dies zu überprüfen. Ich denke nicht, dass das Ändern von LinkedList für ArrayList irgendetwas ändern würde, da beide Tests dazu beitragen sollten, dass die Zeiten nicht beeinflusst werden sollten. Könnten Sie bitte die Ergebnisse erklären? Es ist schwer zu sagen, was Sie hier messen (Einheiten sagen ns / op, aber was wird als op angesehen?).
Mister Smith
52
Ihre Schlussfolgerung zur Leistung ist zwar gültig, aber übertrieben. Es gibt viele Fälle, in denen der Stream-Code schneller als der iterative Code ist, hauptsächlich weil die Zugriffskosten pro Element bei Streams günstiger sind als bei einfachen Iteratoren. In vielen Fällen entspricht die Streams-Version etwas, das der handgeschriebenen Version entspricht. Natürlich steckt der Teufel im Detail; Jedes Codebit kann sich anders verhalten.
Brian Goetz
26
@BrianGoetz, könnten Sie bitte Anwendungsfälle angeben, wenn Streams schneller sind?
Alexandr
1
In der letzten Version von FMH: Verwenden Sie @Benchmarkanstelle von@GenerateMicroBenchmark
pdem
3
@BrianGoetz, Könnten Sie Anwendungsfälle angeben, wenn Streams schneller sind?
Kiltek
17

1) Mit Ihrem Benchmark sehen Sie eine Zeit von weniger als 1 Sekunde. Das bedeutet, dass Nebenwirkungen einen starken Einfluss auf Ihre Ergebnisse haben können. Also habe ich deine Aufgabe zehnmal erhöht

    int max = 10_000_000;

und lief Ihre Benchmark. Meine Ergebnisse:

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)

ohne edit ( int max = 1_000_000) Ergebnisse waren

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)

Es ist wie bei Ihren Ergebnissen: Der Stream ist langsamer als die Sammlung. Fazit: viel Zeit für die Stream-Initialisierung / die Übertragung von Werten aufgewendet.

2) Nach dem Erhöhen wurde der Task-Stream schneller (das ist in Ordnung), aber der parallele Stream blieb zu langsam. Was ist los mit dir? Hinweis: Sie haben collect(Collectors.toList())in Ihrem Befehl. Das Sammeln in einer einzigen Sammlung führt im Wesentlichen zu Leistungsengpässen und Overhead bei gleichzeitiger Ausführung. Es ist möglich, die relativen Gemeinkosten durch Ersetzen zu schätzen

collecting to collection -> counting the element count

Für Streams kann es von gemacht werden collect(Collectors.counting()). Ich habe Ergebnisse:

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)

Das ist eine große Aufgabe! ( int max = 10000000) Schlussfolgerung: Das Sammeln von Gegenständen zur Sammlung dauerte die meiste Zeit. Der langsamste Teil ist das Hinzufügen zur Liste. Übrigens wird einfach ArrayListfür verwendet Collectors.toList().

Sergey Fedorov
quelle
Sie müssen diesen Test mit einem Mikrobenchmark versehen, was bedeutet, dass er zuerst häufig aufgewärmt und dann häufig ausgeführt und gemittelt werden sollte.
Skiwi
@skiwi sicher, Sie haben Recht, vor allem, weil es große Abweichungen in den Messungen gibt. Ich habe nur grundlegende Untersuchungen durchgeführt und tue nicht so, als wären die Ergebnisse genau.
Sergey Fedorov
Die JIT im Servermodus wird nach 10.000 Ausführungen aktiviert. Und dann dauert es einige Zeit, um den Code zu kompilieren und auszutauschen.
Pveentjer
Zu diesem Satz: " Sie haben collect(Collectors.toList())einen Befehl in Ihrem Befehl, dh es kann vorkommen, dass Sie eine einzelne Sammlung von vielen Threads adressieren müssen. " Ich bin mir fast sicher, dass mehrere Sammelinstanzen parallel toListerfasst werden . Erst als letzter Schritt in der Sammlung werden die Elemente in eine Liste übertragen und dann zurückgegeben. Es sollte also keinen Synchronisationsaufwand geben. Aus diesem Grund haben Sammler sowohl eine Lieferanten- als auch eine Akkumulator- und eine Kombiniererfunktion. (Es könnte natürlich aus anderen Gründen langsam sein.)
Lii
@Lii Ich denke hier genauso über die collectImplementierung. Am Ende sollten jedoch mehrere Listen zu einer einzigen zusammengeführt werden, und es sieht so aus, als ob das Zusammenführen in einem bestimmten Beispiel die schwerste Operation ist.
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);
}

Ich ändere den Code ein wenig, lief auf meinem MacBook Pro, das 8 Kerne hat, ich habe ein vernünftiges Ergebnis erhalten:

Sammlungen: Verstrichene Zeit: 1522036826 ns (1,522037 Sekunden)

Streams: Verstrichene Zeit: 4315833719 ns (4,315834 Sekunden)

Parallele Streams: Verstrichene Zeit: 261152901 ns (0,261153 Sekunden)

Mellon
quelle
Ich denke, Ihr Test ist fair, Sie brauchen nur eine Maschine mit mehr CPU-Kernen.
Mellon
3

Für das, was Sie versuchen, würde ich sowieso keine normalen Java-APIs verwenden. Es gibt eine Menge Boxen / Unboxen, also gibt es einen enormen Leistungsaufwand.

Persönlich denke ich, dass viele APIs Mist sind, weil sie viel Objektmüll erzeugen.

Versuchen Sie, ein primitives Array von double / int zu verwenden, und versuchen Sie es mit einem einzigen Thread, um die Leistung zu ermitteln.

PS: Vielleicht möchten Sie sich JMH ansehen, um den Benchmark durchzuführen. Es behebt einige der typischen Fallstricke wie das Aufwärmen der JVM.

pveentjer
quelle
LinkedLists sind noch schlechter als ArrayLists, da Sie alle Knotenobjekte erstellen müssen. Der Mod-Operator ist auch hundeschwach. Ich glaube so etwas wie 10/15 Zyklen + es leert die Anweisungspipeline. Wenn Sie eine sehr schnelle Division durch 2 durchführen möchten, verschieben Sie einfach das Bit Nummer 1 nach rechts. Dies sind grundlegende Tricks, aber ich bin sicher, dass es im Modus erweiterte Tricks gibt, um die Dinge zu beschleunigen, aber diese sind wahrscheinlich problemspezifischer.
Pveentjer
Ich bin mir des Boxens bewusst. Dies ist nur ein informeller Maßstab. Die Idee ist, sowohl in den Sammlungen als auch in den Streams die gleiche Menge an Boxen / Unboxing zu haben.
Mister Smith
Zuerst würde ich sicherstellen, dass es kein Messfehler ist. Versuchen Sie, den Benchmark einige Male auszuführen, bevor Sie den eigentlichen Benchmark durchführen. Dann haben Sie zumindest die JVM-Aufwärmphase aus dem Weg und der Code ist korrekt JITTED. Ohne dies machen Sie wahrscheinlich die falschen Schlussfolgerungen.
Pveentjer
Ok, ich werde nach deinem Rat neue Ergebnisse veröffentlichen. Ich habe mir JMH angesehen, aber es erfordert Maven und die Konfiguration dauert einige Zeit. Danke trotzdem.
Mister Smith
Ich denke, es ist am besten, nicht an Benchmark-Tests in Bezug auf "Für das, was Sie versuchen zu tun" zu denken. Das heißt, normalerweise sind diese Arten von Übungen so vereinfacht, dass sie demonstrierbar sind, aber so komplex, dass sie so aussehen, als könnten / sollten sie vereinfacht werden.
Ryvantage