Optimierungen der Regex-Maschine

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

Verketten von Literalen

Das ist vielleicht die naheliegendste und einfachste Optimierung: Die Maschine betrachtet ˹abc˼ als ein Ganzes und nicht als Folge der drei einzelnen Teile »˹a˼, dann ˹b˼ und dann ˹c˼«. So kann dieser eine Teil auf einmal verarbeitet werden und benötigt nicht drei Iterationen der internen Schleife der Regex-Maschine.

Optimierung »Einfache Quantoren«

Wenn sich ein Quantor auf etwas Einfaches bezieht, beispielsweise auf ein literales Zeichen oder eine Zeichenklasse, dann ist es oft günstig, dies anders als mit dem normalen Voranschreiten der NFA-Maschine zu behandeln. Die zentrale Schleife in einer Regex-Maschine muss sehr allgemein gehalten sein, damit all die verschiedenen Konstrukte behandelt werden können. Beim Programmieren ist aber »allgemein« fast immer auch »langsam«. Mit dieser Optimierung werden die einfachen Quantoren in einer kleinen, spezialisierten und daher schnelleren Schleife behandelt, die anstelle der allgemeinen Schleife benutzt wird.

Die Ausdrücke ˹.*˼ und ˹(?:.)*˼ sind logisch gesehen identisch, aber je nach System ist das einfache ˹.*˼ deutlich schneller als die andere Regex. Ein paar Beispiele: Beim Java-Regex-Package von Sun beträgt der Unterschied nur 10 %, bei Ruby und den .NET-Sprachen macht er schon einen Faktor von 2,5 aus, bei Python ist ˹(?:.)*˼ 50 mal so schnell und bei PCRE/PHP sogar 150 mal. Perl benutzt die Optimierung aus dem nächsten Abschnitt, daher sind hier ˹.*˼ und ˹(?:.)*˼ gleich schnell. (Beachten Sie auch die Erläuterungen zu solchen Benchmark-Zahlen im folgenden Kasten.)

Die Benchmark-Tests in diesem Kapitel

Die meisten Benchmark-Resultate in diesem Kapitel sind relative Zahlen aus Messungen an verschiedenen Ausdrücken in der gleichen Programmiersprache. Zum Beispiel wird im obigen Abschnitt gesagt, dass die optimierte Version einer Regex im Java-Package von Sun 10 % schneller sei. Im .NET-Framework ist die optimierte Version zweieinhalbmal schneller, in PCRE 150 mal! In Perl wird ein Faktor von eins gefunden, d.h., die Ausdrücke sind gleich schnell.

Was kann man daraus im Hinblick auf die Geschwindigkeiten der regulären Ausdrücke in verschiedenen Sprachen folgern? Rein gar nichts. Der kolossale Faktor von 150 bei PCRE kann bedeuten, dass diese besondere Optimierung im Vergleich zu anderen Sprachen dort sehr gut implementiert ist, er kann aber auch bedeuten, dass die unoptimierte Version bei PCRE ausgesprochen langsam ist. Vergleiche zwischen den einzelnen Programmiersprachen führe ich nur selten an, denn das ist vor allem für Leute interessant, die sich mit den Vorzügen ihrer Lieblingsprogrammiersprache brüsten wollen.

Wofür auch immer das gut sein mag – wenn es um derart große Unterschiede wie die 10 % bei Java und den Faktor 150 bei PCRE geht, vergleiche ich hier einmal die verschiedenen Sprachen. Es stellt sich heraus, dass die nicht-optimierte Version in PCRE etwa 11 mal langsamer ist als die entsprechende Version in Java, dafür ist die optimierte 13 mal schneller. Die optimierten Versionen von Java und Ruby sind etwa gleich schnell; die unoptimierte Version von Ruby ist etwa 2,5 mal langsamer als die von Java. Die unoptimierte Version von Ruby ist nur etwa 10 % langsamer als die von Python; bei den optimierten Varianten ist Python aber um den Faktor 20 schneller.

