re_intuit_start(): fix another utf8 slowdown
authorDavid Mitchell <davem@iabyn.com>
Thu, 16 Jan 2014 16:00:41 +0000 (16:00 +0000)
committerDavid Mitchell <davem@iabyn.com>
Fri, 7 Feb 2014 22:39:36 +0000 (22:39 +0000)
commit8e9f2289b28bd22cb8af0c73dee7f73d590dca2c
treeca930ae47f582279facf6d6a1b03744512f1af39
parenteb3831ce7cc842e7305959e873fcc82e356c7a57
re_intuit_start(): fix another utf8 slowdown

The code that looks for a floating substr after a fixed substr has
already been found, was very slow on long utf8 strings. For example
this used to take an hour or more, and now takes millisecs:

    $s = "ab" x 1_000_000;
    utf8::upgrade($s);
    $s =~ /ab.{1,2}x/;

When calculating the maximum position at which the floating substr could
start, there are two possible upper limits.

First, the absolute max position, ignoring the results of the previous
fixed substr match - this is the end-of-string less a bit (last1);

Second, float_max_offset on from the current origin of the regex (this
is dependent on where the fixed substr previously matched).

To decide which of these two values to use (the smaller), it used to
calculate the distance in chars from the regex origin to last1, and if
this was greater than float_max_offset, it used origin + float_max_offset
(in chars) instead.

This distance calculation involved doing a utf8 length calculation on the
majority of the string, which for long strings was a big slowdown.

Fix this by instead always using HOP3(origin + float_max_offset), but
using last1 as the upper HOP limit rather than strend, so it's always
limited to <= last1.

If L is number of chars that had to be hopped over for the distance
calculation (which could be most of the string), and if M is the
chars hopped for origin +  float_max_offset (typically either small or
infinite), then we:

    previously hopped: (M>=L ? L : L+M) chars
    now hop:           min(L,M) chars; or if M is infinite, hop 0 chars

Which is always less than or equal to the amount of work done previously,
and is a very big win for long strings with smallish maximum float
offsets.
regexec.c
t/re/pat.t