Regex-Kompilierung, der /o-Modifikator, qr/.../ und Effizienz

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

Wie effizient reguläre Ausdrücke jeweils sind, hängt davon ab, was Perl hinter den Kulissen alles erledigen muss, nachdem das Programm auf einen Regex-Operator gestoßen ist und bevor die Regex angewandt werden kann. Was da genau passiert, hängt von der Art des Regex-Operanden ab. In den meisten Fällen ist es wohl ein Regex-Literal, wie bei m/.../ oder s/.../.../ oder qr/.../. Bei diesen muss Perl jedes Mal einige Vorbereitungen treffen, die wir nach Möglichkeit lieber vermeiden würden. Untersuchen wir zuerst, was da alles abläuft, und dann, wie sich das möglicherweise einsparen lässt.

Interne Vorgänge beim Vorbereiten einer Regex

Was genau hinter den Kulissen abläuft, bevor ein Regex-Operand der eigentlichen Regex-Maschine übergeben wird, wurde in Die Kunst, reguläre Ausdrücke zu schreiben (siehe Wie ein regulärer Ausdruck angewendet wird) behandelt, aber bei Perl gibt es ein paar zusätzliche Besonderheiten.

Die Vorverarbeitung eines Regex-Operanden geschieht in Perl in zwei Phasen:

  1. Verarbeitung von Regex-Literalen. Wenn der Regex-Operand ein Literal ist, wird er behandelt, wie das im Abschnitt Wie Regex-Literale geparst werden beschrieben wurde. Unter anderem werden in diesem Schritt Variablen interpoliert.
  2. Regex-Kompilierung. Die Regex wird untersucht, und wenn sie wohlgeformt ist, wird sie in eine interne Form übersetzt, die von der Regex-Maschine direkt verarbeitet werden kann. (Bei ungültigen Ausdrücken wird eine Fehlermeldung ausgegeben.)

Wenn Perl eine kompilierte Regex hat, kann sie auf den Suchstring angewendet werden.

Nicht alle Schritte dieser Vorverarbeitung müssen bei jeder Regex jedes Mal ausgeführt werden. Sicher müssen sie beim ersten Mal ausgeführt werden. Wenn aber die gleiche Regex wiederholt angewendet wird (beispielsweise in einer Schleife oder in einer Funktion, die mehrfach aufgerufen wird), dann kann Perl unter Umständen auf früher geleistete Arbeit zurückgreifen. In den nächsten Abschnitten untersuchen wir, wie und in welchen Fällen dies möglich ist und wie der Programmierer darauf Einfluss nehmen kann.

Wie Perl Regex-Kompilierungen vermeidet

In den nächsten Abschnitten untersuchen wir zwei Wege, die Perl einschlägt, um unnötiges Neukompilieren von regulären Ausdrücken zu vermeiden: Caching und Neukompilierung nur bei Bedarf.

Caching

Wenn ein Regex-Literal keine Variablen enthält, die interpoliert werden müssen, weiß Perl, dass die Regex zwischen zwei Aufrufen unverändert bleibt; wenn die Regex einmal kompiliert wurde, kann beim zweiten Mal die im Cache abgespeicherte interne Form verwendet werden. Die Regex wird nur einmal untersucht und kompiliert, egal wie häufig sie im Programm verwendet wird. Die meisten regulären Ausdrücke in diesem Buch enthalten keine Variablen, die interpoliert werden müssen, und sind daher gute Kandidaten für diese Optimierung.

Es geht hier nicht um Variablen in Codemustern oder in dynamischen Regex-Konstrukten. Diese werden nicht in die Regex interpoliert, sondern sind Teil eines unabänderlichen Programmstücks, das ausgeführt wird. Wenn in einem solchen Konstrukt my-Variablen auftreten, wünschte man sich nicht selten, das Programmstück würde bei jedem Aufruf neu interpretiert; siehe dazu die Warnung Vorsicht bei my-Variablen in Codemustern.

Dieses Caching bezieht sich immer auf die Laufzeit eines Programms – Perl unterhält keinen Cache, der reguläre Ausdrücke von einem Programmaufruf zum nächsten aufbewahrt.

Neukompilierung nur bei Bedarf

Manche Regex-Operanden können nicht direkt gecacht werden. Ein Beispiel:

my $heute = (qw<Sun Mon Tue Wed Thu Fri Sat>)[(localtime)[6]];
# $heute enthält je nach Wochentag "Mon", "Tue" usw.

