Leerzeichen-Regex lässt StackExchange ausfallen? (Allgemeines zu Perl)

[thread]20120[/thread]

Leerzeichen-Regex lässt StackExchange ausfallen?

Tags: perl5 regex Similar Threads

Readers: 16

Articles: hide open all | hide show old branches

+28 replies
GwenDragon

2016-07-21 13:24

User since
2005-01-17
14835 articles
Admin1

Durch ein Regex, das Leerzeichen (\x20 bzw \u200c) am Anfang und Ende von Postings entfernt, wurde StackExchange lahmgelegt weil 20.000 Leerzeichen gepostet wurden?
Siehe http://stackstatus.net/post/147710624694/outage-po...

Ist so eine Falle auch in Perl möglich?

more (46.5kb)
timethis 10000000: 1.91004 wallclock secs ( 1.91 usr + 0.00 sys = 1.91 CPU) @ 5246589.72/s (n=10000000)
timethis 10000000: 27.0479 wallclock secs (26.95 usr + 0.02 sys = 26.97 CPU) @ 370796.10/s (n=10000000)

Kommt darauf an wie falsch es gemacht wird, damit es lahmt ;)
Last edited: 2016-07-21 13:34:12 +0200 (CEST)
die Drachin Gwen

Meine Perl-Artikel · perldev – verschiedene Perl-Versionen unter Windows starten
- +4 replies
- clms
  
  2016-07-21 15:52
  
  User since
  2010-08-29
  373 articles
  BenutzerIn
  
  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.
  - +3 replies
  - GwenDragon
    
    2016-07-21 16:09
    
    User since
    2005-01-17
    14835 articles
    Admin1
    
    2016-07-21T13:52:29 clms
    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.
    Was? Die haben den Müll mit in die DB geschrieben? Dann ist es kein Wunder, das sowas lahmt.
    die Drachin Gwen
    
    Meine Perl-Artikel · perldev – verschiedene Perl-Versionen unter Windows starten
    - clms
      
      2016-07-21 16:25
      
      User since
      2010-08-29
      373 articles
      BenutzerIn
      
      2016-07-21T14:09:30 ?
      Was? Die haben den Müll mit in die DB geschrieben? Dann ist es kein Wunder, das sowas lahmt.
      
      Ja, so würde ich folgenden Satz interpretieren:
      
      Quote
      The post was in the homepage list, and that caused the expensive regular expression to be called on each home page view.
      
      Für mich das Erstaunlichste ist, dass das Stopfen dieser "root cause" nicht in den "follow-up actions" auftaucht.
    - betterworld
      
      2016-07-21 21:56
      
      User since
      2003-08-21
      2614 articles
      ModeratorIn
      
      2016-07-21T14:09:30 GwenDragon
      Was? Die haben den Müll mit in die DB geschrieben? Dann ist es kein Wunder, das sowas lahmt.
      
      Der Müll in diesem Fall war ein Beitrag, wo Leerzeichen in der Mitte vorgekommen sind. Der Regexp war nicht dazu vorgesehen, Leerzeichen aus der Mitte zu entfernen. Daher ist es klar, dass der Müll in der Datenbank war.
      
      Der Regexp soll nur Leerzeichen am Ende entfernen. Aber zur DOS wird der Regexp eben durch Leerzeichen, die nicht am Ende sind.
      
      Was clms aber wohl auch meint, dass der Regexp eigentlich nur beim Schreiben in die DB nötig ist und nicht beim Auslesen. Wenn man also beim Auslesen den Filter weglässt, könnte man so eine Dos auch vermeiden. Zumindest wenn man mit so etwas rechnen würde ;)
      Lieblingsmodule: IPC::System::Simple, Path::Class
