◐ Shell
clean mode source ↗

gh-146455: Fix O(N²) in add_const() after constant folding moved to CFG by zSirius · Pull Request #146456 · python/cpython

zSirius

…d to CFG

The add_const() function in flowgraph.c uses a linear search over the
consts list to find the index of a constant. After pythongh-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

Eclips4

Eclips4

iritkatriel

Eclips4 pushed a commit that referenced this pull request

Apr 26, 2026 
…ed 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 5d41632)

Co-authored-by: zSirius <107359899+zSirius@users.noreply.github.com>