Perl kopiert den Suchstring vor der Mustersuche

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

Bei einer Mustersuche oder bei einer Substitution muss Perl manchmal mit einigem Aufwand eine Kopie des Suchstrings anlegen. Wir werden sehen, dass diese Kopie für bestimmte Regex-Variablen und deren Eigenschaften benötigt wird, aber manchmal ist das Kopieren des Suchstrings eigentlich unnötig. Wenn eine Kopie angelegt wird, diese aber nicht benötigt wird – besonders, wenn der Suchtext sehr lang ist und wenn Geschwindigkeit eine Rolle spielt –, sollten wir versuchen, diesen zusätzlichen Aufwand zu vermeiden.

In den nächsten Abschnitten wird erläutert, warum und wann Perl diese Kopie erzeugt, wofür die Kopie gebraucht wird und wie dieses Kopieren vermieden werden kann, wenn Effizienz gefragt ist.

Die Kopie des Suchstrings wird für $1, $&, $', $+ ... benötigt

Perl kopiert den Suchstring vor der Mustersuche oder vor der Substitution, damit $1, $& und die anderen Regex-Variablen, die Textstücke aus dem Suchstring enthalten, unterstützt werden können (siehe unter Durch das Matching gesteuerte Spezialvariablen). Diese Textstücke werden nicht wirklich erzeugt, vielmehr speichert Perl für $1 usw. Verweise auf Anfangs- und Endpositionen in dieser Kopie des Suchstrings ab. Das erfordert während der Mustersuche weniger Aufwand, und das ist gut so, weil diese Variablen später oft gar nicht gebraucht werden. Dies ist eine Art von »aufgeschobener Auswertung« (lazy evaluation); damit wird eine Menge unnötiger Arbeit eingespart.

Stattdessen muss vor der Mustersuche mit zusätzlichem Aufwand eine Kopie des gesamten Suchstrings angelegt werden. Aber warum eigentlich? Kann Perl nicht einfach Verweise auf Positionen im ursprünglichen Suchstring abspeichern? Nun, betrachten wir eine Substitution der folgenden Art:

$Subject =~ s/^(?:Re:\s*)+//;

Nach dieser Substitution verweist $& auf den Text, der aus der Suchtext-Variablen $Subject entfernt wurde, aber genau dieser Text ist nun gelöscht, und die Verweise zeigen ins Leere. Perl kann sich nicht auf $Subject beziehen, wenn danach $& benutzt wird. Ganz ähnlich geht es in der folgenden Situation:

if ($Subject =~ m/^SPAM:(.+)/i) {
    $Subject = "-- Spam entfernt --";
    $SpamAnzahl{$1}++;
}

Zum Zeitpunkt, an dem $1 ausgewertet wird, ist die Variable $Subject bereits überschrieben. Perl muss eine Kopie anlegen, damit $1 unterstützt werden kann.

Die Kopie des Suchstrings wird nicht immer benötigt

In der Praxis wird die Kopie des Suchstrings vor allem für die Variablen $1, $2, $3 usw. benötigt. Wenn die Regex aber keine einfangenden Klammern besitzt, können diese Variablen nicht gesetzt werden und die zusätzliche Arbeit braucht nicht erledigt zu werden. Kann bei regulären Ausdrücken ohne einfangende Klammern auf die Kopie des Suchstrings verzichtet werden? Nicht immer ...

Die Variablen $`, $& und $' sind »unartig«

Die drei Variablen $`, $& und $' beziehen sich nicht auf einfangende Klammern. Einen Treffertext und einen Text vor und nach dem Treffer gibt es bei jeder Mustersuche und bei jeder Substitution. Perl kann nicht ohne Weiteres herausfinden, auf welche Regex sich diese Variablen beziehen, also muss jedes Mal eine Kopie des Suchstrings angelegt werden.

Es sieht so aus, als ob diese Kopie auf jeden Fall angelegt werden müsste. Perl merkt immerhin, wenn im ganzen Programm (mit allen Bibliotheksfunktionen!) nirgends eine der Variablen $`, $& oder $' benutzt wird. Wenn diese nicht vorkommen, geht Perl davon aus, dass auf das Kopieren des Suchstrings verzichtet werden kann. Wenn Sie sicherstellen können, dass Ihr Code und alle benutzten Module nie eine der Variablen $`, $& oder $' verwenden, dann muss keine Kopie des Suchstrings angelegt werden – eine beträchtliche Optimierung! Mit nur einem $`, $& oder $' irgendwo im Programm ist die Optimierung dahin. Wie asozial! Ich nenne diese Variablen deshalb »unartig«.

Wie teuer ist die Kopie des Suchstrings?

Als ganz einfachen Benchmark-Test habe ich m/c/ auf die gut 130 000 Zeilen des Perl-Quelltextes angewandt. Dieser Test untersucht nur jede Zeile, ob darin ein ›c‹ vorkommt – diese Information wird aber nicht weiter gebraucht. Der einzige Zweck besteht darin, die Leistungseinbuße beim Kopieren des Suchtextes zu messen. Ich habe auf zwei Arten getestet: Einmal stellte ich sicher, dass keine Kopien angelegt werden, und einmal erzwang ich das Kopieren. Ein Leistungsunterschied ist also allein dem zusätzlichen Kopieren des Suchtextes zuzuschreiben.

Der Versuch mit dem zusätzlichen Kopieren dauerte mehr als 40 % länger. Dies entspricht einem »durchschnittlichen schlechten Fall«. Je mehr Arbeit das Programm sonst verrichtet, desto kleiner wird der negative Effekt. Der Benchmark-Test tut aber sonst gar nichts, also wird die Leistungseinbuße überhöht dargestellt.

In einem wirklich katastrophalen Fall kann die Arbeit durch das Kopieren des Suchstrings alles andere überdecken. Ich habe den gleichen Test auf die gleichen Daten angewandt, diesmal aber als eine einzige Zeile (mehr als 3,5 Megabyte) statt etwa 130 000 Zeilen vernünftiger Länge. So kann die relative Leistung bei einem einzigen Matching getestet werden. Der Test ohne Kopieren war beinahe sofort beendet, weil nur das erste ›c‹ in der riesengroßen Zeile gefunden werden musste. Im zweiten Test musste dagegen eine Kopie dieser Zeile angelegt werden. Mit dieser mehr als 3,5 Megabyte großen Zeile dauerte das mehr als 7000 mal länger! Wenn man diese Einflüsse kennt, kann man sie beim Programmieren auch berücksichtigen.

Kopieren des Suchstrings vermeiden

Es wäre schön, wenn Perl die Absicht des Programmierers kennen und den Suchtext nur dann kopieren würde, wenn es wirklich nötig ist. Diese Kopiervorgänge sind aber nicht an sich »schlecht« – das ist eine der Eigenschaften, weshalb wir eben Perl benutzen und nicht etwa C oder Assembler. Einer der Hauptgründe zur Entwicklung von Perl war ja gerade der, dass sich der Programmierer nicht um jedes Detail kümmern muss, sondern sich auf die eigentliche Problemlösung konzentrieren kann.

»Unartige« Variablen vermeiden

Dennoch wäre es gut, unnötige Arbeit zu vermeiden. Nach Möglichkeit wird man natürlich in einem Programm vollständig auf die Variablen $`, $& und $' verzichten. Die Variable $& kann man oft sehr einfach eliminieren, indem man die ganze Regex einklammert und stattdessen $1 verwendet. Anstatt HTML-Tags mit s/<\w+>/\L$&\E/g in Kleinbuchstaben zu verwandeln, verwendet man besser s/(<\w+>)/\L$1\E/g.

Wenn der Suchstring nicht verändert wurde, können $` und $' oft durch substr() ersetzt werden. Nach einer erfolgreichen Mustersuche im Suchstring kann man die unartigen Variablen durch die Ausdrücke aus der folgenden Tabelle ersetzen:

