gettext regex

[PHP-Desaster]

Ich hoffe der eine oder andere fands interessant.

Super erklärt, vielen Dank für den kleinen Einblick in die Interna der Regex-Engine

[onemorenerd]

Bei deinem Beispiel gab es einen Mismatch für den letzten Slash im Pattern.
Das Backtracking ist aber linear, es geht Zeichen für Zeichen zurück: /foo/bar, /foo/ba, /foo/b, /foo/. Deswegen eignet sich dein Beispiel nicht für Performancetests.

Der Performanceeinbruch zeigt sich, wenn in den Backtracking-Schritten noch weitere Expansionen getestet werden müssen. Ein klassisches Beispiel hierfür ist die beliebige Wiederholung eines Musters, das über mehrere Pfade gematcht werden kann.

((/foo)+(/foo)+)+/bar ist so ein "schlechtes" Pattern.
Um es übersichtlich zu halten, vereinfache ich es mal zu x+x+y.

Jeder sieht sofort, dass es äquivalent zu x{2,}y ist. Aber x{2,}y ist ein "gutes" Pattern. Angewendet auf xxy matcht es so lange x'e bis es nicht mehr geht, dann ein y und alles ist gut. 4 Zeichenvergleiche genügen also.

Das Pattern x+x+y beginnt genau so. Anfangs wird x+ auf xx expandiert. Das ist die Greedy-Eigenschaft.
Nun kommt im String ein y, aber das Pattern verlangt nach x+. Backtracking, einen Schritt zurück.
Jetzt matcht x+ mit x und das zweite x+ kann ein x matchen.
Zum Schluß noch das y.
Insgesamt 5 Zeichenvergleiche, also schon einer mehr als bei dem "guten" Pattern.

Natürlich ist ein Zeichenvergleich mehr kein Drama. Aber jetzt nehmen wir mal einen String, der nicht matcht: xxx.
Sehr kurz, aber mit viel Potential! Die Regex-Engine muss alle Expansionen der Wiederholungsgruppen durchprobieren. Es gibt zwei davon und wenn ich mich nicht verzählt habe, sind dafür 6 Zeichenvergleiche nötig. Das "gute" Pattern hätte wieder nur 4 gebraucht.

Jetzt nehmen wir mal xxxx, also ein x mehr. Für x+x+ gibt es nun schon 3 mögliche Expansionen und es sind 10 Zeichenvergleiche nötig.

Wie man sieht, steigt die Zahl der Backtracking-Schritte und Zeichenvergleiche gleichermaßen an, wenn man die Anzahl der x'e erhöht. Und in jedem Backtracking-Schritt muss wieder expandiert werden und darin wieder Backtracking und darin wieder Expansion ...
Die Performance geht exponentiell in den Keller!

[Griecherus]

Ah, OK. Hatte jetzt erst die Gelegenheit, mir das mal genauer durchzulesen. Danke für das interessante Beispiel

Grüße

[frank7l7]

Top, ... super erklärung. das sollte man in das php manual posten!