GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — [3.14] gh-146455: Fix O(N²) in add_const() after constant folding moved to CFG (GH-146456) by miss-islington · Pull Request #149011 · python/cpython

Conversation

@miss-islington

@miss-islington miss-islington commented Apr 26, 2026 •
edited by bedevere-app Bot
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

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 [email protected]

  • Issue: Performance regression: O(N²) compile time for large constant tuples after const folding moved to CFG #146455

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@zSirius @miss-islington
pythongh-146455: Fix O(N²) in add_const() after constant folding move…
c58000d
…d to CFG (pythonGH-146456)

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
(cherry picked from commit 5d41632)

Co-authored-by: zSirius <[email protected]>
@miss-islington
miss-islington requested review from iritkatriel and markshannon as code owners April 26, 2026 12:16
@python-cla-bot

python-cla-bot Bot commented Apr 26, 2026 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown

All commit authors signed the Contributor License Agreement.

CLA signed

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@bedevere-app bedevere-app Bot mentioned this pull request Apr 26, 2026
gh-146455: Fix O(N²) in add_const() after constant folding moved to CFG #146456
Merged
@bedevere-app bedevere-app Bot added the awaiting review label Apr 26, 2026
@bedevere-app bedevere-app Bot mentioned this pull request Apr 26, 2026
Performance regression: O(N²) compile time for large constant tuples after const folding moved to CFG #146455
Closed
Eclips4
Eclips4 approved these changes Apr 26, 2026
View reviewed changes
@bedevere-app bedevere-app Bot added awaiting merge and removed awaiting review labels Apr 26, 2026
@Eclips4
Eclips4 merged commit 78c5e54 into python:3.14 Apr 26, 2026
54 checks passed

Uh oh!

There was an error while loading. Please reload this page.

@bedevere-app bedevere-app Bot removed the awaiting merge label Apr 26, 2026
@miss-islington
miss-islington deleted the backport-5d41632-3.14 branch April 26, 2026 15:45
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@Eclips4 Eclips4 Eclips4 approved these changes
@markshannon markshannon Awaiting requested review from markshannon markshannon is a code owner
@iritkatriel iritkatriel Awaiting requested review from iritkatriel iritkatriel is a code owner

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

3 participants

@miss-islington @Eclips4 @zSirius
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.