Leserbriefe Juli 2020

Hoffentlich nur ein Testballon

(iX Special 2020 – Moderne Programmiersprachen)

Ich bin inzwischen seit einem gefühlten halben Leben Abonnent von c’t und iX und schätze beide Formate sehr für ihre Qualität und Kontinuität. Obwohl ich es nicht immer schaffe, die abonnierten Magazine gründlich zu lesen – mindestens überflogen werden sie eigentlich immer.

Heute landete das iX Special – Moderne Programmiersprachen im Brief­kasten. Interessantes Thema – als bekennender IT-Nerd freute ich mich darauf, in gewohnt kompakter, aber kompetenter Form einen Einblick in neue Sprachkonzepte zu erhalten.

Das Editorial hätte ja noch ein Ausdruck persönlichen Stils sein können, aber im gleichen Muster ging es weiter: In einem Großteil der Artikel wird das Gender­sternchen verwendet. Wenn ich mir so die Bandbreite der Artikel ansehe, drängt sich mir die Vermutung auf, dass hier seitens der Redaktion auf die Autoren Einfluss genommen wurde, doch bitte möglichst das Gendersternchen zu verwenden. Erfreulicherweise verzichten einige Autoren des Sonderheftes darauf, und ebenso erfreulicherweise scheinen die reguläre iX und c’t noch nicht „betroffen“ zu sein.

Das Konstrukt Gendersternchen gehört nicht zur deutschen Sprache, auch wenn es irritierenderweise scheinbar Bestrebungen gibt, ein nicht sinnvoll aussprechbares ASCII-Sonderzeichen in unsere offizielle Grammatik aufzunehmen. Es würde mich wirklich sehr freuen, auch in Zukunft gut lesbare und grammatikalisch korrekte Artikel in Veröffentlichungen des Heise-­Verlags zu lesen und nicht durch unnötige Stolpersteine im Fließtext an der Aufnahme des eigentlichen Inhalts behindert zu werden.

Martin Bartosch, via E-Mail

Einige unklare Stellen

(Quantencomputer: Quantencomputer programmieren – ein Einstieg; iX Special 2020, S. 146)

Zuerst mal herzlichen Dank für das Heft. Die auf dem Titel beworbenen neuen ­Programmieransätze Quantencomputing wollte ich doch gerne näher kennenlernen. Leider aber ist der Artikel für die anspruchsvolle Materie etwas zu holprig und salopp geraten. Und leider weiß ich auch nach mehrmaliger Lektüre des Artikels nicht, was und wie man mit QC etwas besser und schneller herauskriegen kann als mit wiederholtem Würfeln.

Matthias Ferdinand, via E-Mail

Praktisch unverzichtbar für viele Programme

(Regex-Katastrophen: Wenn reguläre Ausdrücke Software lahmlegen; iX 5/2020, S. 110)

Von Jamie Zawinski stammt das Zitat: „Some people, when confronted with a problem, think ‚I know, I’ll use regular expressions.‘ Now they have two problems.“ Und es scheint mir, als habe der Autor genau das gemeint – reguläre Ausdrücke seien ein schwer zu beherrschendes Werkzeug und man täte besser daran, sie nicht zu nutzen. Vor allem das Backtracking ist allem Anschein nach ein großes Risiko für die Laufzeit. Diese Aussage ist in dem betrachteten Fall richtig, aber die Begründung, dass es sich um ein Problem mit regulären Ausdrücken handelt, ist schlicht falsch. Es handelt sich um ein Problem mit einer schlecht implementierten Bibliothek für reguläre Ausdrücke.

Zunächst ist festzustellen, dass für reguläre Ausdrücke drei verschiedene Ansätze existieren. Von Cloudflare wurde eine LUA-Bibliothek verwendet, die den einfachen, aber laufzeitmäßig riskanten Ansatz des Backtracking verwendet. Das gab es auch schon früher, in den 80ern war ein ähnlicher Algorithmus in der csh implementiert. Mit einem einfachen ls *************************a konnte man die Shell zwar nicht zum Absturz bringen, allerdings war sie dann bei 100 Prozent CPU-Nutzung für Stunden blockiert, sodass man sie von außen mit kill abschießen musste.

