[Python-Dev] AST-level type inference optimizations

[David Turner]

I wrote a patch to Tom Lee's AST optimization branch, which I have
submitted at http://bugs.python.org/issue4264.  Here's a brief
explanation of what the patch does, followed by a little general
discussion of the future.

Python bytecode includes at least one operation which is not directly
accessible from Python code: LIST_APPEND, which pops a value and a list
off the stack and appends the value to the list. This is used in
generating code for list comprehensions:

[x for x in somelist]

generates the following code for the body of the loop:

...
LOAD_FAST 1#a local is generated to hold the new list
LOAD_FAST 2 #the iteration variable, x
LIST_APPEND
...

Whereas if you were to try to write the comprehension directly, you
would get:

LOAD_FAST 1
LOAD_ATTR 0 #an index into the constant table: “append”
LOAD_FAST 2
CALL_FUNCTION 1 #remove x and the append function from the top of the
stack and push the result of the call
POP_TOP

This is much slower. In part, it’s the cost of doing the attribute
lookup each time, which is why it’s common to see code like
a = []
ap = a.append
for x in ...: 
   ap(x + ...) 
return a 

But the function call is naturally slower than the simpler LIST_APPEND
operation. My patch tries to determine statically if a local is all
circumstances holds a list, and if so, generates LIST_APPEND whenever
user code would call local.append.   It also works with the manual
optimization mentioned above -- it tracks whether variables hold a
method call to append on a list.  It’s not perfect — in particular, I
could track local types on a more fine-grained level than per-function.
Anyway, the patch is a win on microbenchmarks. 

There's a lot more we could do with function-local type inference.  We
could eliminate temp variables, and unnecessary stores to variables that
are never used again.  We could potentially track the types of what goes
into lists, and generate special-case code for numbers (using array), or
strings (using stringio or something).  And there's probably more than
I'm not thinking of right now.

What do you think?