[Python-Dev] AST-level type inference optimizations (original) (raw)
David Turner novalis at openplans.org
Wed Nov 5 20:48:19 CET 2008
- Previous message: [Python-Dev] Why don't range and xrange threat floats as floats?
- Next message: [Python-Dev] RELEASED Python 3.0rc2
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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?
- Previous message: [Python-Dev] Why don't range and xrange threat floats as floats?
- Next message: [Python-Dev] RELEASED Python 3.0rc2
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]