Der zweite Ansatz ist derjenige, aus einem regulären Ausdruck einen endlichen (nichtdeterministischen) Automaten zu erzeugen. Die Zahl der Zustände eines solchen ist proportional zur Länge des regulären Ausdrucks. Anders als die Bezeichnung nichtdeterministisch nahelegt, braucht man an dieser Stelle kein Backtracking, um die Eingabe zu verarbeiten. Stattdessen verfolgt man bei der Auswertung des Automaten einfach alle möglichen Rechenwege parallel, jedes Eingabezeichen wird genau einmal angefasst. Abgerechnet wird am Schluss: Entweder hat der Automat einen Zustand erreicht, in dem er die Eingabe akzeptiert, oder er hat es nicht. Der Rechenzeitbedarf ist also im schlimmsten Fall so groß wie das Produkt aus der Länge des regulären Ausdrucks und der Länge der Eingabe.

So schnell der endliche Automat auch ist, er hat einen kleinen Nachteil, weil er bestimmte reguläre Ausdrücke nicht verarbeiten kann, insbesondere nicht die sogenannten Rückwärtsreferenzen. Dafür gibt es den letzten Ansatz, der mit dynamischer Programmierung berechnet, welcher Teil des regulären Ausdrucks auf welchen Teil der Eingabe passt. Dieser Ansatz hat einen klaren Laufzeitnachteil gegenüber dem zweiten Ansatz, denn in der Theorie muss er jeden Teil der Eingabe (bei n Zeichen also n*n-n Teilstrings) gegen jedes Element des regulären Ausdrucks prüfen, der Zeitbedarf ist also grob geschätzt n^²*m, wobei m die Länge des regulären Ausdrucks ist. Aber auch das ist noch weit entfernt vom exponentiellen Zeitbedarf des Backtracking-Verfahrens. So braucht dieses Verfahren auf einem herkömmlichen Laptop etwa vier Sekunden, um in einem Zufallstext mit zwei Millionen Zeichen (0 oder 1) mit dem regulären Ausdruck ([01]{1,50}).*(\\1).* das längste Anfangsstück mit maximal 50 Zeichen zu finden, das weiter hinten im Text nochmals vorkommt.

Vor etwas über 20 Jahren war ich für meinen damaligen Arbeitgeber bei einem Kunden, der ein Problem mit MySQL hatte. Grob gesagt führte MySQL damals in bestimmten Situationen einen Join zwischen zwei Tabellen aus, in dem das Kreuzprodukt aus allen Einträgen der ersten Tabelle mit etwa 10 000 Datensätzen und allen Einträgen der zweiten Tabelle mit etwa 500 Datensätzen gebildet wurde und dann aus diesem Kreuzprodukt von 5000000 Datensätzen diejenigen 10000 gefiltert wurden, bei denen die Kundennummer aus der ersten Tabelle gleich der Kundennummer aus der zweiten Tabelle war. Das war kein Problem der Abfragesprache SQL und kein Problem relationaler Datenbanken an sich, sondern ein – seit Langem behobenes – Problem von MySQL. Genauso ist die Lage im vorliegenden Fall. Es war kein Problem von regulären Ausdrücken, sondern ein Problem der verwendeten Implementierung. Man könnte auch sagen: Es war ein Bug.

Peter Heusch, via E-Mail

Ergänzungen und Berichtigungen

Medien: Rezensionen; iX 6/2020, S. 148

Das Buch Cyber-Sicherheit erscheint im Springer Verlag und nicht wie angegeben im Hanser Verlag.

C++20: Modernes Programmieren mit C++20; iX Special 2020, S. 12

Bei der Beschreibung des „Raumschiffoperators“ gibt es eine falsche Angabe. Der dritte Fall lautet „> 0 bei x > y (x ist größer bzw. y ist kleiner)“. Im Text steht hierzu „wenn y größer ist“. Korrekt ist jedoch „wenn x größer ist“.

Die iX-Redaktion behält sich Kürzungen und auszugsweise Wiedergabe der Leserbriefe vor. Die abgedruckten Zuschriften geben ausschließlich die Meinung des Einsenders wieder, nicht die der Redaktion.