Repository navigation
constant folding opens compiler to quadratic time hashing #74601
Description
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
assignee = 'https://github.com/benjaminp'
closed_at = <Date 2018-07-08.09:29:23.123>
created_at = <Date 2017-05-20.21:01:37.163>
labels = ['interpreter-core', 'type-bug']
title = 'constant folding opens compiler to quadratic time hashing'
updated_at = <Date 2018-07-08.09:29:31.925>
user = 'https://bugs.python.org/dalke'bugs.python.org fields:
activity = <Date 2018-07-08.09:29:31.925>
actor = 'serhiy.storchaka'
assignee = 'benjamin.peterson'
closed = True
closed_date = <Date 2018-07-08.09:29:23.123>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2017-05-20.21:01:37.163>
creator = 'dalke'
dependencies = []
files = ['46887']
hgrepos = []
issue_num = 30416
keywords = ['patch']
message_count = 15.0
messages = ['294050', '294051', '294107', '294120', '294182', '294246', '294247', '308386', '308388', '308558', '308622', '314848', '318511', '318512', '321269']
nosy_count = 6.0
nosy_names = ['dalke', 'mark.dickinson', 'pitrou', 'benjamin.peterson', 'serhiy.storchaka', 'Jim Fasarakis-Hilliard']
pr_nums = ['4860', '4865', '4896']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue30416'
versions = ['Python 2.7']
Activity
dalke commentedon May 20, 2017
Others have reported issues like bpo-21074 where the peephole compiler generates and discards large strings, and bpo-30293 where it generates multi-MB integers and stores them in the .pyc.
This is a different issue. The code:
takes over four minutes (257 seconds) to compile on my machine. The seemingly larger:
takes a small fraction of a second to compile, and is equally fast to run.
Neither code generates a large data structure. In fact, they only needs about 1K.
A sampling profiler of the first case, taken around 30 seconds into the run, shows that nearly all of the CPU time is spent in computing the hash of the highly-nested tuple20, which must visit a very large number of elements even though there are only a small number of unique elements. The call chain is:
Py_Main -> PyRun_SimpleFileExFlags -> PyAST_CompileObject -> compiler_body -> compiler_function -> compiler_make_closure -> compiler_add_o -> PyDict_GetItem and then into the tuple hash code.
It appears that the peephole optimizer converts the highly-nested tuple20 into a constant value. The compiler then creates the code object with its co_consts. Specifically, compiler_make_closure uses a dictionary to ensure that the elements in co_consts are unique, and mapped to the integer used by LOAD_CONST.
It takes about 115 seconds to compute hash(tuple20). I believe the hash is computed twice, once to check if the object is present, and the second to insert it. I suspect most of the other 26 seconds went to computing the intermediate constants in the tuple.
Based on the previous issues I highlighted in my first paragraph, I believe this report will be filed under "Doctor, doctor, it hurts when I do this"/"Then don't do it." I see no easy fix, and cannot think of how it would come about in real-world use.
I point it out because in reading the various issues related to the peephole optimizer there's a subset of people who propose a look-before-you-leap technical solution of avoiding an optimization where the estimated result is too large. While it does help, it does not avoid all of the negatives of the peephole optimizer, or any AST-based optimizer with similar capabilities. I suspect even most core developers aren't aware of this specific negative.
serhiy-storchaka commentedon May 20, 2017
Nice example.
The only fix I see is caching the hash in a tuple. This can even help in more cases, when tuples are used as dict keys. But this affect too much code, and can even break a code that mutates a tuple with refcount 1.
pitrou commentedon May 21, 2017
Caching a tuple's hash value is a nice idea but it would increase the memory consumption of all tuples, which would probably hurt much more in the average case... Unless of course we find a way to cache the hash value in a separate memory area that's reserved on demand.
dalke commentedon May 22, 2017
A complex solution is to stop constant folding when there are more than a few levels of tuples. I suspect there aren't that many cases where there are more than 5 levels of tuples and where constant creation can't simply be assigned and used as a module variable.
This solution would become even more complex should constant propagation be supported.
Another option is to check the value about to be added to co_consts. If it is a container, then check if it would require more than a few levels of hash calls. If so, then simply add it without ensuring uniqueness.
This could be implemented because the compiler could be told how to carry out that check for the handful of supported container types.
serhiy-storchaka commentedon May 22, 2017
Proposed patch makes const folding more safe by checking arguments before doing expensive calculation that can create large object (multiplication, power and left shift). It fixes examples in this issue, bpo-21074, bpo-30293. The limit for repetition is increase from 20 to 256. There are no limits for addition/concatenation and like, since it is hard to create really large objects with these operations.
mdickinson commentedon May 23, 2017
After testing on Python 2, I was surprised to discover that this issue was introduced to the 2.x series quite recently: 2.7.11 doesn't have the issue, while 2.7.13 does.
The culprit appears to be this commit: 67edf73, introduced as part of bpo-27942.
pitrou commentedon May 23, 2017
Yet another proof that performance improvements should *not* be committed to bugfix branches.
Please, can someone learn a lesson?
serhiy-storchaka commentedon Dec 15, 2017
New changeset 2e3f570 by Serhiy Storchaka in branch 'master':
bpo-30416: Protect the optimizer during constant folding. (bpo-4860)
2e3f570
serhiy-storchaka commentedon Dec 15, 2017
New changeset b580f4f by Serhiy Storchaka in branch '3.6':
[3.6] bpo-30416: Protect the optimizer during constant folding. (bpo-4865)
b580f4f
serhiy-storchaka commentedon Dec 18, 2017
PR 4896 fixes this issue in 2.7, but I'm not sure that I want to merge it. The code in 2.7 is more complex because of two integer types.
serhiy-storchaka commentedon Dec 19, 2017
What do you suggest to do with 2.7? Revert the changes that introduced the regression, merge the backported fix, or keep all as is?
benjaminp commentedon Apr 3, 2018
We should revert the breaking 2.7 changes.
On Sun, Mar 25, 2018, at 13:59, Gregory P. Smith wrote:
serhiy-storchaka commentedon Jun 2, 2018
Reverting bpo-27942 (67edf73) doesn't solve this issue in 2.7. The previous revision has this issue, as well as 2.7.12 and 2.7.11. Even 2.6.9 and 2.5.6 have this issue.
We have either merge PR 4896 or decide that this issue is "won't fix" in 2.7.
pitrou commentedon Jun 2, 2018
I vote for "won't fix". 2.7 has lived long enough with this issue, AFAIU. And it won't be triggered by regular code.
serhiy-storchaka commentedon Jul 8, 2018
Okay, this issue is fixed in 3.6.