Alle diese Versionen sind langsamer als die Regex-Maschine in Perl. Bei Perl besteht kein Unterschied zwischen der unoptimierten und der optimierten Regex, beide sind etwa 10 % schneller als die schnellste Regex von Python. Jede Implementation hat aber Stärken und Schwächen, und diese Zahlen gelten nur für einen ganz spezifischen Testfall.

Entfernen von unnötigen Klammern

Wenn eine Implementation feststellen kann, dass ˹(?:.)*˼ exakt das Gleiche ist wie ˹.*˼, dann kann sie die Klammer auch weglassen.

Entfernen von unnötigen Zeichenklassen

Eine Zeichenklasse, die nur ein einzelnes Zeichen enthält, ist etwas albern, weil die Zeichenklasse nur unnötigen Aufwand verursacht, ohne einen Vorteil zu bewirken. Dennoch schreiben manche Leute für einen literalen Punkt ˹[.]˼; eine schlaue Implementation behandelt das genauso wie ˹\.˼.

Das Zeichen nach einem nicht-gierigen Quantor

Bei einem genügsamen Quantor in einer Regex wie etwa ˹"(.*?)"˼ muss die Maschine normalerweise zwischen dem quantisierten Unterausdruck (hier dem Punkt) und dem Zeichen hinter dem Quantor (˹"˼) hin- und herspringen. Deshalb (und auch aus anderen Gründen) sind genügsame Quantoren im Allgemeinen langsamer als gierige, besonders wenn die Maschine die Optimierung »Einfache Quantoren« verwendet, die oben erwähnt wurde. Wenn der nicht-gierige Quantor im Innern von einfangenden Klammern auftritt, muss die Maschine wiederholt in die Klammern hinein- und wieder herausspringen. Das erfordert einen erhöhten Verwaltungsaufwand.

Wenn nach dem nicht-gierigen Quantor ein literales Zeichen folgt, kann der Quantor so lange als ganz normaler gieriger Quantor behandelt werden, wie kein solches Zeichen auftritt. Bei dieser Optimierung wird ebenfalls die allgemeine, große Schleife in der Regex-Maschine durch spezialisierten, nur für nicht-gierige Quantoren geeigneten Code ersetzt, der den Suchtext nach dem literalen Zeichen absucht und die normale »Nächster Versuch«-Iteration vermeidet, solange dieses Zeichen nicht auftritt.

Bei einer Variante dieser Optimierung wird nicht nur auf ein literales Zeichen geprüft, sondern auf eine Zeichenklasse (z.B. wird bei der Regex ˹['"](.*?)["']˼ im Voraus auf ˹['"]˼ geprüft). Das entspricht etwa der »Erstes Zeichen«-Optimierung.

Erkennung von »übermäßigem« Backtracking

Beim Problem von Zurück zur Realität hatten wir festgestellt, dass bestimmte Kombinationen von Quantoren ein exponentielles Backtrack-Verhalten zeigen und ein »unendliches« Matching entsteht. Dies lässt sich auf eine einfache Art lösen, indem man einen Backtrack-Zähler führt und aufgibt, »wenn es zu viel wird«. Das ist für den normalen Gebrauch ganz nützlich, aber es ergibt sich daraus eine künstliche Grenze für die Größe des Suchtexts.

Wenn wir das Limit beispielsweise auf 10 000 Backtrack-Vorgänge setzen, wird ˹.*?˼ nicht mehr auf Texte passen, die länger als 10 000 Zeichen sind, weil bei jedem erkannten Zeichen ein Backtracking ausgelöst wird. Solche Texte sind aber nicht selten, gerade im Zusammenhang mit Webseiten; eine willkürliche Grenze ist also etwas unglücklich.

Aus anderen Gründen ist bei manchen Implementationen die Größe des Backtrack-Stacks (in dem die gespeicherten Zustände abgelegt werden) begrenzt. In Python z.B. liegt diese maximale Stackgröße bei 10 000, damit wird die Länge des Suchtexts für bestimmte reguläre Ausdrücke eingeschränkt.

Dieser Umstand hat das Schreiben von Benchmarks für dieses Buch doch etwas behindert. Für aussagekräftige Resultate sollte die eigentliche Arbeit der Regex-Maschine gemessen werden, und der Code, der die gleiche Regex immer wieder auf den gleichen String ansetzt, sollte vernachlässigbar sein. Ich habe dazu riesige Strings generiert und die zu testenden Ausdrücke wie ˹"(.*)"˼, ˹"(.)*"˼, ˹"(.)*?"˼ oder ˹"([^"])*?"˼ nur wenige Male auf diesen großen String angewandt. Das funktionierte nicht mit allen Implementationen; ich musste den Suchstring verkürzen, damit der Backtrack-Stack nicht überlief. Unter Benchmarks mit Tcl sehen Sie ein Beispiel dazu.

Vermeidung von exponentiellem (super-linearem) Verhalten

Es ist natürlich viel besser, wenn man das exponentielle bzw. super-lineare Verhalten erkennen und so das »unendliche« Matching vermeiden kann. Dazu notiert die Regex-Maschine die Position jedes Unterausdrucks, der von einem Stern oder einem Plus quantisiert wird.

Es ist sogar ziemlich einfach, das super-lineare Verhalten zu erkennen. Ein Quantor sollte im Allgemeinen nicht mehr Iterationen ergeben, als der Suchstring Zeichen hat. Wenn das dennoch passiert, ist das ein starker Hinweis darauf, dass ein exponentielles Matching stattfindet. Damit ist das Problem aber erst diagnostiziert; es ist jedoch wesentlich komplizierter, herauszufinden, welche Versuche unnötig sind. Wenn durch das »Kurzzuschließen« der super-linearen Regex ein ewiges Matching verhindert werden kann, ist das dennoch gut investierte Arbeit.

Diese Optimierung hat einen überraschenden und leider unerwünschten Nebeneffekt: Der Programmierer erkennt wirklich schlecht und ineffizient formulierte reguläre Ausdrücke nicht. Auch mit der Optimierung ist eine solche Regex möglicherweise immer noch wesentlich langsamer, als sie sein könnte, aber nicht mehr so langsam, dass es auffällt (statt mehreren Stunden benötigt sie vielleicht nur noch eine Hundertstelsekunde; das nimmt der Benutzer kaum wahr, aber für den Computer ist das eine halbe Ewigkeit).

Der mögliche Zeitgewinn rechtfertigt jedoch die Optimierung. Viele Benutzer kümmern sich ohnehin nicht um die Effizienz, sie verstehen die regulären Ausdrücke kaum und sind froh, wenn es überhaupt »irgendwie« funktioniert. Vielleicht gehörten Sie ja bislang auch zu diesen Benutzern, und ich hoffe, dass dieses Buch diesem Zustand ein Ende setzt.

Löschen von unnötigen abgespeicherten Zuständen mit possessiven Quantoren

Nachdem ein Unterausdruck mit einem normalen, gierigen Quantor gepasst hat, existiert noch eine Anzahl von gespeicherten Zuständen vom Typ »diese Möglichkeit überspringen«; nämlich ein Zustand für jede Iteration des Quantors. Bei einem possessiven Quantor werden diese Zustände explizit beseitigt (siehe Possessive Quantoren). Diese unnötigen Zustände können aber schon während der Anwendung des Quantors beseitigt werden, wenn die nächste Iteration des Quantors ansteht (während des Matchings wird mindestens ein gespeicherter Zustand benötigt).

Das ist effizienter, als wenn alle gespeicherten Zustände am Ende des Quantors auf einmal beseitigt würden, weil weniger Speicherplatz verbraucht wird. Bei ˹.*˼ wird für jedes gefundene Zeichen ein Zustand abgespeichert, und bei langen Suchstrings kann das Unmengen von Speicher benötigen.

Automatische »Possessifizierung«

In einem Beispiel unter Wie Regex-Maschinen arbeiten (siehe Schnellere Fehlschläge mit atomaren Gruppen) hatten wir ˹^\w+:˼ auf ›Subject‹ angewendet. Zunächst passt ˹\w+˼ bis zum Ende des Strings, aber der Doppelpunkt passt da nicht. Die Maschine muss mittels Backtracking jedes einzelne Zeichen zurückfordern und nach viel unnötiger Arbeit feststellen, dass ˹:˼ auf keines dieser Zeichen passt. Wir hatten festgestellt, dass wir diese unnötige Arbeit mit atomaren Klammern, ˹^(?>\w+):˼, oder mit einem possessiven Quantor, ˹^\w++:˼, vermeiden können.

Eine sehr gute Implementation könnte das selbst machen. Bei der Kompilierung der Regex kann die Maschine feststellen, dass nach dem Quantor etwas folgt, das durch den quantisierten Unterausdruck niemals erkannt werden kann, dass also der Unterausdruck mit dem Quantor effektiv dasselbe ist wie ein possessiver Ausdruck.

Mir ist kein System bekannt, das diese Optimierung implementiert; ich hoffe aber, dass sich die Entwickler herausgefordert fühlen. Ich denke, dass der Effizienzgewinn beträchtlich sein kann.

Kleine Quantoren

Manche Leute schreiben ˹\d\d\d\d˼, andere mögen die Quantoren mit den geschweiften Klammern lieber und schreiben ˹\d{4}˼. Ist einer dieser Ausdrücke effizienter als der andere? Bei einem NFA ist das fast ganz sicher so, aber welcher Ausdruck schneller ist, hängt von der Implementation ab. Wenn das verwendete Werkzeug optimierte Quantoren hat, ist sehr wahrscheinlich ˹\d{4}˼ schneller, aber auch die andere Version könnte besser optimiert werden. Verwirrend? In der Tat.

Nach meinen Messreihen ist ˹\d{4}˼ bei Perl, Python, PHP/PCRE und .NET bis zu 20 % schneller. Andererseits ist bei Ruby und beim Java-Package von Sun der Ausdruck ˹\d\d\d\d˼ schneller, manchmal sogar um ein Mehrfaches. Offenbar sind also kleine Quantoren bei bestimmten Programmen besser, bei anderen schlechter. Doch halt! Es wird noch komplizierter.

Vergleichen wir ˹====˼ und ˹={4}˼. Hier ist der wiederholte Teil ein Literal, und vielleicht kann die Regex-Maschine bei ˹====˼ besser erkennen, dass ein literaler Substring vorliegt. Wenn ja, kann die Optimierung mit literalen Substrings angewendet werden (siehe dazu Optimierung mit literalen Strings mitten im Text), die sehr viel Zeit einspart. Genau das passiert bei Python und dem Java-Regex-Package von Sun, hier ist ˹====˼ bis zu hundertmal schneller als ˹={4}˼.

Perl, Ruby und .NET erkennen diese Optimierung sowohl bei ˹====˼ als auch bei ˹={4}˼, daher sind beide praktisch gleich schnell, aber hundert- oder tausendmal schneller als ˹\d\d\d\d˼ oder ˹\d{4}˼.

Welche Resultate der Mustersuche werden tatsächlich gebraucht?

Wenn die Maschine feststellen kann, dass bestimmte Resultate oder Aspekte der Mustersuche (zum Beispiel von Klammern eingefangener Text) im späteren Verlauf des Programms gar nicht verwendet werden, kann sie die dafür notwendige Arbeit einfach auslassen. Ob das gelingt, hängt sehr stark von der jeweiligen Sprache ab. Manchmal gibt es dafür aber eine spezielle Option.

Tcl z.B. verwendet diese Optimierung. Die einfangenden Klammern fangen hier nur dann wirklich Text auf, wenn man explizit danach fragt. Umgekehrt gibt es bei den regulären Ausdrücken im .NET-Framework eine Option, mit der man angeben kann, dass die einfangenden Klammern nichts einfangen sollen.

  

<< zurück vor >>

 

 

 

Tipp der data2type-Redaktion:
Zum Thema Reguläre Ausdrücke bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an:
   

Copyright der deutschen Ausgabe © 2008 by O’Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "Reguläre Ausdrücke" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

O’Reilly Verlag GmbH & Co. KG, Balthasarstr. 81, 50670 Köln