Speed up multiline regexes anchored by `^`.

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:

https://github.com/python/cpython/blob/42d645a7e81e0a5e6e0d35e222a8520450ac28ef/Modules/_sre/sre_lib.h#L1747

https://github.com/python/cpython/blob/42d645a7e81e0a5e6e0d35e222a8520450ac28ef/Modules/_sre/sre_lib.h#L1775-L1776

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-148778
• gh-152339

Review the linked PRs first, then read the SRE search loop in Modules/_sre/sre_lib.h, especially the referenced prefix-scan code. Reproduce the multiline ^foo and unanchored foo searches and compare their performance. Done means the anchored case is measurably closer in speed without changing regex behavior.