]> git.ipfire.org Git - thirdparty/Python/cpython.git/commit
[3.14] gh-146455: Fix O(N²) in add_const() after constant folding moved to CFG (GH...
authorMiss Islington (bot) <31488909+miss-islington@users.noreply.github.com>
Sun, 26 Apr 2026 15:45:38 +0000 (17:45 +0200)
committerGitHub <noreply@github.com>
Sun, 26 Apr 2026 15:45:38 +0000 (18:45 +0300)
commit78c5e54b4fd5798d8b74b901c34539bb09a5a064
tree7395586a016ed7d31aa8d0ad6a24f389112c6417
parent5770df43dc6d8d23b66b843ee708e4b239af35a8
[3.14] gh-146455: Fix O(N²) in add_const() after constant folding moved to CFG (GH-146456) (#149011)

gh-146455: Fix O(N²) in add_const() after constant folding moved to CFG (GH-146456)

The add_const() function in flowgraph.c uses a linear search over the
consts list to find the index of a constant. After gh-126835 moved
constant folding from the AST optimizer to the CFG optimizer, this
function is now called N times for N inner tuple elements during
fold_tuple_of_constants(), resulting in O(N²) total time.

Fix by maintaining an auxiliary _Py_hashtable_t that maps object
pointers to their indices in the consts list, providing O(1) lookup.

For a file with 100,000 constant 2-tuples:
- Before: 10.38s (add_const occupies 83.76% of CPU time)
- After:  1.48s
(cherry picked from commit 5d416324c56cd6f262fa123f41b97b48631bea79)

Co-authored-by: zSirius <107359899+zSirius@users.noreply.github.com>
Misc/NEWS.d/next/Core_and_Builtins/2026-03-26-08-49-35.gh-issue-146455.f54083a9.rst [new file with mode: 0644]
Python/flowgraph.c