classification
Title: BUILD_SET followed by COMPARE_OP (in) can be optimized if all items are consts
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.2, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: alex, dmalcolm, pitrou, rhettinger
Priority: normal Keywords: patch

Created on 2009-08-12 21:32 by alex, last changed 2010-01-16 18:38 by pitrou. This issue is now closed.

Files
File name Uploaded Description Edit
simple-optimization-of-BUILD_SET-COMPARE_OP(IN)-to-LOAD_CONST(tuple)_COMPARE_OP(IN)-py3k.patch dmalcolm, 2010-01-12 19:36
simple-optimization-of-BUILD_SET-COMPARE_OP(IN)-to-LOAD_CONST(frozenset)_COMPARE_OP(IN)-py3k.patch dmalcolm, 2010-01-12 19:57
simple-optimization-of-BUILD_SET-COMPARE_OP(IN)-to-LOAD_CONST(frozenset)_COMPARE_OP(IN)-with-tests-py3k.patch dmalcolm, 2010-01-12 22:59
optimize-BUILD_SET-v4.patch dmalcolm, 2010-01-16 00:13
Messages (14)
msg91506 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2009-08-12 21:32
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
msg91614 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-08-15 17:39
It's certainly possible to do so, do you have a patch?
msg91626 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2009-08-16 02:31
Antoine, I hope to have some time to write a patch for this in the
coming week.
msg94324 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-10-21 20:45
+1
msg97640 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2010-01-12 18:05
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.
msg97650 - (view) Author: Dave Malcolm (dmalcolm) (Python committer) Date: 2010-01-12 19:36
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
msg97651 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2010-01-12 19:39
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.
msg97653 - (view) Author: Dave Malcolm (dmalcolm) (Python committer) Date: 2010-01-12 19:57
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.
msg97654 - (view) Author: Alex Gaynor (alex) * (Python committer) Date: 2010-01-12 19:58
The patch looks more or less right to me (but I'm far from an expert).  It needs tests in the peephole tests though.
msg97671 - (view) Author: Dave Malcolm (dmalcolm) (Python committer) Date: 2010-01-12 22:59
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?
msg97856 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2010-01-15 22:41
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)
msg97858 - (view) Author: Dave Malcolm (dmalcolm) (Python committer) Date: 2010-01-16 00:13
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.
msg97859 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2010-01-16 01:44
Nice looking patch.
msg97894 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2010-01-16 18:38
The patch was committed in r77543 (py3k), thank you!
History
Date User Action Args
2010-01-16 18:38:14pitrousetstatus: open -> closed
resolution: fixed
messages: + msg97894

stage: patch review -> resolved
2010-01-16 17:54:39brian.curtinsetstage: needs patch -> patch review
2010-01-16 01:44:48rhettingersetmessages: + msg97859
2010-01-16 00:13:37dmalcolmsetfiles: + optimize-BUILD_SET-v4.patch

messages: + msg97858
2010-01-15 22:41:43pitrousetmessages: + msg97856
2010-01-12 22:59:44dmalcolmsetfiles: + simple-optimization-of-BUILD_SET-COMPARE_OP(IN)-to-LOAD_CONST(frozenset)_COMPARE_OP(IN)-with-tests-py3k.patch

messages: + msg97671
2010-01-12 19:58:53alexsetmessages: + msg97654
2010-01-12 19:57:18dmalcolmsetfiles: + simple-optimization-of-BUILD_SET-COMPARE_OP(IN)-to-LOAD_CONST(frozenset)_COMPARE_OP(IN)-py3k.patch

messages: + msg97653
2010-01-12 19:39:12alexsetmessages: + msg97651
2010-01-12 19:36:20dmalcolmsetfiles: + simple-optimization-of-BUILD_SET-COMPARE_OP(IN)-to-LOAD_CONST(tuple)_COMPARE_OP(IN)-py3k.patch

nosy: + dmalcolm
messages: + msg97650

keywords: + patch
2010-01-12 18:07:14pitrousetversions: + Python 2.7
2010-01-12 18:05:24alexsetmessages: + msg97640
2009-10-21 20:45:41rhettingersetassignee: rhettinger ->
messages: + msg94324
2009-08-16 05:04:11rhettingersetassignee: rhettinger
2009-08-16 02:31:34alexsetmessages: + msg91626
2009-08-15 17:39:37pitrousetpriority: normal

nosy: + rhettinger, pitrou
messages: + msg91614

type: performance
stage: needs patch
2009-08-12 21:32:06alexcreate