Überlegungen zur Effizienz

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

Die preg-Funktionen in PHP verwenden PCRE, eine optimierte NFA-Regex-Maschine, daher sind die meisten der unter Wie Regex-Maschinen arbeiten bis Die Kunst, reguläre Ausdrücke zu schreiben beschriebenen Methoden direkt anwendbar. Dazu gehört auch das Benchmarking von zeitkritischen Programmabschnitten, damit man nicht nur in der Theorie, sondern auch ganz konkret sieht, was schnell ist und was nicht. Die Kunst, reguläre Ausdrücke zu schreiben enthält dazu ein Beispiel in PHP (siehe Benchmarks mit PHP).

Bei besonders zeitkritischen Abschnitten sollte man beachten, dass Callbacks ganz allgemein schneller sind als der Gebrauch des e-Modifikators (siehe Callback oder e-Modifikator?) und dass bei sehr langen Strings die benannten Klammern aufwendige Kopieroperationen auslösen können.

Die regulären Ausdrücke werden zur Laufzeit kompiliert, wenn sie auftauchen, aber PHP verwendet einen sehr großen Cache (4096 Einträge, siehe Kompilations-Caching), so dass in der Praxis ein bestimmter Regex-String nur einmal kompiliert wird.

Zum S-Modifikator gibt es mehr zu sagen: Die Regex wird genauer analysiert und es wird versucht, weitere Optimierungen herauszuholen. (Der Modifikator bewirkt etwas anderes als der gleichnamige study-Operator in Perl; letzterer optimiert den Suchstring, mit dem S-Modifikator wird die Regex optimiert, siehe Die Funktion study.)

Der S-Modifikator

Bei Gebrauch des S-Modifikators wendet die preg-Maschine ein bisschen (Anmerkung: Wirklich nur ein bisschen: Auch bei sehr langen und komplizierten regulären Ausdrücken dauert die zusätzliche Optimierung auf einem durchschnittlichen Rechner weniger als eine Hunderttausendstelsekunde.) mehr Zeit als sonst zur Optimierung der Regex auf, in der Hoffnung, dass dieser Aufwand bei der eigentlichen Mustersuche hereingeholt werden kann. Es kann durchaus sein, dass dabei kein Netto-Zeitgewinn herausspringt, aber in manchen Fällen kann die Beschleunigung ganze Größenordnungen ausmachen.

In der jetzigen Implementation kann man die Situationen, in denen der S-Modifikator wirklich etwas bringt, recht genau umreißen: Es wird dabei die »Erstes Zeichen«-Optimierung angewandt.

Ich möchte gleich zu Anfang betonen, dass diese Optimierung nur dann etwas bringt, wenn eine Regex auf große Textmengen angesetzt werden soll.

Normale Optimierung ohne den S-Modifikator

Wir betrachten einen einfachen regulären Ausdruck wie ˹<(\w+)˼. Wir stellen fest, dass jeder mögliche Treffer mit dem Zeichen ›<‹ beginnen muss. Eine Regex-Maschine kann das ausnutzen (und die preg-Maschine tut das), den String nach diesem Zeichen absuchen und die komplette Regex-Maschinerie nur an diesen Positionen ansetzen (wenn ein Treffer mit ˹<˼ beginnen muss, ist es sinnlos, die Maschine bei einem anderen Zeichen anzusetzen).

Eine solche Vorauswahl kann mit einer einfachen String-Suche viel schneller als mit einer kompletten Regex-Suche getroffen werden. Insbesondere wenn das fragliche Zeichen nur selten im Suchstring vorkommt, ist der Gewinn beachtlich. Wenn die Regex sehr komplex ist, ist der Geschwindigkeitsvorteil einer einfachen String-Suche ebenfalls größer. Diese Optimierung bringt beispielsweise im Fall ˹<i>|</i>|<b>|</b>˼ mehr als bei ˹<(\w+)˼, weil die Regex-Maschine im ersten Fall alle vier Alternativen durchprobieren müsste.

Verbesserte Optimierung mit dem S-Modifikator

Die preg-Maschine wendet diese Optimierung in den meisten Fällen von sich aus an, wenn sie feststellt, dass ein Treffer mit einem bestimmten Zeichen beginnen muss. Mit dem S-Modifikator kann man die Maschine instruieren, die Regex genauer zu analysieren und die Optimierung auch dann anzuwenden, wenn die möglichen Treffer mit mehreren Zeichen beginnen können.

Hier eine kleine Liste von Ausdrücken, bei denen man mit dem S-Modifikator diese Optimierung forcieren kann:

Regex	Mögliche Startzeichen
<(\w+)|&(\w+);	< &
[Rr]e:	R r
(Jan|Feb|...|Dez)\b	A D F J M N O S
(Re:\s*)?SPAM	R S
\s*,\s*	\x09 \x0A \x0C \x0D \x20 ,
[&<">]	& < " >
\r?\n\r?\n	\r \n

Wann bringt der S-Modifikator nichts?

Es ist auch ganz lehrreich, sich die Fälle anzuschauen, bei denen der S-Modifikator keine Wirkung zeigt:

• Reguläre Ausdrücke mit einem Zeilenanfang-Anker (˹^˼ und ˹\b˼) oder einer Alternation auf oberster Ebene, bei der eine Alternative mit einem solchen Anker beginnt. Im Fall von ˹\b˼ ist das eine Unvollkommenheit der jetzigen Implementation, im Prinzip könnte die Optimierung auch hier angewandt werden.
• Ausdrücke, die auf den Leerstring passen können, z.B. ˹\s*˼.
• Ausdrücke, bei denen ein Treffer mit beliebigen oder jedenfalls sehr vielen verschiedenen Zeichen beginnen kann, z.B. ˹(?:[^()]++|\((?R)\))*˼ aus dem Programmbeispiel von Text mit verschachtelten Klammern parsen. Ein Treffer für diese Regex kann bei jedem Zeichen außer bei ›)‹ beginnen, deshalb bringt eine Vorauswahl möglicher Startzeichen so gut wie gar nichts.
• Ausdrücke mit genau einem möglichen Startzeichen, denn diese Fälle werden automatisch optimiert, auch ohne den S-Modifikator.

Wann soll der S-Modifikator verwendet werden?

Der Aufwand für die zusätzliche Analyse der Regex ist nicht sehr groß; wenn größere Textmengen abgesucht werden sollen, ist er im Vergleich zum gesamten Suchaufwand verschwindend gering. Wenn Sie vermuten, dass damit die Regex optimiert werden kann, dann kann sich das durchaus auszahlen.

  

<< zurück

vor >>