Skip to content

Negative tuple elements produce inefficient code. #55453

Closed
Closed
Negative tuple elements produce inefficient code.#55453
Assignees
mdickinson
Labels
performancePerformance or resource usage

Description

@jdharper
jdharper
mannequin
opened on Feb 18, 2011
BPO 11244
Nosy @rhettinger, @mdickinson, @pitrou, @bitdancer, @eltoder
Files
  • test_peepholer.patch: Patch to test_peephole that verifies expressions containing negative constants are optimized.
  • constfold.patch
  • constfold2.patch
  • fold-0.patch
  • fold-0.2.patch
    		•

    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/mdickinson'
closed_at = <Date 2011-03-23.18:20:49.447>
created_at = <Date 2011-02-18.17:41:04.894>
labels = ['performance']
title = 'Negative tuple elements produce inefficient code.'
updated_at = <Date 2011-03-23.18:20:49.446>
user = 'https://bugs.python.org/jdharper'

    bugs.python.org fields:

    activity = <Date 2011-03-23.18:20:49.446>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2011-03-23.18:20:49.447>
closer = 'mark.dickinson'
components = []
creation = <Date 2011-02-18.17:41:04.894>
creator = 'jdharper'
dependencies = []
files = ['20787', '20790', '20897', '21073', '21083']
hgrepos = []
issue_num = 11244
keywords = ['patch']
message_count = 28.0
messages = ['128795', '128801', '128805', '128806', '128809', '128810', '128812', '128817', '128825', '128841', '128844', '128876', '129429', '129430', '130529', '130550', '130576', '130579', '130582', '130583', '130640', '130641', '130642', '130665', '131068', '131069', '131901', '131902']
nosy_count = 9.0
nosy_names = ['rhettinger', 'mark.dickinson', 'pitrou', 'nadeem.vawda', 'Arfrever', 'r.david.murray', 'jdharper', 'python-dev', 'eltoder']
pr_nums = []
priority = 'high'
resolution = None
stage = 'commit review'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue11244'
versions = ['Python 3.1', 'Python 3.2', 'Python 3.3']

    Activity

    1. jdharper commented on Feb 18, 2011

      @jdharper
      jdharpermannequin
      on Feb 18, 2011
      MannequinAuthor

      In Python 3.2, a tuple like (1,-2,3) will not be optimized into a constants at compile time. The tuple is built at run-time. Earlier versions of Python optimized these tuples at compile time.

      Here's an example program.

      # test.py
from dis import dis

def x(): return (1,2,3)
def y(): return (1,-2,3)

      print ("dis x:")
      dis(x)
      print()

      print("dis y:")
dis(y)

      The compiler in 3.2rc3 produces code for function y() that builds the tuple at run-time while the tuple in x() is optimized at compile time.

      C:\tmp>c:\python32\python --version
      Python 3.2rc3

      C:\tmp>c:\python32\python test.py
      dis x:
      3 0 LOAD_CONST 4 ((1, 2, 3))
      3 RETURN_VALUE

      dis y:
      4 0 LOAD_CONST 1 (1)
      3 LOAD_CONST 4 (-2)
      6 LOAD_CONST 3 (3)
      9 BUILD_TUPLE 3
      12 RETURN_VALUE

      However, under 3.1.3, the tuples in both functions are optimized at compile time.

      C:\tmp>c:\python31\python test.py
      dis x:
      3 0 LOAD_CONST 4 ((1, 2, 3))
      3 RETURN_VALUE

      dis y:
      4 0 LOAD_CONST 4 ((1, -2, 3))
      3 RETURN_VALUE

      Although the compiled code produced 3.2rc3 is correct, it is much slower than the code generated by 3.1.3.

    2. jdharper
      added
      performancePerformance or resource usage
      on Feb 18, 2011

    3. jdharper commented on Feb 18, 2011

      @jdharper
      jdharpermannequin
      on Feb 18, 2011
      MannequinAuthor

      I have also determined that negative elements interfere with the frozenset optimization described in bpo-6690. http://bugs.python.org/issue6690.

      Here's an example program:

      # test.py
from dis import dis

def x(var): return var in {1,2,3} # Note curly braces.  These are sets.
def y(var): return var in {1,-2,3}

      print ("dis x:")
      dis(x)
      print()

      print("dis y:")
