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

Überprüfe zuerst die verknüpften PRs und lies dann die SRE-Suchschleife in Modules/_sre/sre_lib.h, insbesondere den referenzierten Präfix-Scan-Code. Reproduziere die mehrzeiligen Suchen ^foo und die nicht verankerten Suchen foo und vergleiche ihre Performance. Fertig ist die Aufgabe, wenn der verankerte Fall messbar näher an der Geschwindigkeit liegt, ohne das Verhalten von regulären Ausdrücken zu ändern.