Title: Performance regression: O(N²) compile time for large constant tuples after const folding moved to CFG · Issue #146455 · python/cpython · GitHub
Open Graph Title: Performance regression: O(N²) compile time for large constant tuples after const folding moved to CFG · Issue #146455 · python/cpython
X Title: Performance regression: O(N²) compile time for large constant tuples after const folding moved to CFG · Issue #146455 · python/cpython
Description: Bug report Bug description: After gh-126835 moved constant folding from AST to CFG (specifically gh-130769 for tuple folding and gh-129550 for unary/binary op folding), compiling files with large constant tuples suffers from an O(N²) slo...
Open Graph Description: Bug report Bug description: After gh-126835 moved constant folding from AST to CFG (specifically gh-130769 for tuple folding and gh-129550 for unary/binary op folding), compiling files with large c...
X Description: Bug report Bug description: After gh-126835 moved constant folding from AST to CFG (specifically gh-130769 for tuple folding and gh-129550 for unary/binary op folding), compiling files with large c...
Opengraph URL: https://github.com/python/cpython/issues/146455
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Performance regression: O(N²) compile time for large constant tuples after const folding moved to CFG","articleBody":"# Bug report\n\n### Bug description:\n\nAfter gh-126835 moved constant folding from AST to CFG (specifically gh-130769 for tuple folding and gh-129550 for unary/binary op folding), compiling files with large constant tuples suffers from an O(N²) slowdown.\n\nThe root cause is `add_const()` in `Python/flowgraph.c` — it does a linear scan over the `consts` list to find a constant's index by identity:\n\n```c\nfor (index = 0; index \u003c PyList_GET_SIZE(consts); index++) {\n if (PyList_GET_ITEM(consts, index) == newconst) {\n break;\n }\n}\n```\n\nBefore gh-126835, large constant tuples were folded in one shot at the AST stage, so `add_const` was rarely called with big `consts` lists. After gh-130769 moved tuple folding to CFG, `fold_tuple_of_constants()` calls `add_const()` once per inner tuple — N calls × O(N) scan = O(N²).\n\nThis also affects unary/binary op folding (`fold_const_unaryop`, `fold_const_binop`) moved to CFG in gh-129550:\n\n- `(-1, -2, ..., -N)` — each `UNARY_NEGATIVE` folded via `add_const`, **31.7x slower** than 3.11 at N=100K\n- `(0+1, 0+2, ..., 0+N)` — each `BINARY_OP` folded via `add_const`, **9.7x slower** at N=100K\n\n`perf` profiling shows `add_const` taking **83.76%** of CPU time at N=100K.\n\n**Performance impact (N=100K):**\n\n| Scenario | 3.11 | 3.14 (regression) | Slowdown |\n|---|---|---|---|\n| Nested tuples `((f, f), ...)` | 1.24s | 10.38s | **8.4x** |\n| Unary neg `(-1, -2, ..., -N)` | 0.22s | 6.86s | **31.7x** |\n| Binary add `(0+1, 0+2, ..., 0+N)` | 0.27s | 2.59s | **9.7x** |\n\n**Reproducer:**\n\n```python\nimport sys, time\n\nN = int(sys.argv[1]) if len(sys.argv) > 1 else 100000\n\nelements = \", \".join(f\"({i * 0.001:.6f}, {i * 0.002:.6f})\" for i in range(N))\nsource = f\"vertices = ({elements},)\"\n\nt0 = time.perf_counter()\ncode_obj = compile(source, \"\u003ctest>\", \"exec\")\nt1 = time.perf_counter()\nprint(f\"Compile time: {t1-t0:.4f}s\", flush=True)\n```\n\nDiscussion: https://discuss.python.org/t/o-n-compile-time-regression-for-large-constant-tuples-after-const-folding-moved-to-cfg/106609\n\n### CPython versions tested on:\n\n3.14, 3.15\n\n### Operating systems tested on:\n\nLinux\n\n\u003c!-- gh-linked-prs -->\n### Linked PRs\n* gh-146456\n* gh-149011\n\u003c!-- /gh-linked-prs -->\n","author":{"url":"https://github.com/zSirius","@type":"Person","name":"zSirius"},"datePublished":"2026-03-26T08:33:15Z","url":"https://github.com/python/cpython/issues/146455"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:f7c908a2-ac12-0235-46f1-7e22d923be3b |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | AA2E:7A60E:456F59B:58D8B92:6B023A96 |
| html-safe-nonce | 2c5203eea9284fff4405dd83b3acda9b07bd7a3fbba8b1ee76d5156a6fe19f77 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJBQTJFOjdBNjBFOjQ1NkY1OUI6NThEOEI5Mjo2QjAyM0E5NiIsInZpc2l0b3JfaWQiOiIyNDYwMTc1OTA5MTAyMTcyODIzIiwicmVnaW9uX2VkZ2UiOiJpYWQiLCJyZWdpb25fcmVuZGVyIjoiaWFkIn0= |
| visitor-hmac | 07d1fd8b78d69acb044a8404e0cea7db12997bf757c750a488feaef4c486f106 |
| hovercard-subject-tag | issue:4141784480 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/cpython/146455/issue_layout |
| twitter:image | https://opengraph.githubassets.com/ee5af0e9a50494f7e4928d6773ee8bc5c50cec1bcb115e18a33bcd4f5ef6b12c/python/cpython/issues/146455 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/ee5af0e9a50494f7e4928d6773ee8bc5c50cec1bcb115e18a33bcd4f5ef6b12c/python/cpython/issues/146455 |
| og:image:alt | Bug report Bug description: After gh-126835 moved constant folding from AST to CFG (specifically gh-130769 for tuple folding and gh-129550 for unary/binary op folding), compiling files with large c... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | zSirius |
| hostname | github.com |
| expected-hostname | github.com |
| None | 87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456 |
| turbo-cache-control | no-preview |
| go-import | github.com/python/cpython git https://github.com/python/cpython.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 81598961 |
| octolytics-dimension-repository_nwo | python/cpython |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 81598961 |
| octolytics-dimension-repository_network_root_nwo | python/cpython |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 423dbb54c5e7bfecc838eb387c1435eb3d0e760d |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width