https://github.com/python/cpython/commit/d49e76b1eb6e49d0ba4f5a3ba6e822d5621e1b55
commit: d49e76b1eb6e49d0ba4f5a3ba6e822d5621e1b55
branch: main
author: Pablo Galindo Salgado <[email protected]>
committer: pablogsal <[email protected]>
date: 2026-07-18T18:12:38+02:00
summary:
gh-153568: Skip parser memo lookups that cannot match (#153571)
Each token now carries a small filter of the rule types present in its
memo list, so the common case of a miss no longer walks the list.
files:
A
Misc/NEWS.d/next/Core_and_Builtins/2026-07-11-14-57-19.gh-issue-153568.memoflt.rst
M Parser/pegen.c
M Parser/pegen.h
diff --git
a/Misc/NEWS.d/next/Core_and_Builtins/2026-07-11-14-57-19.gh-issue-153568.memoflt.rst
b/Misc/NEWS.d/next/Core_and_Builtins/2026-07-11-14-57-19.gh-issue-153568.memoflt.rst
new file mode 100644
index 00000000000000..9e78e5ad545a83
--- /dev/null
+++
b/Misc/NEWS.d/next/Core_and_Builtins/2026-07-11-14-57-19.gh-issue-153568.memoflt.rst
@@ -0,0 +1,2 @@
+Speed up the parser by letting memoization lookups that cannot match return
+immediately.
diff --git a/Parser/pegen.c b/Parser/pegen.c
index 447124cbe00b66..fcec810037e98d 100644
--- a/Parser/pegen.c
+++ b/Parser/pegen.c
@@ -100,6 +100,7 @@ _PyPegen_insert_memo(Parser *p, int mark, int type, void
*node)
m->mark = p->mark;
m->next = p->tokens[mark]->memo;
p->tokens[mark]->memo = m;
+ p->tokens[mark]->memo_mask |= 1ULL << (type & 63);
return 0;
}
@@ -360,6 +361,10 @@ _PyPegen_is_memoized(Parser *p, int type, void *pres)
Token *t = p->tokens[p->mark];
+ if (!(t->memo_mask & (1ULL << (type & 63)))) {
+ return 0;
+ }
+
for (Memo *m = t->memo; m != NULL; m = m->next) {
if (m->type == type) {
#if defined(Py_DEBUG)
diff --git a/Parser/pegen.h b/Parser/pegen.h
index 884b3ff62d7d99..3cca698692bf6b 100644
--- a/Parser/pegen.h
+++ b/Parser/pegen.h
@@ -42,6 +42,10 @@ typedef struct {
int level;
int lineno, col_offset, end_lineno, end_col_offset;
Memo *memo;
+ // Filter over the rule types present in `memo` (bit `type & 63` is set
+ // for every entry): lets lookups skip walking the list on definite
+ // misses, which are the common case.
+ uint64_t memo_mask;
PyObject *metadata;
} Token;
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/python-checkins.python.org
Member address: [email protected]