Variable Umschreibung mit substr
$` substr(Suchstring, 0, $-[0])
$& substr(Suchstring, $-[0], $+[0] - $-[0])
$' substr(Suchstring, $+[0])

Die Elemente der Arrays @- und @+ (siehe @- und @+) enthalten Positionen, die sich auf den ursprünglichen Suchstring beziehen, und nicht Textstücke daraus, sie können daher ohne Bedenken benutzt werden.

Ich habe auch eine Ersatzdarstellung für $& angegeben. Diese kann effizienter sein als der Gebrauch einer Klammer und $1, wenn dadurch einfangende Klammern überhaupt vermieden werden können. Die Idee beim Vermeiden von $& war ja, das Kopieren des Suchstrings bei den regulären Ausdrücken zu vermeiden, die keine einfangenden Klammern enthalten. Wenn überall $& vermieden wird, dafür aber jede Regex einfangende Klammern erhält, ist gar nichts gewonnen.


Ein Programm auf Kontamination mit $& testen

Es ist nicht immer einfach festzustellen, ob ein Programm »unartig« ist (d.h. ob es $&, $` oder $' verwendet), insbesondere wenn diese Variablen in Modulen verwendet werden. Aber es gibt dennoch einige Möglichkeiten. Wenn der Perl-Interpreter mit der Compiler-Option -DDEBUGGING übersetzt wurde und Sie beim Aufruf von Perl die Optionen -c und -Mre=debug angeben (siehe Debugging-Informationen zu regulären Ausdrücken), erscheinen gegen Ende der Debugging-Ausgabe Zeilen der Art ›Enabling $` $& $' support‹ oder ›Omitting $` $& $' support‹. Wenn »Enabling« (eingeschaltet) ausgegeben wird, ist das Programm kontaminiert.

Es ist möglich (allerdings etwas unwahrscheinlich), dass im Programm eine unartige Variable in einem eval vorkommt, was Perl erst dann erkennen kann, wenn der eval-Code ausgeführt wird. Diese Fälle kann man mit dem Modul Devel::SawAmpersand aufspüren, das auf dem CPAN zu finden ist:

END {
   require Devel::SawAmpersand;
   print "Unartige Variablen!\n" if Devel::SawAmpersand::sawampersand;
}
Devel::SawAmpersand enthält auch das Paket Devel::FindAmpersand, das die Stelle ausgeben sollte, an der die fragliche Variable auftritt. Leider funktioniert diese Routine mit den neuesten Perl-Versionen nicht zuverlässig. Außerdem sind beide Module nicht ganz einfach zu installieren.

Man kann das Vorhandensein von unartigen Variablen auch dadurch feststellen, dass man zur Laufzeit testet, ob die Effizienzeinbuße tatsächlich auftritt:

use Time::HiRes;
sub Knigge() {                 # Test auf Gutartigkeit.
   my $text = 'x' x 10_000;    # Nicht-triviale Datenmenge.

   # Zeit für die leere Schleife ermitteln.
   my $start = Time::HiRes::time();
   for (my $i = 0; $i < 5_000; $i++)  {  }
   my $leer = Time::HiRes::time() - $start;

   # Zeit für die gleiche Anzahl einfacher Matchings ermitteln.
   $start = Time::HiRes::time();
   for (my $i = 0; $i < 5_000; $i++)  { $text =~ m/^/  }
   my $delta = Time::HiRes::time() - $start;
  
   # Faktor 5 ist nur Pi mal Daumen.
   printf "Ihr Programm ist %s (Leerschleife=%.2f, Delta=%.2f)\n",
      ($delta > $leer*5) ? "unartig" : "brav", $leer, $delta;
}

»Unartige« Module vermeiden

$`, $& und $' zu vermeiden bedeutet auch, keine Bibliotheksdateien zu verwenden, in denen diese Variablen auftauchen. Bei den mit Perl mitgelieferten Modulen werden die Variablen nirgends außer im English-Modul verwendet. Aber auch dieses Modul kann man so verwenden, dass die drei Variablen nicht gebraucht werden:

use English '-no_match_vars';

Damit wird das Modul »brav«, nur sind für die drei Variablen keine »langen« Namen verfügbar. Aber wir wollen diese Variablen ohnehin nicht verwenden, weder mit kurzen noch mit langen Namen! Wenn Sie ein anderes Modul vom CPAN oder von sonst wo installieren wollen, möchten Sie vielleicht testen, ob das Modul $`, $& oder $' verwendet. Im obigen Kasten wird eine Methode vorgestellt, mit der dies einfach möglich ist.

  

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