Replacing whole string is faster than replacing only its first character

user_1232660 0
Viewed 271

I tried to replace a character a by b in a given large string. I did an experiment - first I replaced it in the whole string, then I replaced it only at its beginning.

import re
# pattern = re.compile('a')
pattern = re.compile('^a')
string = 'x' * 100000

pattern.sub('b', string)

I expected that replacing the beginning would have to be much faster then replacing the whole string because you have to check only 1 position instead of 100000. I did some measuring:

python -m timeit --setup "import re; p=re.compile('a'); string='x'*100000" "p.sub('b', string)"
10000 loops, best of 3: 19.1 usec per loop

python -m timeit --setup "import re; p=re.compile('^a'); string='x'*100000" "p.sub('b', string)"
1000 loops, best of 3: 613 usec per loop

The results show that, on the contrary, trying to replace the whole string is about 30x faster. Would you expect such result? Can you explain that?

time python regex
1 Answers

The functions provided in the Python re module do not optimize based on anchors. In particular, functions that try to apply a regex at every position - .search, .sub, .findall etc. - will do so even when the regex can only possibly match at the beginning. I.e., even without multi-line mode specified, such that ^ can only match at the beginning of the string, the call is not re-routed internally. Thus:

$ # .match only looks at the first position regardless
$ python -m timeit --setup "import re; p=re.compile('a'); string='x'*100000" "p.match(string)"
2000000 loops, best of 5: 155 nsec per loop
$ python -m timeit --setup "import re; p=re.compile('^a'); string='x'*100000" "p.match(string)"
2000000 loops, best of 5: 157 nsec per loop
$ # .search looks at every position, even if there is an anchor
$ python -m timeit --setup "import re; p=re.compile('a'); string='x'*100000" "p.search(string)"
10000 loops, best of 5: 22.4 usec per loop
$ # and the anchor only adds complexity to the matching process
$ python -m timeit --setup "import re; p=re.compile('^a'); string='x'*100000" "p.search(string)"
500 loops, best of 5: 746 usec per loop

While re does not optimize for anchors, it does optimize for several other things that could occur at the start of a pattern. One of those optimizations is for a pattern starting with a single constant character:

    if (prefix_len == 1) {
        /* pattern starts with a literal character */
        SRE_CHAR c = (SRE_CHAR) prefix[0];
#if SIZEOF_SRE_CHAR < 4
        if ((SRE_CODE) c != prefix[0])
            return 0; /* literal can't match: doesn't fit in char width */
#endif
        end = (SRE_CHAR *)state->end;
        state->must_advance = 0;
        while (ptr < end) {
            while (*ptr != c) {
                if (++ptr >= end)
                    return 0;
            }
            ...

This optimization performs a simple character comparison to skip candidate matches that don't start with the required character, instead of invoking the full match engine. This optimization is why the unanchored regex was so much faster - there are 3 separate optimizations like this in the code, one for a single constant character, one for a multi-character constant prefix, and one for a character class, but nothing for a ^ anchor.

I think a reasonable case can be made to file a bug report against this - not having such an obvious optimization implemented clearly violates expectations. Aside from which, while it's easy to replace .search with an anchor using .match, it's not so straightforward to replace .sub with an anchor - you have to .match, check the result, and then call .replace on the string yourself.

If you need to anchor to the end of the string and not the start, it gets much more difficult; I recall ancient Perl advice to try reversing the string first, but it's hard in general to write a pattern that matches the reverse of what you want.

user_5236120
Related