[RFC/RFA] Patches to speed up . (period)

[Paolo Bonzini]

The top time-eater part of regular expression matching is currently (and 
by a large amount) the handling of subexpressions.  When they are found, 
the matcher goes through the string twice: once operating as a DFA, with 
a cost that is O(string length) and once operating as a "backwards NFA" 
with a worst-case cost of O(string length * NFA states) and with a big 
constant in front of it.

This constant can be lowered a bit by avoiding to go through the 
expensive multi-byte paths.  Single-byte searches do this by mistake, 
because OP_PERIOD is always passed through check_node_accept_bytes even 
in SBCS, and we can easily fix this: this is the purpose of patch 1 of 
the three attached files, which I had already submitted a prototype of.

Other searches need to do this, but an important exception is that of 
UTF-8 searches that were optimized.  To do so, we can lower the UTF-8 
period to [00-7f]|[c2-fd][80-bf]+, or to a more complicated regex that 
only passes valid UTF-8 encodings.  Patch 2 implements the more precise 
approach, which is what OP_UTF8_PERIOD token type in current CVS; patch 
3 uses the simpler regex (anyway both current CVS and patch 3 accept 
surrogate low/high characters which are invalid UTF-8).

The DFA performance of the two patches is comparable, but patch 3's NFA 
behavior is much better because the automaton has fewer states.

To time the patches, I've made a 48MB file from "find /" on my machine, 
and passed it through 5 matchers:

1) current CVS
2) patch 1
3) patch 1+2 (precise UTF-8 optimization)
4) patch 1+3 (faster UTF-8 optimization)
5) PCRE, based on a very fast syntax-directed matcher.

For each matcher, I made 3 tests in the C locale and three tests in the 
it_IT.UTF-8 locale.  I must say that PCRE knows very little about MBCS 
(many optimization it does are still applicable to UTF-8, though, and 
sed does induce some overhead in the UTF-8 cases too.

1) s,\(.*\)/\(.*\),\1 \2,
2) s,.*/,/\n, ; s,/\n, ,
3) s,.*/,/\n, ; s,.\n, ,

The result is the same, but scripts 2/3 do not employ subexpressions.  
Script 2 allows the fastmap to do more work.  This is faster in glibc's 
DFA matcher but slower in PCRE's syntax-directed matcher.  The timings 
are mixed, and that's why I presented the patches separately:

            C locale    C locale    C locale    UTF-8     UTF-8     UTF-8
            script 1    script 2    script 3    script 1  script 2  script 3
CVS         86.21       7.88        16.02       101.30    24.93     40.66
patch 1     79.42       7.91        15.96       102.53    25.33     41.42  
patch 1+2   79.30       7.91        16.41       158.43    17.81     25.84
patch 1+3   79.64       7.68        15.83       108.59    17.86     25.72
PCRE        4.60        5.08        10.59       11.26     15.07     20.05

Patches 2 and 3 have the same improvement on DFA-only queries, but the 
timing of patch 3 in the UTF-8 NFA query is awful.  Patch 1 does improve 
C locale searches, but causes a 1% decrease of performance in UTF-8 
searches.  This is expected since I did not mean patch 1 to be applied 
independently.

However, given this numbers my preference would be to apply patch 1 
only, since it does yield some wins, and wait if I can speed up grouping 
subexpressions until patch 2 is not a loss anymore (or at least the loss 
is balanced by the gains as is the case for patch 3 now).  Patch 1+3 is 
also good for me, since the differences are localized in 
replace_utf8_period_node; you can make a choice.

All patches tested against the glibc and sed testsuites on powerpc-linux.

Paolo

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 02-utf8-precise.patch
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20041206/23156ac8/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 01-sbcs.patch
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20041206/23156ac8/attachment-0001.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 03-utf8-faster.patch
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20041206/23156ac8/attachment-0002.ksh>