2016-07-21T11:24:08 GwenDragon

Kommt darauf an wie falsch es gemacht wird, damit es lahmt ;)

Deine beiden Beispiele unterscheiden sich ja nur darin, dass die Regex einmal fest codiert ist und das andere Mal als Variable übergeben wird.
Die Regex selbst und das potentielle Backtracking-Problem unterscheiden sich nicht.

Woher kommen die unterschiedlichen Laufzeiten?
Ist eine festcodierte Regex immer deutlich schneller? Ist der Zeitfresser evtl. nur die Zeile my $re = qr(...)? (Die könnte man aus dem Code-Schnipsel c2 auslagern.) Ist es evtl. nur ein Artefakt des Benchmarks, weil bei c2 die Regex-Engine 10000 mal geladen wird, während sie bei c1 nur einmal geladen wird? Kommt die festcodierte Regex dank irgendwelcher Optimierungen besser mit dem dem Backtracking-Problem zurecht? Oder ist der Zeitunterschied unabhängig vom Backtracking-Problem?

Ich habe jetzt leider keine Zeit um das genauer zu untersuchen.

Was mir bei dem verlinkten Artikel noch aufgefallen ist:
1. das Backtracking-Problem könnte man umgehen, wenn man zuerst mit s/\s+/ /g Whitespace zusammenfasst und erst dann Whitespace am Anfang und Ende der Strings entfernt (vorrausgesetzt, das ist an der Stelle zulässig - wenn man mehrfachen Whitespace innerhalb des Strings erhalten muss, geht es natürlich nicht.)
2. das eigentliche Problem liegt im Flow des CMS. Das System ist kollabiert, weil bei jeder Ausgabe der Homepage der problematische Input aus der Datenbank geholt und erst dann der Filter darauf angewendet wurde. Warum filtern die das Zeug nicht einmal bei der Eingabe bevor sie es in die Datenbank schreiben? Das hätte nur bei einem Request zu einer höheren Serverbelastung geführt. Der Server wäre dann evtl. kurzzeitig langsamer geworden, evtl. wäre die Eingabe gescheitert, aber der Server selbst wäre durchgelaufen.

Auch wenn ich den eigentlichen Grund für den Serverausfall im Aufbau/Flow des CMS und nicht im Backtracking der Regex sehe, bleibt die Frage, ob das mit Perl auch passieren kann. Oder ist die Regex-Engine bei Perl schlauer und optimiert in diesem Fall die Suche auf O(N) statt O(N^2)?

Zur Erinnerung - die Regex ist \s+$.
Wenn jetzt ein String eine lange Reihe von N Leerzeichen hat, muss die Regex beim erste Leerzeichen anfangen zu suchen, ob ein Match vorliegt. Sie überprüft dann die N Leerzeichen und stellt fest, dass hinter den Leerzeichen ein anderes Zeichen kommt, also kein Match vorliegt. Das hat die Komplexität O(N).

Laut StackExchange probiert die Regex es beim nächsten Leerzeichen erneut - und wieder wird die lange Reihe von Leerzeichen nicht von einem Zeilenende sondern einem anderen Zeichen abgeschlossen. Also Backtracking - und das Ganze mit dem dritten Leerzeichen als Start versuchen. So kommt man dann auf O(N*N).

Nun ist aber klar, dass wenn die Regex nicht schon beim ersten Leerzeichen als Start matched, sie auch bei allen anderen Leerzeichen der Reihe nicht matchen kann. Entsprechend kann man die Suche auf O(N) optimieren.