Benchmarking
(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)
In diesem Kapitel geht es um Geschwindigkeit und Effizienz, und ich erwähne ab und zu Resultate von Benchmarks für einzelne reguläre Ausdrücke. Ich möchte deshalb ein paar grundsätzliche Dinge zum Benchmarking sagen und einfache Benchmark-Programme in einer Reihe von Sprachen vorstellen.
Beim Benchmarking geht es darum zu messen, wie viel Zeit für einen bestimmten Programmteil benötigt wird. Man fragt dazu die Systemzeit ab, lässt den Programmteil laufen, fragt die Systemzeit erneut ab und gibt die Differenz der zwei Zeiten aus, die offenbar der Laufzeit des Programmstücks entspricht. Als Beispiel vergleichen wir die zwei Ausdrücke ˹^(a|b|c|d|e|f|g)+$˼ und ˹^[a-g]+$˼. Hier sehen Sie ein Benchmark-Programm in Perl (andere Sprachen folgen später), das aber in dieser Form noch nicht brauchbar ist:
use Time::HiRes 'time'; # time() gibt jetzt eine Fließkommazahl zurück.
$Startzeit = time();
"abababdedfg" =~ m/^(a|b|c|d|e|f|g)+$/;
$Endzeit = time();
printf("Alternation: %.3f sec.\n", $Endzeit - $Startzeit);
$Startzeit = time();
"abababdedfg" =~ m/^[a-g]+$/;
$Endzeit = time();
printf("Zeichenklasse: %.3f sec.\n", $Endzeit - $Startzeit);Das Skript sieht einfach aus (und ist es auch), aber für einen aussagekräftigen Benchmark-Test müssen ein paar Bedingungen erfüllt sein:
Nur »interessanter« Code soll gemessen werden
Von allen Funktionen, die das Programm verrichtet, wird nur die »wirkliche Arbeit« gemessen bzw. so wenig wie möglich vom Drum und Dran. Wenn Daten erst initialisiert werden müssen oder wenn nach der eigentlichen Arbeit aufgeräumt werden muss, soll das außerhalb der Zeitmessung passieren.
Es muss genügend Code getestet werden
Oft ist das interessante Stück Code sehr kurz, und die Auflösung der Systemuhr ist zu ungenau, als dass man aussagekräftige Messungen machen könnte.
Wenn ich das einfache Perl-Programm oben auf meinem Rechner laufen lasse, erhalte ich folgende Ausgabe:
Alternation: 0.000 sec.
Zeichenklasse: 0.000 sec.Das sagt nun fast gar nichts aus, außer dass beide regulären Ausdrücke schneller ablaufen als die kürzeste messbare Zeit. Wenn etwas so schnell abläuft, lässt man es daher zweimal, zehnmal, hundertmal oder gleich 10 000 000 mal ablaufen – so oft, bis man »genügend« genaue Daten bekommt. Was »genügend« ist, hängt etwas vom System ab. Bei den meisten Systemen hat die Systemzeit eine Auflösung von mindestens einer Hundertstelsekunde. Dann bekommt man bei einer Messzeit von einer halben Sekunde schon aussagekräftige Werte.
Es soll der »richtige« Code gemessen werden
Wenn eine sehr schnelle Operation 10 000 000 mal ausgeführt wird, darf man bereits das Nachführen der Zählervariablen nicht mehr vernachlässigen, aber das ist Overhead und keine »wirkliche Arbeit«. Nach Möglichkeit soll der Verwaltungsaufwand minimiert werden, so dass nur die eigentliche Arbeit gemessen wird. In unserem Perl-Beispiel werden die Ausdrücke auf ziemlich kurze Strings angewendet; wenn man längere Strings nimmt, wird pro Iteration viel mehr eigentliche Arbeit verrichtet.
Wenn man dies alles berücksichtigt, ergibt sich ein neues Benchmark-Programm:
use Time::HiRes fltimefl; # time() gibt jetzt eine Fließkommazahl zurück.
$Iterationen = 1000; # Anzahl der Iterationen.
$Teststring = "abababdedfg" x 1000; # Ergibt einen sehr langen String.
$Zaehler = $Iterationen;
$Startzeit = time();
while ($Zaehler-- > 0) {
$Teststring =~ m/^(a|b|c|d|e|f|g)+$/;
}
$Endzeit = time();
printf("Alternation: %.3f sec.\n", $Endzeit - $Startzeit);
$Zaehler = $Iterationen;
$Startzeit = time();
while ($Zaehler-- > 0) {
$Teststring =~ m/^[a-g]+$/;
}
$Endzeit = time();
printf("Zeichenklasse: %.3f sec.\n", $Endzeit - $Startzeit);Hier werden $Teststring und $Zaehler vor der Zeitmessung initialisiert. (Für $Teststring nehmen wir den für solche Zwecke idealen x-Operator von Perl, der den String auf der linken Seite so oft repliziert, wie auf der rechten Seite angegeben wird.) Auf meinem Rechner bekomme ich mit Perl 5.8 die folgende Ausgabe:
Alternation: 7.276 sec.
Zeichenklasse: 0.333 sec.
Bei diesen Testdaten ist die Zeichenklasse also etwa 22 mal so schnell wie die Alternation. Ein solcher Benchmark-Test sollte mehrfach ausgeführt werden, es gilt die kürzeste gemessene Zeit. Auf diese Weise schaltet man den Einfluss von möglicherweise gleichzeitig ablaufenden Hintergrundprozessen aus.
Was genau wird da gemessen?
Wir wollen sehen, was passiert, wenn wir den Initialisierungsteil folgendermaßen abändern:
my $Iterationen = 1000000;
my $Teststring = "abababdedfg";Nun ist der Teststring tausendmal kürzer, dafür werden tausendmal so viele Iterationen ausgeführt. Die Menge der zu verrichtenden »Arbeit« ist im Prinzip dieselbe, aber die Resultate unterscheiden sich deutlich:
Alternation: 18.167 sec.
Zeichenklasse: 5.231 sec.
Beide Versionen sind langsamer als zuvor, aber die zwei Ausdrücke unterscheiden sich nur noch um den Faktor 3,5. Warum? Nach der Änderung gibt es mehr Verwaltungsarbeit, mehr Overhead. Das Hinunterzählen und Testen von $Zaehler und das Vorbereiten der Regex-Maschine geschieht nun tausendmal so oft wie vorhin.
Diese zusätzliche Verwaltungsarbeit macht im schnelleren Fall fast 5 Sekunden aus, bei der Version mit der Alternation sogar mehr als 10 Sekunden. Warum macht das im zweiten Fall so viel mehr aus? Vor allem liegt es an den einfangenden Klammern, die nun tausendmal Text einfangen – der dann gar nicht verwendet wird.
Wie dem auch sei, es geht hier vor allem darum zu zeigen, dass die gemessenen Resultate oft in krasser Weise davon abhängen, wie viel eigentliche Arbeit und wie viel Verwaltungs-Overhead gemessen wurde.
Benchmarks mit PHP
Hier folgt eine PHP-Version des Benchmark-Programms:
$Iterationen = 1000;
/* Einen langen Suchtext aufsetzen */
$TestString = "";
for ($i = 0; $i < 1000; $i++)
$TestString .= "abababdedfg";
/* Erster Test mit einer Alternation */
$Startzeit = gettimeofday();
for ($i = 0; $i < $Iterationen; $i++)
preg_match('/^(a|b|c|d|e|f|g)+$/', $TestString);
$Endzeit = gettimeofday();
$sec = ($Endzeit['sec'] + $Endzeit['usec'] /1000000) -
($Startzeit['sec'] + $Startzeit['usec']/1000000);
printf("Alternation: %.3f sec.\n", $sec);
/* Zweiter Test mit einer Zeichenklasse */
$Startzeit = gettimeofday();
for ($i = 0; $i < $Iterationen; $i++)
preg_match('/^[a-g]+$/', $TestString);
$Endzeit = gettimeofday();
$sec = ($Endzeit['sec'] + $Endzeit['usec'] /1000000) -
($Startzeit['sec'] + $Startzeit['usec']/1000000);
printf("Zeichenklasse: %.3f sec.\n", $sec);Auf meinem Rechner erhalte ich:
Alternation: 27.404 sec.
Zeichenklasse: 0.288 sec.
Wenn Sie bei diesem Benchmark einen Fehler der Art »not being safe to rely on the system’s timezone settings« bekommen, sollten Sie zuoberst diese Zeilen einfügen:
if (phpversion() >= 5)
date_default_timezone_set("GMT");Benchmarks mit Java
Das Benchmarking in Java ist aus verschiedenen Gründen eine etwas zweifelhafte Wissenschaft. Wir betrachten zunächst ein etwas einfältiges Beispiel, erläutern, warum es einfältig ist, und zeigen dann, wie wir es weniger einfältig machen können.
import java.util.regex.*;
public class JavaBenchmark {
public static void main(String [] args)
{
Matcher regex1 = Pattern.compile("^(a|b|c|d|e|f|g)+$").matcher("");
Matcher regex2 = Pattern.compile("^[a-g]+$").matcher("");
long iterationen = 1000;
StringBuffer temp = new StringBuffer();
for (int i = 1000; i > 0; i--)
temp.append("abababdedfg");
String testString = temp.toString();
// Erste Regex ...
long zaehler = iterationen;
long startZeit = System.currentTimeMillis();
while (--zaehler > 0)
regex1.reset(testString).find();
double sekunden =
// Zweite Regex ... (System.currentTimeMillis() - startZeit)/1000.0;
System.out.println("Alternation: " + sekunden + " sec.");
zaehler = iterationen;
startZeit = System.currentTimeMillis();
while (--zaehler > 0
regex2.reset(testString).find();
sekunden = (System.currentTimeMillis() - startZeit)/1000.0;
System.out.println("Zeichenklasse: " + sekunden + " sec.");
}
}Die regulären Ausdrücke werden zu Programmbeginn kompiliert, im Initialisierungsteil. Wir wollen die Geschwindigkeit der eigentlichen Treffersuche messen, nicht die der Kompilierung.
Bei Java hängt die Geschwindigkeit von der benutzten Virtuellen Maschine (VM) ab. Allein im normalen JRE von Sun sind zwei verschiedene virtuelle Maschinen enthalten, eine Client-VM, die besonders schnell startet, und eine Server-VM, die für längere Programme besser optimiert ist.
Auf meinem System ergab der Benchmark-Test mit der Client-VM Folgendes:
Alternation: 19.318 sec.
Zeichenklasse: 1.685 sec.
Mit der Server-VM ergaben sich folgende Werte:
Alternation: 12.106 sec.
Zeichenklasse: 0.657 sec.
Der Benchmark-Test ist deswegen zweifelhaft und das Beispiel etwas naiv, weil die Zeitmessung unter Umständen sehr stark von den Optimierungen der VM abhängt. Manche virtuellen Maschinen enthalten einen JIT-Compiler (Just-In-Time-Compiler), der ein Programmstück erst dann kompiliert, wenn es gebraucht wird.
In der Java-VM von Sun wird ein Verfahren verwendet, das ich als »Besser-spät-als-nie-Compiler« (BSAN) bezeichnen möchte. Er wird während der Ausführung aufgerufen und kompiliert und optimiert ein bestimmtes Stück Code, wenn die VM bemerkt, dass dieser Code »heiß« ist, d.h., dass er sehr häufig ausgeführt wird. Wenn die VM schon länger läuft (zum Beispiel in einem Serverprozess), dann sind naturgemäß schon etliche Codeteile so optimiert – die VM ist »aufgewärmt«; in unseren Benchmark-Tests dagegen ist die VM »kalt« (der BSAN-Compiler hat noch nichts optimiert).
Wir können die VM »aufwärmen«, indem wir den Teil mit den Zeitmessungen in eine Schleife verpacken:
// Erste Regex ...
for (int i = 4; i > 0; i--)
{
long zaehler = iterationen;
long startZeit = System.currentTimeMillis();
while (--zaehler > 0)
{
regex1.reset(testString).find();
}
double sekunden = (System.currentTimeMillis() - startZeit)/1000.0;
System.out.println("Alternation: " + sekunden + " sec.");
}Wenn die Regex durch die zusätzliche Schleife oft genug angewendet wird (z.B. länger als 10 Sekunden), dann hat der BSAN-Compiler den heißen Code optimiert, und die späteren Iterationen laufen etwas schneller. Mit der Server-VM erhalte ich Zeiten, die etwa 8 % bzw. 25 % schneller sind:
Alternation: 11.151 sec.
Zeichenklasse: 0.483 sec.
Ein anderes Problem bei Java ist der Garbage Collector, der irgendwann aktiviert wird und unbenutzten Speicher freigibt. Auch diese Störung kann man durch genügend lange Laufzeit minimieren.
Benchmarks mit VB.NET
Hier folgt unser Benchmark-Programm in VB.NET:
Option Explicit On
Option Strict On
Imports System.Text.RegularExpressions
Module Benchmark
Sub Main()
Dim Regex1 as Regex = New Regex("^(a|b|c|d|e|f|g)+$")
Dim Regex2 as Regex = New Regex("^[a-g]+$")
Dim Iterationen as Integer = 1000
Dim Teststring as String = ""
Dim I as Integer
For I = 1 to 1000
Teststring = Teststring & "abababdedfg"
Next
Dim Startzeit as Double = Timer()
For I = 1 to Iterationen
Regex1.Match(Teststring)
Next
Dim Sekunden as Double = Math.Round(Timer() - Startzeit, 3)
Console.WriteLine("Alternation: " & Sekunden & " sec.")
Startzeit = Timer()
For I = 1 to Iterationen
Regex2.Match(Teststring)
Next
Sekunden = Math.Round(Timer() - Startzeit, 3)
Console.WriteLine("Zeichenklasse: " & Sekunden & " sec.")
End Sub
End ModuleAuf meinem Rechner erhalte ich:
Alternation: 13.311 sec.
Zeichenklasse: 1.680 sec.
Im .NET-Framework kann man beim Regex-Konstruktor die Option RegexOptions.Compiled angeben. Die Regex wird dann in eine weitergehend optimierte Form kompiliert (siehe Optimierte Ausdrücke mit »Compiled«). Damit erhalte ich:
Alternation: 5.499 sec.
Zeichenklasse: 1.157 sec.
Beide Versionen sind mit der Compiled-Option schneller, vor allem aber die Alternation (sie ist fast dreimal so schnell, die Version mit der Zeichenklasse ist nur 1,5 mal so schnell). Offenbar kann der Compiler bei der Alternation mehr optimieren.
Benchmarks mit Ruby
Hier sehen Sie das Benchmark-Programm in Ruby:
Iterationen=1000
testString=""
for i in 1..1000
testString += "abababdedfg"
end
Regex1 = Regexp::new("^(a|b|c|d|e|f|g)+$");
Regex2 = Regexp::new("^[a-g]+$");
startZeit = Time.new.to_f
for i in 1..Iterationen
Regex1.match(testString)
end
print "Alternation: %.3f sec.\n" % (Time.new.to_f - startZeit);
startZeit = Time.new.to_f
for i in 1..Iterationen
Regex2.match(testString)
end
print "Zeichenklasse: %.3f sec.\n" % (Time.new.to_f - startZeit);Auf meinem System erhalte ich die folgenden Laufzeiten:
Alternation: 16.311 sec.
Zeichenklasse: 3.479 sec.
Benchmarks mit Python
Hier sehen Sie unser Benchmark-Beispiel in Python:
import re, time, fpformat
Regex1 = re.compile("^(a|b|c|d|e|f|g)+$")
Regex2 = re.compile("^[a-g]+$")
Iterationen = 1250;
Teststring = ""
for i in range(800):
Teststring += "abababdedfg"
Startzeit = time.time()
for i in range(Iterationen):
Regex1.search(Teststring)
Sekunden = time.time() - Startzeit
print "Alternation: " + fpformat.fix(Sekunden,3) + " sec."
Startzeit = time.time()
for i in range(Iterationen):
Regex2.search(Teststring)
Sekunden = time.time() - Startzeit
print "Zeichenklasse: " + fpformat.fix(Sekunden,3) + " sec."Bei der Python-Version musste ich den Suchstring etwas zurechtstutzen, weil die Regex-Maschine bei der Originalversion mit einem Laufzeitfehler abbrach (»maximum recursion limit exceeded«). Das ist so eine Art Überdruckventil, das anspricht, wenn die Gefahr einer unendlichen Schleife besteht.
Ich habe das durch eine entsprechend höhere Anzahl von Iterationen kompensiert. Auf meinem Rechner gibt das Programm Folgendes aus:
Alternation: 10.357 sec.
Zeichenklasse: 0.769 sec.
Benchmarks mit Tcl
Hier ist unser bekanntes Beispiel, diesmal in Tcl:
set Iterationen 1000
set Teststring ""
for {set i 1000} {$i > 0} {incr i -1} {
append Teststring "abababdedfg"
}
set Zaehler $Iterationen
set Startzeit [clock clicks -milliseconds]
for {} {$Zaehler > 0} {incr Zaehler -1} {
regexp {^(a|b|c|d|e|f|g)+$} $Teststring
}
set Endzeit [clock clicks -milliseconds]
set Sekunden [expr ($Endzeit - $Startzeit)/1000.0]
puts [format "Alternation: %.3f sec." $Sekunden]
set Zaehler $Iterationen
set Startzeit [clock clicks -milliseconds]
for {} {$Zaehler > 0} {incr Zaehler -1} {
regexp {^[a-g]+$} $Teststring
}
set Endzeit [clock clicks -milliseconds]
set Sekunden [expr ($Endzeit - $Startzeit)/1000.0]
puts [format "Zeichenklasse: %.3f sec." $Sekunden]Auf meinem Rechner erhalte ich mit diesem Benchmark-Test:
Alternation: 0.362 sec.
Zeichenklasse: 0.352 sec.
Boah! Die sind praktisch gleich schnell! Nun, Sie erinnern sich an die Tabelle Einige Programme und ihre Regex-Maschinentypen: Tcl besitzt eine kombinierte NFA/DFA-Maschine, und für einen DFA sind diese zwei regulären Ausdrücke identisch. Das meiste aus diesem Kapitel spielt für Tcl einfach keine Rolle. Beachten Sie auch den Kasten DFAs, Tcl und das »Tuning« von regulären Ausdrücken.
| << 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