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

Trước tiên, hãy xem xét các PR được liên kết, sau đó đọc vòng lặp tìm kiếm SRE trong Modules/_sre/sre_lib.h, đặc biệt là mã quét tiền tố được tham chiếu. Tái tạo các lần tìm kiếm nhiều dòng ^foo và các lần tìm kiếm không neo foo, rồi so sánh hiệu năng của chúng. Được xem là hoàn tất khi trường hợp có neo có tốc độ gần hơn một cách đo được, mà không thay đổi hành vi của biểu thức chính quy.