Pourquoi "\ s +" est-il tellement plus rapide que "\ s \ s *" dans cette expression rationnelle Perl?

Question

Pourquoi remplacer \s* (ou même \s\s*) avec \s+ entraîne une accélération de cette entrée?

use Benchmark qw(:all);
$x=(" " x 100000) . "_\n";
$count = 100;
timethese($count, {
    '/\s\s*\n/' => sub { $x =~ /\s\s*\n/ },
    '/\s+\n/' => sub { $x =~ /\s+\n/ },
});

Lien vers la version en ligne

J'ai remarqué une lente regex s/\s*\n\s*/\n/g dans mon code - lors d'une 450KB fichier d'entrée composé de beaucoup d'espaces avec un peu de non-lieux, ici et là, et un dernier saut de ligne à la fin de la regex hung et jamais fini.

Je intuitivement a remplacé la regex avec s/\s+\n/\n/g; s/\n\s+/\n/g; et tout allait bien.

Mais pourquoi est-il si rapide? Après l'utilisation de re Debug => "EXECUTE" j'ai remarqué l' \s+ version est en quelque sorte optimisé pour exécuter en une seule itération: http://pastebin.com/0Ug6xPiQ

Matching REx "\s*\n" against "       _%n"
Matching stclass ANYOF{i}[\x09\x0a\x0c\x0d ][{non-utf8-latin1-all}{unicode_all}] against "       _%n" (9 bytes)
   0 <> <       _%n>         |  1:STAR(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
   1 < > <      _%n>         |  1:STAR(3)
                                  SPACE can match 6 times out of 2147483647...
                                  failed...
   2 <  > <     _%n>         |  1:STAR(3)
                                  SPACE can match 5 times out of 2147483647...
                                  failed...
   3 <   > <    _%n>         |  1:STAR(3)
                                  SPACE can match 4 times out of 2147483647...
                                  failed...
   4 <    > <   _%n>         |  1:STAR(3)
                                  SPACE can match 3 times out of 2147483647...
                                  failed...
   5 <     > <  _%n>         |  1:STAR(3)
                                  SPACE can match 2 times out of 2147483647...
                                  failed...
   6 <      > < _%n>         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
                                  failed...
   8 <       _> <%n>         |  1:STAR(3)
                                  SPACE can match 1 times out of 2147483647...
   8 <       _> <%n>         |  3:  EXACT <\n>(5)
   9 <       _%n> <>         |  5:  END(0)
Match successful!

Matching REx "\s+\n" against "       _%n"
Matching stclass SPACE against "       _" (8 bytes)
   0 <> <       _%n>         |  1:PLUS(3)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...

Je sais Perl 5.10+ sera immédiatement échouer la regex (sans courir) si un saut de ligne n'est pas présente. Je soupçonne que c'est à l'aide de l'emplacement de la nouvelle ligne de réduire la quantité de la recherche qu'il fait. Pour tous les cas ci-dessus, il semble habilement réduire la mandature impliqués (habituellement /\s*\n/ contre une chaîne d'espaces prendre exponentielle en temps). Quelqu'un peut-il offrir un aperçu de pourquoi l' \s+ version est beaucoup plus rapide?

Notez aussi que l' \s*? n'offre aucune accélération.

Answer 1

Tout d'abord, même si la regex ne vais pas garder le même sens, nous allons réduit regexes d' \s*0 et \s+0 et l'utilisation (" " x 4) . "_0" comme une entrée. Pour les sceptiques, vous pouvez voir ici que le décalage est toujours présent.

Maintenant considérons le code suivant:

$x = (" " x 4) . "_ 0";
$x =~ /\s*0/; # The slow line 
$x =~ /\s+0/; # The fast line

En creusant un peu avec use re debugcolor; , nous obtenons le résultat suivant:

Guessing start of match in sv for REx "\s*0" against "    _0"
Found floating substr "0" at offset 5...
start_shift: 0 check_at: 5 s: 0 endpos: 6 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s*0" against "    _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against "    _0" (6 bytes)
   0 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 4 times out of 2147483647...
                                  failed...
   1 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 3 times out of 2147483647...
                                  failed...
   2 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 2 times out of 2147483647...
                                  failed...
   3 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 1 times out of 2147483647...
                                  failed...
   5 <    _0>|  1:STAR(3)
                                  POSIXD[\s] can match 0 times out of 2147483647...
   5 <    _0>|  3:  EXACT <0>(5)
   6 <    _0>|  5:  END(0)
Match successful!

-----------------------

Guessing start of match in sv for REx "\s+0" against "    _0"
Found floating substr "0" at offset 5...
start_shift: 1 check_at: 5 s: 0 endpos: 5 checked_upto: 0
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+0" against "    _0"
Matching stclass POSIXD[\s] against "    _" (5 bytes)
   0 <    _0>|  1:PLUS(3)
                                  POSIXD[\s] can match 4 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed

Perl semble être optimisé pour l'échec. Il va d'abord chercher les chaines (qui ne consomment que O(N)). Ici, il va chercher pour 0 : Found floating substr "0" at offset 5...

Puis il va commencer avec la variable de la partie de l'expression régulière, respectivement \s* et \s+, contre l'ensemble de la chaîne minimum à vérifier:

Matching REx "\s*0" against "    _0"
Matching stclass ANYOF_SYNTHETIC[\x09-\x0d 0\x85\xa0][{unicode_all}] against "    _0" (6 bytes)
Matching REx "\s+0" against "    _0"
Matching stclass POSIXD[\s] against "    _" (5 bytes) # Only 5 bytes because there should be at least 1 "\s" char

Après cela, il va chercher pour la première position de réunion de l' stclass d'exigence, d'ici à la position 0.

• \s*0:
  • commence à 0, trouver 4 places puis échouer;
  • commence à 1, trouver les 3 espaces échec;
  • commence à 2, de 2 espaces, alors l'échec;
  • commence à 3, de 1 les espaces puis l'échec;
  • démarre à 4, trouver 0 espaces, alors ne pas en panne;
  • Trouver une exacte 0
• \s+0:
  • commence à 0, trouver 4 places puis d'échouer. Comme le nombre minimal de places n'est pas adapté, la regex ne parvient pas instantanément.

Si vous voulez avoir du plaisir avec expression rationnelle Perl optimisation, vous pouvez envisager la suite regexes / *\n et / * \n. Au premier coup d'œil, ils se ressemblent, ont le même sens... Mais si vous l'exécutez à son encontre (" " x 40000) . "_\n" le premier va vérifier toutes les possibilités, alors que le second cherchera " \n" et ne parviennent pas immédiatement.

Dans un de la vanille, de la non-optimisé moteur d'expressions régulières, les deux regex peut causer catastrophique retour en arrière, car ils ont besoin pour recommencer le motif qu'elle bosses le long. Cependant, dans l'exemple ci-dessus, le deuxième ne pas échouer avec Perl, car il a été optimisée afin d' find floating substr "0%n"

---

Vous pouvez en voir un autre exemple sur Jeff Atwood du blog.

Notez également que la question n'est pas de \s considération, mais tout modèle où l' xx* est utilisé à la place de x+ voir exemple avec des 0 et aussi regex explosif quantificateurs

Avec plus court exemple le comportement est "trouvable", mais si vous commencez à jouer avec des modèles complexes, il est loin d'être facile à repérer, par exemple: expression Régulière se bloque programme (100% d'utilisation du PROCESSEUR)

Answer 2

Quand il y a un "plus" nœud (par exemple, \s+) au début d'un dessin et le nœud échoue de match, le moteur d'expressions régulières saut vers l'avant jusqu'au point de défaillance et essaie de nouveau; avec \s*, d'autre part, le moteur avance d'un caractère à la fois.

Yves Orton explique cette optimisation bien ici:

Le début de la classe d'optimisation a deux modes, "essayer tous les valide la position de départ" (doevery) et "flip flop mode" (!doevery) où il essaye seulement le premier qui valide la position de départ dans une séquence.

