Speed up multiline regexes anchored by `^`.

[haampie]

Feature or enhancement

Proposal:

I noticed that for regexes of the form

regex = re.compile("^foo", re.MULTILINE)
regex.search(...)

there's a character by character loop calling SRE(match) every iteration. That's significantly slower than the regex

regex = re.compile("foo...")
regex.search(...)

which does a special prefix scan for "foo" without having to call SRE(match) on each character:

cpython/Modules/_sre/sre_lib.h

Line 1747 in 42d645a

/* pattern starts with a literal character */

cpython/Modules/_sre/sre_lib.h

Lines 1775 to 1776 in 42d645a

	/* pattern starts with a known prefix. use the overlap
	table to skip forward as fast as we possibly can */

I would expect ^foo and foo to have more or less identical performance. A simple patch like this fixes that.

diff --git a/Modules/_sre/sre_lib.h b/Modules/_sre/sre_lib.h
index df377905bfa..70de4cccefd 100644
--- a/Modules/_sre/sre_lib.h
+++ b/Modules/_sre/sre_lib.h
@@ -1855,6 +1855,18 @@ SRE(search)(SRE_STATE* state, SRE_CODE* pattern)
             return 0;
         }
         while (status == 0 && ptr < end) {
+            if (pattern[0] == SRE_OP_AT &&
+                pattern[1] == SRE_AT_BEGINNING_LINE &&
+                (void*) ptr > state->beginning &&
+                !SRE_IS_LINEBREAK((int) ptr[-1]))
+            {
+                /* fast-forward to the next newline character */
+                while (ptr < end && !SRE_IS_LINEBREAK((int) *ptr)) {
+                    ptr++;
+                }
+                if (ptr >= end) {
+                    return 0;
+                }
+            }
             ptr++;
             RESET_CAPTURE_GROUP();
             TRACE(("|%p|%p|SEARCH\n", pattern, ptr));

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

No response

Linked PRs

• gh-148762: speed up SRE_AT_BEGINNING_LINE regexes #148778
• gh-148762: Speed up multiline regexes anchored by ^ #152339

[haampie]

On a benchmark on Darwin M4 with PGO+LTO I'm getting the following results on a realistic benchmark, running regexes on the Python source code from this repo's Lib/.

UCS-1: 29472107 chars

Pattern	Hits	before	after	change
^class \w'	7384 hits	87.13 ms	14.16 ms	-83%
^def \w'	4916 hits	87.03 ms	14.06 ms	-83%
^import \w'	5887 hits	87.15 ms	14.11 ms	-83%
^False \w'	0 hits	86.83 ms	13.81 ms	-84%
^# \w'	5748 hits	84.99 ms	14.25 ms	-83%

UCS-2: 35367992 chars

Pattern	Hits	before	after	change
^class \w'	8374 hits	205.31 ms	21.95 ms	-89%
^def \w'	5522 hits	208.63 ms	21.85 ms	-89%
^import \w'	6598 hits	207.80 ms	21.89 ms	-89%
^False \w'	0 hits	210.89 ms	21.65 ms	-89%
^# \w'	6200 hits	208.76 ms	21.89 ms	-89%

UCS-4: 38021052 chars

Pattern	Hits	before	after	change
^class \w'	8768 hits	213.74 ms	23.69 ms	-88%
^def \w'	5578 hits	224.03 ms	23.54 ms	-89%
^import \w'	6786 hits	218.25 ms	23.59 ms	-89%
^False \w'	0 hits	260.07 ms	23.20 ms	-91%
^# \w'	6311 hits	228.88 ms	23.54 ms	-89%

Similar results on GNU Linux Intel(R) Xeon(R) CPU E5-2620 v3 @ 2.40GHz also with PGO+LTO:

• UCS-1 : 245.01 ms -> 40.90 ms (-83%)
• UCS-2: 319.62 ms -> 53.98 ms (-83%)
• UCS-4: 354.95 ms -> 60.59 ms (-82%)

Benchmark

import timeit
import re
import os
import sys

# Collect all .py source files from Lib/
source_dir = os.path.join(os.path.dirname(__file__) or ".", "Lib")
all_files = []
for root, dirs, files in os.walk(source_dir):
    for f in files:
        if f.endswith(".py"):
            try:
                all_files.append(open(os.path.join(root, f)).read())
            except (OSError, UnicodeDecodeError):
                pass

# Classify files by their max codepoint
ucs1_files = [t for t in all_files if t and max(ord(c) for c in t) <= 0xFF]
ucs2_files = [t for t in all_files if t and max(ord(c) for c in t) <= 0xFFFF]
ucs4_files = all_files

corpora = {
    "UCS-1": "".join(ucs1_files),
    "UCS-2": "".join(ucs2_files),
    "UCS-4": "".join(ucs4_files),
}

regexes = [re.compile(r, re.MULTILINE) for r in (r"^class \w", r"^def \w", r"^import \w", r"^False \w", r"^# \w")]

number = 100
repeat = 5

for label, corpus in corpora.items():
    nchars = len(corpus)
    nbytes = sys.getsizeof(corpus)
    print(f"--- {label}: {nchars} chars, {nbytes} bytes ({nbytes / nchars:.1f} bytes/char) ---")
    for regex in regexes:
        count = sum([1 for x in regex.finditer(corpus)])
        t = min(timeit.repeat(lambda c=corpus, r=regex: sum([1 for x in r.finditer(c)]), number=number, repeat=repeat))
        print(f"  count({regex!r:10s}): {count:6d} hits, {t*1e3/number:8.2f} ms")
    print()

[haampie]

I've edited this issue to keep it simple :).

A future optimization would be to use find_char instead of the hand-written loop, similar to #148733.

[eendebakpt]

@haampie The speedup is good and added complexity is small. Can you re-open the PR and rebase to current main? The only thing I would like different is to move the checks on pattern out of the default loop. (this might main having another if branch with a while loop, but that is ok I think)

[haampie]

Hi @eendebakpt, thanks for returning to this issue. Do you mean like this?

    } else {
        /* general case */
        assert(ptr <= end);
        TRACE(("|%p|%p|SEARCH\n", pattern, ptr));
        state->start = state->ptr = ptr;
        status = SRE(match)(state, pattern, 1);
        state->must_advance = 0;
        if (status == 0 && pattern[0] == SRE_OP_AT &&
            (pattern[1] == SRE_AT_BEGINNING ||
             pattern[1] == SRE_AT_BEGINNING_STRING))
        {
            state->start = state->ptr = ptr = end;
            return 0;
        }
        if (pattern[0] == SRE_OP_AT && pattern[1] == SRE_AT_BEGINNING_LINE) {
            while (status == 0 && ptr < end) {
                /* skip to the start of the next line */
                while (ptr < end && !SRE_IS_LINEBREAK((int) *ptr))
                    ptr++;
                if (ptr >= end)
                    break;
                ptr++;
                RESET_CAPTURE_GROUP();
                TRACE(("|%p|%p|SEARCH\n", pattern, ptr));
                state->start = state->ptr = ptr;
                status = SRE(match)(state, pattern, 0);
            }
        } else {
            while (status == 0 && ptr < end) {
                ptr++;
                RESET_CAPTURE_GROUP();
                TRACE(("|%p|%p|SEARCH\n", pattern, ptr));
                state->start = state->ptr = ptr;
                status = SRE(match)(state, pattern, 0);
            }
        }
    }