dis(y)

      Running this produces:

      C:\tmp>c:\Python32\python.exe test.py
      dis x:
      3 0 LOAD_FAST 0 (var)
      3 LOAD_CONST 4 (frozenset({1, 2, 3}))
      6 COMPARE_OP 6 (in)
      9 RETURN_VALUE

      dis y:
      4 0 LOAD_FAST 0 (var)
      3 LOAD_CONST 1 (1)
      6 LOAD_CONST 4 (-2)
      9 LOAD_CONST 3 (3)
      12 BUILD_SET 3
      15 COMPARE_OP 6 (in)
      18 RETURN_VALUE

    4. bitdancer commented on Feb 18, 2011

      @bitdancer
      bitdancer
      on Feb 18, 2011
      Member

      I wonder if this has anything to do with bpo-9011?

    5. pitrou commented on Feb 18, 2011

      @pitrou
      pitrou
      on Feb 18, 2011
      Member

      The culprit is r82043: "Issue bpo-9011: Remove buggy and unnecessary ST->AST compilation code".

    6. pitrou
      assigned
      mdickinson
      on Feb 18, 2011

    7. pitrou commented on Feb 18, 2011

      @pitrou
      pitrou
      on Feb 18, 2011
      Member

      The problem is that the "UNARY_NEGATIVE + LOAD_CONST" optimization, which occurs first in bytecode order, inserts a NOP and prevents the tuple optimization to work.

    8. jdharper commented on Feb 18, 2011

      @jdharper
      jdharpermannequin
      on Feb 18, 2011
      MannequinAuthor

      I think r82043 may also explain why 3.1.3 can fold the expression 2 * -3 into -6 while 3.2rc3 cannot.

      # test.py
from dis import dis

def y(): 2 * -3

print("dis y:")
dis(y)

      C:\tmp>c:\Python32\python.exe --version
      Python 3.2rc3

      C:\tmp>c:\Python32\python.exe test.py
      dis y:
      3 0 LOAD_CONST 1 (2)
      3 LOAD_CONST 3 (-3)
      6 BINARY_MULTIPLY
      7 POP_TOP
      8 LOAD_CONST 0 (None)
      11 RETURN_VALUE

      C:\tmp>c:\Python31\python.exe --version
      Python 3.1.3

      C:\tmp>c:\Python31\python.exe test.py
      dis y:
      3 0 LOAD_CONST 3 (-6)
      3 POP_TOP
      4 LOAD_CONST 0 (None)
      7 RETURN_VALUE

    9. pitrou commented on Feb 18, 2011

      @pitrou
      pitrou
      on Feb 18, 2011
      Member

      Ouch. Obviously test_peephole doesn't have enough tests...

    10. jdharper commented on Feb 18, 2011

      @jdharper
      jdharpermannequin
      on Feb 18, 2011
      MannequinAuthor

      Here's a patch against the version of test_peepholer.py in 3.2rc3. It verifies that expressions like the following are optimized:

      3*-4
      (1,-2,3)
      a in {1,-2,3)

    11. pitrou commented on Feb 18, 2011

      @pitrou
      pitrou
      on Feb 18, 2011
      Member

      Here is a patch that enables advanced (recursive) constant folding.
      Example:

      python -c "import dis; f=lambda x: x in {(3*-5)+(-1-6),(1,-2,3)*2,None};dis.dis(f)"

      With 3.1:
      1 0 LOAD_FAST 0 (x)
      3 LOAD_CONST 7 (-15)
      6 LOAD_CONST 8 (-7)
      9 BINARY_ADD
      10 LOAD_CONST 10 ((1, -2, 3, 1, -2, 3))
      13 LOAD_CONST 11 (None)
      16 BUILD_SET 3
      19 COMPARE_OP 6 (in)
      22 RETURN_VALUE

      With 3.2+patch:
      1 0 LOAD_FAST 0 (x)
      3 LOAD_CONST 14 (frozenset({None, -22, (1, -2, 3, 1, -2, 3)}))
      6 COMPARE_OP 6 (in)
      9 RETURN_VALUE

    12. mdickinson commented on Feb 19, 2011

      @mdickinson
      mdickinson
      on Feb 19, 2011
      Member

      Unassigning. I don't think that r82043 is the *real* culprit here; that bugfix just happened to expose a deficiency in the peepholer; one that's already present in other situations:

      >>> dis.dis(lambda: 2*(3*4))
  1           0 LOAD_CONST               1 (2)
              3 LOAD_CONST               4 (12)
              6 BINARY_MULTIPLY     
              7 RETURN_VALUE        
