Iterierst du noch, oder streamst du schon?

Iteratoren und Streams in Java: Gemeinsamkeiten und Unterschiede
7
Sep

Iterierst du noch, oder streamst du schon?

Bei einer Diskussion mit Kollegen kam die Frage auf, worin sich Streams und Iteratoren in Java eigentlich unterscheiden. Man sollte denken, dass beide Ansätze dazu gedacht sind, Dinge wiederholt auszuführen, und dass Streams nur eine komfortablere Art und Weise sind, den Algorithmus auszudrücken. Tatsächlich sind sich die beiden APIs in manchen Dingen ähnlich, in anderer Hinsicht unterscheiden sie sich jedoch.

Ziel dieses Artikels ist es, die beiden Ansätze zu vergleichen, zum einen mit Blick auf die Ergonomie (oder die „Schönheit“, wenn man es ehrlich formuliert) eines Beispiels, zum anderen auf funktionale Unterschiede bei der Parallelisierung und Mutabilität.

Als Diskussionsgrundlage verwenden wir die Implementierung einer paginierten Datenbankabfrage sowohl via Stream als auch via Iterator, damit wir die grundlegenden Unterschiede sehen können. Bei Paginierung werden die Ergebnisse nicht auf einmal aus der Datenbank geholt, sondern „Stück für Stück“. Wir kennen dieses Vorgehen aus der Google-Suche, auch wenn ich normalerweise alle Ergebnisse nach Seite eins ignoriere.

Paginierung hat den Vorteil, dass große Ergebnismengen verarbeitet werden können, ohne die Daten komplett in den Arbeitsspeicher zu laden. Nach dem Verarbeiten eines Teilstücks können die verarbeiteten Daten verworfen und das nächste Teilstück kann verarbeitet werden. Als Beispiel sei folgende Tabelle angegeben, bei der wir die Summe der Werte bestimmen wollen (und das zum Wohle des Beispiels nicht in der Datenbank tun). Stellvertretend soll dies für kompliziertere Operationen stehen, die nicht einfach in der Datenbank ausgeführt werden können. Tabelle 1 zeigt ein paar Zeilen Datenbank für unsere Demozwecke. Wie durch die Punkte impliziert, ist die eigentliche Datenbank natürlich deutlich größer.

ID Wert
1 15
2 24
3 45
4 38

Tabelle 1: Beispieldatenbank

Unpaginiert würden wir die gesamte Datenbank abfragen und die Werte addieren. Das würde bedeuten, dass wir die komplette lange Liste im Hauptspeicher halten müssen. Bei einer paginierten Abfrage würden wir immer z. B. zehn Werte abfragen, summieren und dann die nächsten zehn Werte abfragen und so weiter. Bei einer paginierten Vorgehensweise müssen wir also nie alle Daten vorhalten und können auch Datenmengen verarbeiten, die nicht in den Hauptspeicher passen. Natürlich geht mit diesem Vorgehen auch ein gewisser Overhead einher, weil ja wiederholt Abfragen an die Datenbank geschickt werden und somit mehr Zeit für Roundtrips zwischen Server und Datenbank verbraucht wird.

In SQL können wir mit den LIMIT– und OFFSET-Parametern [1] paginieren. Wir fragen also erst die ersten zehn Werte ab (LIMIT 10 OFFSET 0), dann die nächsten zehn (LIMIT 10 OFFSET 10) und so weiter. Nachfolgend die Query für unsere Beispieldatenbank:

SELECT wert FROM t1 ORDER BY id OFFSET 0 LIMIT 10;

Wichtig ist hier, dass die Abfrage geordnet ist, da sonst die Reihenfolge der Ergebnisse nicht definiert ist und wir ohne konsistente Reihenfolge keine korrekte Paginierung erhalten.

