I understand (I think) why this is fast. What I don't understand is how it works. I'll admit that I am not much of regex hacker, but how does the variable length look behind now how far to look, in the case of quantifiers, especially greedy ones? It seems that the goal of the anchor is to prevent backtracking (hence the speed gains) but how does it now when to stop? If the \K anchor tells the regex engine to watch for the oncoming regex and stop matching there, whats the difference between \K and a minimal match, or negated character class? If the engine doesn't stop at the first instance of, say '.' (as in your example) how do you keep it from backtracking (which is where I'm presuming the speed gains come from)? Or is \K an optimization using sexegers?

Now, japhy I have absolute faith in your pattern - foo, so I take it on faith that this works. What I'm curious about is how. Am I missing something in thinking that the performance gains here are related to backtracking?

Light a man a fire, he's warm for a day. Catch a man on fire, and he's warm for the rest of his life. - Terry Pratchet

You're thinking too hard. I cheated. My patch just fools the regex engine into thinking it hasn't actually started matching yet. Here's a drawn-out example.

$str = "abc.def.ghi.jkl";
$str =~ s{
  .*     # match as much as you can
  \K     # and then pretend HERE is where we start
  \. .*  # then a . and anything else
}{}x;    # replace with nothing

__END__
abc.def.ghi.jkl       $&
AAAAAAAAAAA     .*    "abc.def.ghi"
                \K    ""
           B    \.    "."
           BCCC .*    ".jkl"
[download]

Does that help you see what I do? My patch consists of a couple lines of support, but this is the beef:

case KEEP:
  PL_regstartp[0] = locinput - PL_bostr;
  break;
[download]

That's what happens when the regex engine encounters the \K. The rest of the patch is just creating the "KEEP" node, and telling toke.c that "\K" is a valid escape sequence.

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

Okay, I know it's because I'm dumb, but I still don't get it. Please don't yell at me, but why does the \K anchor keep .* from matching .jkl? And if it backtracks like normal, then where does the speed come from? I think that may be the essence of my confusion - why is this faster?

If I don't get it this time, I'll give up and just trust it ;-).

Cheers,
Erik

Light a man a fire, he's warm for a day. Catch a man on fire, and he's warm for the rest of his life. - Terry Pratchet

1. filters regexes for the \K escape sequence, and turns them into (?{Regexp::Keep::KEEP})...
2. and defines an XS function, KEEP(), that does what \K is supposed to do

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

Can you post some benchmarks for the module? Or are the ones you posted above from the module (I'm assuming not).

Here's the code:

use Benchmark 'cmpthese';
use Regexp::Keep;
my $s = "abc.def.ghi.jkl";
cmpthese(-5, {
  japhy => sub { (my $x = $s) =~ s/.*\K\..*// },
  old   => sub { (my $x = $s) =~ s/(.*)\..*/$1/ },
});
[download]

In 5.6.1:

old   = 40280.54/s
japhy = 74338.79/s
[download]

And with 5.8.0 (using the module, NOT my patch):

old   =  58188.18/s
japhy = 102409.25/s
[download]

So there's an appreciable speed-up.

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

my $str =           "foo bar baz";
# will 'start' matching here ^
$str =~ s< (?: \w+ [ ] )+ \K \w+ >()x;
print '[' . $str . ']';

__output__

[foo bar ]
[download]

_________
broquaint

update: added missing whitespace in output (odd how an additional character requires so many to explain ;)

You've got the right idea (except for a missing whitespace in your output).

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

What's the mnemonic for \K?

Update: Ah, got it.

This is sort of like Prolog's "cut", isn't it? Match a prefix, then never backtrack back past the \K anchor to satisfy the regex. Can you have multiple \Ks in a single regex? I can see Abigail-II having lots of fun with this.

--
The hell with paco, vote for Erudil!
:wq

Yes, you can have multiple \K's in a regex, although only the last one really means anything, should the regex succeed. I'm actually curious why you would need more than one in the same branch, but it's perfectly legal.

But no, it's not cut. Cut is (?>pat). This is just telling the regex engine to pretend it just started matching, that $& is defined starting HERE.

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

There are two. K = Keep, as in, "keep everything we've just matched", because I envision it being used in substitutions. The other mnemonic is "\K isn't used by anything yet". ;)

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

$str =~ s/\..$//;
[download]

# Under Construction
[download]

Yours is a very special case, because we know there's only one character after the last ".". Here is a benchmark I ran with my new patch:

use Benchmark 'cmpthese';
my $str = join '.', 'a' .. 'z';
cmpthese(-5, {
  old => sub { (my $x = $str) =~ s/(.*)\..*/$1/ },
  new => sub { (my $x = $str) =~ s/.*\K\..*// },
});
__END__
new: 109650.19/s (n=578953)
old:  45258.35/s (n=241227)
[download]

... which is an incredible speed increase!

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

What's the impact on pos() if you fake out the starting point? Does pos() still reflect the start of matching, or does it reflect the start of the last \K?

Present an example that explains your question. pos() refers to the end of the last global match. Are you asking about any interference between \K and \G? I do not foresee any.

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

pos() refers to the end of the last global match.

Oops, you're right. The code fragement I was thinking of used pos() - $delta to get the starting point.

Look forward to it.