Java Magazin   11.2021 - Java 17

Preis: 9,80 €

Erhältlich ab:  Oktober 2021

Umfang:  100

Autoren / Autorinnen: 
Sebastian Meyen ,  
Tam Hanna ,  
Falk Sippach ,  
Falk Sippach ,  
Roman Kennke ,  
Anzela Minosi ,  
Ikuru Otomo ,  
Tim ZöllerIngo Küper ,  
Dr. Veikko Krypczyk ,  
Renke Grunwald ,  
Natalie RampKatrin Bertschy ,  
Jim Armstrong ,  
Manfred Steyer ,  
Roger Butenuth ,  
Tam Hanna ,  
Frank Delporte ,  

Pünktlich, alle halben Jahre wieder, geht es weiter mit Java. Nun ist also Java 17 da. Diese Version ist nicht nur eine weitere der vielen und rasch aufeinanderfolgenden Java-Versionen, sie stellt ein wichtiges Long-Term-Service-(LTS-)Release dar. Das bedeutet, hier wurde besonders auf Stabilität geachtet, denn diese Version soll von Oracle ab jetzt für drei Jahre mit Support unterstützt werden, während die Zwischenreleases vorher und nachher nur bis zur jeweils nächsten Version, also gut ein halbes Jahr, Support erhalten.

So überrascht es nicht, dass beim aktuellen 17er-Release nicht gerade ein Feuerwerk neuer Features erwartet werden kann, sondern ein Java, bei dem besonderer Wert auf Stabilität gelegt wurde. Soll ja auch eine Weile halten.

Wer also die vorigen Releases aufmerksam verfolgt hat, kennt die Liste der einigermaßen neuen Features und APIs bereits und kann sich jetzt auf eine konsolidierte Fassung freuen. So liefert Falk Sippach im Leitartikel dieser Ausgabe nicht nur eine Übersicht über die neuen Features, die in den vorherigen, featurebetonten Releases hinzugekommen sind, sondern auch über alles Neue des Java 17 Long-Term-Release.

Übrigens – drüben, in der .NET-Welt – hat man sich mittlerweile ein ganz ähnliches Vorgehen verordnet: Seit letztem Jahr erscheint stets im November ein Major Release des .NET-Frameworks – demnächst ist zum Beispiel .NET 6 dran. Auch dieses Release wird ein LTS-Release für drei Jahre sein, während in den dazwischen liegenden Jahren jeweils sogenannte „Current Releases“ erscheinen. Die früher einmal geltenden 10 Jahre Support für jedes .NET-Release sind damit Geschichte.

Ich erinnere mich bei dieser Gelegenheit an den Vortrag eines iOS-Entwicklers, der auf unserer W-JAX Apples Releasepolitik bei Betriebssystem und SDK der Entwicklung der JDKs einander gegenüberstellte und deutlich machte, dass für iPhone-Entwickler jeder Support einer Technologie nach zwei Jahren zu Ende geht und der Druck, die verwendeten Technologien aktuell zu halten, enorm ist.

Auch im Java-Lager (sowie bei .NET, wie wir gesehen haben) entsteht ein allmählich ansteigender „sanfter“ Druck, nicht allzu lange bei alten Technologieständen zu verharren. Also – bleiben Sie neugierig und helfen Sie mit, Technologieschulden in Ihrem Projekt bzw. bei Ihrem Kunden abzubauen oder besser: gar nicht erst anzusammeln!

In diesem Sinne wünsche ich eine informative Lektüre des aktuellen Java Magazins!

meyen_sebastian_sw.tif_fmt1.jpgSebastian Meyen | Redakteur

Mail Website Twitter

Java führt kontinuierlich neue, nützliche Features ein – die Einführung des Stream API in Java 8 war zum Beispiel eins der größten Highlights der vergangenen Jahre. Aber ist die Aggregierung der Daten mit dem Stream API ein Universalheilmittel? In diesem Artikel möchte ich untersuchen, ob es in bestimmten Fällen eine bessere Alternative gibt – aus Sicht der Komplexität.

Einige von euch haben wahrscheinlich schon folgenden Code in einem Programm verwendet, um spontan die Laufzeit einer Logik zu messen:

long start = System.currentTimeMillis();
doSomething();
long time = System.currentTimeMillis() - start;

Klar, das ist einfach zu implementieren und man kann die Geschwindigkeit des Codes schnell überprüfen. Allerdings gibt es auch Nachteile. Erstens können die Messwerte Ungewissheiten enthalten, weil andere Prozesse, die auf der gleichen Maschine laufen, sie beeinflussen können. Zweitens kann man die Messwerte nicht mit anderen Messwerten vergleichen, die in unterschiedlichen Umgebungen gemessen wurden. Es ist nicht hilfreich festzustellen, dass eine Lösung schneller als die andere ist, wenn sie auf unterschiedlichen Maschinen gemessen wurden, die zum Beispiel unterschiedliche CPUs und RAM haben. Drittens ist es schwer abzuschätzen, wie die Laufzeit sich verlängern würde, falls man zukünftig mit einer größeren Menge an Daten arbeiten würde. Seit das Stream API in Java 8 eingeführt wurde, ist es viel einfacher geworden, die Daten zu filtern und zu aggregieren. Das Stream API bietet sogar die Möglichkeit, die Bearbeitung zu parallelisieren [1]. Sind aber diese Lösungen weiter performant, wenn man mit der 10- oder 100-fachen Menge an Daten arbeiten muss? Gibt es ein Maß, mit dem wir solche Fragestellungen beantworten können?

Zeitkomplexität

Die Zeitkomplexität ist ein Maß, um die zeitliche Effizienz eines Algorithmus grob zu schätzen. Sie fokussiert, wie die Laufzeit zunimmt, sobald die Eingabe länger wird. Wenn man zum Beispiel eine Liste mit n Elementen mit einem for-Loop iteriert, dann werden n und die Laufzeit eine lineare Beziehung haben. Wenn man mehrere for-Loops hat, die geschachtelt sind und jeweils n-Mal ausgeführt werden, dann wird diese Logik eine exponentielle Auswirkung auf die Laufzeit haben.

Die O-Notation ist eine Möglichkeit, um die Beziehung zwischen der Länge der Eingabe und der Laufzeit darzustellen. Eine lineare Beziehung stellt man mit O(n) dar, O(n²) stellt ein quadratisches Verhältnis dar, wobei n die Länge der Eingabe ist. Ist die Laufzeit unabhängig von der Länge der Eingabe, also konstant, dann schreibt man O(1). Abbildung 1 stellt die typischen Werte der O-Notationen dafür dar, wie die Laufzeit wachsen wird, wenn sich die Länge der Eingabe vergrößert.

otomo_binaere_suche_1.tif_fmt1.jpgAbb. 1: Die Beziehung zwischen der Laufzeit und der Länge der Eingabe je Zeitkomplexität

Es gibt zwei wichtige Regeln für die Darstellung mit Hilfe der O-Notation:

  • Nur der Term mit dem höchsten Grad wird berücksichtigt. Beispiel: Wenn die Zeitkomplexität n + nlogn + n² ist, schreibt man einfach O(n²), da der Term die stärkste Auswirkung auf die Laufzeit hat.

  • Der Koeffizient wird nicht berücksichtigt. Beispiel: Die Zeitkomplexität von 2n², 3n² und ½n² ist gleichermaßen O(n²).

Wichtig zu betonen ist, dass sich die Zeitkomplexität nur auf die Skalierbarkeit fokussiert. Besonders wenn n ein kleinerer Wert ist, kann es möglicherweise passieren, dass ein Algorithmus eine längere Laufzeit hat, obwohl er eine bessere Zeitkomplexität als die anderen aufweist.

Platzkomplexität

Ergänzend zur Zeitkomplexität gibt es ein weiteres Maß, um die Effizienz eines Algorithmus darzustellen: die Platzkomplexität. Diese betrachtet, wie der Speicherbedarf wächst, wenn sich die Länge der Eingabe vergrößert. Wenn man eine Liste mit n Elementen in eine neue Liste kopiert, dann ist die Platzkomplexität O(n), weil der Bedarf an zusätzlichem Speicher linear steigt, wenn man mit einer größeren Eingabeliste arbeitet. Braucht ein Algorithmus nur eine konstante Menge Speicher, unabhängig von der Länge der Eingabe, dann ist die Platzkomplexität O(1).