Es gibt bessere Wege zur Paginierung, diese sind jedoch komplizierter zu implementieren, und stärker vom verwendeten Datenbanksystem abhängig: Eine Paginierung via Cursor [2] oder Keyset Pagination [3] wird meistens vorzuziehen sein, die Implementierung würde jedoch den Rahmen dieses Artikels sprengen. Das generelle Schema der Iteration bleibt jedoch erhalten und die Implementierung einer paginierten Abfrage wäre ähnlich.

Verschaffen Sie sich den Zugang zur Java-Welt mit unserem kostenlosen Newsletter!

Implementierung der Paginierung

Das Ziel unserer Implementierung ist es, eine Query mit großer Ergebnismenge so auszuführen, dass der Speicherbedarf der Lösung konstant ist, d. h. zu keiner Zeit mehr als x Ergebnisse vorgehalten werden, egal wie groß die gesamte Ergebnismenge ist. Der Benutzer sollte von dieser Eigenschaft nichts merken und sollte mit dem Ergebnis-Stream bzw. Iterator umgehen können wie mit einem „normalen“ Stream oder Iterator. Natürlich kann man das von Hand implementieren, aber Java gibt einem mächtige APIs an die Hand, damit man das nicht tun muss. Also ab in den Code!

Paginierung mit Streams

Zuerst betrachten wir die Streams-Implementierung, in der natürlich völlig unvoreingenommenen Ansicht des Autors die elegantere und kürzere Lösung (Listing 1).

List<Result> runQuery(int offset) {...}; // Dummyimplementierung
 
Stream.iterate(0, (skip) -> skip + 10)
  .map(
    (offset) ->
    runQuery(offset))
  .takeWhile((result) -> result.size() > 0)
  .flatMap(Collection::stream)
  .mapToInt((result) -> (int)result.get("wert"))
  .sum();

Was tun wir? Zuerst erzeugen wir in Zeile 1 einen unendlichen Stream [4] von Zahlen, die mögliche Offsets angeben. Das tun wir, indem wir die Funktion x + 10 iterativ anwenden. Das erste Ergebnis ist 0 (das erste Argument von iterate), wir addieren 10 drauf, das Ergebnis ist 10, wir addieren 10, das Ergebnis ist 20, und so weiter. Was machen wir nun mit diesen Offsets?

Wir mappen unsere Query über die Offsets und geben die Ergebnisse zurück. Das bedeutet, dass wir unsere Query mit jedem Offset einmal ausführen – natürlich nicht sofort, sonst hätten wir eine unendliche Schleife. takeWhile() macht unseren Stream jetzt verwendbar: Der Integer-Stream ist unendlich lang, und der gemappte Stream ist natürlich auch unendlich lang. Wir unterbrechen die Unendlichkeit jetzt mit takeWhile(), das so lange Elemente aus dem Stream entnimmt, wie es die Bedingung sagt. Unsere Bedingung ist „Query hat mehr als 0 Ergebnisse“. Wenn eine Query keine Ergebnisse mehr hat, sind im Moment keine Daten verfügbar, die wir zurückgeben können. Wir können also aufhören, unseren Stream zu lesen, sobald das erste Mal eine leere Ergebnisliste zurückkommt. Wir haben jetzt eine Liste von Ergebnislisten – diese machen wir mit flatMap() zu einer Liste von Ergebnissen, operieren mit mapToInt() unseren Wert aus dem Ergebnis und summieren ihn mit sum().

Paginierung mit Iteratoren

Listing 2 zeigt zum Vergleich die Paginierung mittels Iterator-API. Was tun wir mit diesem vielen Code?

List<Result> runQuery(int offset) {...}; // Dummyimplementierung
 
var iterator = new Iterator<Result>() {
  private Iterator<Result> subIter = runQuery(0).iterator();
  private int offset = 0;
  @Override
  public boolean hasNext() {
    if (subIter.hasNext())
      return true;
    offset += 10;
    subIter = runQuery(offset).iterator();
    return subIter.hasNext();
  }
  @Override
  public Integer next() {
    return subIter.next();
  }
};
 
