GeezerVisonThe World Wide Web, restored to 800 pixels of glory. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Home|About|Gaming cabinet|Archives|How it works|Starter sites | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
GeezerVison is showing github.com — gh-146455: Fix O(N²) in add_const() after constant folding moved to CFG by zSirius · Pull Request #146456 · python/cpython Conversation
|
| Scenario | 3.11 | 3.14 (before) | 3.14 (after fix) |
|---|---|---|---|
Nested tuples ((f, f), ...) |
1.24s | 10.38s | 1.48s |
Unary neg (-1, -2, ..., -N) |
0.22s | 6.86s | 1.12s |
Binary add (0+1, 0+2, ..., 0+N) |
0.27s | 2.59s | 1.40s |
All existing tests pass: test_compile, test_peepholer, test_ast, test_dis.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
All reactions
…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
|
Most changes to Python require a NEWS entry. Add one using the blurb_it web app or the blurb command-line tool. If this change has little impact on Python users, wait for a maintainer to apply the |
All reactions
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
| /* O(1) lookup via pointer-keyed hashtable (replaces linear search). */ | ||
| _Py_hashtable_entry_t *entry = _Py_hashtable_get_entry(consts_index, (void *)newconst); | ||
| if (entry != NULL) { | ||
| /* Already exists */ | ||
| Py_DECREF(newconst); | ||
| return (int)(uintptr_t)entry->value; | ||
| } | ||
| if (index == PyList_GET_SIZE(consts)) { | ||
| if ((size_t)index >= (size_t)INT_MAX - 1) { | ||
| PyErr_SetString(PyExc_OverflowError, "too many constants"); | ||
| Py_DECREF(newconst); | ||
| return -1; | ||
| } | ||
| if (PyList_Append(consts, newconst)) { | ||
| Py_DECREF(newconst); | ||
| return -1; | ||
| } | ||
|
|
||
| /* Not found – append to consts list */ | ||
| Py_ssize_t index = PyList_GET_SIZE(consts); | ||
| if ((size_t)index >= (size_t)INT_MAX - 1) { | ||
| PyErr_SetString(PyExc_OverflowError, "too many constants"); | ||
| Py_DECREF(newconst); | ||
| return -1; | ||
| } | ||
| if (PyList_Append(consts, newconst)) { | ||
| Py_DECREF(newconst); | ||
| return -1; | ||
| } | ||
|
|
||
| /* Update index (must be after successful append) */ | ||
| if (_Py_hashtable_set(consts_index, (void *)newconst, (void *)(uintptr_t)index) < 0) { | ||
| /* OOM – rollback append for consistency */ | ||
| PyList_SetSlice(consts, index, index + 1, NULL); | ||
| Py_DECREF(newconst); | ||
| PyErr_NoMemory(); | ||
| return -1; | ||
| } | ||
|
|
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Can you please remove those comments? They're unnecessary since the code is pretty straightforward
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
All reactions
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I have removed all comments.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
All reactions
| /* Auxiliary pointer→index hashtable for O(1) lookup in add_const. */ | ||
| _Py_hashtable_t *consts_index = _Py_hashtable_new( | ||
| _Py_hashtable_hash_ptr, _Py_hashtable_compare_direct); | ||
| if (consts_index == NULL) { | ||
| PyErr_NoMemory(); | ||
| return ERROR; | ||
| } | ||
|
|
||
| /* Seed the index with pre-existing constants. */ | ||
| for (Py_ssize_t i = 0; i < PyList_GET_SIZE(consts); i++) { | ||
| PyObject *item = PyList_GET_ITEM(consts, i); | ||
| if (_Py_hashtable_get_entry(consts_index, (void *)item) != NULL) { | ||
| continue; /* duplicate pointer; keep first occurrence */ | ||
| } | ||
| if (_Py_hashtable_set(consts_index, (void *)item, | ||
| (void *)(uintptr_t)i) < 0) { | ||
| _Py_hashtable_destroy(consts_index); | ||
| PyErr_NoMemory(); | ||
| return ERROR; | ||
| } | ||
| } | ||
|
|
||
| int ret = optimize_cfg(g, consts, const_cache, consts_index, firstlineno); | ||
|
|
||
| /* consts_index is invalid after this (consts list may be modified). */ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
And those comments also.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
All reactions
|
FWIW, I've run refleak tests and everything seems to be fine. |
All reactions
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
|
The results from the issue are confirmed. After this PR (I took the example from the issue), Macbook Pro M3 Pro: |
All reactions
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
|
Thank you @zSirius! |
All reactions
-
😄 1 reaction
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
|
GH-149011 is a backport of this pull request to the 3.14 branch. |
All reactions
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
| PyErr_NoMemory(); | ||
| return ERROR; | ||
| } | ||
| } |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I wonder if we can make const_cache be a data structure that maps bi-directionally, so that we don't need to do this here.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
All reactions
…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 <[email protected]>
Reviewers
Uh oh!
There was an error while loading. Please reload this page.
Assignees
No one assignedLabels
Projects
Milestone
No milestoneDevelopment
Successfully merging this pull request may close these issues.
Uh oh!
There was an error while loading. Please reload this page.
3 participants
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.