Es gibt oft eine Trade-off-Beziehung zwischen Zeitkomplexität und Platzkomplexität. Je nach Fall ist es wichtig zu überlegen, ob die Laufzeit oder der Speicher wichtiger ist, wenn man mehrere Algorithmen vergleicht.

Binäre Suche

Wie Abbildung 1 zeigt, hat ein Algorithmus mit der Zeitkomplexität O(logn) eine bessere zeitliche Performance als O(n). Die binäre Suche ist einer der Algorithmen, die diese Zeitkomplexität aufweist, und sie ist anwendbar, wenn man einen Zielwert aus einer sortierten Liste suchen möchte. Der Algorithmus vergleicht in jedem Vorgang, ob sich der Zielwert in der linken oder der rechten Hälfte des Suchbereichs befindet. Man kann sich als Beispiel ein Wörterbuch vorstellen: Man wird wahrscheinlich nicht auf der ersten Seite des Wörterbuches anfangen, um das gesuchte Wort zu finden, sondern man wird eine Seite in der Mitte des Buches öffnen und von dort aus die Suche starten.

otomo_binaere_suche_2.tif_fmt1.jpgAbb. 2: Ablauf der binären Suche

Abbildung 2 stellt grafisch dar, wie die binäre Suche ablaufen wird, wenn man den Zielwert 7 in einer Liste mit elf Elementen sucht. Das rot markierte Element stellt die Mitte des Suchbereichs des jeweiligen Vorgangs dar. Ist die Anzahl der Elemente des Suchbereichs eine gerade Zahl, dann nimmt man das „linke“ Element in der Mitte. In jedem Vorgang vergleicht man, ob der Zielwert (also in diesem Fall die 7) kleiner oder größer als die Mitte ist, und halbiert den Suchbereich, bis man den Zielwert erreicht hat.

Die maximale Anzahl der nötigen Vergleichsvorgänge, um den Zielwert mit der binären Suche zu finden, ist log2n, während n die Länge der Eingabeliste ist. Lasst uns n = 8 als Beispiel nehmen: Die Länge des Suchbereichs beginnt mit 8 und verringert sich nach dem ersten Vorgang auf 4. Nach dem zweiten Vorgang wird sie noch einmal auf 2 halbiert und nach dem dritten Vorgang gibt es nur noch einen einzigen Wert im Suchbereich. Aus diesem Beispiel kann man schlussfolgern, dass die Anzahl der nötigen Vorgänge höchstens ein Logarithmus von 8 zur Basis 2 ist (log28 = 3), denn 23 = 8. In der O-Notation lässt man die Basis aus und schreibt nur O(logn).

In Java sind die Implementierungen der binären Suche in den Methoden java.util.Arrays.binarySearch [2] und java.util.Collections.binarySearch zu finden [3]. Wenn man mit einem Array arbeitet, kann man die Methoden in der Klasse java.util.Arrays benutzen. Arbeitet man mit einer Liste, dann sind die Methoden in der Klasse java.util.Collections anwendbar.

Sortierverfahren

Es gibt mehrere Arten von Sortierverfahren, die jeweils unterschiedliche Zeitkomplexitäten und Platzkomplexitäten haben. Typische Sortierverfahren, die in der Praxis verwendet werden, sind Quicksort, Mergesort und deren Varianten. Die Zeitkomplexität dieser beiden Verfahren ist im Durchschnitt O(nlogn) [4], [5]. Es gibt auch Sortierverfahren, die über bessere Zeitkomplexitäten verfügen, allerdings weisen diese meistens Einschränkungen in der Anordnung der Eingabeliste auf oder benötigen spezielle Hardware.

In Java sind die Methoden für die Sortierverfahren in java.util.Arrays.sort [2] und java.util.Collections.sort implementiert [3]. Seit Java 8 bietet das List-Interface auch die Methode sort [6], und das Stream API hat auch die intermediäre Operation sorted [1]. Nach der Java-Dokumentation sind diese Methoden standardmäßig mit Quicksort, Timesort oder Mergesort implementiert, allerdings kann das je nach Anbieter des JDK variieren.

Aufgabe 1: Suche in einer sortierten Liste

Die erste Aufgabe ist, den Zielwert in einer bereits sortierten Liste zu finden. Eine mögliche Lösung wäre, die contains-Methode des List-Interface zu verwenden (Listing 1).

Listing 1

// input
List<Integer> list = List.of(12, 15, 19, 20, 21, 24);
int target = 19;
 
// solution
boolean answer = list.contains(target);

Die Zeitkomplexität dieser Lösung ist O(n), weil diese im schlimmsten Fall die ganze Liste durchsucht, bis man das Ende der Liste erreicht hat. Eine andere Lösung wäre es, den Vorteil zu nutzen, dass die Eingabeliste bereits sortiert, also die binäre Suche anwendbar ist (Listing 2). Collections.binarySearch liefert einen Integer größer oder gleich 0, wenn der Zielwert in der Liste enthalten ist. Die Platzkomplexität der beiden Lösungen ist O(1), weil sie nur eine konstante Menge an Speicher brauchen, um das Ergebnis festzusetzen, unabhängig von den Eingabewerten.

Listing 2

// input
List<Integer> list = List.of(12, 15, 19, 20, 21, 24);
int target = 19;
 
// solution
boolean answer = Collections.binarySearch(list, target) >= 0;

Ich habe Testdaten aus 103 und 104 Elementen generiert und mit diesen die Laufzeit der beiden Lösungen verglichen. Die Zielwerte für die Suche sind in regelmäßigen Abständen ausgewählt, und für den jeweiligen Zielwert wurde die Laufzeit mehrmals gemessen. Die Tests wurden auf einem Windows-10-Rechner mit Intel Core i7-1065G7 CPU 1.30GHz und 32 GB RAM ausgeführt. Das verwendete JDK ist Amazon Corretto 11.0.11 und die Laufzeiten wurden mit Hilfe der Java Microbenchmark Harness [7] gemessen.

Abbildung 3 stellt die Ergebnisse für die jeweilige Länge der Eingaben als Box-Plot dar. Jeder Box-Plot enthält die Messzeiten der Aufrufe, die mit verschiedenen Zielwerten ausgeführt wurden. Der Box-Plot ist eine grafische Darstellung der Verteilung der Messergebnisse und stellt den Median, die zwei Quartile (deren Intervall die mittleren 50 Prozent der Daten enthält) und die beiden Minimum- und Maximumwerte der Daten dar (Abb. 4). Man kann in Abbildung 3 erkennen, dass die Laufzeit der Lösung in Listing 1 mehr gestreut ist als die in Listing 2 mit der binären Suche. Das liegt daran, dass die Laufzeit der Listing-1-Lösung stark davon abhängt, an welcher Stelle in der Liste sich der Zielwert befindet. Diese Tendenz wird deutlicher, wenn man die Ergebnisse zwischen den Testfällen n = 103 und = 104 vergleicht. Die Worst-Case-Laufzeit von Listing 1 ist zwischen den beiden Testfällen deutlicher gestiegen als die von Listing 2.

otomo_binaere_suche_3.tif_fmt1.jpgAbb. 3: Laufzeiten der jeweiligen Lösungen der Aufgabe 1
otomo_binaere_suche_4.tif_fmt1.jpgAbb. 4: Box-Plot

Aufgabe 2: Suche eines Wertebereichs in einer sortierten Liste

Die nächste Aufgabe besteht darin, das Auftreten der Werte in einer bereits sortierten Liste zu zählen, die größer oder gleich a und kleiner als b sind, also a ≤ xi < b, wobei xi der jeweilige Wert in der Eingabeliste ist. Die Voraussetzungen sind, dass die Eingabewerte a und b immer a ≤ b erfüllen und die Eingabeliste keine Duplikate enthält. Eine intuitive Idee wäre, mit der intermediären Operation filter im Stream API nur die Elemente zu sammeln, die innerhalb des angegebenen Wertebereichs liegen, und schließlich die Anzahl der Elemente mit der terminalen Operation count zu zählen (Listing 3).

Listing 3

// input
List<Integer> list = List.of(12, 15, 19, 20, 21, 24);
int a = 14, b = 19;
 
// solution
long answer = list.stream().mapToInt(Integer::intValue)
                        .filter(value -> a <= value && value < b).count();

Die Zeitkomplexität dieser Lösung ist O(n), weil man einmal durch die ganze Liste iterieren muss, um für jedes Element in der Liste zu überprüfen, ob der Wert im Wertebereich liegt. Wäre es aber möglich, auch für diese Aufgabe die binäre Suche zu verwenden? Wie wäre es, wenn wir die folgenden beiden Informationen festsetzen könnten:

  • Position des Wertes a in der Eingabeliste, wenn er enthalten ist. Ansonsten die Position in der Eingabeliste, an der man den Wert a einfügen kann.

  • Position des Wertes b in der Eingabeliste, wenn er enthalten ist. Ansonsten die Position in der Eingabeliste, an der man den Wert b einfügen kann.

Die Differenz der beiden berechneten Positionen ist die Anzahl der Elemente, die sich zwischen den beiden Schwellenwerten befinden. In dieser Lösung wird die binäre Suche zweimal ausgeführt, aber weil man in der O-Notation den Koeffizienten nicht berücksichtigt, ist die Zeitkomplexität dieser Lösung immer noch O(logn). Aus dem gleichen Grund wie in Aufgabe 1: Die Platzkomplexität der beiden Lösungen ist O(1).

Listing 4 zeigt eine Beispielimplementierung dieser Lösung. Zu beachten ist, dass dieser Code nicht funktionieren wird, wenn die Eingabeliste Duplikate enthält. Wie in der Dokumentation von Collections.binarySearch beschrieben ist [3], garantiert die Methode nicht, dass die gesuchte Position in der Liste zurückgegeben wird, falls der Zielwert mehrmals enthalten ist.

Listing 4

// input
List<Integer> list = List.of(12, 15, 19, 20, 21, 24);
int a = 14, b = 19;
 
// solution
int lower = Collections.binarySearch(list, a);
int upper = Collections.binarySearch(list, b);
lower = lower < 0 ? ~lower : lower;
upper = upper < 0 ? ~upper : upper;
int answer = upper - lower;

Collections.binarySearch liefert einen Integer größer oder gleich 0 zurück, wenn der Zielwert in der Liste enthalten ist. Ansonsten liefert sie einen negativen Wert zurück wobei -(insertion point)-1 ist. Der insertion point ist die Position in der Liste, an der der Zielwert eingefügt werden sollte, damit die Liste weiterhin sortiert bleibt. Um den insertion point aus dem Rückgabewert -(insertion point)-1 zurückzuberechnen, kann man einfach den bitweisen NICHT-Operator ~ verwenden.

Genau wie in Aufgabe 1 stellt Abbildung 5 die Laufzeiten der beiden Lösungen als Box-Plot dar, die mit verschiedener Länge der Eingabe und der Zielwerte gemessen wurden. Auch hier ist gut zu erkennen, dass die Lösung in Listing 4 mit binärer Suche stabilere Laufzeiten hat als die in Listing 3.

otomo_binaere_suche_5.tif_fmt1.jpgAbb. 5: Laufzeiten der jeweiligen Lösung der Aufgabe 2

Aufgabe 3: Größten Wert aus einer unsortierten Liste suchen

Die Aufgabe ist nun, den größten Wert einer unsortierten Liste zu finden, die aus Integern besteht. Eine mögliche Lösung mit Hilfe des Stream API wäre die Verwendung von IntStream und seiner terminalen Operation max [8] (Listing 5).

Listing 5

// input
List<Integer> list = List.of(23, 18, 15, 38, 8, 24);
 
// solution
OptionalInt answer = list.stream().mapToInt(Integer::intValue).max();

Diese Lösung hat die Zeitkomplexität O(n) und die Platzkomplexität O(1). Eine andere Idee wäre, die Liste einmal absteigend zu sortieren und den ersten Wert in der Liste zurückzugeben (Listing 6). Wie bereits erwähnt bietet Java mehrere Wege, um eine Liste zu sortieren. Um absteigend zu sortieren, muss man in Java einen Komparator angeben, der rückwärts vergleicht, weil die Liste standardmäßig aufsteigend sortiert wird. Auch zu beachten ist, dass man keine unveränderbare Liste verwenden darf, ausgenommen dann, wenn man mit der intermediären Operation sorted im Stream API arbeitet, weil die sort-Methoden die Liste direkt verarbeiten. Unveränderbare Listen sind zum Beispiel Listen, die mit der List.of-Methode erstellt wurden.

Listing 6

// input
List<Integer> list = Arrays.asList(23, 18, 15, 38, 8, 24);
 
// solution
list.sort(Collections.reverseOrder());
int answer = list.get(0);

Diese Lösung hat die Zeitkomplexität O(nlogn). Allerdings ist die Platzkomplexität dieser Lösung abhängig vom Sortierverfahren, das in der Implementierung der sort-Methode verwendet wurde. Wie bereits in Abbildung 1 zu erkennen war, ist die Zeitkomplexität O(nlogn) schlechter als O(n). Tatsächlich ist in Abbildung 6 zu sehen, dass, wenn sich die Länge der Eingabeliste n vergrößert, die Laufzeit der Lösung aus Listing 6 mit der Sortierung drastischer steigt als bei Listing 5. In der nächsten Aufgabe werden wir allerdings sehen, dass es in bestimmten Fällen doch eine gute Idee ist, die Liste zu sortieren.

otomo_binaere_suche_6.tif_fmt1.jpgAbb. 6: Durchschnittliche Laufzeiten der jeweiligen Lösung der Aufgabe 3

Aufgabe 4: Die größten k-Elemente aus einer unsortierten Liste suchen

In der letzten Aufgabe haben wir festgestellt, dass eine Sortierung nicht nötig ist, wenn man nur den größten Wert einer unsortierten Liste wissen möchte. Wie wäre es dann, wenn man die k größten Werte aus der Liste braucht? Das heißt, wenn k = 3, dann muss man die drei größten Werte aus der Liste herausfinden (vorausgesetzt, k ist kleiner als die Länge der Eingabe). In diesem Fall reicht es nicht mehr aus, einmal durch die Eingabeliste zu iterieren, aber die Lösung mit der Sortierung wird weiter funktionieren (Listing 7).

Listing 7

// input
List<Integer> list = Arrays.asList(23, 18, 15, 38, 8, 24);
int k = 3;
 
// solution
list.sort(Collections.reverseOrder());
List<Integer> answer = list.subList(0, k);

Diese Lösung kann man mit einer Priority Queue (Vorrangwarteschlange) noch leicht optimieren. Die Priority Queue, die in Java mit binärem Heap implementiert ist [9], ist eine abstrakte Datenstruktur, mit der man den kleinsten Wert (oder den größten Wert, je nachdem, welcher Komparator angegeben ist) in der Queue abfragen kann. Generell ist die Zeitkomplexität für das Hinzufügen und Löschen der Werte O(logn), für die Abfrage des kleinsten Werts ist sie O(1), während n die Länge der Priority Queue ist.

In unserem Fall fügt man die einzelnen Elemente aus der Eingabeliste in die Priority Queue und löscht jeweils den kleinsten Wert, sobald die Länge der Priority Queue größer als k ist. Schließlich fügt man die einzelnen Elemente aus der Priority Queue in eine Liste ein. Listing 8 zeigt eine Beispielimplementierung dieser Lösung. Als kleine Optimierung ist die Priority Queue mit einer initialen Kapazität k+1 instanziiert, weil sie höchstens k+1 Elemente beinhalten kann. Die Zeitkomplexität dieser Lösung ist O(nlogk), weil man n Elemente aus der Eingabeliste jeweils in die Priority Queue einfügt, aber die Länge der Priority Queue auf k begrenzt ist. Die Platzkomplexität ist O(k), weil man temporär k Elemente in der Priority Queue behält, um schließlich die Rückgabeliste zu erstellen.

Abbildung 7 stellt die durchschnittlichen Laufzeiten der jeweiligen Lösungen dar, die mit verschiedenen Längen der Eingabeliste n gemessen wurden. Je größer die Differenz zwischen n und k, umso größer wirkt sie sich auf die Laufzeit aus.

