]> git.ipfire.org Git - thirdparty/Python/cpython.git/commit
gh-146455: Fix O(N²) in add_const() after constant folding moved to CFG (#146456)
authorzSirius <107359899+zSirius@users.noreply.github.com>
Sun, 26 Apr 2026 12:15:24 +0000 (20:15 +0800)
committerGitHub <noreply@github.com>
Sun, 26 Apr 2026 12:15:24 +0000 (15:15 +0300)
commit5d416324c56cd6f262fa123f41b97b48631bea79
treed3dd16cf4c83cdb8ff94b634833d7f7a1ecf6af0
parent6d4ca16f47586533c9223fe5729f6b7e221fa9f9
gh-146455: Fix O(N²) in add_const() after constant folding moved to CFG (#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
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