var sum = 0;
while (iterator.hasNext())
  sum += iterator.next().getValue("wert");

Wir erzeugen einen neuen Iterator, der unsere Query paginiert. Voraussetzung (wie beim Streams-Beispiel oben) ist natürlich, dass die Query einen Offset-Parameter unterstützt und eine Liste an Ergebnissen zurückliefert. Wir bauen uns dann einen neuen Iterator, der die Query paginiert ausführt. Iteratoren [5] benötigen zwei Methoden, hasNext() und next()hasNext() gibt genau dann true zurück, wenn der Iterator noch Elemente hat, next() gibt ein Element zurück, wenn es noch eins gibt, ansonsten wirft es eine NoSuchElementException. Wir implementieren hasNext() jetzt einfach über einen unterliegenden Iterator auf unserer Queryliste. Wenn diese Liste noch Ergebnisse enthält, können wir einfach auf diesem Iterator next() aufrufen. Wenn die Liste keine Ergebnisse mehr enthält, müssen wir uns eine neue Liste holen. Wir geben dann hasNext() der neuen Liste zurück. Wenn die neue Liste leer ist, ist unsere Iteration zu Ende, wenn noch Elemente enthalten sind, können wir weitermachen. Die next()-Implementierung ist entsprechend einfach, weil hasNext() sich um den unterliegenden Iterator kümmert und nur true zurückgibt, wenn dieser weiter iterierbar ist.

Ergonomie

An diesem Beispiel kann man meiner Meinung nach die ästhetischen Unterschiede zwischen Iteratoren und Streams sehen: Der Stream-Code ist sehr viel flüssiger und erlaubt es mir, über die Daten und Operationen nachzudenken. Beim Iteratorenbeispiel verschwindet die eigentliche Logik hinter einem Wald aus Boilerplate, anonymen Klassen, while-Schleifen und anderem. Ergonomie also: Streams: 1, Iteratoren 0!

Man muss natürlich anmerken, dass das Beispiel klein und recht gut auf Streams zugeschnitten ist. Mit externen Bibliotheken, wie z. B. Googles Guava [6], kann man auch Iteratoren besser handhabbar machen, sodass das Beispiel dann fast gleich ausschaut.

Ein anderer Gesichtspunkt ist die Kontrolle über die Evaluation: Streams sind lazy, d. h., die „intermediate“-Operationen eines Streams werden erst dann ausgeführt, wenn eine „terminale“ Operation auf dem Stream aufgerufen wird. Wir haben das im Beispiel oben gesehen, bei dem die Map über den Stream erst aufgerufen wird, wenn sum() ausgeführt wird. Bei Iteratoren kann man meistens davon ausgehen, dass „teurer“ Code im next()-Aufruf ausgeführt wird. Bei Streams weiß man das nicht so genau, und man sollte sich genau überlegen, wann man den Stream konsumiert. Meine persönliche Meinung ist, dass ich Streams für einfache Transformationen bevorzuge, wenn funktionale Unterschiede keine Rolle spielen.

Es gibt natürlich auch noch andere Unterschiede zwischen Streams und Iteratoren. Über diese lässt sich zwar nicht so trefflich diskutieren wie über die Codeschönheit, relevant sind sie jedoch allemal. Wir gehen deshalb auch noch auf die Unterschiede bei Mutabilität und Parallelisierung von Streams und Iteratoren ein.

Parallelisierung

Im Gegensatz zu Iteratoren sind Streams einfach parallelisierbar. Um einen Iterator zu parallelisieren, muss man sich selbst mit Thread Pools und Nebenläufigkeit herumschlagen. Bei Streams kann ich statt stream() einfach parallelStream() aufrufen und erhalte eine parallelisierbare Variante meiner Transformation.