Listing 8

// input
List<Integer> list = List.of(23, 18, 15, 38, 8, 24);
int k = 3;
 
// solution
Queue<Integer> queue = new PriorityQueue<>(k+1);
for(int v : list) {
  queue.offer(v);
  if(queue.size() > k) {
    queue.poll();
  }
}
List<Integer> answer = Stream.generate(queue::poll)
  .takeWhile(Objects::nonNull).collect(Collectors.toList());
otomo_binaere_suche_7.tif_fmt1.jpgAbb. 7: Durchschnittliche Laufzeiten der jeweiligen Lösung der Aufgabe 4

Fazit

In diesem Artikel habe ich die Ideen der Zeit- und Platzkomplexitäten zusammengefasst und insbesondere verglichen, wie sich die Zeitkomplexität auf die Laufzeit auswirkt, wenn man mit einer größeren Menge an Daten arbeitet. Es ist eine gute Praxis, die beiden Maße im Hinterkopf zu behalten und bei Trade-offs andere Kriterien wie die Lesbarkeit oder Wartbarkeit des Codes zu berücksichtigen. Bei kleineren Datenmengen ist das Stream API ein sehr mächtiges Werkzeug. Allerdings ist die Zeitkomplexität grundsätzlich O(n), wenn man über die gesamte Eingabe filtert oder sucht und keinen vorzeitigen Abbruch vollzieht. Wenn die Möglichkeit besteht, dass künftig die Größe der Eingabe wächst, sollte man von Anfang an überlegen, ob es keine bessere Lösung aus Sicht der beiden Komplexitäten gibt.

otomo_ikuru_sw.tif_fmt1.jpgIkuru Otomo schloss den Master of Information Science and Technology an der Hokkaido University ab und arbeitet zurzeit als Professional Software Developer bei der sidion GmbH.

Das Wort „Debugging“ erzeugt bei vielen sofort bestimmte Bilder im Kopf und weckt damit verbundene Erwartungen. Es mag überraschen, aber das, was wir mit Debugging verbinden, wird hauptsächlich durch die Art und Weise bestimmt, wie wir in der zugrundeliegenden Sprache programmieren.

Um zu verstehen, warum die Suche nach Fehlern in Clojure vielleicht ganz anders ist, als wir es womöglich bisher gewohnt sind, müssen wir zuerst verstehen, wie Softwareentwicklung unter Clojure funktioniert.

REPL – die Leinwand des Künstlers

In Clojure beginnen wir die Entwicklung eines Programms damit, dass wir genau dieses Programm starten. Ab dann verläuft die Entwicklung interaktiv und im ständigen Dialog mit dem laufenden Programm, das Schritt für Schritt vervollständigt wird. Es ist sehr vergleichbar mit der Arbeit eines Malers, der sein Werk in einem kontinuierlichen Arbeitsfluss auf der Leinwand erschafft. Unsere Leinwand ist am Anfang die initiale Quellcodedatei. Entscheidend ist dabei, dass wir während der gesamten Entwicklung in einem immer gleichen gedanklichen Kontext bleiben. Den für einige vielleicht üblichen Wechsel zwischen den Phasen Programmieren, ggf. Kompilieren, dann Ausführen und Testen gibt es nicht. Demzufolge wird auch unser mentaler Fluss nicht unterbrochen, weshalb man in Clojure sehr schnell „im Flow“ ist.

Ermöglicht wird das durch den Read-Evaluate-Print-Loop (kurz: REPL). REPL unterstützen mittlerweile viele Programmiersprachen. Aber vier zusätzliche Eigenschaften von Clojure machen die REPL erst zur Leinwand:

  1. Wenn Du was brauchst, schreib’s einfach hin: Literal Values and Data Structures

  2. Unveränderliche Daten: Immutable Data

  3. Ganz oder gar nicht: Software Transactional Memory

  4. Am schnellsten geht’s, wenn ich’s gar nicht mache: Laziness

Ein Beispiel soll das Arbeiten mit REPL verdeutlichen. Es ist ein kleines Programm, damit es in dieser Folge vollständig abgehandelt werden kann und auch mit wenig Kenntnis von Clojure nachvollziehbar bleibt. Die Ansätze und Prinzipien, die wir kennenlernen werden, skalieren aber problemlos: Wir schreiben seit Jahren fachlich komplexe Web-, Mobil- und Desktopanwendungen sowie Webdienste mit genau diesen Methoden.

Die Summe gerader Fibonacci-Zahlen

Die fiktive Geschäftslogik unseres Kunden verlangt, dass wir die Fibonacci-Zahlen bis zu einer Grenze fibmax berechnen und die Summe der geraden Fibonacci-Zahlen bilden. Wir haben den REPL gestartet, unser Programm läuft bereits, aber die Quellcodedatei – unsere Leinwand – ist noch leer. Der Fibonacci-Generator wäre schnell geschrieben, soll in diesem Beispiel aber als externes System gesehen werden, das es anzubinden gilt. In der funktionalen Programmierung gilt der Leitsatz „Thinking in Data“: Schnittstellen, auch Schnittstellen zu externen Systemen, sind bevorzugt Daten und Datenstrukturen. Wir müssen nur die Datenstruktur spezifizieren, die wir über die Schnittstelle austauschen möchten. Für den Fibonacci-Generator modellieren wir als Datenschnittstelle eine Zahlenfolge. Um ohne Generator erstmal weiter an der eigentlichen Geschäftslogik arbeiten zu können, definieren wir eine stellvertretende Zahlenfolge als konstanten Wert:

'(0 1 1 2 3 5 8 13 21 34)

Das können wir genauso und als Ergebnis erster Überlegungen in unsere bisher leere Quellcodedatei schreiben und auch im REPL evaluieren lassen. Das Ergebnis dieser Liste ist die Liste selbst, und sie wird als flüchtige Ausgabe im Quellcode angezeigt.

'(0 1 1 2 3 5 8 13 21 34) 
=> (0 1 1 2 3 5 8 13 21 34)

Das war unsere erste Interaktion mit dem laufenden Programm. Und was hier sehr unscheinbar und wenig aufregend erscheint, ist in Wirklichkeit spektakulär, denn alle externen Systeme, auch Webserver, -dienste und Datenbanken lassen sich auf diese Weise anbinden und simulieren, als wären sie bereits existent. Wir können Beispieldaten literal formulieren, über Randfälle nachdenken und diese bereits für Testfälle bevorraten. Ist die Schnittstelle später implementiert, können wir die Daten bei Bedarf aufzeichnen, konservieren und für Testszenarien wieder heranziehen. Reale Schnittstellen bei Bedarf punktuell oder zeitweise wieder gegen Surrogate auszutauschen, ist geradezu lächerlich einfach. Des Weiteren fällt auf, dass die Fibonacci-Folge eine unendliche Zahlenfolge ist, die wir hier durch eine endliche Zahlenfolge ersetzen. Auch das funktioniert problemlos und wir werden später keine Zeile Code in der Geschäftslogik ändern müssen, wenn die Schnittstelle eine tatsächlich unendliche Zahlenfolge liefert. Noch haben wir allerdings keine Schnittstelle, denn Schnittstellen sind Funktionen, die Daten optional entgegennehmen, auf jeden Fall aber liefern. Deshalb schreiben wir als stellvertretenden Fibonacci-Generator flink eine Funktion um unsere konstante Liste, die diese einfach zurückliefert.

