Title: Use `memchr` in SRE's prefix scanner · Issue #148729 · python/cpython · GitHub
Open Graph Title: Use `memchr` in SRE's prefix scanner · Issue #148729 · python/cpython
X Title: Use `memchr` in SRE's prefix scanner · Issue #148729 · python/cpython
Description: 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 sk...
Open Graph Description: 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 repla...
X Description: 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 r...
Opengraph URL: https://github.com/python/cpython/issues/148729
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Use `memchr` in SRE's prefix scanner","articleBody":"# Feature or enhancement\n\n### Proposal:\n\nPython'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).\n\nThe two loops are at \n\nhttps://github.com/python/cpython/blob/7ce737ea11919aebf7eef174f910759e74d0ea50/Modules/_sre/sre_lib.h#L1756-L1759\n\nhttps://github.com/python/cpython/blob/7ce737ea11919aebf7eef174f910759e74d0ea50/Modules/_sre/sre_lib.h#L1789-L1792\n\nSimilar issues/prs are gh-145797 (`memchr` in `str.split`) and building on gh-57343, gh-57345.\n\nProposed patch:\n\n```diff\n--- a/Modules/_sre/sre_lib.h\n+++ b/Modules/_sre/sre_lib.h\n@@ -1753,10 +1753,19 @@\n end = (SRE_CHAR *)state->end;\n state->must_advance = 0;\n while (ptr \u003c end) {\n+#if SIZEOF_SRE_CHAR == 1\n+ {\n+ SRE_CHAR *found = memchr(ptr, c, end - ptr);\n+ if (!found)\n+ return 0;\n+ ptr = found;\n+ }\n+#else\n while (*ptr != c) {\n if (++ptr >= end)\n return 0;\n }\n+#endif\n TRACE((\"|%p|%p|SEARCH LITERAL\\n\", pattern, ptr));\n state->start = ptr;\n@@ -1786,10 +1795,19 @@\n while (ptr \u003c end) {\n SRE_CHAR c = (SRE_CHAR) prefix[0];\n+#if SIZEOF_SRE_CHAR == 1\n+ {\n+ SRE_CHAR *found = memchr(ptr, c, end - ptr);\n+ if (!found)\n+ return 0;\n+ ptr = found + 1;\n+ }\n+#else\n while (*ptr++ != c) {\n if (ptr >= end)\n return 0;\n }\n+#endif\n if (ptr >= end)\n return 0;\n```\n\nI 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.\n\nMicrobenchmark on my M4 macbook (without PGO):\n\nSingle-char prefix `re.compile(r\"X(A|B)\")`, match at position `N` against `aaa...aXA`\n\n| match position | baseline | patched | speedup |\n|----------------|----------|---------|---------|\n| 0 | 55 ns | 58 ns | ~flat |\n| 50 | 70 ns | 53 ns | 1.3x |\n| 100 | 83 ns | 55 ns | 1.5x |\n| 500 | 217 ns | 62 ns | 3.5x |\n| 1,000 | 326 ns | 70 ns | 4.7x |\n| 10,000 | 2,379 ns | 219 ns | 10.9x |\n| 100,000 | 23,348 ns | 1,576 ns | 14.8x |\n\nMulti-char prefix `re.compile(r\"XXXX(A|B)\")`, match at position N against `aaaa...aXXXXA`\n\n| match position | baseline | patched | speedup |\n|----------------|----------|---------|---------|\n| 0 | 57 ns | 56 ns | ~flat |\n| 100 | 71 ns | 58 ns | 1.2x |\n| 500 | 142 ns | 65 ns | 2.2x |\n| 1,000 | 221 ns | 72 ns | 3.1x |\n| 10,000 | 1,652 ns | 225 ns | 7.3x |\n| 100,000 | 15,952 ns | 1,621 ns | 9.8x |\n\nThe 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.\n\n\u003cdetails>\n\u003csummary>Synthetic benchmark\u003c/summary>\n\n```py\n\"\"\"Synthetic benchmark for SRE prefix scanning at various string lengths.\"\"\"\n\nimport re\nimport time\n\ndef bench(pat, text, iterations):\n for _ in range(1000):\n pat.search(text)\n t0 = time.perf_counter()\n for _ in range(iterations):\n pat.search(text)\n dt = time.perf_counter() - t0\n ns_per_call = dt / iterations * 1e9\n print(f\" {ns_per_call:8.1f} ns/call\")\n\n# Single-char prefix: X(A|B) has prefix \"X\" (len=1)\npat1 = re.compile(r\"X(A|B)\")\nprint(\"Single-char prefix: X(A|B), match at position N\")\nfor n in [0, 5, 10, 50, 100, 500, 1000, 10000, 100000]:\n text = \"a\" * n + \"XA\"\n print(f\" match at pos {n:>6d} (len={len(text):>6d})\", end=\"\")\n bench(pat1, text, max(100000, 1000000 // max(n, 1)))\n\n# Multi-char prefix: XXXX(A|B) has prefix \"XXXX\" (len=4)\npat4 = re.compile(r\"XXXX(A|B)\")\nprint()\nprint(\"Multi-char prefix: XXXX(A|B), match at position N\")\nfor n in [0, 5, 10, 50, 100, 500, 1000, 10000, 100000]:\n text = \"a\" * n + \"XXXXA\"\n print(f\" match at pos {n:>6d} (len={len(text):>6d})\", end=\"\")\n bench(pat4, text, max(100000, 1000000 // max(n, 1)))\n```\n\n\u003c/details>\n\n### Has this already been discussed elsewhere?\n\nThis is a minor feature, which does not need previous discussion elsewhere\n\n### Links to previous discussion of this feature:\n\n_No response_\n\n\u003c!-- gh-linked-prs -->\n### Linked PRs\n* gh-148733\n\u003c!-- /gh-linked-prs -->\n","author":{"url":"https://github.com/haampie","@type":"Person","name":"haampie"},"datePublished":"2026-04-18T15:29:29Z","url":"https://github.com/python/cpython/issues/148729"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:1ebe806d-bfba-9935-848c-863269dbb12d |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | A468:1F2B:2DBF3:41BD6:6B020264 |
| html-safe-nonce | 1821194459a39a1b49231e19880370a2186a1dbc1c9b75e213760270560b85c8 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJBNDY4OjFGMkI6MkRCRjM6NDFCRDY6NkIwMjAyNjQiLCJ2aXNpdG9yX2lkIjoiNjg0NTI3MzQxMDYxNDA3MzMyIiwicmVnaW9uX2VkZ2UiOiJpYWQiLCJyZWdpb25fcmVuZGVyIjoiaWFkIn0= |
| visitor-hmac | e67cf7b275fe41139d49e2804a3a83341ad917300bc370e467a9cee0da809c5d |
| hovercard-subject-tag | issue:4288420105 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/cpython/148729/issue_layout |
| twitter:image | https://opengraph.githubassets.com/02368f776a40f731747b03c8b36edcbae16eeda6f416af8aafa6f578daddeb9a/python/cpython/issues/148729 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/02368f776a40f731747b03c8b36edcbae16eeda6f416af8aafa6f578daddeb9a/python/cpython/issues/148729 |
| og:image:alt | 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 repla... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | haampie |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width