Envisager /(\d+)X/ et la chaîne "123456Y", maintenant nous savons que si nous ne parvenons pas à correspondre à X après la mise en correspondance "123456" ensuite, nous allons aussi ne correspondent après "23456" (en supposant que pas mal de trucs sont en place, désactiver l'optimisation de toute façon), donc nous savons que nous pouvons avancer jusqu'à ce que le check /échec/ et ensuite seulement commencer à chercher un vrai match. C'est à la mode flip-flop.

/\s+/ déclencheurs mode flip-flop; /\s*/, /\s\s*/, et /\s\s+/ n'en ont pas. Cette optimisation ne peut pas être appliquée à la "star" des nœuds comme \s* car ils peuvent correspondre à des caractères nul, donc un échec à un moment donné dans une séquence n'est pas indicatif de l'échec plus tard dans la même séquence.

---

Vous pouvez les voir dans la sortie de débogage pour chaque regex. J'ai mis en évidence le sauté de caractères avec des ^. Comparer ce (ignore les quatre caractères à la fois):

$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d+x/'
   ...
   0 <> <123 456 78>         |  1:PLUS(3)
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   4 <123 > <456 789 x>      |  1:PLUS(3)
      ^^^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   8 <23 456 > <789 x>       |  1:PLUS(3)
         ^^^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...

(saute un ou deux caractères à la fois):

$ perl -Mre=Debug,MATCH -e'"123 456 789 x" =~ /\d*x/'
   ...
   0 <> <123 456 78>         |  1:STAR(3)
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   1 <1> <23 456 789>        |  1:STAR(3)
      ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
   2 <12> <3 456 789 >       |  1:STAR(3)
       ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
   4 <123 > <456 789 x>      |  1:STAR(3)
        ^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   5 <123 4> <56 789 x>      |  1:STAR(3)
          ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
   6 <23 45> <6 789 x>       |  1:STAR(3)
          ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
   8 <23 456 > <789 x>       |  1:STAR(3)
           ^^
                                  POSIXD[\d] can match 3 times out of 2147483647...
                                  failed...
   9 <23 456 7> <89 x>       |  1:STAR(3)
             ^
                                  POSIXD[\d] can match 2 times out of 2147483647...
                                  failed...
  10 <23 456 78> <9 x>       |  1:STAR(3)
              ^
                                  POSIXD[\d] can match 1 times out of 2147483647...
                                  failed...
  12 <23 456 789 > <x>       |  1:STAR(3)
               ^^
                                  POSIXD[\d] can match 0 times out of 2147483647...
  12 <23 456 789 > <x>       |  3:  EXACT <x>(5)
  13 <23 456 789 x> <>       |  5:  END(0)

Notez que l'optimisation n'est pas appliquée à l' /\s\s+/car \s+ n'est pas au début du motif. Les deux /\s\s+/ (logiquement équivalent à /\s{2,}/) et /\s\s*/ (logiquement équivalent à /\s+/) probablement pu être optimisé; il pourrait être judicieux de demander sur perl5-porteurs de savoir si l'un et l'autre être en vaut la peine.

---

_{Dans le cas où vous êtes intéressé, "mode flip-flop" est activée par le réglage de l' PREGf_SKIP drapeau sur une regex quand il est compilé. Voir le code autour de lignes 7344 et 7405 dans regcomp.c et de la ligne de 1585 dans regexec.c dans le 5.24.0 source.}

Answer 3

L' \s+\n exige que le caractère qui précède l' \n est SPACE.

Selon use re qw(debug) la compilation établit qu'il a besoin d'un droit de chaîne d'un nombre de places, jusqu'à la sous-chaîne \n, ce qui est vérifié dans l'entrée. Puis il vérifie la longueur fixe de l'espace-seulement une sous-chaîne à l'égard de l'autre partie de l'entrée, à défaut d' _. C'est une simple possibilité de vérifier, peu importe la façon dont de nombreux espaces de l'entrée. (Quand il y a plus d' _\n chacune d'elles se trouve à l'échec tout aussi directement, par la sortie de débogage.)

Regardé de cette façon, c'est une optimisation que vous seriez presque s'attendre, en utilisant un assez spécifique modèle de recherche et lucking avec cette entrée. Sauf s'il est pris en comparaison avec d'autres moteurs, qui clairement ne pas faire ce genre d'analyse.

Avec \s*\n ce n'est pas le cas. Une fois l' \n est trouvée et que le caractère précédent n'est pas un espace, la recherche n'a pas manqué depuis \s* permet rien (zéro caractères). Il n'y a pas de longueur fixe des sous-chaînes, soit, et c'est dans la mandature jeu.

Answer 4

Je ne suis pas sûr du fonctionnement interne du moteur d'expression régulière, mais on dirait qu'il ne reconnaît pas qu' \s+ est en quelque sorte la même que \s\s*, puisque dans le second il correspond à un espace, puis essaie de faire correspondre jamais un nombre croissant d'espaces, alors que dans le premier, il conclut immédiatement qu'il n'y a pas de match.

La sortie à l'aide d' use re qw( Debug ); montre clairement ce, à l'aide d'une beaucoup plus courte chaîne de caractères:

test_re.pl

#!/usr/bin/env perl
use re qw(debug);

$x=(" " x 10) . "_\n";
print '-'x50 . "\n";
$x =~ /\s+\n/;
print '-'x50 . "\n";
$x =~ /\s\s*\n/;
print '-'x50 . "\n";

Sortie

Compiling REx "\s+\n"
Final program:
    1: PLUS (3)
    2:   SPACE (0)
    3: EXACT <\n> (5)
    5: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE plus minlen 2
Compiling REx "\s\s*\n"
Final program:
    1: SPACE (2)
    2: STAR (4)
    3:   SPACE (0)
    4: EXACT <\n> (6)
    6: END (0)
floating "%n" at 1..2147483647 (checking floating) stclass SPACE minlen 2
--------------------------------------------------
Guessing start of match in sv for REx "\s+\n" against "          _%n"
Found floating substr "%n" at offset 11...
    start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s+\n" against "          _%n"
Matching stclass SPACE against "          _" (11 bytes)
   0 <> <          >         |  1:PLUS(3)
                                  SPACE can match 10 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Guessing start of match in sv for REx "\s\s*\n" against "          _%n"
Found floating substr "%n" at offset 11...
    start_shift: 1 check_at: 11 s: 0 endpos: 11
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx "\s\s*\n" against "          _%n"
Matching stclass SPACE against "          _" (11 bytes)
   0 <> <          >         |  1:SPACE(2)
   1 < > <         _>        |  2:STAR(4)
                                  SPACE can match 9 times out of 2147483647...
                                  failed...
   1 < > <         _>        |  1:SPACE(2)
   2 <  > <        _>        |  2:STAR(4)
                                  SPACE can match 8 times out of 2147483647...
                                  failed...
   2 <  > <        _>        |  1:SPACE(2)
   3 <   > <       _%n>      |  2:STAR(4)
                                  SPACE can match 7 times out of 2147483647...
                                  failed...
   3 <   > <       _%n>      |  1:SPACE(2)
   4 <    > <      _%n>      |  2:STAR(4)
                                  SPACE can match 6 times out of 2147483647...
                                  failed...
   4 <    > <      _%n>      |  1:SPACE(2)
   5 <     > <     _%n>      |  2:STAR(4)
                                  SPACE can match 5 times out of 2147483647...
                                  failed...
   5 <     > <     _%n>      |  1:SPACE(2)
   6 <      > <    _%n>      |  2:STAR(4)
                                  SPACE can match 4 times out of 2147483647...
                                  failed...
   6 <      > <    _%n>      |  1:SPACE(2)
   7 <       > <   _%n>      |  2:STAR(4)
                                  SPACE can match 3 times out of 2147483647...
                                  failed...
   7 <       > <   _%n>      |  1:SPACE(2)
   8 <        > <  _%n>      |  2:STAR(4)
                                  SPACE can match 2 times out of 2147483647...
                                  failed...
   8 <        > <  _%n>      |  1:SPACE(2)
   9 <         > < _%n>      |  2:STAR(4)
                                  SPACE can match 1 times out of 2147483647...
                                  failed...
   9 <         > < _%n>      |  1:SPACE(2)
  10 <          > <_%n>      |  2:STAR(4)
                                  SPACE can match 0 times out of 2147483647...
                                  failed...
Contradicts stclass... [regexec_flags]
Match failed
--------------------------------------------------
Freeing REx: "\s+\n"
Freeing REx: "\s\s*\n"