- +21 replies
- clms
  
  2016-07-25 12:30
  
  User since
  2010-08-29
  373 articles
  BenutzerIn
  
  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.
  - Muffi
    
    2016-07-25 16:35
    User since
    2012-07-18
    1465 articles
    BenutzerIn
    
    Glaub ich nicht, dass da was optimiert wird.
    
    Edit: so könnts evtl. gehen.
    
    Code: (dl )
    
    .*\S(\s+)$
    
    Der .* fängt von hinten an und geht zurück bis an die Stelle des ersten Whitespace.
    Last edited: 2016-07-25 16:38:56 +0200 (CEST)
    1 + 1 = 10
  - +19 replies
  - clms
    
    2016-07-25 23:23
    User since
    2010-08-29
    373 articles
    BenutzerIn
    
    Ich habe es jetzt mit einem leicht modifizierten Beispiel ausprobiert.
    
    Code (perl): (dl )
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
    
    use strict; use warnings; use 5.010; use Benchmark qw(:all :hireswallclock) ; my $inputA = "X".(" \t" x 200000)."A"; my $inputB = "X".(" \t" x 200000)."B"; my $c1A = <<'CODE'; my $s = $inputA; $s =~ s/[\s\u200c]+A/ A/; CODE my $c1B = <<'CODE'; my $s = $inputB; $s =~ s/[\s\u200c]+A/ A/; CODE my $c2A = <<'CODE'; my $s = $inputA; $s =~ s/(?<=\S)[\s\u200c]+A/ A/; CODE my $c2B = <<'CODE'; my $s = $inputB; $s =~ s/(?<=\S)[\s\u200c]+A/ A/; CODE timethis(50_000_000,$c1A); timethis(50_000_000,$c1B); timethis(50_000_000,$c2A); timethis(50_000_000,$c2B);
    
    Wenn gegen inputA gematched wird, ist die Regex ein Treffer, es findet also kein Backtracking statt, dafür muss der String verändert werden.
    Wenn gegen inputB gematched wird, ist die Regex kein Treffer, bei $c1B kann das Backtracking also stattfinden.
    Dann habe ich noch Muffis Vorschlag aufgegriffen. In den Fällen $c2A und $c2B wird das Backtracking durch die Look-Behind-Assertion als Anker vor dem \s+ verhindert.
    
    Ergebnis:
    Alle vier Varianten brauchen auf meiner Maschine mit Perl 5.20.2 ca. 4 Sekunden. Die Unterschiede liegen jeweils innerhalb der Schwankungsbreite zwischen zwei erneuten Durchläufen.
    
    Fazit: Die Regex-Engine scheint an dieser Stelle zu optimieren. Eine Verlangsammung durch Backtracking kann ich nicht feststellen.
    - +3 replies
    - Muffi
      
      2016-07-26 08:55
      
      User since
      2012-07-18
      1465 articles
      BenutzerIn
      
      So ganz hab ichs nicht kapiert.
      
      Das Ursprungsproblem war doch, dass hinten Leerzeichen weggeschnitten werden sollten oder?
      
      Und wenn du da \s+$ schreibst, dann ackert der natürlich alles durch. Wenn du allerdings sowas wie .*\S(\s+)$ schreibst, dann kommt erst der .* der gierig ist und somit fängt die Suche am Stringende an.
      
      \s+$ (1 Match - 589 Steps)
      und
      .*\S(\s+)$ (1 Match - 31 Steps)
      1 + 1 = 10
      - +2 replies
      - clms
        
        2016-07-26 09:58
        
        User since
        2010-08-29
        373 articles
        BenutzerIn
        
        Um das wiederholte Backtracking auszuschließen und Komplexität auf O(N) zu begrenzen brauchst Du das .* am Anfang nicht. Da genügt das \S vor dem \s+. Das stellt sicher, dass die Regex nicht bei jedem Whitespace mit dem Suchen anfangen muss, sondern nur bei Whitespace, direkt hinter einem non-Whitespace.
        
        Ich habe \S dann noch in eine Look-behind Assertion gepackt, damit das Zeichen vor dem Whitespace nicht vom s/// mit ersetzt wird.
        
        Muffi
        
        2016-07-26 10:00
        
        User since
        2012-07-18
        1465 articles
        BenutzerIn
        
        Ah, kapiert
        1 + 1 = 10
    - +3 replies
    - Muffi
      
      2016-07-26 11:19
      
      User since
      2012-07-18
      1465 articles
      BenutzerIn
      
      Grad in den online-Regex gefüttert. Bei beiden B-Varianten:
      
      Your match failed outright. What this means is the engine, due to its internal optimizations, understood that your pattern would never match at any position, and thus did not even attempt to. If you want to see what would have happened if it tried, disable them with the checkbox above.
      
      D.h. bei deinen Beispielen fängt er nicht mal zu arbeiten an, weil er vorher schon erkennt, dass es keinen match geben wird.
      Last edited: 2016-07-26 11:23:28 +0200 (CEST)
      1 + 1 = 10
      - +2 replies
      - Linuxer
        
        2016-07-26 11:33
        
        User since
        2006-01-27
        3891 articles
        HausmeisterIn
        
        Wer ist denn dieser "online-Regex"?
        meine Beiträge: I.d.R. alle Angaben ohne Gewähr und auf Linux abgestimmt!
        Die Sprache heisst Perl, nicht PERL. - Bitte Crossposts als solche kenntlich machen!
        
        Muffi
        
        2016-07-26 11:37
        
        User since
        2012-07-18
        1465 articles
        BenutzerIn
        
        Ich benutz meist den
        
        https://regex101.com/
        1 + 1 = 10
    - +12 replies
    - clms
      
      2016-07-26 12:04
      
      User since
      2010-08-29
      373 articles
      BenutzerIn
      
      Mein Benchmark funktionierte leider überhaupt nicht, da die Code-Schnipsel in einem Scope ausgewertet wurden, wo $inputA und $inputB nicht sichtbar sind. Es wurde also immer ein undefinierter String durchsucht. Kein Wunder, dass das immer sehr schnell ging.
      
      Ich habe das Programm deshalb gefixt und auch gleich eine Kontrolle eingeführt, dass die Anzahl der erwarteten Matches stimmt.
      
      Code (perl): (dl )
      
      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
      
      use strict; use warnings; use Benchmark qw(:all :hireswallclock) ; our $inputA = "X".(" \t" x 10000)."A"; our $inputB = "X".(" \t" x 10000)."B"; our $m1A = 0; our $m1B = 0; our $m2A = 0; our $m2B = 0; my $c1A = <<'CODE'; my $s = $inputA; $m1A++ if ($s =~ s/[\s\u200c]+A/ A/g); CODE my $c1B = <<'CODE'; my $s = $inputB; $m1B++ if ($s =~ s/[\s\u200c]+A/ A/g); CODE my $c2A = <<'CODE'; my $s = $inputA; $m2A++ if ($s =~ s/(?<=\S)[\s\u200c]+A/ A/g); CODE my $c2B = <<'CODE'; my $s = $inputB; $m2B++ if ($s =~ s/(?<=\S)[\s\u200c]+A/ A/g); CODE timethis(100_000,$c1A); timethis(100_000,$c1B); timethis(100_000,$c2A); timethis(100_000,$c2B); print "M1A: $m1A\n"; print "M1B: $m1B\n"; print "M2A: $m2A\n"; print "M2B: $m2B\n";
      
      Das Ergebnis mit Perl 5.18.2:
      
      Code: (dl )
      
      1 2 3 4 5 6 7 8
      
      timethis 100000: 3.81796 wallclock secs ( 3.82 usr + 0.00 sys = 3.82 CPU) @ 26178.01/s (n=100000) timethis 100000: 1.70095 wallclock secs ( 1.70 usr + 0.00 sys = 1.70 CPU) @ 58823.53/s (n=100000) timethis 100000: 2.86398 wallclock secs ( 2.87 usr + 0.00 sys = 2.87 CPU) @ 34843.21/s (n=100000) timethis 100000: 1.70098 wallclock secs ( 1.70 usr + 0.00 sys = 1.70 CPU) @ 58823.53/s (n=100000) M1A: 100000 M1B: 0 M2A: 100000 M2B: 0
      
      und mit 5.8.8
      
      Code: (dl )
      
      1 2 3 4 5 6 7 8 9
      
      Subroutine Benchmark::mytime redefined at /usr/lib/perl5/5.8.8/Benchmark.pm line 459. timethis 100000: 23.9664 wallclock secs (23.95 usr + 0.01 sys = 23.96 CPU) @ 4173.62/s (n=100000) timethis 100000: 1.69792 wallclock secs ( 1.70 usr + 0.00 sys = 1.70 CPU) @ 58823.53/s (n=100000) timethis 100000: 23.9532 wallclock secs (23.94 usr + 0.02 sys = 23.96 CPU) @ 4173.62/s (n=100000) timethis 100000: 1.6998 wallclock secs ( 1.70 usr + 0.00 sys = 1.70 CPU) @ 58823.53/s (n=100000) M1A: 100000 M1B: 0 M2A: 100000 M2B: 0
      
      Das Backtracking schein also kein Problem zu sein. Die Version C1B, bei der das Backtracking auftreten könnte, ist nicht langsamer.
      
      Zeitfresser scheint das Ersetzen im String zu sein, wobei das zwischen 5.8.8 und 5.18.2 deutlich optimiert wurde.
      
      Ich habe das s///g daraufhin durch m//g ersetzt. Praktisch die gleichen Ergebnisse. Das Ersetzen bei einem Treffer kann es auch nicht sein. Ist es das "Reinspringen" in das durch if geschützte Statement? Nächster Versuch: $m1A++ if ($s =~ m/[\s\u200c]+A/g); durch $s =~ s/[\s\u200c]+A/ A/g; ersetzt. Gleiches Ergebnis, außer dass $m1A und $m1B natürlich 0 sind.
      Kann der Zeitfresser das Kopieren der Treffer in die $MATCH Variable der Regex-Engine sein?
      - +11 replies
      - renee
        
        2016-07-26 14:42
        
        User since
        2003-08-04
        14371 articles
        ModeratorIn
        
        Ändere mal in Deinem Regex mal +A in *$... Das Problem sind ja nicht die Treffer, sondern die Fehlschläge.
        OTRS-Erweiterungen (http://feature-addons.de/)
        Frankfurt Perlmongers (http://frankfurt.pm/)
        --
        
        Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
        Perl-Entwicklung: http://perl-services.de/
        
        +2 replies
        
        renee
        
        2016-07-26 14:59
        
        User since
        2003-08-04
        14371 articles
        ModeratorIn
        
        Wer Lust hat, kann ja mal
        
        Code (perl): (dl )
        
        1 2 3 4 5 6 7 8 9
        
        use strict; use warnings; use re 'debug'; my $inputA = "X".(" \t" x 10000)."A"; (my $t1 = $inputA) =~ s/[\s\u200c]+A/ A/; <STDIN>; (my $t1 = $inputA) =~ s/[\s\u200c]*$/ A/;
        
        starten...
        OTRS-Erweiterungen (http://feature-addons.de/)
        Frankfurt Perlmongers (http://frankfurt.pm/)
        --
        
        Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
        Perl-Entwicklung: http://perl-services.de/
        
        renee
        
        2016-07-26 15:14
        
        User since
        2003-08-04
        14371 articles
        ModeratorIn
        
        Durch die Mächtigkeit der Regex-Engine in Perl ist diese eher langsam. Für diese Problematik hier gibt es geeignetere Engines. z.B. Googles RE2:
        
        Code (perl): (dl )
        
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
        
        use v5.10; use Time::HiRes qw(time); my $inputA = "X".(" \t" x 10000)."A " . ( " " x 10000); my $start = time; (my $t1 = $inputA) =~ s/[\s\u200c]*$/ A/; say time - $start; use re::engine::RE2; $start = time; (my $t2 = $inputA) =~ s/[\s\u200c]*$/ A/; say time - $start; say "gleich: " . ( $t1 eq $t2 );
        
        Ausgabe:
        
        Code: (dl )
        
        1 2 3
        
        1.35114789009094 0.000217914581298828 gleich: 1
        
        OTRS-Erweiterungen (http://feature-addons.de/)
        Frankfurt Perlmongers (http://frankfurt.pm/)
        --
        
        Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
        Perl-Entwicklung: http://perl-services.de/
        
        +8 replies
        
        clms
        
        2016-07-26 16:44
        
        User since
        2010-08-29
        373 articles
        BenutzerIn
        
        2016-07-26T12:42:08 renee
        Ändere mal in Deinem Regex mal +A in *$... Das Problem sind ja nicht die Treffer, sondern die Fehlschläge.
        
        Deshalb habe ich ja die Fälle C1B und C2B dabei. Da gibt es keine Treffer.
        C1B ist für das bei StackExchange geschilderte Backtracking-Problem anfällig, C2B wegen des Ankers \S am Anfang der Regex nicht.
        
        Nach der bei StackExchange aufgestellten Theorie müsste C1B deutlich länger laufen als C1A. Das Gegenteil ist der Fall. Es gibt auch kaum messbare Unterschiede zwischen C1B und C2B.
        
        Daraus schließe ich, das die Regex-Engine bei Perl erkennt, dass sie kein Backtracking machen muss, wenn die Regex im ersten Anlauf nicht matched.
        
        +2 replies
        
        renee
        
        2016-07-26 17:05
        
        User since
        2003-08-04
        14371 articles
        ModeratorIn
        
        Das hat wiederum damit zu tun, dass Du eine "Zeichenkette" (das A) verwendest. Die Regex-Engine erkennt, dass dieser Substring nicht vorkommt und bricht dann ruckzuck ab...
        
        Code (perl): (dl )
        
        1 2 3 4
        
        use re 'debug'; my $inputB = "X".(" \t" x 10000)."B"; $inputB =~ s/[\s\u200c]+A/ A/g;
        
        Code: (dl )
        
        1 2 3 4 5 6 7 8 9 10 11 12 13
        
        $ perl clms_regex.pl Compiling REx "[\s200c]+A" Final program: 1: PLUS (13) 2: ANYOF[\x{09}-\x{0D} 02c][{utf8}0085 00A0 1680 2000-200A 2028-2029 202F 205F 3000] (0) 13: EXACT <A> (15) 15: END (0) floating "A" at 1..9223372036854775807 (checking floating) stclass ANYOF[\x{09}-\x{0D} 02c][{utf8}0085 00A0 1680 2000-200A 2028-2029 202F 205F 3000] plus minlen 2 Matching REx "[\s200c]+A" against "X %t %t %t %t %t %t %t %t %t %t %t %t %t %t %t %t %t %t %t "... Intuit: trying to determine minimum start position... Did not find floating substr "A"... Match rejected by optimizer Freeing REx: "[\s200c]+A"
        
        Und dann ändere mal in
        
        Code (perl): (dl )
        
        1 2 3 4
        
        use re 'debug'; my $inputB = "X".(" \t" x 10000)."B"; $inputB =~ s/[\s\u200c]*$/ A/;
        
        OTRS-Erweiterungen (http://feature-addons.de/)
        Frankfurt Perlmongers (http://frankfurt.pm/)
        --
        
        Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
        Perl-Entwicklung: http://perl-services.de/
        
        clms
        
        2016-07-26 18:10
        
        User since
        2010-08-29
        373 articles
        BenutzerIn
        
        2016-07-26T15:05:01 renee
        Das hat wiederum damit zu tun, dass Du eine "Zeichenkette" (das A) verwendest. Die Regex-Engine erkennt, dass dieser Substring nicht vorkommt und bricht dann ruckzuck ab...
        
        OK, das ist der Grund warum die Suche nach 'A' am Ende so schnell war.
        
        Ich hatte in der Zwischenzeit weiter experimentiert.
        
        *$ habe ich weggelassen, weil das ja immer matched, und es stattdessen mit +$ probiert.
        
        Insgesamt habe ich jetzt drei Inputstrings mit fünf Regex kombiniert:
        
        Die Input-Strings:
        
        MxA: "A" am Ende
        MxB: "B" am Ende
        MxS: kein Zeichen mehr hinter dem Whitespace
        
        Die Regex:
        
        M1x: /\s+A/ - also Whitespace vor A
        M2x: /(?<=\S)\s+A/ - also Whitespace mit Anker als lookbehind Assertion vor A
        M3x: /\s+$/ - also Whitespace vor Zeilenende
        M4x: /(?<=\S)\s+$/ - also Whitespace mit Anker als lookbehind Assertion vor Zeilenende
        M5x: /\S\s+$/ - also non-Whitespare vor Whitespace vor Zeilenende
        
        Hier der Code:
        more (3.1kb)
        
        Das Ergebnis (hier mit Perl 5.18.2) hat mich überraschend:
        
        Code: (dl )
        
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
        
        timethis 100000: 2.16451 wallclock secs ( 2.17 usr + 0.00 sys = 2.17 CPU) @ 46082.95/s (n=100000) M1A: 100000 timethis 100000: 1.70105 wallclock secs ( 1.70 usr + 0.00 sys = 1.70 CPU) @ 58823.53/s (n=100000) M1B: 0 timethis 100000: 1.70482 wallclock secs ( 1.71 usr + 0.00 sys = 1.71 CPU) @ 58479.53/s (n=100000) M1S: 0 timethis 100000: 1.7609 wallclock secs ( 1.76 usr + 0.00 sys = 1.76 CPU) @ 56818.18/s (n=100000) M2A: 100000 timethis 100000: 1.70132 wallclock secs ( 1.70 usr + 0.00 sys = 1.70 CPU) @ 58823.53/s (n=100000) M2B: 0 timethis 100000: 1.70033 wallclock secs ( 1.70 usr + 0.00 sys = 1.70 CPU) @ 58823.53/s (n=100000) M2S: 0 timethis 100000: 7.1719 wallclock secs ( 7.17 usr + 0.00 sys = 7.17 CPU) @ 13947.00/s (n=100000) M3A: 0 timethis 100000: 7.17198 wallclock secs ( 7.17 usr + 0.00 sys = 7.17 CPU) @ 13947.00/s (n=100000) M3B: 0 timethis 100000: 2.04794 wallclock secs ( 2.05 usr + 0.00 sys = 2.05 CPU) @ 48780.49/s (n=100000) M3S: 100000 timethis 100000: 155.864 wallclock secs (155.84 usr + 0.00 sys = 155.84 CPU) @ 641.68/s (n=100000) M4A: 0 timethis 100000: 155.899 wallclock secs (155.86 usr + 0.01 sys = 155.87 CPU) @ 641.56/s (n=100000) M4B: 0 timethis 100000: 1.75641 wallclock secs ( 1.76 usr + 0.00 sys = 1.76 CPU) @ 56818.18/s (n=100000) M4S: 100000 timethis 100000: 7.17382 wallclock secs ( 7.18 usr + 0.00 sys = 7.18 CPU) @ 13927.58/s (n=100000) M5A: 0 timethis 100000: 7.18063 wallclock secs ( 7.18 usr + 0.00 sys = 7.18 CPU) @ 13927.58/s (n=100000) M5B: 0 timethis 100000: 1.91674 wallclock secs ( 1.92 usr + 0.00 sys = 1.92 CPU) @ 52083.33/s (n=100000) M5S: 100000
        
        Wenn nach Whitespace vor dem Zeilenende gesucht wird, könnte plötzlich Backtracking ins Spiel kommen. Die Fälle M3A und M3B, bei denen Backtracking auftreten kann, weil es keinen Treffer gibt, sind plötzlich 5 mal langsamer als die vergebliche Suche nach Whitespace vor dem 'A'. Matched die Regex dagegen (=> kein Backtracking) ist die Geschwindigkeit so wie in den vergleichbaren Fällen mit Treffern (M1A, M2A, M4S, M5S).
        
        Erschreckend sind die Zeiten für M4A und M4B (Mismatches mit lookbehind als Anker): Fast 100 mal langsamer als im Fall wo nach Whitespace vor 'A' gesucht wird und immer noch 20 mal langsamer als ohne lookbehind Assertion.
        
        In den Fällen M5A und M5B entspricht die Zeit dagegen den Fällen M3A und M3B obwohl hier wegen des \S am Anfang der Regex kein Backtracking auftreten kann.
        
        +5 replies
        
        Linuxer
        
        2016-07-26 17:05
        
        User since
        2006-01-27
        3891 articles
        HausmeisterIn
        
        Habe ich da einen Denkfehler?
        
        Ich habe Dein Skript einmal ausgeführt, um ein Gefühl für die Laufzeit zu bekommen. Und es lief in akzeptabler Zeit durch.
        
        Code: (dl )
        
        1 2 3 4 5 6 7 8
        
        timethis 100000: 5.43372 wallclock secs ( 5.43 usr + 0.00 sys = 5.43 CPU) @ 18419.60/s (n=100000) timethis 100000: 1.66317 wallclock secs ( 1.67 usr + 0.00 sys = 1.67 CPU) @ 59916.12/s (n=100000) timethis 100000: 5.62105 wallclock secs ( 5.59 usr + 0.00 sys = 5.59 CPU) @ 17905.10/s (n=100000) timethis 100000: 1.7069 wallclock secs ( 1.70 usr + 0.00 sys = 1.70 CPU) @ 58788.95/s (n=100000) M1A: 100000 M1B: 0 M2A: 100000 M2B: 0
        
        Dann habe ich das Skript etwas abgeändert, um mit echtem "$" zu arbeiten. D.h. den String in $inputB lass ich wirklich mit Spaces enden (ohne das B am Ende).
        Und die s/// habe ich geändert, dass wirklich nach Spaces am Ende ($) gesucht werden soll und diese dann durch Leerstring ersetzt werden...
        
        Die Laufzeit wurde lang, sehr lang für den C2A ... Keine Ahnung, ob ich warten mag, bis er fertig wird.
        
        more (8.9kb)
        
        Ich habe ausreichend gewartet und hier das Ergebnis:
        
        Ausgabe:
        
        Code: (dl )
        
        1 2 3 4 5 6 7 8
        
        timethis 100000: 12.2518 wallclock secs (12.18 usr + 0.00 sys = 12.18 CPU) @ 8208.16/s (n=100000) timethis 100000: 5.47224 wallclock secs ( 5.48 usr + 0.00 sys = 5.48 CPU) @ 18261.50/s (n=100000) timethis 100000: 195.541 wallclock secs (194.83 usr + 0.00 sys = 194.83 CPU) @513.27/s (n=100000) timethis 100000: 5.57992 wallclock secs ( 5.55 usr + 0.00 sys = 5.55 CPU) @ 18005.04/s (n=100000) M1A: 0 M1B: 100000 M2A: 0 M2B: 100000
        
        Getestet auf einem WinDOS 7 mit einem Perl 5.18.0
        meine Beiträge: I.d.R. alle Angaben ohne Gewähr und auf Linux abgestimmt!
        Die Sprache heisst Perl, nicht PERL. - Bitte Crossposts als solche kenntlich machen!
        
        +4 replies
        
        clms
        
        2016-07-26 18:18
        
        User since
        2010-08-29
        373 articles
        BenutzerIn
        
        Deckt sich mit meinen Ergebnissen. Verstehen tue ich es noch nicht.
        
        OK. Die Regex-Engine könnte Backtracking machen und, jedes der 200000 Whitespacezeichen durchgehen und dann die Lookbehind Assertion durchführen.
        Und das könnte sehr ineffizient sein.
        
        Ich habe aber noch /\S\s+$/ getestet. Da kann eigentlich kein Backtracking-Problem auftauchen, weil es nur zwei \S im String gibt. Trotzdem braucht die Suche so lang wie mit /\s+$/.
        
        +3 replies
        
        Muffi
        
        2016-07-27 10:07
        
        User since
        2012-07-18
        1465 articles
        BenutzerIn
        
        Der macht da sehr komische Sachen
        
        https://regex101.com/r/iU1kH3/1
        
        (klick auf regex Debugger)
        1 + 1 = 10
        
        +2 replies
        
        renee
        
        2016-07-27 11:38
        
        User since
        2003-08-04
        14371 articles
        ModeratorIn
        
        Warum findest Du das komisch?
        OTRS-Erweiterungen (http://feature-addons.de/)
        Frankfurt Perlmongers (http://frankfurt.pm/)
        --
        
        Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
        Perl-Entwicklung: http://perl-services.de/
        
        Muffi
        
        2016-07-27 11:46
        
        User since
        2012-07-18
        1465 articles
        BenutzerIn
        
        Ich hätt nicht gedacht, dass er eine ganze Weile versucht mit Backtracking das Zeilenende zu finden.
        Und auch der look-behind ist doch eigentlich völlig überflüssig, wenn er schon das Zeilenende nicht gefunden hat.
        Last edited: 2016-07-27 11:47:58 +0200 (CEST)
        1 + 1 = 10
- +2 replies
- guest wer
  
  2016-07-25 16:06
  zum entfernen einzelner zeichen sollte man eh tr bzw y benutzen:
  
  Code (perl): (dl )
  
  $str =~ y/\x20//d;
  
  Last edited: 2016-07-25 16:11:26 +0200 (CEST)
  - GwenDragon
    
    2016-07-25 16:13
    
    User since
    2005-01-17
    14835 articles
    Admin1
    
    Sollte man, aber nur unter bestimmten Umständen.
    Mit deinem Beispiel entfernst du alle Leerzeichen überall, nicht nur die am Ende oder Anfang der Eingabezeile. Das ist wohl kaum sinnvoll in dem besprochenen Kontext!
    die Drachin Gwen
    
    Meine Perl-Artikel · perldev – verschiedene Perl-Versionen unter Windows starten

View all threads created 2016-07-21 13:24.