[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

Okay, this issue is fixed in 3.6.

--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
priority: deferred blocker -> normal

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Antoine Pitrou]

Antoine Pitrou  added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Benjamin Peterson]

Benjamin Peterson  added the comment:

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 :
> 
> 
> --
> assignee:  -> benjamin.peterson
> 
> ___
> Python tracker 
> 
> ___

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Gregory P. Smith]

Change by Gregory P. Smith :


--
assignee:  -> benjamin.peterson

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
nosy: +benjamin.peterson
priority: normal -> deferred blocker
versions: +Python 2.7 -Python 3.7

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

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?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
pull_requests: +4788

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:


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


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:


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


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
pull_requests: +4755

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
pull_requests: +4749

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Antoine Pitrou]

Antoine Pitrou added the comment:

Yet another proof that performance improvements should *not* be committed to 
bugfix branches.

Please, can someone learn a lesson?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Mark Dickinson]

Mark Dickinson added the comment:

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.

--
nosy: +mark.dickinson

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--
keywords: +patch
stage:  -> patch review
type:  -> behavior
versions:  -Python 2.7, Python 3.3, Python 3.4, Python 3.5, Python 3.6
Added file: http://bugs.python.org/file46887/safe-const-folding.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Andrew Dalke]

Andrew Dalke added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Antoine Pitrou]

Antoine Pitrou added the comment:

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Jim Fasarakis-Hilliard]

Changes by Jim Fasarakis-Hilliard :


--
nosy: +Jim Fasarakis-Hilliard

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
nosy: +pitrou

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

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.

--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue30416] constant folding opens compiler to quadratic time hashing

[Andrew Dalke]

New submission from Andrew Dalke:

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.

--
components: Interpreter Core
messages: 294050
nosy: dalke
priority: normal
severity: normal
status: open
title: constant folding opens compiler to quadratic time hashing
versions: Python 2.7, Python 3.3, Python 3.4, Python 3.5, Python 3.6, Python 3.7

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com