Re: Substitution ${...///} slows down when certain UTF character occurs

[Bart Schaefer <schaefer@xxxxxxxxxxxxxxxx>]

On Sep 26,  2:19pm, Sebastian Gniazdowski wrote:
}
} I attach a script that does ${...///} substitution.

I worry that the attachement hasn't come through correctly?  When I
unpack the base64 into text, I get (in part)

str="c4d5148ca6 ce3a2d24203abfb385 30f5fe85434ae ... 5d468f6"

Is the value of $str supposed to look like that?  So the pattern in
the ${str//...} replacement never matches?

} It  is very slow for some chars and very fast for others. How to explain
} and hopefully fix this?

Each time pattryrefs() fails to find a match, it increments the area
to be searched by one character and then tries the entire pattern
match again.  So for a 120000-character string, it's doing a non-
matching search 120000 times.

I rewrote your test to use "float SECONDS" + "print $SECONDS" instead
of forking off subshells for "time" and to use loops so I didn't have
to comment things in and out.  Observations:

1. It's only fast for the Yen symbol, which is the only one that does
not have a byte with the high-order bit set.  This case is avoiding
this block in pattern.c:

2124	    if (!(patflags & (PAT_PURES|PAT_ANY))
2125		&& (needfullpath || unmetalen != stringlen)) {
2126		/*
2127		 * We need to copy if we need to prepend the path so far
2128		 * (in which case we copy both chunks), or if we have
2129		 * Meta characters.
2130		 */

I.e., unmetalen == stringlen, so we do not allocate and copy the entire
120k bytes of $str for each pattern comparison.

This means in the case where there are high-order characters, the search
algorithm becomes O(N)^2 rather than O(N).

2. It's consistently slower the longer the prefix string before the
high-order byte becomes.

I believe this means that once the search loop has "gotten past" the
high-order byte, it stops doing the O(N)^2 copy-and-scan and drops in
to the O(N) scan of the original input string.  But I haven't traced
it down to exactly where that happens.  The nested loops around line
2908 in glob.c, I suspect.

So this could be sped up by factoring out the unmetafication, but it
would require some pretty serious reworking of the relationship between
pattrylen() / pattryrefs() and their callers.