>>> dis.dis(lambda: (2*3)*4)
  1           0 LOAD_CONST               5 (24)
              3 RETURN_VALUE

      Antoine, does your patch take care of this case too?

    13. mdickinson
      removed their assignment
      on Feb 19, 2011

    14. pitrou commented on Feb 19, 2011

      @pitrou
      pitrou
      on Feb 19, 2011
      Member
      Le samedi 19 février 2011 à 10:45 +0000, Mark Dickinson a écrit :
> Mark Dickinson <dickinsm@gmail.com> added the comment:
> 
> Unassigning.  I don't think that r82043 is the *real* culprit here;  that bugfix just happened to expose a deficiency in the peepholer;  one that's already present in other situations:
> 
> >>> dis.dis(lambda: 2*(3*4))
>   1           0 LOAD_CONST               1 (2)
>               3 LOAD_CONST               4 (12)
>               6 BINARY_MULTIPLY     
>               7 RETURN_VALUE        
> >>> dis.dis(lambda: (2*3)*4)
>   1           0 LOAD_CONST               5 (24)
>               3 RETURN_VALUE        
> 
> Antoine, does your patch take care of this case too?

      It should. Can you test?

    15. mdickinson commented on Feb 19, 2011

      @mdickinson
      mdickinson
      on Feb 19, 2011
      Member

      It should. Can you test?

      Ah, you're asking me to actually do some (minimal) work instead of just complaining?

      Yep, the patch tests fine over here (OS X 10.6), and fixes the 2*(3*4) case.

    16. 8 remaining items

    17. pitrou
      assigned
      mdickinson
      on Mar 11, 2011

    18. rhettinger commented on Mar 11, 2011

      @rhettinger
      rhettinger
      on Mar 11, 2011
      Contributor

      Eugene's patch looks like a correct fix to the regression. I'll review further in the next couple of days.

      Antoine, we need to further discuss your checkin to the peephole optimizer. I believe it was inappropriate.

    19. rhettinger
      assigned
      rhettinger
      and unassigned
      mdickinson
      on Mar 11, 2011

    20. pitrou commented on Mar 11, 2011

      @pitrou
      pitrou
      on Mar 11, 2011
      Member

      Eugene's patch looks like a correct fix to the regression.

      No, it's orthogonal.

    21. eltoder commented on Mar 11, 2011

      @eltoder
      eltodermannequin
      on Mar 11, 2011
      Mannequin

      Yes, my patch doesn't fix the regression, only a special case of -0.

    22. mdickinson commented on Mar 12, 2011

      @mdickinson
      mdickinson
      on Mar 12, 2011
      Member

      Eugene's new patch looks good to me; +1 on applying it.

      Raymond, do you happen to remember why it was necessary to add the zero-check in the first place?

    23. eltoder commented on Mar 15, 2011

      @eltoder
      eltodermannequin
      on Mar 15, 2011
      Mannequin

      Is anyone reviewing my patch? It's just 1 line long. Should it be moved to another issue? Though, technically, it's needed to address the regression in question: Python 3.1 folds -0, the current code still does not.

    24. pitrou commented on Mar 15, 2011

      @pitrou
      pitrou
      on Mar 15, 2011
      Member

      Eugene, according to Mark your patch is fine. It just needs someone to commit it. I would personally prefer to let Mark handle it, since he's our specialist in negative zeroes (and other numerical subtleties) ;)

    25. rhettinger
      assigned
      mdickinson
      and unassigned
      rhettinger
      on Mar 22, 2011

    26. python-dev commented on Mar 23, 2011

      @python-dev
      python-devmannequin
      on Mar 23, 2011
      Mannequin

      New changeset ead9c1b9f547 by Mark Dickinson in branch 'default':
      Issue bpo-11244: Remove outdated peepholer check that was preventing the peepholer from folding -0 and -0.0. Thanks Eugene Toder for the patch.
      http://hg.python.org/cpython/rev/ead9c1b9f547

    27. mdickinson commented on Mar 23, 2011

      @mdickinson
      mdickinson
      on Mar 23, 2011
      Member

      Fixed in 'default' branch. Note that the regression still exists in 3.2; I'm not sure that it's worth backporting the two fixes.

    28. mdickinson
      closed this as completedon Mar 23, 2011
    29. ezio-melotti
      transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    Labels

    performancePerformance or resource usage

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions