[Python-Dev] Prospective Peephole Transformation

[Raymond Hettinger]

> Wouldn't it help a lot more if the compiler would detect that
> (1,2,3) is immutable and convert it into a constant at
> compile time ?!

Yes.  We've already gotten it to that point:

Python 2.5a0 (#46, Feb 15 2005, 19:11:35) [MSC v.1200 32 bit (Intel)] on
win32
>>> import dis
>>> dis.dis(compile('x in ("xml", "html", "css")', '', 'eval'))
  0           0 LOAD_NAME                0 (x)
              3 LOAD_CONST               3 (('xml', 'html', 'css'))
              6 COMPARE_OP               6 (in)
              9 RETURN_VALUE  

The question is whether to go a step further to replace the linear
search with a single hashed lookup:

  0           0 LOAD_NAME                0 (x)
              3 LOAD_CONST               3 (searchset(['xml', 'html',
'css']))
              6 COMPARE_OP               6 (in)
              9 RETURN_VALUE  

This situation seems to arise often in source code.  You can see the
cases in the standard library with:   grep 'in ("' *.py

The transformation is easy to make at compile time.  The part holding me
back is the introduction of searchset as a frozenset subtype and
teaching marshal how to put it a pyc file.

FWIW, some sample timings are included below (using frozenset to
approximate what searchset would do).  The summary is that the tuple
search takes .49usec plus .12usec for each item searched until a match
is found.  The frozenset lookup takes a constant .53 usec.



Raymond



------------------------------------------------------------------------

C:\py25>python -m timeit -r9 -s "s=('xml', 'css', 'html')" -s "x='xml'"
"x in s"
1000000 loops, best of 9: 0.49 usec per loop

C:\py25>python -m timeit -r9 -s "s=('xml', 'css', 'html')" -s "x='css'"
"x in s"
1000000 loops, best of 9: 0.621 usec per loop

C:\py25>python -m timeit -r9 -s "s=('xml', 'css', 'html')" -s "x='html'"
"x in s"
1000000 loops, best of 9: 0.747 usec per loop

C:\py25>python -m timeit -r9 -s "s=('xml', 'css', 'html')" -s "x='pdf'"
"x in s"
100000 loops, best of 9: 0.851 usec per loop

C:\py25>python -m timeit -r9 -s "s=frozenset(['xml', 'css', 'html'])" -s
"x='xml'" "x in s"
1000000 loops, best of 9: 0.529 usec per loop

C:\py25>python -m timeit -r9 -s "s=frozenset(['xml', 'css', 'html'])" -s
"x='css'" "x in s"
1000000 loops, best of 9: 0.522 usec per loop

C:\py25>python -m timeit -r9 -s "s=frozenset(['xml', 'css', 'html'])" -s
"x='html'" "x in s"
1000000 loops, best of 9: 0.53 usec per loop

C:\py25>python -m timeit -r9 -s "s=frozenset(['xml', 'css', 'html'])" -s
"x='pdf'" "x in s"
1000000 loops, best of 9: 0.523 usec per loop