Use `memchr` in SRE's prefix scanner · Issue #148729 · python/cpython · GitHub

Feature or enhancement

Proposal:

Python's regex prefix scanning loops advance one byte at a time to find the first character of a literal prefix. For SIZEOF_SRE_CHAR == 1, memchr is a drop-in replacement that uses SIMD. The idea is to skip say 32 bytes per iteration in the negative case (no match).

The two loops are at

cpython/Modules/_sre/sre_lib.h

Lines 1756 to 1759 in 7ce737e

    
           while (*ptr != c) { 
        
               if (++ptr >= end) 
        
                   return 0; 
        
           }

cpython/Modules/_sre/sre_lib.h

Lines 1789 to 1792 in 7ce737e

    
           while (*ptr++ != c) { 
        
               if (ptr >= end) 
        
                   return 0; 
        
           }

Similar issues/prs are gh-145797 (memchr in str.split) and building on gh-57343, gh-57345.

Proposed patch:

--- a/Modules/_sre/sre_lib.h
+++ b/Modules/_sre/sre_lib.h
@@ -1753,10 +1753,19 @@
         end = (SRE_CHAR *)state->end;
         state->must_advance = 0;
         while (ptr < end) {
+#if SIZEOF_SRE_CHAR == 1
+            {
+                SRE_CHAR *found = memchr(ptr, c, end - ptr);
+                if (!found)
+                    return 0;
+                ptr = found;
+            }
+#else
             while (*ptr != c) {
                 if (++ptr >= end)
                     return 0;
             }
+#endif
             TRACE(("|%p|%p|SEARCH LITERAL\n", pattern, ptr));
             state->start = ptr;
@@ -1786,10 +1795,19 @@
         while (ptr < end) {
             SRE_CHAR c = (SRE_CHAR) prefix[0];
+#if SIZEOF_SRE_CHAR == 1
+            {
+                SRE_CHAR *found = memchr(ptr, c, end - ptr);
+                if (!found)
+                    return 0;
+                ptr = found + 1;
+            }
+#else
             while (*ptr++ != c) {
                 if (ptr >= end)
                     return 0;
             }
+#endif
             if (ptr >= end)
                 return 0;

I ran into this while profiling a log parser (pretty much grepping for error and warning strings) that applies a handful of literal-prefix regexes to each line of a ~5MB log file. With the patch, the runtime is reduced by ~14% end-to-end. A similar use case in the same application is scanning a binary executable/library for strings with a pattern /common/prefix/(foo|bar|baz) where I would benefit even more from memchr to find the / anchors.

Microbenchmark on my M4 macbook (without PGO):

Single-char prefix re.compile(r"X(A|B)"), match at position N against aaa...aXA

match position	baseline	patched	speedup
0	55 ns	58 ns	~flat
50	70 ns	53 ns	1.3x
100	83 ns	55 ns	1.5x
500	217 ns	62 ns	3.5x
1,000	326 ns	70 ns	4.7x
10,000	2,379 ns	219 ns	10.9x
100,000	23,348 ns	1,576 ns	14.8x

Multi-char prefix re.compile(r"XXXX(A|B)"), match at position N against aaaa...aXXXXA

match position	baseline	patched	speedup
0	57 ns	56 ns	~flat
100	71 ns	58 ns	1.2x
500	142 ns	65 ns	2.2x
1,000	221 ns	72 ns	3.1x
10,000	1,652 ns	225 ns	7.3x
100,000	15,952 ns	1,621 ns	9.8x

The reason the second benchmark is not as good as the first is that the apple clang compiler seems to have unrolled the second loop 4x while the first loop is not unrolled at all. Neither of them were auto-vectorized.

Synthetic benchmark

"""Synthetic benchmark for SRE prefix scanning at various string lengths."""

import re
import time

def bench(pat, text, iterations):
    for _ in range(1000):
        pat.search(text)
    t0 = time.perf_counter()
    for _ in range(iterations):
        pat.search(text)
    dt = time.perf_counter() - t0
    ns_per_call = dt / iterations * 1e9
    print(f"  {ns_per_call:8.1f} ns/call")

# Single-char prefix: X(A|B) has prefix "X" (len=1)
pat1 = re.compile(r"X(A|B)")
print("Single-char prefix: X(A|B), match at position N")
for n in [0, 5, 10, 50, 100, 500, 1000, 10000, 100000]:
    text = "a" * n + "XA"
    print(f"  match at pos {n:>6d} (len={len(text):>6d})", end="")
    bench(pat1, text, max(100000, 1000000 // max(n, 1)))

# Multi-char prefix: XXXX(A|B) has prefix "XXXX" (len=4)
pat4 = re.compile(r"XXXX(A|B)")
print()
print("Multi-char prefix: XXXX(A|B), match at position N")
for n in [0, 5, 10, 50, 100, 500, 1000, 10000, 100000]:
    text = "a" * n + "XXXXA"
    print(f"  match at pos {n:>6d} (len={len(text):>6d})", end="")
    bench(pat4, text, max(100000, 1000000 // max(n, 1)))

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-148729: use memchr in SRE prefix scan #148733

I'll check later if I can get some numbers with PGO enabled, if someone doesn't beat me to it.

Edit: with PGO the timings are pretty much the same.

pythongh-148729: use memchr in SRE prefix scan

Out of curiosity, how does GCC fare? please make PGO+LTO benchmarks (not just PGO) as well as they are also redistributed as is. If possible it would be great to know about Windows / Linux builds.

I won't be able to verify that now, but will check somewhere in the next few days.

For what it's worth, I'm slightly unhappy with the fact that only UCS-1 is fast with the patch and not UCS-2/UCS-4. Add one emoji to a string, and suddenly the regex runs 10x slower. Do you think that should be addressed? Or better to stick to this small, incremental improvement just for latin-1 strings and byte arrays?

I'm struggling a bit with getting uniformly good performance. The prefix matching is exactly str.find, so in principle I could reuse that code, but even then there are a few considerations.

The TL;DR:

wmemchr can be slow; and its emulation already written in cpython is usually fast, but also not always.
The call site in sre would still be somewhat complex.

Details:

The fast "Two-Way" algorithm only kicks in at needle length >= 6, so it is unlikely to be used much in regexes; the fallback to default_find is pretty slow. So then I'd have to branch like:
- prefix_len < 6: use find_char
  
  cpython/Objects/stringlib/fastsearch.h
  
  Line 50 in 5a3f479
  
  STRINGLIB(find_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
  
  to find the next possible match
- prefix_len >= 6: use fastsearch:
  
  cpython/Objects/stringlib/fastsearch.h
  
  Line 773 in 5a3f479
  
  FASTSEARCH(const STRINGLIB_CHAR* s, Py_ssize_t n,

find_char has variable performance:

With apple-clang, wmemchr is not optimized at all, so I would not define STRINGLIB_FAST_MEMCHR to wmemchr to avoid this branch

cpython/Objects/stringlib/fastsearch.h

Lines 57 to 62 in 5a3f479

    
           #ifdef STRINGLIB_FAST_MEMCHR 
        
                   p = STRINGLIB_FAST_MEMCHR(s, ch, n); 
        
                   if (p != NULL) 
        
                       return (p - s); 
        
                   return -1; 
        
           #else

On other platforms though, wmemchr might as well be perfectly optimized and therefore the best option -- hard to know at compile time.

The fallback case still has a non-zero likelihood of being slow (1 in 256) depending on input:

cpython/Objects/stringlib/fastsearch.h

Lines 67 to 70 in 5a3f479

    
                   /* If looking for a multiple of 256, we'd have too 
        
                      many false positives looking for the '\0' byte in UCS2 
        
                      and UCS4 representations. */ 
        
                   if (needle != 0) {

After playing around more I think I would go with find_char from fastsearch.h to jump to the next prefix match. That dispatches to memchr for the UCS-1 case, with reasonable fallback for the UCS-2 and UCS-4 cases.

Using fastsearch.h's algorithm for str.find in the regex engine is probably not a good idea. The regex compiler precomputes an overlap table once and for all, whereas FASTSEARCH has to do similar bookkeeping on every call.

Out of curiosity, how does GCC fare? please make PGO+LTO benchmarks (not just PGO) as well as they are also redistributed as is. If possible it would be great to know about Windows / Linux builds.

I now have data for GNU Linux and Darwin with PGO+LTO, for the UCS-1, UCS-2, and UCS-4 cases, using stringlib's find_char at commit haampie@6e1b1b9.

Benchmark 1 is basically grepping for things like def \w in cpython's Python sources, and should be realistic example.
Benchmark 2 is a synthetic micro-benchmark for best and worst case scenarios for the new code.

It shows the pros and cons of memchr well. The regression on darwin is because the letter i has a density of 2.88% in the corpus; the cross-over density is apparently about 2%, below which memchr is faster. However, on the intel CPU the cross-over point is closer to 20% or so, and it's a uniform speedup in practice.

Realistic benchmark

x86_64-linux-gnu, GCC 10, Intel(R) Xeon(R) CPU E5-2620 v3

Machine cfarm13 from https://portal.cfarm.net/machines/list/

UCS-1: 29480807 chars		before	after	change
class \w	15637 hits	25.92 ms	16.76 ms	-35%
def \w	58764 hits	37.38 ms	28.87 ms	-22%
import \w	13882 hits	29.98 ms	20.13 ms	-32%
False \w	171 hits	13.79 ms	3.17 ms	-77%
yield \w	1237 hits	15.95 ms	5.66 ms	-64%

UCS-2: 35376692 chars		before	after	change
class \w	17372 hits	44.49 ms	24.08 ms	-45%
def \w	69801 hits	60.33 ms	40.21 ms	-33%
import \w	16268 hits	49.64 ms	30.59 ms	-38%
False \w	194 hits	29.14 ms	6.55 ms	-77%
yield \w	1455 hits	32.20 ms	9.34 ms	-70%

UCS-4: 38029752 chars		before	after	change
class \w	18588 hits	48.72 ms	30.69 ms	-37%
def \w	72981 hits	64.82 ms	47.11 ms	-27%
import \w	16866 hits	53.92 ms	38.10 ms	-29%
False \w	200 hits	32.52 ms	13.06 ms	-59%
yield \w	1495 hits	35.94 ms	15.62 ms	-56%

arm64-apple-darwin24.6.0, Apple clang 17.0.0, M4

UCS-1: 29480807 chars		before	after	change
class \w	15637 hits	9.13 ms	8.70 ms	-4.7%
def \w	58764 hits	12.07 ms	11.26 ms	-6.7%
import \w	13882 hits	10.96 ms	12.49 ms	13.9%
False \w	171 hits	5.17 ms	1.14 ms	-77.9%
yield \w	1237 hits	6.08 ms	2.77 ms	-54.4%

UCS-2: 35376692 chars		before	after	change
class \w	17372 hits	14.27 ms	11.49 ms	-19.4%
def \w	69801 hits	18.17 ms	14.70 ms	-19.0%
import \w	16268 hits	16.43 ms	16.00 ms	-2.6%
False \w	194 hits	9.24 ms	2.07 ms	-77.5%
yield \w	1455 hits	10.43 ms	4.02 ms	-61.4%

UCS-4: 38029752 chars		before	after	change
class \w	18588 hits	15.44 ms	13.55 ms	-12.2%
def \w	72981 hits	18.96 ms	16.84 ms	-11.1%
import \w	16866 hits	17.45 ms	18.42 ms	5.5%
False \w	200 hits	10.02 ms	3.51 ms	-64.9%
yield \w	1495 hits	11.22 ms	5.61 ms	-50.0%

Synthetic micro-benchmark

x86_64-linux-gnu, GCC 10, Intel(R) Xeon(R) CPU E5-2620 v3

X(A\|B) in aaa...aXA	before	after	change
match at 0	336 ns	353 ns	+5%
match at 50	359 ns	359 ns	0%
match at 100	393 ns	361 ns	-8%
match at 500	557 ns	364 ns	-35%
match at 1,000	761 ns	368 ns	-52%
match at 10,000	4471 ns	479 ns	-89%
match at 100,000	41646 ns	2135 ns	-95%

aX(A\|B) in aaa...aaXA	before	after	change
match at 0	344 ns	348 ns	+1%
match at 50	515 ns	858 ns	+67%
match at 100	670 ns	1321 ns	+97%
match at 500	1926 ns	5340 ns	+177%
match at 1,000	3507 ns	10738 ns	+206%
match at 10,000	32012 ns	100797 ns	+215%
match at 100,000	310484 ns	1015 us	+227%

arm64-apple-darwin24.6.0, Apple clang 17.0.0, M4

X(A\|B) in aaa...aXA	before	after	change
match at 0	87 ns	63 ns	-28%
match at 50	104 ns	66 ns	-37%
match at 100	122 ns	65 ns	-47%
match at 500	280 ns	74 ns	-74%
match at 1,000	426 ns	84 ns	-80%
match at 10,000	2880 ns	236 ns	-92%
match at 100,000	22900 ns	1669 ns	-93%

aX(A\|B) in aaa...aaXA	before	after	change
match at 0	64 ns	70 ns	+9%
match at 50	145 ns	360 ns	+148%
match at 100	221 ns	682 ns	+209%
match at 500	848 ns	3338 ns	+294%
match at 1,000	1629 ns	6636 ns	+307%
match at 10,000	15767 ns	66570 ns	+322%
match at 100,000	157975 ns	670602 ns	+324%

Benchmark code (realistic)

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"yield \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()

Benchmark code (synthetic)

import re
import timeit

cases = [
    ("Single-char prefix", re.compile(r"X(A|B)"), "XA"),
    ("Multi-char prefix", re.compile(r"XXXX(A|B)"), "XXXXA"),
    ("Adversarial (first char always matches)", re.compile(r"aX(A|B)"), "aXA"),
]

positions = [0, 50, 100, 500, 1_000, 10_000, 100_000]

number = 1_000
repeat = 5

for label, pattern, needle in cases:
    print(f"{label}  {pattern.pattern!r}, match at position N against aaa...a{needle}")
    print(f"{'match position':>20s}  {'time':>10s}")
    for pos in positions:
        haystack = "a" * pos + needle
        t = min(timeit.repeat(lambda h=haystack, p=pattern: p.search(h), number=number, repeat=repeat))
        ns = t / number * 1e9
        print(f"{pos:>20,d}  {ns:>8.0f} ns")
    print()

Sorry for the delay. Yes, find_char is the right direction: the low-byte memchr filter is exactly what the UCS2/UCS4 cases need, and one emoji should not cost 10x.

On including the header: _sre is a core module, so including stringlib/fastsearch.h is technically possible, but it drags the whole two-way search machinery into _sre for one function, and the STRINGLIB_* parametrization would have to be repeated for each of the three SRE_CHAR widths inside an already thrice-included template. I would rather factor find_char out of fastsearch.h into a small separate stringlib/find_char.h included by both — one implementation, no duplication. Copying the ~40-line loop into sre_lib.h under SIZEOF_SRE_CHAR guards is an acceptable fallback.

Two things to keep when you reopen the PR: both scan loops should be converted (the prefix_len == 1 path also serves single-literal patterns, and the overlap-table path needs the "points one past the candidate" invariant preserved), and the s[n] over-read caveat at the top of fastsearch.h does not apply to find_char — worth a comment either way.

FWIW, I independently reproduced the plain-memchr variant for SIZEOF_SRE_CHAR == 1 and measured ~21x on scanning 8-bit haystacks (miss and late-hit alike), with 217k search/finditer span comparisons against the unpatched engine over bytes and UCS1/UCS2/UCS4 haystacks — no differences. The differential harness applies unchanged to the find_char version; happy to share it.

Happy to try it on the machines I have access to.

@haampie Is this still on your list? If not, I can pick it up following @serhiy-storchaka's find_char.h suggestion. Happy to just review or test if you'd rather keep it!

Use `memchr` in SRE's prefix scanner · Issue #148729 · python/cpython · GitHub

Repository navigation

Use memchr in SRE's prefix scanner #148729

Feature or enhancement

Proposal:

Has this already been discussed elsewhere?

Links to previous discussion of this feature:

Linked PRs

Realistic benchmark

Synthetic micro-benchmark

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	#ifdef STRINGLIB_FAST_MEMCHR
	p = STRINGLIB_FAST_MEMCHR(s, ch, n);
	if (p != NULL)
	return (p - s);
	return -1;
	#else

	/* If looking for a multiple of 256, we'd have too
	many false positives looking for the '\0' byte in UCS2
	and UCS4 representations. */
	if (needle != 0) {

Use `memchr` in SRE's prefix scanner · Issue #148729 · python/cpython · GitHub

Repository navigation

Use memchr in SRE's prefix scanner #148729

Description

Feature or enhancement

Proposal:

Has this already been discussed elsewhere?

Links to previous discussion of this feature:

Linked PRs

Activity

haampie commented on Apr 18, 2026

picnixz commented on Apr 20, 2026

haampie commented on Apr 20, 2026

haampie commented on Apr 21, 2026

haampie commented on Apr 22, 2026

Realistic benchmark

Synthetic micro-benchmark

serhiy-storchaka commented on Jul 6, 2026

haampie commented on Jul 6, 2026

maurycy commented on Oct 7, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions