Effizienz in Perl

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

Zum größten Teil sind die Überlegungen zur Effizienz bei Perl die gleichen, die für jede traditionelle NFA-Maschine gelten. Die Methoden aus Die Kunst, reguläre Ausdrücke zu schreiben – interne Optimierungen, das »Schleifen aufbrechen«, und nicht zuletzt der Abschnitt »Denken!« – sind auf Perl genauso anwendbar.

Daneben gibt es natürlich Perl-spezifische Eigenheiten. In diesem Abschnitt betrachten wir die folgenden Themen eingehender:

There’s More Than One Way To Do It

(TMTOWTDI, Viele Wege führen zum Ziel). Perl ist ein großer Werkzeugkasten mit einer Fülle von Möglichkeiten, um ein bestimmtes Problem zu lösen. Wie man Probleme am besten mit Perl löst und welche Werkzeuge man am vorteilhaftesten dazu verwendet – das ist »The Perl Way« zu einem effizienten und verständlichen Programm. Manchmal sieht es aus, als ob sich Effizienz und Verständlichkeit gegenseitig ausschließen, deshalb hilft ein besseres Verständnis der Sprache, die gute Lösung zu finden.

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

Auf den Gebieten Variableninterpolation und Kompilierung der Regex kann man oft viel Zeit einsparen. Mit dem Modifikator /o, über den ich bisher wenig gesagt habe, kann man zusammen mit Regex-Objekten (qr/.../) steuern, wann eine Regex neu kompiliert werden muss und wann das unnötige Arbeit ist.

Strafpunkte durch $&

Die drei Nebeneffekt-Variablen $, $& und $' sind häufig ganz praktisch, aber führen zu einem Effizienz-Nachteil bei jeder Regex in jedem Skript, in dem sie auftauchen. Sie müssen nicht einmal wirklich benutzt werden, es genügt schon, wenn sie irgendwo vorkommen.

Die Funktion study

Seit Urzeiten kennt Perl die Funktion study(...). Ihr Gebrauch soll reguläre Ausdrücke schneller machen, aber niemand scheint study zu verstehen. Wir werden sehen, ob wir dieser Funktion auf den Grund gehen können.

Benchmarking

Das schnellste Programm ist das, das zuerst fertig ist (banal, aber wahr). Ob es sich um ein kleines Programmstück, eine wichtige Funktion oder um ein ganzes Programm mit wirklichen Daten handelt – nur Benchmark-Tests geben genaue Auskunft darüber, was wirklich schnell ist. In Perl sind Benchmark-Tests recht einfach aufzustellen, aber auch hier gibt es natürlich verschiedene Wege. Ich stelle eine einfache Methode vor, die mir bei der Vorbereitung dieses Buches in Hunderten von Fällen gute Dienste geleistet hat.

Debugging-Unterstützung für reguläre Ausdrücke in Perl

Es gibt Debugging-Optionen und Pragmas, die Perl instruieren, Auskunft über manche der Optimierungen zu geben, die die Regex-Maschine und das Getriebe vornehmen. Wir werden diese Debugging-Informationen analysieren und sehen, welche Geheimnisse Perl damit preisgibt.

»There’s More Than One Way To Do It«

Für ein bestimmtes Problem gibt es oft viele mögliche Lösungsmethoden. Wenn Effizienz und Lesbarkeit gegeneinander abgewogen werden sollen, gibt es oft nichts anderes, als alle Möglichkeiten durchzuprobieren. Wir betrachten das einfache Problem, die Zahlen in einer IP-Adresse wie ›18.181.0.24‹ mit Nullen aufzufüllen, so dass alle Bytes mit drei Ziffern dargestellt werden: ›018.181.000.024‹. Eine einfache und leicht verständliche Lösung ist:

Das ist so weit ganz gut, aber es gibt sicherlich andere Lösungen. In der folgenden Tabelle habe ich eine Reihe davon zusammengestellt. Sie sind nach relativer Laufzeit geordnet, wobei die schnellste auf eins normiert wurde. Die Aufgabe ist einfach und für sich genommen nicht sehr »interessant«, aber sie steht für eine ganze Klasse von ähnlichen Textverarbeitungsaufgaben. Ich kann nur empfehlen, die verschiedenen Lösungen zu vergleichen. Vielleicht entdecken Sie ja auch Perl-Konstrukte, die für Sie neu sind.

Tabelle: Eine IP-Adresse auf verschiedene Arten mit Nullen auffüllen.

Jedes der Beispiele ergibt bei einer wohlgeformten IP-Adresse das richtige Resultat; wenn sie dagegen mit einer unzulässigen Adresse konfrontiert werden, versagen sie auf recht verschiedene Arten. Wenn also die Gefahr besteht, dass die Daten falsch sind, müssen diese auf anderen Wegen validiert werden. Abgesehen davon bestehen Unterschiede nur bei Effizienz und Lesbarkeit. In Bezug auf die Lesbarkeit schneiden Nr. 1 und 13 gut ab (es ist aber erstaunlich, dass sie so verschieden schnell sind). Auch Nr. 3 und 4 (ähnlich wie Nr. 1) und Nr. 8 (ähnlich wie Nr. 13) sind noch ziemlich klar. Der Rest sieht zumindest kryptisch aus.

Und wie steht’s mit der Effizienz? Warum sind manche Ansätze schneller als andere? Das hängt von verschiedenen Faktoren ab: von der Arbeitsweise eines NFA (Wie Regex-Maschinen arbeiten), den eingesetzten Optimierungen (Die Kunst, reguläre Ausdrücke zu schreiben) und der Effizienz anderer Konstrukte von Perl (hier z.B. von sprintf und vom Substitutionsoperator). Die Lösungen mit dem /e-Modifikator stehen offenbar fast alle am Ende der Liste.

Die Paare Nr. 3/4 und Nr. 8/14 unterscheiden sich nur durch das Vorhandensein von Klammern in der Regex – die Version ohne Klammern ist offenbar ein bisschen schneller. Bei Nr. 8 wird aber statt der Klammern und $1 die Variable $& verwendet, und diese kann bei anderen regulären Ausdrücken im Programm zu großen Leistungseinbuße führen (siehe unter Perl kopiert den Suchstring vor der Mustersuche); in diesem Fall tut sie das aber offenbar nicht.

• Regex-Kompilierung, der /o-Modifikator, qr/.../ und Effizienz
• Perl kopiert den Suchstring vor der Mustersuche
• Die Funktion study
• Benchmarks
• Debugging-Informationen zu regulären Ausdrücken