Hierbei muss man allerdings gut darauf achten, welche Operationen man auf dem Stream ausführt und welche Reihenfolge der Stream-Elemente man erwartet. Ein Stream kann geordnet oder ungeordnet sein, je nach Quelle des Streams. So gibt List.of(1, 2, 3, 4).stream().forEachOrdered(System.out::println) stets 1, 2, 3, 4 aus, Set.of(1, 2, 3, 4).stream().forEachOrdered(System.out::println) gibt die Elemente in einer zufälligen Reihenfolge aus. Parallelismus ändert die Sortierung des Streams nicht, solange ich nicht unordered() aufrufe. Es ändert jedoch die Reihenfolge, in der Operationen angewendet werden.

ForEach ist hier ein Sonderfall, da es bei parallelen Streams explizit die Sortierung des Streams ignoriert, egal ob ordered oder unordered. List.of(1, 2, 3).stream().parallel().forEach(System.out::println) kann also die Zahlen in einer beliebigen Reihenfolge ausgeben.

Ich muss also darauf achten, dass die Lambdas, die ich in meiner Pipeline verwende, den Anforderungen des API gerecht werden. So produziert zum Beispiel der Code in Listing 3 auf parallelen und nichtparallelen Streams unterschiedliche Ergebnisse.

List.of(1, 2, 3).stream().reduce(0, (x, y) -> x - y)
== (((0 - 1) - 2) - 3)
== -6;
List.of(1, 2, 3).parallelStream().reduce(0, (x, y) -> x - y)
== (0 - (1 - (2 - 3)))
== -2;
Verschaffen Sie sich den Zugang zur Java-Welt mit unserem kostenlosen Newsletter!

Beide Ergebnisse sind Zufall: reduce gibt keine Reihenfolge vor, in der Operationen ausgeführt werden, und hier kann man diesen Unterschied sehen. In Listing 3 kommt das davon, dass 0 keine Identität von  ist (0 – x ≠ x) und dass – nicht assoziativ ist ((x – y) – z ≠ x – (y – z)). Beide Bedingungen sind in der Dokumentation von reduce() angegeben [7]. Wenn man diese Seitenbedingungen nicht erfüllt, kann es bei der Parallelisierung zu interessanten Ergebnissen kommen, es lohnt sich also stets, die Anforderungen von (Terminal-)Operationen zu kennen. Bei Iteratoren hat man dieses Problem nicht, muss sich jedoch selbst um die Feinheiten der Parallelisierung kümmern, was meiner Meinung nach viel größere Sorgfalt voraussetzt.

Das Streams-API ist inhärent für Parallelität designt, weshalb man bei Nichtnutzung von Parallelitätsfeatures vereinzelt auf Eigenschaften stößt, die sich nicht unbedingt erschließen. So kann man z. B. nicht direkt einen Stream aus einem Iterator erzeugen, sondern muss erst aus dem Iterator einen Spliterator [8] machen, der dann mittels StreamSupport.stream [9] zu einem Stream wird. Man kann die Parallelität eines Streams zwar mit isParallel() abfragen, diese Eigenschaften des Streams sind jedoch nicht im Typsystem hinterlegt, weshalb alle Operationen des Streams potenziell parallel ausgeführt werden können müssen.

Neben Parallelität ist der Umgang mit veränderlichen Daten ein anderer wichtiger Unterschied zwischen Streams und Iteratoren.

Mutabilität

Im Gegensatz zu Streams kann man über den Iterator die unterliegende Quelle während der Iteration strukturell verändern, indem man Elemente entfernt. Der (sinnfreie) Code in Listing 4 ist also kein Problem.

var list = new ArrayList<>(List.of(1, 2, 3));
var iter = list.iterator();
while (iter.hasNext()) {
  System.out.println(iter.next());
  iter.remove();
}
System.out.println(list.size()); // 0

Nach der Iteration ist die Liste leer, und der Iterator ist durchgelaufen. Das ist ein Sonderfall, den das Iterator-API anbietet. Modifikationen von list (z. B. über add) lösen weiterhin eine ConcurrentModificationException aus.

