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 &&
+                !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

[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.