Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

BUILD_SET followed by COMPARE_OP (in) can be optimized if all items are consts #50939

Closed
alex opened this issue Aug 12, 2009 · 14 comments
Closed
Labels
interpreter-core Interpreter core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@alex
Copy link
Member

alex commented Aug 12, 2009

BPO 6690
Nosy @rhettinger, @pitrou, @alex, @davidmalcolm
Files
  • simple-optimization-of-BUILD_SET-COMPARE_OP(IN)-to-LOAD_CONST(tuple)_COMPARE_OP(IN)-py3k.patch
  • simple-optimization-of-BUILD_SET-COMPARE_OP(IN)-to-LOAD_CONST(frozenset)_COMPARE_OP(IN)-py3k.patch
  • simple-optimization-of-BUILD_SET-COMPARE_OP(IN)-to-LOAD_CONST(frozenset)_COMPARE_OP(IN)-with-tests-py3k.patch
  • optimize-BUILD_SET-v4.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 = None
    closed_at = <Date 2010-01-16.18:38:14.837>
    created_at = <Date 2009-08-12.21:32:06.485>
    labels = ['interpreter-core', 'performance']
    title = 'BUILD_SET followed by COMPARE_OP (in) can be optimized if all items are consts'
    updated_at = <Date 2010-01-16.18:38:14.835>
    user = 'https://github.com/alex'

    bugs.python.org fields:

    activity = <Date 2010-01-16.18:38:14.835>
    actor = 'pitrou'
    assignee = 'none'
    closed = True
    closed_date = <Date 2010-01-16.18:38:14.837>
    closer = 'pitrou'
    components = ['Interpreter Core']
    creation = <Date 2009-08-12.21:32:06.485>
    creator = 'alex'
    dependencies = []
    files = ['15840', '15841', '15845', '15900']
    hgrepos = []
    issue_num = 6690
    keywords = ['patch']
    message_count = 14.0
    messages = ['91506', '91614', '91626', '94324', '97640', '97650', '97651', '97653', '97654', '97671', '97856', '97858', '97859', '97894']
    nosy_count = 4.0
    nosy_names = ['rhettinger', 'pitrou', 'alex', 'dmalcolm']
    pr_nums = []
    priority = 'normal'
    resolution = 'fixed'
    stage = 'resolved'
    status = 'closed'
    superseder = None
    type = 'performance'
    url = 'https://bugs.python.org/issue6690'
    versions = ['Python 2.7', 'Python 3.2']

    @alex
    Copy link
    Member Author

    alex commented Aug 12, 2009

    Just like we turn BUILD_LIST; COMPARE_OP (in) into a LOAD_CONST if all
    the members are consts, we can do the same for BUILD_SET, instead
    turning it into a LOAD_CONST of a frozenset. The following is the
    bytecode that is current produced for each datastructure.

    >>> dis.dis(lambda o: o in (1,2,3))
      1           0 LOAD_FAST                0 (o) 
                  3 LOAD_CONST               3 ((1, 2, 3)) 
                  6 COMPARE_OP               6 (in) 
                  9 RETURN_VALUE         
    >>> dis.dis(lambda o: o in [1,2,3])
      1           0 LOAD_FAST                0 (o) 
                  3 LOAD_CONST               3 ((1, 2, 3)) 
                  6 COMPARE_OP               6 (in) 
                  9 RETURN_VALUE         
    >>> dis.dis(lambda o: o in {1,2,3})
      1           0 LOAD_FAST                0 (o) 
                  3 LOAD_CONST               0 (1) 
                  6 LOAD_CONST               1 (2) 
                  9 LOAD_CONST               2 (3) 
                 12 BUILD_SET                3 
                 15 COMPARE_OP               6 (in) 
                 18 RETURN_VALUE

    @alex alex added the interpreter-core Interpreter core (Objects, Python, Grammar, and Parser dirs) label Aug 12, 2009
    @pitrou
    Copy link
    Member

    pitrou commented Aug 15, 2009

    It's certainly possible to do so, do you have a patch?

    @pitrou pitrou added the performance Performance or resource usage label Aug 15, 2009
    @alex
    Copy link
    Member Author

    alex commented Aug 16, 2009

    Antoine, I hope to have some time to write a patch for this in the
    coming week.

    @rhettinger rhettinger self-assigned this Aug 16, 2009
    @rhettinger
    Copy link
    Contributor

    rhettinger commented Oct 21, 2009

    +1

    @rhettinger rhettinger removed their assignment Oct 21, 2009
    @alex
    Copy link
    Member Author

    alex commented Jan 12, 2010

    Ugh, I haven't had the time to work on this, just wanted to note that this now applies to 2.7 as well since set literals were backported.

    @davidmalcolm
    Copy link
    Member

    davidmalcolm commented Jan 12, 2010

    Attaching a probably over-simplistic attempt at this patch, against the py3k branch.

    This patch attempts to extend the replacement of
    LOAD_CONST, ...., LOAD_CONST, BUILD_LIST, COMPARE_OP(in)
    with
    LOAD_CONST(tuple), COMPAREOP(in)

    so that it also replaces:
    LOAD_CONST, ...., LOAD_CONST, BUILD_SET, COMPARE_OP(in)
    with
    LOAD_CONST(tuple), COMPAREOP(in)

    i.e. using a tuple, not a frozenset (on the grounds that the "in" conditions should at least still work); caveat: I'm relatively new to the innards of this code.

    With this patch:
    >>> dis.dis(lambda o: o in {1,2,3})
      1           0 LOAD_FAST                0 (o) 
                  3 LOAD_CONST               3 ((1, 2, 3)) 
                  6 COMPARE_OP               6 (in) 
                  9 RETURN_VALUE         
    but:
    >>> dis.dis(lambda o: o in {1,2,3,3,2,1})
      1           0 LOAD_FAST                0 (o) 
                  3 LOAD_CONST               3 ((1, 2, 3, 3, 2, 1)) 
                  6 COMPARE_OP               6 (in) 
                  9 RETURN_VALUE         

    Is it worth me working on a rewrite to use a frozenset.

    Hope this is helpful
    Dave

    @alex
    Copy link
    Member Author

    alex commented Jan 12, 2010

    David, I think it should use frozen set since doing it this way could actually increase the time the operation takes (which is certainly not our goal!). Plus marshall.c already handles frozenset, so I don't think it's that much more work.

    @davidmalcolm
    Copy link
    Member

    davidmalcolm commented Jan 12, 2010

    Alex: good point - thanks!

    Attaching updated version of the patch (again, against py3k, likewise, I'm somewhat new to this code, so I may have missed things)

    With this:
    >>> dis.dis(lambda o: o in {1,2,3})
      1           0 LOAD_FAST                0 (o) 
                  3 LOAD_CONST               3 (frozenset({1, 2, 3})) 
                  6 COMPARE_OP               6 (in) 
                  9 RETURN_VALUE         
    >>> dis.dis(lambda o: o in {1,2,3,3,2,1})
      1           0 LOAD_FAST                0 (o) 
                  3 LOAD_CONST               3 (frozenset({1, 2, 3})) 
                  6 COMPARE_OP               6 (in) 
                  9 RETURN_VALUE         
    and the tuple/list cases are again as in the original comment.

    I'm in the process of running the full test suite.

    @alex
    Copy link
    Member Author

    alex commented Jan 12, 2010

    The patch looks more or less right to me (but I'm far from an expert). It needs tests in the peephole tests though.

    @davidmalcolm
    Copy link
    Member

    davidmalcolm commented Jan 12, 2010

    Thanks for looking at the patch.

    Attached is an updated version (again against py3k) which adds tests to Lib/test/test_peepholer.py, for both the new folding away of BUILD_SET, and for the pre-existing folding of BUILD_LIST (which didn't seem to have tests).

    Hopefully these look good. One possible worry I had with them is with the string comparison against repr(various frozensets) for the disassembly of the bytecode: the new tests thus assume that the ordering of the repr of a frozenset is constant. Is this a reasonable assumption, or should the choice of test items be changed to ones with more robust ordering in their repr() string?

    @pitrou
    Copy link
    Member

    pitrou commented Jan 15, 2010

    No, you can't rely on the repr of a frozenset with multiple items. You should find another way of testing (if you are brave you could match the "frozenset(...)" with a regex and eval() it).

    Some comments on the patch:

    • there's a line or two in peephole.c which seems to use spaces for indentation; please always use tabs (for this file anyway)
    • instead of self.assertTrue(X in Y), you can use self.assertIn(X, Y) (and self.assertNotIn(X, Y) for the negation)

    @davidmalcolm
    Copy link
    Member

    davidmalcolm commented Jan 16, 2010

    Thanks for the suggestions.

    Attached is a revised version of the patch.

    • I believe I've fixed all tab/space issues in this version of the patch, though I may have missed some (http://www.python.org/dev/tools/ doesn't recommend an automated way of checking this).
    • I've rewritten the selftests as you suggested, using re and eval
    • I've rewritten the new selftests to use assertIn, assertNotIn

    The existing tests don't use assertIn/assertNotIn; I'm working on a patch for that, but I'll file that as a separate bug.

    @rhettinger
    Copy link
    Contributor

    rhettinger commented Jan 16, 2010

    Nice looking patch.

    @pitrou
    Copy link
    Member

    pitrou commented Jan 16, 2010

    The patch was committed in r77543 (py3k), thank you!

    @pitrou pitrou closed this as completed Jan 16, 2010
    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    interpreter-core Interpreter core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage
    Projects
    None yet
    Development

    No branches or pull requests

    4 participants