(defn fibonacci   "Liefert die Fibonacci-Folge, beginnend mit 0 und 1."   []   '(0 1 1 2 3 5 8 13 21 34))

Diesen Code evaluieren wir in der REPL und haben damit dem laufenden Programm eine weitere Funktion beigebracht, die wir nun in der gleichen Quellcodedatei sofort und live ausprobieren können:

(fibonacci) => (0 1 1 2 3 5 8 13 21 34)

Alles, ohne zu kompilieren, ohne ein Programm zu beenden oder neu zu starten, ohne Breakpoints.

Rich Comments

Bereits an dieser Stelle der Entwicklung erkennen wir aber zwei offensichtlich unterschiedliche Bereiche in der Quellcodedatei: einen Bereich mit fertigem oder zumindest im Moment ausreichend fertigem Code – unsere Funktion fibonacci – und einen explorativen Bereich, in dem wir noch in der Findungsphase sind, Ideen oder Teillösungen ausprobieren und unsere Daten kennen und verstehen lernen. Um in der Analogie der Leinwand zu bleiben: Einige Bereiche lassen schon fertige Bildelemente erkennen, andere enthalten gezeichnete Skizzen oder ein paar Hilfslinien für die Perspektive.

Als „Skizzenbereich“ eignen sich bei der Entwicklung mit der REPL sogenannte Rich Comments, die sich mit comment nutzen lassen. comment ignoriert den Funktionsbody und gibt immer nil zurück. Der damit umschlossene Code wird nie interpretiert und somit auch nie ausgeführt. Er ist später in der kompilierten Software nicht enthalten. Gleichzeitig ist er jedoch für unsere Entwicklungsumgebung und unser Tooling greifbar. Wir können innerhalb eines Rich Comments Code schreiben und werden dabei von Syntax-Highlighting, Lintern und natürlich der REPL unterstützt. Da die REPL uns erlaubt, Ausdrücke und Teilausdrücke auszuführen, eignet sich ein comment-Block hervorragend als Spielwiese, um Code in der REPL zu evaluieren, der noch nicht finalisiert ist. In unserem Beispiel sähe das zunächst so aus:

(comment
  (let [fib-max 10]
    (take-while #(< % fib-max) (fibonacci)))
  => (0 1 1 2 3 5 8)
)

Wir definieren einen let-Block und binden den maximalen Wert der zu betrachtenden Fibonacci-Zahlen an das Symbol fib-max. Um die gewünschte Teilmenge der Fibonacci-Zahlen zu erhalten, nutzen wir die Funktion take-while, die so lange Elemente einer Sequenz zurückgibt, wie diese eine Bedingung erfüllen. Eine Bedingung ist eine Funktion, die ein Element entgegennimmt und einen Wahrheitswert zurückliefert. Funktionen mit diesen Eigenschaften heißen Prädikate. Hier nutzen wir eine anonyme Funktion – eingeleitet durch das Zeichen –, die prüft, ob der eingehende Parameter kleiner fib-max ist. Der Parameter ist ebenfalls namenlos und wird durch das Symbol % repräsentiert. Führen wir in der REPL die let-Expression aus, erhalten wir das erwartete Ergebnis und können uns darum kümmern, nur die geraden Zahlen beizubehalten.

(comment
  (let [fib-max 10]
    (filter even? (take-while #(< % fib-max) (fibonacci))))
  => (0 2 8)
)

Wir wenden die Funktion even? als Filter auf die Sequenz an, die take-while uns zurückliefert, und erhalten nur noch die Zahlen mit geraden Werten zurück. Auch hier sieht das Ergebnis, das sofort im REPL ersichtlich ist, gut aus. Um sicherzugehen, könnten wir nun fib-max auf 15 setzen, um zu überprüfen, ob die Logik auch für die weiteren Zahlen funktioniert. Darüber hinaus könnten wir den Ausdruck auch einmal mit einer fib-max von 0 auswerten, um bereits einen Randfall zu testen. Wir können mit der Entwicklung fortfahren und die Logik um eine Funktion ergänzen, die die Summe aller Zahlen aus der gefilterten Sequenz bildet. Das können wir mit der Funktion reduce erreichen. Diese wendet eine Funktion, in unserem Fall die Funktion + zunächst auf die beiden ersten Einträge einer Sequenz an, dann auf das Ergebnis der ersten Operation und den dritten Eintrag usw.:

(comment
  (let [fib-max 10]
    (reduce + (filter even? (take-while #(< % fib-max) (fibonacci)))))
  => 10
)

Das Ergebnis sieht so aus, wie wir es erwartet haben. Auch hier können wir fib-max wieder auf verschiedene Werte setzen, um Randfälle zu überprüfen. Ein fib-max von 0 ergibt beispielsweise eine Summe von 0, die wir ebenfalls erwartet hätten. Wir sind fast zufrieden, wenden aber noch einen Refactoring-Schritt an, um aus den verschachtelten Funktionsaufrufen eine Datenverarbeitungspipeline zu formulieren:

(comment
  (let [fib-max 10]
    (->> (fibonacci)
         (take-while #(< % fib-max))
         (filter even?)
         (reduce +)))
)

In dieser Darstellung werden die einzelnen Verarbeitungsschritte der Daten sehr deutlich. Jede Zeile widmet sich einer Teilaufgabe, wodurch wir optisch einen hohen Grad an Separation of Concerns erreichen.

->> bedeutet Thread last und verkettet die Ausdrücke, indem jeder vorhergehende Ausdruck an die letzte Position des nachfolgenden Ausdrucks gesetzt wird. Aus (->> 5 (* 2)(+ 7)) wird (+ 7 (* 2 5)). Es ist aber auch nur eine Funktion, die den bildlichen Namen ->> trägt und Ausdrücke als Parameter entgegennimmt. Sie wirkt allerdings zur Compile-Zeit, nicht zur Laufzeit. Funktionen dieser Art werden Makros genannt und im späteren Verlauf dieser Serie unter „M wie Makros“ noch einmal gesondert erläutert werden.

Von der Leinwand zur strukturierten Software

Wir haben das Problem schrittweise gelöst und konnten jeden Teilschritt sofort und während des Programmierens interaktiv prüfen. Es ist Zeit, die gewonnenen Ergebnisse aus dem Skizzenbereich des Programms ins finale Bild zu übernehmen (Listing 1).

Listing 1

(defn sum-of-even-fibonacci
  "Liefert die Summe der geraden Fibonacci-Zahlen bis `fib-max`."
  [fib-max]
  (->> (fibonacci)
       (take-while #(< % fib-max))
       (filter even?)
       (reduce +)))

fib-max – eine fachliche Vorgabe, die wir bisher versuchsweise mit unterschiedlichen Werten belegt haben, um Standard- und Randfälle auszutesten – wurde zum Parameter; am erarbeiteten Quellcode mussten wir dafür aber nichts ändern. Und natürlich können wir unsere neue Funktion direkt ausprobieren:

(sum-of-even-fibonacci 13)
=> 10

Es fehlt noch der Fibonacci-Generator. Der ist aber so übersichtlich, dass wir ihn in zwei Schritten direkt als Ergebnis festhalten. Zuerst berechnen wir auf Basis eines Fibonacci-Tupels das darauffolgende:

(defn fibonacci-tuple
  "Berechnet auf Basis des angegebenen Fibonacci-Tupels das darauf folgende."
  [[a b]]
  [b (+ a b)])

Direkt ausprobiert:

(fibonacci-tuple [0 1]) 
=> [1 1]

Der Fibonacci-Generator ist nun die Liste der Zwischenergebnisse einer unendlichen Wiederholung dieser Vorschrift, wobei das letzte Rechenergebnis jeweils als Eingabe für den nächsten Rechenschritt dient. Genau das leistet die Funktion iterate:

(iterate fibonacci-tuple [0 1]) 
=> ([0 1] [1 2] [2 3] ...)

Wieviel REPL bei unendlichen Folgen ausgibt, ist konfigurierbar. Die Fibonacci-Folge ergibt sich im letzten Schritt aus dem jeweils ersten Element dieser Tupelfolge:

(defn fibonacci
  "Liefert die Fibonacci-Folge, beginnend mit 0 und 1."
  []
  (->> [0 1]
       (iterate fibonacci-tuple)
       (map first)))

map bildet eine Werteliste mit Hilfe einer Abbildungsvorschrift auf eine neue Werteliste ab, ähnlich wie es bei Java Streams der Fall ist. Die Abbildungsvorschrift ist hier die Funktion first, die aus einer Wertemenge – im vorliegenden Fall aus einem Fibonacci-Tupel – den ersten Wert ermittelt. Nun haben wir unseren Platzhalter durch eine echte Implementierung ersetzt. Auf der Spielwiese verschaffen wir uns wieder einen Eindruck:

(fibonacci)
=> (0 1 1 2 3 5 8 13 21 34 55 89 144 233 ...)
(drop 30 (fibonacci)) 
=> (832040 1346269 2178309 3524578 ...)

drop verwirft die angegebene Anzahl der Elemente und gibt die verbleibenden Elemente zurück. Auf diese Weise schauen wir uns einen späteren Ausschnitt der Fibonacci-Zahlen in der REPL an.

Den Fibonacci-Generator betrachten wir in diesem Beispiel als Schnittstelle zu einem externen System, das wir während der Entwicklung stellvertretend durch eine endliche Werteliste ersetzt hatten. Am Ende hat sich der Fibonacci-Generator zu einer Berechnungsvorschrift gewandelt, die eine unendliche Zahlenfolge liefert. Trotz dieser fundamentalen Änderung müssen wir keine Anpassung am Quellcode von sum-of-even-fibonacci vornehmen:

(sum-of-even-fibonacci 9999) 
=> 3382

Rich Comments dienen uns als Spielwiese, um Algorithmen schrittweise zu erarbeiten und direkt zu erproben, und um sich mit Daten einer Fachdomäne interaktiv und explorativ auseinanderzusetzen. Rich Comments können aber auch eine wertvolle Hinterlassenschaft für unser Team oder unser zukünftiges Ich sein. In Rich Comments können wir nicht nur Algorithmen, sondern auch unsere Herleitung in Textform festhalten. Wir können ein API nicht nur beschreiben, sondern funktionsfähig erfahrbar machen. Zum Beispiel ließen sich HTTP Requests in ein Shop-API bringen, um einen Kaufprozess zu simulieren. Der Autor des Rich Comments bestimmt, welche Systeme dabei real angesteuert oder durch Surrogate ersetzt werden. Ein Kauf über ein Webshop-API lässt sich auch ganz hervorragend ohne Web- und Datenbankserver und ohne Browser verstehen, untersuchen und umsetzen.

Vorteile von zustandslosen (Sub-)Systemen

Nachdem wir nun gesehen haben, wie die Arbeit mit REPL funktioniert, stellt sich die Frage, wieso sich dieser Entwicklungsstil in Clojure durchgesetzt hat. Die Hauptursache kann im Paradigma der zustandslosen Programmierung gefunden werden. Während objektorientierte Sprachen naturgemäß und absichtlich Zustände erzeugen, indem sie Daten und Logik kapseln, werden Datenstrukturen in Clojure durch Funktionen manipuliert, möglichst ohne dabei Seiteneffekte auszulösen. Der Großteil aller Funktionen in Clojure-Programmen ist idempotent, woraus sich ergibt, dass auch ihre Verkettungen idempotent sind. Um eine Funktion oder gleich ein ganzes Subsystem zu testen, reicht es also aus, sie mit definierten Parametern aufzurufen und den Rückgabewert zu kontrollieren. Dabei ist es unerheblich, ob die Funktion im Kontext eines Unit-Tests, auf dem lokalen Entwicklersystem oder in Produktion läuft – oder eben in der REPL. Die Vorteile, die daraus entstehen, sind zahlreich: Da sich Funktionen (und Subsysteme des Programms, die aus verketteten Funktionen bestehen) keinen Zustand teilen, sind sie voneinander unabhängig. Um sie zu testen, muss kein Zustand künstlich hergestellt werden, etwa durch Initialisierungen oder Mocks. Demnach verursacht auch kein vorab hergestellter Zustand Probleme, wenn Funktionen in REPL geändert und erneut ausgeführt werden – wir können uns ausschließlich auf den Code und das zu lösende Problem konzentrieren.

Fehler suchen und finden

Wir haben gezeigt, dass Programme in Clojure kontinuierlich und mit großer Selbstverständlichkeit während ihres gesamten Entstehungsprozesses kleinteilig vom Entwickler geprüft werden. Egal, ob man sich top-down oder bottom-up bewegt, Teilergebnisse werden ständig bewertet und falsche Berechnungen somit oft sehr früh erkannt. Das deckt die Qualitätssicherung während der Entwicklung ab. Aber wie sieht es mit der nachgelagerten Fehlersuche aus? Die erfolgt auf die gleiche Weise. Man entscheidet, ob man sich dem Fehler von innen nach außen oder von außen nach innen nähern möchte und streut Realdaten in Form literal deklarierter Datenstrukturen auf einer Spielwiese in die Schichten ein. Rich Comments helfen einem entweder dabei oder werden genau jetzt für zukünftige Untersuchungen angelegt.

Test-driven Development – ohne Tests

Nimmt man all diese Informationen über den REPL-Workflow zusammen, ist es nicht verwunderlich, dass die ursprüngliche Idee von Test-driven Development (TDD) in der Clojure-Community nicht viel Anklang findet. Wieso sollte man zwischen seinem Code und Unit-Tests springen, wenn man REPL hat? Der Ansatz ist jedoch sehr ähnlich – nur halt zuerst ohne strukturierte Tests. Möchten wir eine neue Funktion in unserem Programm entwickeln, starten wir üblicherweise mit einem Rich Comment, in dem wir unseren ersten Code schreiben – üblicherweise mit statisch definierten Werten in einem let-Block und nicht parametrisiert. Das verhindert, dass der Code ausgeführt wird, wenn das Programm geladen wird, da Kommentare nicht ausgeführt werden. Diesen Code erweitern, verfeinern und evaluieren wir im REPL so lange, bis wir mit den Ergebnissen zufrieden sind. Im nächsten Schritt verschieben wir den Code von unserem Comment-Block in eine Funktion, die parametrisiert aufgerufen werden kann. Auf unserer Spielwiese, dem Rich-Comment-Block, testen wir diese nun weiterhin mit verschiedenen Parametern und stellen sicher, dass auch Edge Cases sich so verhalten, wie wir uns das wünschen. Haben wir das evaluiert, können wir davon ausgehen, dass die Implementierung abgeschlossen ist. Erst jetzt verschieben wir unsere Test-Cases in einen ordentlichen Unit-Test, der dann zukünftig mit der Test-Suite ausgeführt wird und sicherstellt, dass unsere Logik zukünftig nicht durch Erweiterungen des Programms zerstört wird.

Beim Nachstellen und Beheben eines Bugs sieht der Workflow ähnlich aus: Zunächst wird versucht, das Fehlverhalten mit einem parametrisierten Aufruf der Funktion aus einem Rich-Comment-Block heraus nachzustellen. Gelingt das, kann man die betroffene Funktion anpassen, im REPL evaluieren und erneut aufrufen, bis man den Fehler behoben hat. Erst danach würde man die Unit-Test-Suite um einen Testfall für das behobene Fehlverhalten ergänzen.

Fazit

Code mit dem REPL-Workflow zu debuggen, also zu schreiben oder zu untersuchen, ist kleinteilig und enorm interaktiv. Wir können uns kontinuierlich im selben Kontext bewegen und ausschließlich auf den zu bearbeitenden Code konzentrieren. Die vier namensgebenden Eigenschaften von REPL, also Read, Evaluate, Print und Loop, sind einer der Hauptgründe dafür, dass Clojure eine Sprache ist, die uns sehr nah an den Code bringt; sie machen REPL zum wichtigsten Werkzeug für die Entwicklung mit Clojure. Ergänzt um Rich Comments, die gleichermaßen virtuelle Spielwiese und Bedienungsanleitung für unseren Code sein können, ergibt sich ein dermaßen interaktives Entwicklungserlebnis, dass wir sie beim Wechsel zu „Kompilieren und Ausführen“ oder „TDD“ in anderen Ökosystemen schmerzlich vermissen.

kueper_ingo_sw.tif_fmt1.jpgIngo Küper studierte Angewandte Mathematik und Informatik, ist geschäftsführender Gesellschafter der doctronic GmbH & Co. KG, bildet seit 20 Jahren Fachinformatiker aus und blickt auf über 35 Jahre Erfahrung in der Softwareentwicklung und -architektur zurück.

Mail

zoeller_tim_sw.tif_fmt1.jpgTim Zöller arbeitet seit über 13 Jahren als Softwareentwickler, davon über 10 Jahre mit Java. Mit der von ihm gegründeten Firma lambdaschmiede GmbH in Freiburg unterstützt er Kunden in Softwareprojekten und entwickelt eigene Software mit Clojure.

Mail

Offlinefähige Anwendungen sind für viele das nächste große Ding. Auch wenn in der Realität – vor allem im Kontext von Enterprise-Software – diese noch eher selten zum Einsatz kommen, lohnt es sich trotzdem, einen Blick auf die verschiedenen Storagetechnologien in modernen Browsern zu werfen. Selbst wenn die Anwendung keine offlinefähige Anwendung im eigentlichen Sinne ist, kann die Datenhaltung im Browser – wenn auch nur als Ergänzung zur Speicherung im Backend – sinnvoll für viele Anwendungsfälle sein.

Viele der Storage-APIs im Browser gibt es natürlich schon etwas länger. Warum widme ich die Kolumne gerade jetzt diesem Thema? Ein bekannter Entwickler im Webumfeld – James Long, bekannt als Erfinder von prettier, einem automatischen Codeformatierer für JavaScript – stellte jüngst sein seit längerer Zeit angekündigtes Projekt absurd-sql [1] vor. Kurz gesagt: absurd-sql erlaubt die Nutzung von SQLite im Browser mit persistenter Speicherung.

Bevor ich erkläre, warum absurd-sql ein wichtiger Baustein für die Entwicklung von Webanwendungen ist, werfen wir aber zunächst einmal ein Blick auf die Storage-APIs, die heutzutage relevant sind – oder es zumindest waren. Danach sollte hoffentlich nachvollziehbar sein, warum ich persönlich sehr glücklich bin, dass es Projekte wie absurd-sql und vor allem die Technologien, die diese überhaupt erst ermöglichen, gibt.

In den meisten modernen Browser stehen mindestens die folgenden APIs zur Auswahl:

  • WebStorage API

  • IndexedDB

  • Cache API

Die Wahl des richtigen API hängt natürlich wie immer von den konkreten Anwendungsfällen ab. Wir werden einen kurzen Blick auf die ersten beiden werfen, da diese in vielen Projekten sinnvoll zum Einsatz kommen können.

Zudem existieren noch einige APIs, die entweder nicht mehr oder noch nicht von allen Browsern unterstützt werden:

  • File System Access API

  • File and Directory Entries API

  • WebSQL

  • Storage Foundation API

Diese sind daher nur bedingt relevant für die Entwicklung von Anwendungen, die in allen Browsern funktionieren müssen, aber durchaus eine historische Bedeutung haben oder in der Zukunft wichtig sein werden.

Key-Value ist oft genug, aber nicht immer

Wollen wir heutzutage Daten persistent im Browser hinterlegen, bietet uns dieser faktisch zwei verschiedene Möglichkeiten: das WebStorage API und IndexedDB.

Das wohl bekannteste API, das auch oft außerhalb offlinefähiger Anwendungen zum Einsatz kommt, ist das WebStorage API. Das WebStorage API besteht konkret aus zwei verschiedenen APIs, localStorage und sessionStorage.

Während sessionStorage seltener zum Einsatz kommt, wird localStorage häufig verwendet, um kleine Datensätze so zu persistieren, dass diese auch beim nächsten Besuch der Anwendung weiterhin zur Verfügung stehen. Für Datensätze, die bewusst nur an die Lebensdauer eines Tabs gebunden sind, bietet sich hingegen die Verwendung von sessionStorage an.

Egal, ob localStorage oder sessionStorage verwendet wird, das API ist denkbar einfach:

localStorage.setItem("key", "value"); // Speichert den Wert "value" unter                                                     // dem Schlüssel "key"
localStorage.getItem("key"); // Liest den Wert, der unter dem Schlüssel "key"                                         // gespeichert ist
localStorage.deleteItem("key"); // Löscht den Wert, der unter dem Schlüssel                                             // "key" gespeichert ist

Das WebStorage API ist ein simpler Key-Value-Storage, bei dem sowohl Schlüssel als auch Wert vom Typ String sein müssen. Die Begrenzung auf Strings birgt einige Nachteile, die das WebStorage API für viele Anwendungsfälle unbrauchbar macht.

So können komplexe Datentypen nur durch vorherige Serialisierung (typischerweise nach JSON) im WebStorage abgelegt werden. Zur Speicherung von Binärdaten, wie beispielsweise Bildern, muss üblicherweise eine Konvertierung nach Base64 erfolgen. Dies ist problematisch, da das WebStorage API ein synchrones API ist, das somit bei jeder Operation die JavaScript-Ausführung blockiert. Bei größeren Datenmengen kann das zu für den Benutzer sichtbarem Hängen der Anwendung führen. Da das WebStorage API nicht in Web Workern nutzbar ist, lässt sich dieser Umstand auch nicht umgehen.

Ein weiterer Nachteil ist die eingeschränkte Möglichkeit zur Abfrage von Datensätzen im WebStorage. Da sich Datensätze lediglich über einen einfachen stringbasierten Schlüssel abrufen lassen, ist das API für das Speichern von Listen oder ähnlichen Strukturen ungeeignet, die beispielsweise anhand ihres Inhalts sortiert oder filtriert werden sollen. Zwar lassen sich durch kreative Auswahl von Schlüsseln, in denen etwa bestimmte Informationen kodiert sind, einige Abfragen realisieren, aber dennoch stößt man hier schnell an die Grenzen des API.

Trotz der Nachteile bietet sich die Verwendung gerade für einfache Anwendungsfälle an, in denen wenig Daten gespeichert werden müssen, insbesondere dann, wenn gerade die Synchronität des API einen Vorteil für die Nachvollziehbarkeit des Codes darstellt. So hat sich etwa die Speicherung von Access-Tokens oder die Zustimmung bzw. Ablehnung von Tracking im WebStorage als gängige Praxis etabliert.

NoSQL ist nicht immer die Lösung (auch nicht im Browser)

Wo das WebStorage API nicht mehr ausreicht, kann IndexedDB oft die Rettung sein. Als NoSQL-Datenbank dient IndexedDB als persistenter Storage für nahezu beliebige Daten. In vielerlei Hinsicht ist IndexedDB dabei das völlige Gegenteil des WebStorage API.

So können nahezu alle Datentypen [2] persistiert werden, ohne dass diese vom Entwickler erst serialisiert oder konvertiert werden müssen. Insbesondere können Binärdaten in Form von Blobs oder ganze Dateien als Files effizient in der Datenbank abgelegt werden. Auch die Verwendung von Schlüsseln weicht vom WebStorage API ab. Ein Schlüssel kann etwa direkt Teil des eigentlichen Datensatzes sein und – falls gewünscht – automatisch generiert werden.

Ein weiterer Gegensatz: Das API von IndexedDB ist durchweg asynchron. Die Operationen blockieren damit nicht die JavaScript-Ausführung. Auch die Verwendung in Web Workern ist möglich. Da IndexedDB bereits vor dem Einzug des Promise API Teil von Browsern war, wird die Asynchronität jedoch durch Callbacks modelliert. Das lässt IndexedDB nicht zu Unrecht etwas veraltet erscheinen und wirkt daher bei direkter Verwendung in Kombination mit modernen APIs oft fehl am Platz.

Da IndexedDB bewusst für komplexere Anwendungsfälle konzipiert wurde, werden Transaktionen – nicht unähnlich denen, die in der SQL-Welt zum Einsatz kommen – unterstützt. Zwar gibt es, anders als im Backend, im weiteren Sinne nicht mehrere Benutzer, die gleichzeitig auf dieselben Datensätze zugreifen, aber dennoch will man aufgrund nicht definierter Reihenfolge der asynchronen Operationen stets sicherstellen, dass die Daten in der Datenbank zu jeder Zeit konsistent sind. Transaktionen in IndexedDB ermöglichen das.

Um als echter Ersatz für eine Datenbank im Backend zu dienen, bietet IndexedDB im Vergleich zum WebStorage API auch deutlich mehr Möglichkeiten zur Abfrage von Datensätzen. Um das effizient zu ermöglichen, bedarf es der Angabe von Indizes, die festlegen, auf welche Art Datensätze abgefragt werden können. Das schließt sowohl das Filtern als auch Sortieren von Datensätzen ein.

Wie auch bei vielen anderen NoSQL-Datenbanken muss sich der Entwickler hier durchaus Gedanken machen, welche Abfragen von der Anwendung benötigt werden, um so die richtigen Indizes zu setzen. Beliebige Queries, wie sie in SQL-Datenbanken möglich sind, bietet IndexedDB leider nicht.

Zwar bietet IndexedDB einen deutlichen höheren Funktionsumfang als das WebStorage API, dennoch lässt sich das Callback-basierte API durchaus als Low-Level bezeichnen. Die Verwendung von Wrapper Libraries ist ratsam, um einen modernen, Promise-basierten Zugriff auf IndexedDB zu ermöglichen und repetitiven Code zu vermeiden. Zusätzlich können die leider teils gravierenden Verhaltensunterschiede der verschiedenen Browser versteckt werden.

Die Verwendung solcher Wrapper Libraries macht die Nutzung deutlich einfacher, wie im Beispiel mit der Library Dexie.js [3] in Listing 1 erkennbar ist.

Listing 1

// Erstellt eine Datenbank
const db = new Dexie("AppDB'); 
 
// Legt initiale Struktur der Datenbank fest
db.version(1).stores({
  products: "++id, title, price" // Automatische ID und jeweils ein Index für id, title und price
});
 
// Speichert ein neues Produkt ab
await db.products.add({title: "Fancy Product", price: 9}),
 
// Lädt alle Produkte die günstiger als 10 Euro sind
const cheapProducts = await db.products.where(price).below(10).toArray();

Für komplexe Anwendungen, die persistente Datenhaltung im Browser benötigen, gibt es heutzutage faktisch keine Alternative zu IndexedDB. Das ist oft kein Problem, aber gerade bei aufwendigen Abfragen stößt auch IndexedDB schnell an Grenzen. Durch Wrapper Libraries lässt sich die Verwendung zwar deutlich angenehmer gestalten, aber dennoch scheinen Low-Level-Aspekte hier und dort durch. Viele Entwickler sehnen sich daher nach einer brauchbaren Alternative.

Die Rückkehr von WebSQL und die Zukunft des Webs

Mit dem WebStorage API und vor allem IndexedDB lassen sich viele Anwendungsfälle bereits umsetzen. Der Aufwand, das zu erreichen, fühlt sich jedoch oft größer an, als er sein müsste. Insbesondere komplexe Abfragen lassen sich meist nur über Umwege realisieren und fordern durchaus einiges an Kreativität.

Eine Alternative zu diesen APIs hatte durchaus das Potenzial, die Antwort auf viele Persistenzfragen zu sein: WebSQL. Ein SQL-basiertes API zur Speicherung von Daten. Da SQL immer noch der Platzhirsch ist, was die Speicherung von Daten im Backend anbelangt, liegt der Einsatz auch im Browser nahe. Vorhandene SQL-Erfahrung – von verschieden Dialekten mal abgesehen – lässt sich direkt auf die Entwicklung im Browser übertragen. Gerade für Backend-Entwickler, die auch im Frontend unterwegs sind, ist das ein enormer Vorteil.

Es hätte so schön sein können, aber: Die WebSQL-Spezifikation konnte sich nicht durchsetzen, da die Browserhersteller sich nicht auf einen implementierungsunabhängigen Standard, der nicht ausschließlich auf SQLite basiert, einigen konnten [4]. Aufgrund dieser Formalie stellt WebSQL heutzutage leider keine wirkliche Alternative zu den vorgestellten Storage-APIs dar.

Glücklicherweise hat sich das Web seit dem inzwischen über zehn Jahre zurückliegenden Tod von WebSQL prächtig weiterentwickelt und ermöglicht nun durchaus interessante Wege, um die Limitierungen bestehender Storage-APIs zu umgehen.

Allen voran sei hier das Projekt sql.js [5] genannt, das die Verwendung von SQLite im Browser ermöglicht. Durch die Verwendung von Emscripten [6] wird der C-basierte Source Code von SQLite fast unverändert direkt nach WebAssembly kompiliert und kann mit nahezu nativer Geschwindigkeit direkt im Browser ausgeführt werden. Fast alle Funktionalitäten von SQLite, seien es Views, Indizes oder komplexe Queries, können ohne Einschränkungen im Browser verwendet werden.

Ein großer Nachteil besteht jedoch: Die Daten werden lediglich im Speicher gehalten und nicht direkt im Browser persistiert. Zwar besteht die Möglichkeit, die Datenbank in ihrer Gänze aus dem WebStorage oder aus IndexedDB zu laden und anschließend wieder zu speichern, aber bei größeren Datenmengen ist das naturgemäß sehr ineffizient. sql.js ist daher für viele Anwendungsfälle zunächst ungeeignet.

Aber noch ist nicht alle Hoffnung verloren, denn jetzt kommt endlich die Rettung: absurd-sql. absurd-sql ist ein Zusatz zu sql.js, der die effiziente Nutzung von sql. js mit echter Persistenz ermöglicht. Wie funktioniert das? Wie der Name schon sagt absurderweise durch die Verwendung von IndexedDB. Dabei wird aber nicht die gesamte Datenbank als ein Blob gespeichert, sondern vielmehr dient IndexedDB als effizientes Storage-Backend für sql.js. Die Datenbank wird nur partiell gelesen und geschrieben: immer genau die Daten, die SQLite benötigt, um die entsprechende Anfrage auszuführen.

Die Verwendung von IndexedDB als Storage-Backend für sql.js ist nicht nur clever, sondern dem Entwickler von absurd-sql zufolge paradoxerweise sogar für nahezu alle Abfragen deutlich schneller als die direkte Verwendung von IndexedDB. Durch die Verwendung von absurd-sql büßt man trotz der deutlich mächtigeren Abfragemöglichkeiten also keinerlei Geschwindigkeit ein. Der einzige Nachteil ist die ca. 0,5 MB große WASM-Datei, die einmalig an den Browser übertragen werden muss.

Ob absurd-sql für den produktiven Einsatz bereit ist, sei dahingestellt, aber es auszuprobieren – wenn auch nur für kleinere, interne Anwendungen – lohnt sich in jedem Fall, mindestens um dem Entwickler von absurd-sql durchaus erwünschtes Feedback geben zu können.

Viel wichtiger als absurd-sql ist für mich jedoch die Erkenntnis, dass durch viele der neuen Technologien ganz neue Möglichkeiten im Browser entstehen. Zurückblickend war die Entscheidung, dass WebSQL kein Standard wird, zwar sicherlich für viele eine Enttäuschung, aber mit dem heutigen Wissen vielleicht sogar die richtige Entscheidung. Schließlich können wir SQLite inzwischen auch ohne ein vom Browser bereitgestelltes API mit fast nativer Geschwindigkeit verwenden.

Neben SQLite gibt es viele ähnliche Technologien, auch außerhalb des Bereichs Datenbank, die für die Verwendung im Browser geeignet wären. Statt also nun für jede dieser Technologie ein API – inklusive langwierigem Standardisierungsprozess – in Browsern einzuführen, könnte der Fokus eher auf Low-Level-APIs wie WebAssembly und ähnlichen Ansätzen liegen. Ein konkretes Beispiel ist etwa das vorgeschlagene Storage Foundation API, das bewusst als Low-Level-Baustein gedacht ist, um aufbauend darauf Projekte zu ermöglichen, die absurd-sql ähnlich sind. Anstelle neuer eingebauter Datenbanken könnte die Zukunft also durchaus im Zeichen von Bring-your-own-Database stehen. Ob das der richtige Weg ist, wird sich natürlich immer erst mit der Zeit zeigen. Gespannt sein dürfen wir aber in jedem Fall!

grunwald_renke_sw.tif_fmt1.jpgRenke Grunwald ist Enterprise-Entwickler bei der OPEN KNOWLEDGE GmbH in Oldenburg. Zu seinen Schwerpunkten gehören moderne Frontend-Technologien (insbesondere im Kontext von SPAs), neuartige Architekturansätze wie Microservices sowie das Thema Continuous Integration/Deployment. Die Mission seiner Arbeit ist immer, den Prozess der Softwareentwicklung zu verbessern und zu vereinfachen.

Desktop Tablet Mobile
Desktop Tablet Mobile