classification
Title: constant folding opens compiler to quadratic time hashing
Type: behavior Stage: resolved
Components: Interpreter Core Versions: Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: benjamin.peterson Nosy List: Jim Fasarakis-Hilliard, benjamin.peterson, dalke, mark.dickinson, pitrou, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2017-05-20 21:01 by dalke, last changed 2018-07-08 09:29 by serhiy.storchaka. This issue is now closed.

Files
File name Uploaded Description Edit
safe-const-folding.diff serhiy.storchaka, 2017-05-22 20:42 review
Pull Requests
URL Status Linked Edit
PR 4860 merged serhiy.storchaka, 2017-12-14 10:17
PR 4865 merged serhiy.storchaka, 2017-12-14 13:49
PR 4896 closed serhiy.storchaka, 2017-12-15 21:23
Messages (15)
msg294050 - (view) Author: Andrew Dalke (dalke) * (Python committer) Date: 2017-05-20 21:01
Others have reported issues like #21074 where the peephole compiler generates and discards large strings, and #30293 where it generates multi-MB integers and stores them in the .pyc.

This is a different issue. The code:

  def tuple20():
    return ((((((((1,)*20,)*20,)*20,)*20,)*20,)*20,)*20,)*20

takes over four minutes (257 seconds) to compile on my machine. The seemingly larger:

  def tuple30():
    return ((((((((1,)*30,)*30,)*30,)*30,)*30,)*30,)*30,)*30

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.
msg294051 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-05-20 21:35
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.
msg294107 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2017-05-21 18:20
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.
msg294120 - (view) Author: Andrew Dalke (dalke) * (Python committer) Date: 2017-05-22 02:42
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.
msg294182 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-05-22 20:42
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, issue21074, issue30293. 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.
msg294246 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2017-05-23 12:09
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: https://github.com/python/cpython/commit/67edf73183b8bf0127456454747f596428cc28f6, introduced as part of issue 27942.
msg294247 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2017-05-23 12:42
Yet another proof that performance improvements should *not* be committed to bugfix branches.

Please, can someone learn a lesson?
msg308386 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-15 12:11
New changeset 2e3f5701858d1fc04caedefdd9a8ea43810270d2 by Serhiy Storchaka in branch 'master':
bpo-30416: Protect the optimizer during constant folding. (#4860)
https://github.com/python/cpython/commit/2e3f5701858d1fc04caedefdd9a8ea43810270d2
msg308388 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-15 12:12
New changeset b580f4f2bf49fd3b11f2a046911993560c02492a by Serhiy Storchaka in branch '3.6':
[3.6] bpo-30416: Protect the optimizer during constant folding. (#4865)
https://github.com/python/cpython/commit/b580f4f2bf49fd3b11f2a046911993560c02492a
msg308558 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-18 13:39
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.
msg308622 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-12-19 09:06
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?
msg314848 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2018-04-03 02:13
We should revert the breaking 2.7 changes.

On Sun, Mar 25, 2018, at 13:59, Gregory P. Smith wrote:
> 
> Change by Gregory P. Smith <greg@krypto.org>:
> 
> 
> ----------
> assignee:  -> benjamin.peterson
> 
> _______________________________________
> Python tracker <report@bugs.python.org>
> <https://bugs.python.org/issue30416>
> _______________________________________
msg318511 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-06-02 20:01
Reverting issue27942 (67edf73183b8bf0127456454747f596428cc28f6) 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.
msg318512 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2018-06-02 20:04
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.
msg321269 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-07-08 09:29
Okay, this issue is fixed in 3.6.
History
Date User Action Args
2019-03-03 14:33:28serhiy.storchakalinkissue21074 superseder
2018-07-08 09:29:31serhiy.storchakasetpriority: deferred blocker -> normal
2018-07-08 09:29:23serhiy.storchakasetstatus: open -> closed
resolution: fixed
messages: + msg321269

stage: patch review -> resolved
2018-06-02 20:04:02pitrousetmessages: + msg318512
2018-06-02 20:01:30serhiy.storchakasetmessages: + msg318511
2018-04-03 02:13:22benjamin.petersonsetmessages: + msg314848
2018-03-25 20:59:01gregory.p.smithsetassignee: benjamin.peterson
2018-03-22 14:43:48serhiy.storchakasetpriority: normal -> deferred blocker
nosy: + benjamin.peterson

versions: + Python 2.7, - Python 3.7
2017-12-19 09:06:27serhiy.storchakasetmessages: + msg308622
2017-12-18 13:39:18serhiy.storchakasetmessages: + msg308558
2017-12-15 21:23:00serhiy.storchakasetpull_requests: + pull_request4788
2017-12-15 12:12:17serhiy.storchakasetmessages: + msg308388
2017-12-15 12:11:46serhiy.storchakasetmessages: + msg308386
2017-12-14 13:49:28serhiy.storchakasetpull_requests: + pull_request4755
2017-12-14 10:17:01serhiy.storchakasetpull_requests: + pull_request4749
2017-05-23 12:42:52pitrousetmessages: + msg294247
2017-05-23 12:09:33mark.dickinsonsetnosy: + mark.dickinson
messages: + msg294246
2017-05-22 20:42:05serhiy.storchakasetfiles: + safe-const-folding.diff
versions: - Python 2.7, Python 3.3, Python 3.4, Python 3.5, Python 3.6
messages: + msg294182

keywords: + patch
type: behavior
stage: patch review
2017-05-22 02:42:45dalkesetmessages: + msg294120
2017-05-21 18:20:34pitrousetmessages: + msg294107
2017-05-21 13:35:37Jim Fasarakis-Hilliardsetnosy: + Jim Fasarakis-Hilliard
2017-05-21 06:33:42rhettingersetnosy: + pitrou
2017-05-20 21:35:23serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg294051
2017-05-20 21:01:37dalkecreate