while (<LOGFILE>) {
   if (m/^$heute:/i) {
       ...

Bei der Regex m/^$heute:/ muss interpoliert werden, aber da dies in einer Schleife geschieht, in der sich der Wert von $heute nicht ändert, ist das Resultat dieser Interpolation immer dasselbe. Es wäre sehr ineffizient, die Regex jedes Mal neu zu übersetzen. Perl vergleicht deshalb den interpolierten String (das Resultat der Interpolation) mit dem String aus der vorherigen Iteration. Wenn der String unverändert ist, kann die kompilierte Regex aus dem Cache verwendet werden. Wenn die Strings verschieden sind, muss neu kompiliert werden. Dazu ist in jedem Fall ein zusätzlicher String-Vergleich notwendig, aber dieser ist deutlich weniger aufwendig als die Komplilierung einer ganzen Regex.

Wie viel macht das tatsächlich aus? Eine ganze Menge. Ich habe einmal die drei Varianten des $HttpUrl-Beispiels von Regex-Objekte aufbauen und verwenden mit Benchmarks getestet (und zwar die Version mit der voll ausgebauten $HostnameRegex). In den Tests wurde die Laufzeit der Vorverarbeitung (Interpolation, String-Vergleich, Komplilierung und anderer Verwaltungsaufwand) gemessen, nicht die eigentliche Anwendung der Regex – diese ist ja in allen Fällen dieselbe.

Die Resultate sind recht interessant. Ich habe die Version ohne Interpolation (die gesamte Regex wurde »von Hand« in m/.../ ausformuliert) als Basis genommen. Die Interpolation und der String-Vergleich dauern etwa 25 mal so lange, wenn die Regex immer gleich bleibt. Die gesamte Vorverarbeitung inklusive Komplilierung dauert aber fast tausendmal so lange!

Um diese Zahlen richtig einzuordnen, muss man aber doch sehen, dass auch die gesamte Vorverarbeitung (die tausendmal langsamer war) auf meinem Rechner nur gerade 0,00026 Sekunden dauert. (Ich hatte 3846 Iterationen pro Sekunde gemessen; bei der statischen Regex ohne Interpolation allerdings 3,7 Millionen Iterationen.) Dennoch ist die Ersparnis beeindruckend. In den nächsten Abschnitten untersuchen wir, was man tun kann, um diese Ersparnis auch in anderen Fällen zu erzielen.

Der /o-Modifikator: »Nur einmal kompilieren«

Ganz einfach gesagt, wird ein Regex-Literal, bei dem /o angegeben wird, nur einmal untersucht und kompiliert, unabhängig davon, ob Variablen interpoliert werden oder nicht. Wenn keine Variablen in der Regex auftreten, bringt /o gar nichts, weil reguläre Ausdrücke ohne Interpolation ohnehin immer gecacht werden. Wenn zu interpolierende Variablen vorhanden sind, wird beim ersten Mal kompiliert. In allen weiteren Anwendungen der Regex wird wegen des /o die interne, kompilierte Form aus dem Cache verwendet.

Hier sehen Sie das $heute-Beispiel mit dem /o-Modifikator:

my $heute = (qw<Sun Mon Tue Wed Thu Fri Sat>)[(localtime)[6]];
# $heute enthält je nach Wochentag "Mon", "Tue", usw.

while (<LOGFILE>) {
   if (m/^$heute:/io) {
       ...

Das ist nun wesentlich effizienter, weil $heute nur einmal, nämlich bei der ersten Iteration, ausgewertet und interpoliert wird. Der Verzicht auf Interpolation und String-Vergleich bei jedem Schleifendurchgang bedeutet eine große Ersparnis. Perl kann das nicht von sich aus, der Wert von $heute könnte sich ja ändern, und so muss Perl den String jedes Mal auswerten. Mit dem /o-Modifikator teilen wir Perl mit, dass sich die Regex nach der ersten Komplilierung nie ändern wird. Das können wir in diesem Fall unbesorgt tun, weil wir wissen, dass sich die Variable $heute über die ganze Schleife nie ändert. Wir können /o auch dann verwenden, wenn die Variable sich zwar ändert, wir aber möchten, dass Perl immer den ursprünglichen Wert verwendet.

Mögliche Fallen beim /o-Modifikator

Mit dem /o-Modifikator können sich aber auch Fehler einschleichen. Verpacken wir unser Beispiel in eine Subroutine:

sub LogdateiFuerHeute() {

   my $heute = (qw<Sun Mon Tue Wed Thu Fri Sat>)[(localtime)[6]];

   while (<LOGFILE>) {
      if (m/^$heute:/io) { # Achtung: mögliche Falle!
          ...
      }
   }
}

Das /o besagt, dass dieser Regex-Operand nur einmal ausgewertet und kompiliert werden soll. Beim ersten Aufruf von LogdateiFuerHeute() wird eine Regex mit dem aktuellen Datum im Cache abgelegt. Wenn die Funktion später aufgerufen wird, wird diese kompilierte Regex aus dem Cache verwendet, auch wenn sich das Datum und damit $heute in der Zwischenzeit geändert hat.

Das ist ein großer Nachteil, aber mit Regex-Objekten können wir auch das in den Griff bekommen.

Regex-Objekte zur Effizienzsteigerung

Bei allen bisherigen Überlegungen zur Effizienzsteigerung ging es um Regex-Literale. Das Ziel war, die Regex nur so oft wie unbedingt nötig zu untersuchen und zu kompilieren. Wir können stattdessen aber auch ein Regex-Objekt verwenden. Regex-Objekte sind im Grunde fertige, vorkompilierte reguläre Ausdrücke, die in eine Variable verpackt sind. Sie werden mit dem qr/.../-Operator erzeugt (siehe Der qr/.../-Operator und Regex-Objekte).

Hier sehen Sie eine Version unseres Beispiels mit einem Regex-Objekt:

sub LogdateiFuerHeute()
{
   my $heute = (qw<Sun Mon Tue Wed Thu Fri Sat>)[(localtime)[6]];

   my $RegexObj = qr/^$heute:/i; # Wird einmal pro Funktionsaufruf kompiliert!

   while (<LOGFILE>) {
      if ($_ =~ $RegexObj) {
          ...
      }
   }
}

Hier wird bei jedem Aufruf der Funktion ein neues Regex-Objekt erzeugt. Danach wird dieses Objekt direkt für jede Zeile der Logdatei verwendet. Wenn ein bloßes Regex-Objekt als Operand verwendet wird, werden keinerlei Interpolation, Kompilierung oder sonstige Vorverarbeitungsschritte ausgeführt. Diese Schritte erfolgen früher, wenn das Regex-Objekt erzeugt wird, und nicht erst, wenn es verwendet wird. Man kann sich ein Regex-Objekt als einen Cache-Eintrag mit einem Namen vorstellen, den man einsetzen kann, wenn es einen danach gelüstet.

Diese Lösung vereinigt die Vorteile der früheren: Sie ist effizient, weil die Regex nur dann neu kompiliert wird, wenn die Funktion aufgerufen wird (und nicht bei jeder Zeile der Logdatei). Anders als in der vorherigen Lösung mit /o wird aber die Regex neu kompiliert, wenn sich das Datum geändert haben könnte.

Beachten Sie, dass in diesem Beispiel zwei Regex-Operanden auftreten. Der Operand von qr/.../ ist kein Regex-Objekt. Der qr/.../-Operator erzeugt aus dem Regex-Literal im Operanden ein Regex-Objekt. Dieses wird dann in der Schleife als Operand für den Match-Operator =~ benutzt.

Regex-Objekte mit m/.../ verwenden

Man kann ein Regex-Objekt für eine Mustersuche so angeben:

if ($_ =~ $RegexObj) {

Oder auch mit den bekannten Schrägstrichen:

if (m/$RegexObj/) {

Dies ist kein normales Regex-Literal, auch wenn es so aussieht. Wenn das »Regex-Literal« nur aus einem Regex-Objekt besteht, wird es genauso behandelt wie das Regex-Objekt allein. Dieses Verhalten hat ein paar Vorteile: Die Notation m/.../ ist die übliche, sie ist den meisten vertraut. Wenn man den Standardsuchstring $_ benutzt, muss man ihn nicht explizit angeben. Außerdem kann man nur bei dieser Notation den /g-Modifikator bei einem Regex-Objekt angeben.

Der /o-Modifikator mit qr/.../

Der /o-Modifikator kann zusammen mit qr/.../ benutzt werden, aber bei diesem Beispiel ist das wenig sinnvoll. Wie bei den anderen Regex-Operatoren bewirkt qr/.../o, dass nur bei der ersten Ausführung kompiliert wird, nachher wird immer die kompilierte Version aus dem Cache verwendet. In unserem Fall enthielte $RegexObj immer das gleiche Regex-Objekt, auch bei späteren Aufrufen der Funktion LogdateiFuerHeute() und unabhängig vom Wert von $heute. Wir hätten das gleiche Problem wie bei der Version mit m/.../o weiter oben bei Der /o-Modifikator: »Nur einmal kompilieren«.

Gebrauch der voreingestellten Regex zur Effizienzsteigerung

Die Eigenschaften der voreingestellten Regex (siehe Voreinstellung bei einem leeren Regex-Operanden) können zur Verbesserung der Effizienz ausgenutzt werden, allerdings ist diese Methode weitgehend von den Regex-Objekten abgelöst worden. Ich beschreibe sie nur kurz:

sub LogdateiFuerHeute() {

   my $heute = (qw<Sun Mon Tue Wed Thu Fri Sat>)[(localtime)[6]];

   # Alle Tage durchgehen, bis ein Ausdruck passt; dieser wird zur voreingestellten Regex.
   "Sun:" =~ m/^$heute:/i or
   "Mon:" =~ m/^$heute:/i or
   "Tue:" =~ m/^$heute:/i or
   "Wed:" =~ m/^$heute:/i or
   "Thu:" =~ m/^$heute:/i or
   "Fri:" =~ m/^$heute:/i or
   "Sat:" =~ m/^$heute:/i;

   while (<LOGFILE>) {
      if (m//) { # Voreingestellte Regex anwenden.
         ...
      }
   }
}

Der springende Punkt dabei ist, dass die voreingestellte Regex nur bei einem erfolgreichen Matching gesetzt wird. In diesem Beispiel werden alle Wochentage durchprobiert, und einer davon muss sicher passen und setzt so die voreingestellte Regex. Das ist ziemlich um die Ecke gedacht, und ich empfehle dieses Vorgehen nicht.

  

<< 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