This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
S_regmatch: eliminate WHILEM_A_min paren saving
authorDavid Mitchell <davem@iabyn.com>
Tue, 14 Feb 2017 17:10:34 +0000 (17:10 +0000)
committerDavid Mitchell <davem@iabyn.com>
Tue, 14 Feb 2017 17:49:58 +0000 (17:49 +0000)
In something like

    "a1b2c3d4..." =~ /(?:(\w)(\d))*..../

A WHILEM state is pushed for each iteration of the '*'. Part of this
state saving includes the previous indices for each of the captures within
the body of the thing being iterated over. So we save the following sets of
values for $1,$2:

    ()()
    (a)(1)
    (b)(2)
    (c)(3)
    (d)(4)

Then if at any point we backtrack, we can undo one or more iterations and
restore the older values of $1,$2.

However, when the match is non-greedy, as in A*?B, then on failure of B
and backtracking we attempt *more* A's rather than removing some already
matched A's. So there's never any need to save all the current paren state
for each iteration.

This eliminates a lot of per-iteration overhead for minimal WHILEMs and
makes the following run about 25% faster:

$s = ("a" x 1000);
$s =~ /^(?:(.)(.))*?[XY]/ for 1..10_000;

regexec.c
t/perf/benchmarks

index 73178b3..bd78870 100644 (file)
--- a/regexec.c
+++ b/regexec.c
@@ -7603,11 +7603,11 @@ NULL
            CACHEsayNO;
            NOT_REACHED; /* NOTREACHED */
 
-       case WHILEM_A_min_fail: /* just failed to match A in a minimal match */
-           /* FALLTHROUGH */
        case WHILEM_A_pre_fail: /* just failed to match even minimal A */
            REGCP_UNWIND(ST.lastcp);
             regcppop(rex, &maxopenparen);
+           /* FALLTHROUGH */
+       case WHILEM_A_min_fail: /* just failed to match A in a minimal match */
            cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
            cur_curlyx->u.curlyx.count--;
            CACHEsayNO;
@@ -7661,9 +7661,6 @@ NULL
            );
            /* Try grabbing another A and see if it helps. */
            cur_curlyx->u.curlyx.lastloc = locinput;
-            ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
-                            maxopenparen);
-           REGCP_SET(ST.lastcp);
            PUSH_STATE_GOTO(WHILEM_A_min,
                /*A*/ NEXTOPER(ST.save_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS,
                 locinput);
index 233f1fb..dec29bf 100644 (file)
         setup   => '$_ = ("0" x 100) . ("a" x 100);',
         code    => '/[acgt]+/',
     },
+
+    'regex::whilem::min_captures_fail' => {
+        desc    => '/WHILEM with anon-greedy match and captures that fails',
+        setup   => '$_ = ("a" x 20)',
+        code    => '/^(?:(.)(.))*?[XY]/',
+    },
+    'regex::whilem::max_captures_fail' => {
+        desc    => '/WHILEM with a greedy match and captures that fails',
+        setup   => '$_ = ("a" x 20)',
+        code    => '/^(?:(.)(.))*[XY]/',
+    },
 ];