Das Problem kann jedoch auch bei sinnvollem Code auftreten: Listing 5 versucht, diesen Umstand zu zeigen. Bei der Stream-Variante wird im Hintergrund eine zweite Liste erzeugt, um das Ergebnis aufzubewahren. Am Ende der Schleife ist diese Liste halb so groß wie die Originalliste. Ein ausreichend schlauer Compiler kann das zwar unter Umständen wegoptimieren, darauf verlassen würde ich mich jedoch nicht.

Die Iterator-Variante hingegen benötigt maximal so viel Platz wie die Originalliste, da Elemente sich immer nur in einer der beiden Listen langeliste oder result befinden. Der Stream-Verteidiger wird natürlich argumentieren, dass langeliste selbst in einem Stream vorgehalten werden sollte, in diesem Beispiel ist die Liste allerdings vom API vorgegeben, ein Fall, der in echtem Code häufig auftreten wird.

var langeliste = new ArrayList<Integer>(...);
langeliste = langeliste.stream().filter((x) -> x % 2 == 0).collect(Collectors.toList());
 
var langeliste = new ArrayList<Integer>(…);
var result = new ArrayList<Integer>();
var iter = langeliste.iterator();
while (iter.hasNext()) {
  var value = iter.next();
  iter.remove();
  if (value % 2 == 0)
    result.add(value);
}

Wenn also Performanceoptimierungen fällig sind, lohnt es sich unter Umständen, Iteratoren zu benutzen, da man hier die Kontrolle über die Evaluation hat und auch Modifikationen möglich sind. Natürlich nur, wenn man über veränderliche Listen iteriert.

Fazit

Vielleicht hat man es schon aus dem Text herausgelesen: Ich persönlich mag das Streams-API sehr, weil es mir Aufgaben wie „Tausche bei einer Map Keys und Values“ sehr einfach macht. Man gibt natürlich Kontrolle auf, aber bei einzeiligen Transformationen sollte das selten ein Problem sein.

Das andere Ziel des Streams-API ist es natürlich, performante Datenverarbeitung im großen Stil zu ermöglichen. Hier ist mir mangels Erfahrung noch nicht klar, ob die in diesem Artikel beschriebenen Einschränkungen von Streams relevanter werden. Meine Vermutung ist, dass bei Beachtung einiger Seitenbedingungen das Streams-API genauso schön ist wie bei kleinen Problemen, belegen kann ich das jedoch noch nicht.

Links & Literatur

[1] https://www.postgresql.org/docs/current/queries-limit.html

[2] https://www.postgresql.org/docs/9.2/plpgsql-cursors.html

[3] https://blog.jooq.org/2013/11/18/faster-sql-pagination-with-keysets-continued/

[4] https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html

[5] https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

[6] https://github.com/google/guava

[7] https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html#reduce-T-java.util.function.BinaryOperator-

[8] https://docs.oracle.com/javase/8/docs/api/java/util/stream/StreamSupport.html#stream-java.util.Spliterator-boolean-

[9] https://docs.oracle.com/javase/8/docs/api/java/util/stream/StreamSupport.html#stream-java.util.Spliterator-boolean-

Alle News der Java-Welt:
Alle News der Java-Welt:

Behind the Tracks

Agile & Culture
Teamwork & Methoden

Data Access & Machine Learning
Speicherung, Processing & mehr

Clouds, Kubernets & Serverless
Alles rund um Cloud

Core Java & JVM Languages
Ausblicke & Best Practices

DevOps & Continuous Delivery
Deployment, Docker & mehr

Microservices
Strukturen & Frameworks

Web Development & JavaScript
JS & Webtechnologien

Performance & Security
Sichere Webanwendungen

Serverside Java
Spring, JDK & mehr

Digital Transformation & Innovation
Technologien & Vorgehensweisen

Software-Architektur
Best Practices

Domain-driven Design
Grundlagen und Ausblick

Spring Ecosystem
Wissen in Spring-Technologien

Web-APIs
API-Technologie, Design und Management