This has the downside that common parts of the loop body are duplicated. From the optimizing compiler's perspective there's no difference, so it's mostly a matter of style preference.

[eendebakpt]

I meant like this:

            RESET_CAPTURE_GROUP();
        }
    } else if (pattern[0] == SRE_OP_AT &&
               pattern[1] == SRE_AT_BEGINNING_LINE) {
        /* pattern is anchored at the start of a line (MULTILINE "^").
           Only the start of the string and the character after a linebreak
           can match, so jump from one line start to the next instead of
           trying SRE(match) at every position. */
        end = (SRE_CHAR *)state->end;
        TRACE(("|%p|%p|SEARCH AT_BEGINNING_LINE\n", pattern, ptr));
        state->start = state->ptr = ptr;
        status = SRE(match)(state, pattern, 1);
        state->must_advance = 0;
        while (status == 0) {
            /* skip to the next linebreak ... */
            while (ptr < end && !SRE_IS_LINEBREAK(*ptr))
                ptr++;
            if (ptr >= end)
                return 0;
            ptr++;  /* ... and step past it, onto a line start */
            RESET_CAPTURE_GROUP();
            TRACE(("|%p|%p|SEARCH AT_BEGINNING_LINE\n", pattern, ptr));
            state->start = state->ptr = ptr;
            status = SRE(match)(state, pattern, 0);
        }
    } else {
        /* general case */
        assert(ptr <= end);

It has more code duplication, but it does keep the default path the same and the structure more clear. I don't feel strongly about it though, so it is also fine to update the branch so others can give their opinion.

[haampie]

OK, I don't have strong opinions, I've opened #152339.